2.5 信息熵分析

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

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

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

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

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

如果ε=0，函数将会对适应度值之间的差异特别敏感，S（ε）也会越精确。这个信息串S（ε）包含了适应度地形的结构信息，函数将集合中的元素连接成了路径中的边，每条路径由S（ε）的子串s_is_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₁s₂s₃…s_n的坡度为

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

3.信息稳定性

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

表2-1 地形路径的信息特征