购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.5 信息熵分析

为了进一步研究适应度地形的结构特征,Vesselin等人 [11] 提出了基于信息熵的方法去探究适应度地形的平坦性、崎岖性和中性等多个特征。其基本思想就是将适应度地形看作是对象的集合,每个对象由其和最近的邻居之间的结构构成。如图2-2示例,表示了如何将随机游走得到的路径表示为对象的集合。为了研究崎岖性、平坦性与地形中性的相关性,将初始对象集合分为两个子集合,对于每个子集合,当地形的中性程度增加时,信息函数可以衡量每个子集合熵的变化情况,如图2-3的示意图。

图2-2 适应度值序列示意图

图2-3 适应度地形元素集合示意图

Vesselin等人指出,通过随机游走得到由适应度值组成的一个时间序列,记为 ,该时间序列包含了适应度地形的结构信息,通过将时间序列构成对象集合就是为了提取这个信息。这个集合可以定义为一个信息串 S ε )= s 1 s 2 s 3 s n ,其中 ,它们可以通过如下的方式获得:

式中, ε 为一个实数参数,决定了计算 S ε )的正确性。

如果 ε =0,函数 将会对适应度值之间的差异特别敏感, S ε )也会越精确。这个信息串 S ε )包含了适应度地形的结构信息,函数 将集合 中的元素连接成了路径中的边,每条路径由 S ε )的子串 s i s i +1 构成。 S ε )可以看作是适应度地形关联矩阵的采样结果。

1.信息内容

对于 S ε )长度为 w 的子块集合,Vesselin等人给出了两个基于熵测量的方法,分别是:

H ε )和 h ε )分别记作第一熵测度(the First Entropic Measures,FEM)和第二熵测度(the Second Entropic Measures,SEM)。其中,第一熵测度评估的是地形中相对于中性的崎岖性,而第二熵测度衡量的是中性和平坦性之间的相互作用。概率 P [ pq ] 是可能的组合 pq 出现的频率,定义为

式中, n [ pq ] 是在信息串 S ε )中子串 pq 出现的次数。

由于从 中可能出现的长度为2的子串一共有9种情形,其中 p q 的情形一共有6种, p = q 的情形有3种,因此,式(2-9)和式(2-10)中对数函数的底分别是6和3。

首先,通过进化操作算子对适应度地形进行随机游走,记录下每一步的适应度值,经过多步随机游走就可以得到一个时间序列,这样信息函数 H ε )和 h ε )的值就可以计算。其次,为了量化适应度地形的熵测度,可以采用多种信息分析方法。例如,自相关函数揭示了整个地形的相关性,相关性越低,地形越崎岖。可以采用不一样的信息分析方法,同时分析崎岖性、中性和平坦性之间的关系。

2.部分信息内容

Vesselin等人在文献[4]中指出适应度地形路径 崎岖性的一个重要的特征是路径的模态,可以通过测量由一个字符串 S ε )表示的信息量来评估。由于 H ε )是用来评估与地形最优解相关对象的多样性,因此路径的模态不能通过 H ε )来衡量。为了探究在地形上随机游走的路径形态,假设路径形态仅与路径上最优解数量相关的特征。因此,无论它们可能是孤立的最优解、高原等,这些对象都作为最优解。

S ε )为基础按照以下的方式构造一个新的信息串 S′ ε ):如果 S ε )是0串,那么 S′ ε )就为空;否则, ,其中 j >1。这样通过忽略了 S ε )中不重要的部分,得到了长度为 μ 的信息串 S′ ε ),并且 μ 值反映了路径模态。因此, S′ ε )的形式为“ ”,这表示相应地形路径斜率的最短字符串。如果地形路径是最大的多模态, S ε )就不能改变,它的长度也会保持不变。 S′ ε )的长度在整数区间[0,1]之间,称为部分信息内容,具体定义如下:

式中, n S ε )的长度。

定义函数 Φ S i j k )计算信息串 S ε )= s 1 s 2 s 3 s n 的坡度为

这样, μ 的计算可以写成 Φ S (1,0,0)。如果地形路径是平坦的,即没有坡度,那么部分信息内容 M ε )的值为0。当地形路径是最大的多模态, M ε )的值为1。对于给定的 M ε ),对应地形路径上最优解的数目为

3.信息稳定性

Vesselin等人指出,信息内容和部分信息内容衡量时间序列 存在精度问题,它们主要依赖于参数 ε 。因此,可以将参数 ε 视为放大镜,通过该放大镜可以实现观测适应度地形。如果参数 ε 的值非常小,那么函数 将会对适应度值的差异非常敏感,也就意味着这个放大镜使适应度地形的每个元素都可见。如果 ε 的值等于0,那么 H ε )和 M ε )的准确性就会很高。使适应度地形变得平坦的最小 ε ,记为 ε * ,就被定义为信息稳定性, ε * 对应的 S ε * )是一个只有0的信息串。地形路径的信息特征见表2-1。

表2-1 地形路径的信息特征 +Dmp0Mfeqbx6WHy19KmkN3aHMhsNR7/d7edtGwKDuKaVkpWxL0CTJKKksG0MB+xe

点击中间区域
呼出菜单
上一章
目录
下一章
×