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 地形路徑的信息特征