3.3 局部最優網絡

在搜索空間中，研究局部最優解的分布對于理解在不同地形中搜索的難度有很大幫助，也可以指導高效搜索算法。例如，在許多組合優化問題的適應度地形中，局部最優解并不是隨機分布的，相反，它們往往是集中在一個“中央地段”中（如果是最小化問題，則是大峽谷）。在許多組合優化的問題中，包括旅行商問題、流水車間調度，還有NK地形，都呈現出了全局凸的地形結構。

為了得到局部最優網絡，文獻[8]給出了相關的定義和算法。

1）中性鄰居：一個解s的中性鄰居指的是與之有相同的適應度值f（s）的鄰居x，即

由式（3-2）可以看出，一個解的中性程度就是它的中性鄰居的數量。如果有許多解的中性程度都很高，那么該適應度地形就是中性的。那么，該地形就可以被分解為擁有相同適應度值的幾個子結構。當然，也允許適應度值之間有一定的差值，這樣也認為是中性的。

2）中性網絡：一個頂點擁有相同適應度值的連通子圖，記作中性網絡（Neutral Net-work，NN）。

通過位翻轉變異算子，對于所有的解x和y，如果x∈V（y），那么y∈V（x）。在這種情況下，中性網絡就與R（x，y）（當且僅當x∈V（y）且f（x）=f（y））是等價關系。為了描述方便，將此中性網絡記作NN（s）。

3）局部最優解：一個局部最優解，是局部區域最大的解，即存在一個解s^?，滿足條件?s∈V（s），f（s）≤f（s^?）。

4）局部最優中性網絡：如果中性網絡的所有配置都是局部最優的，則該中性網絡就是局部最優的。

可以使用隨機爬山算法^[9]，提取局部最優中性網絡中的吸引域。在算法中，隨機選擇一個具有最大適應度值的鄰域解，接受適應度值相等或者更優的解。具體的步驟如下：算法3-2：隨機爬山

選擇一個初始解s∈S

repeat

1.從{Z∈V（s）f（Z）=max{f（x）x∈V（s）}}中隨機選擇一個解s′；

2.iff（s）≤f（s′）then

s←s′

end if

untils在一個局部最優中性網絡中

由于適應度地形的大小是有限的，可以將局部最優中性網絡記作NN₁，NN₂，NN₃…NN_n，這些局部最優中性網絡是局部最優網絡的端點。因此，在這樣的情況下，就形成了一個固有網絡，其節點本身就是網絡。對于每個解s，都有一個概率h（s）∈NN_i，并且將概率P（h（s）∈NN_i）記作p_i（s），對于每個s∈S的解，滿足。

在非中性適應度地形中，其中每個中性網絡的大小是1，對于每個解s，只有一個中性網絡（實際上是一個解）NN_i，使得p_i（s）=1使得p_i（s）=1。

在這種情況下，局部最優中性網絡i的吸引域是集合b_i={s∈S｜p_i（s）>0}，但是這個定義不能直接在中性適應度地形中使用，需要按照以下方式擴展該定義^[8]。

5）吸引域：局部最優中性網絡i的吸引域是集合b_i={s∈S｜p_i（s）>0}。吸引域的大小即為。

6）局部最優網絡：局部最優網絡G=（N，E）是一個圖，它的節點都是局部最優解NN，而且當兩個解s_i∈b_i且s_j∈b_j滿足s_i∈V（s_j）時，節點NN_i和NN_j之間就存在一條連接的邊。

7）邊的權重：對于非中性地形的每個解s和s′，將s′是s鄰居的概率記作p（s→s′）。那么，對于s∈S有一個鄰域解在吸引域b_j中的概率就應該為

從吸引域b_i移動到吸引域b_j的總概率是所有s∈b_i到s′∈b_j的轉移概率的平均值。

#b_i是吸引域b_i的大小。

圖3-1給出了加權局部最優網絡的示意圖。其中，圓形表示局部最優盆地（直徑表示盆地大小），加權邊表示轉移的概率。

對于中性地形，定義解s屬于盆地i的概率p_i（s）。因此，需要對下面兩個公式做一定的調整。

其中，#b_i是吸引域b_i的大小。

圖3-1加權局部最優網絡示意圖NK地形（N=6，K=2）

8）加權局部最優網絡：在一個局部最優中性網絡，如果兩個節點i和j之間的p（b_i→b_j）>0，那么這條邊e_ij∈E就加了權重w_ij=p（b_i→b_j）。這是一個有向圖，w_ij與w_ji是兩個不同的值。

通過隨機爬山算法獲得了局部最優中性網絡，需要對該網絡進行一定的評估，才能達到分析問題、指導算法的目的。以下評估方法從不同的角度對網絡特征進行了分析。

Verel等人^[8]利用NK地形開展分析工作，采用不同的參數組合進行相應的實驗，從而得出了一些非常有意義的結論。在他們的實驗中，將N設置為其最大的可能值。他們分別探討了標準的網絡特性、吸引域和高級網絡特性的三種情況。

1.標準的網絡特性

對于標準的網絡特性，主要探討節點、邊緣的數量以及邊緣的權重分布。標準網絡特性與相應地形的搜索難度有關，它們既反映了盆地的數量，又反映了探索地形的能力。

在不同的實驗條件下得到的數值不同，在圖3-2給出節點數量與K之間的示意圖，沒有具體數值意義，具體的曲線形狀和參數取值、地形類型有關。從節點數量來看，節點數量隨著參數K的增加而快速增加。對于給定的N和K，標準NK地形總是比相應的中性地形具有更多的節點。由于非中性地形中適應度地形改變的概率要比中性地形中的高，所以對于給定的K，節點的數量隨著中性的增加而減少。在其他條件相同的情況下，節點數量越多，搜索將越困難。一般情況下，隨著K的增加，搜索更加困難，并且對于給定的K，在中性低的情況下，搜索將更加困難。也就是說，對于較低的K值和高中性，搜索可能會更加容易。

從邊的數量來看，邊的數量隨著K的增加而增長。一般情況下，對于NK地形邊數隨著所有K的中性增加而減小，當然也存在邊數隨著中性增加而增加的情況。需要說明的是，具體的曲線形狀和參數取值、地形類型有關。圖3-3僅為示意圖，不代表具體某一參數下的實驗結果。

圖3-2 節點數示意圖

圖3-3 邊的數量示意圖

從權重分布來看，加權網絡的權重特征包括每條邊的權重w以及權重分布的平均值。對于任意一個節點i，來自i的權重和為1。Verel等人重點關注了自連邊的權重w_ii和節點強度s_i（s_i=∑_j∈_V（i）\{i}w_ij），并且w_ii+s_i=1。節點強度代表了節點的連通性。圖3-4給出了權重的示意圖。網絡中所有節點上的權重w_ii的平均值（可以認為是從盆地中一種結構的突變進行爬山算法之后保持在同一盆地中的概率）。可以看出，跳入另一個盆地的可能性遠小于在同一盆地中走動的概率。權重w_ii隨著K的增加而減小，這也是標準NK地形所遵循的趨勢。

圖3-4 權重的示意圖

關于中性的趨勢更加復雜，一般情況下，對于固定的K，保持在同一盆地的平均權重隨著中性的增加而降低。相反，也存在保持在同一盆地的平均權重隨著中性而增加的情況。中性增加了給定結構逃離其盆地并到達另一個盆地的可能性，但中性也增加了當前結構所連接盆地的數量。

2.吸引域

對于啟發式搜索算法來說，吸引域和局部最優網絡同樣重要。同時，吸引域的某些特征可能和局部最優網絡特征有關。對于吸引域，Verel等人分別分析了給定大小的吸引域數量、局部最優解的適應度值和全局最優的吸引域大小。

對于給定大小的吸引域數量來說，主要觀測所研究地形中吸引域尺寸的平均值和方差。圖3-5給出均值和方差變化曲線的示意圖。吸引域的大小隨著K的增加而呈指數下降。當地形的中性特征減少時，吸引域的大小也會減少。方差同樣隨著K的增加而呈指數下降，并且在中性下降時也會下降。

圖3-5 吸引域大小的平均值和方差示意圖

Verel等人還通過將吸引域的尺寸的某些分布利用對數正態分布進行擬合。對數正態分布意味著大多數盆地的大小接近平均值，并且幾乎沒有大于平均尺寸的盆地，這可能與潛在地形的搜索難度有關。

對于局部最優解的適應度值來說，一般用吸引域大小與其適應度值之間的相關性進行刻畫。正值較大的相關系數意味著較大的吸引域具有較高的適應值，所以一般會更關注較大尺寸的吸引域。因為吸引域尺寸之間的大小差異隨著基因關聯的增加而減少，所以隨著崎嶇度的增加，找到具有更高適應性的盆地的難度也增加。就中性而言，全局最大盆地的規模隨著中性的增加而增大。圖3-6給出相關性的示意圖。

對于全局最優的吸引域大小來說，其關注的是具有全局最優值的吸引域的平均大小。隨著K的減小，全局最優的吸引域尺寸也減少。就中性而言，全局最大吸引域的規模隨著中性的增加而增大。圖3-7給出全局最優值的吸引域尺寸平均值的示意圖。

圖3-6 相關性示意圖

圖3-7 全局最優值的吸引域尺寸平均值的示意圖

3.高級網絡特性

高級網絡特性主要包括加權聚類系數、節點之間的平均路徑長度以及差異系數三個方面。

對于加權聚類系數，Verel等人考慮到標準的聚類系數沒有考慮加權的邊值，結合拓撲信息和網絡權值分布的加權聚類系數。

式中，s_i=∑_j≠iw_ij，如果w_nm>0，那么a_nm=1，如果w_nm=0，那么a_nm=0，并且k_i=∑_j≠ka_ij。

對于在頂點i附近形成的每個三元組，c^w（i）計算頂點i的兩個參與邊緣的權重。c^w被定義為網絡所有頂點上平均的加權聚類系數。

圖3-8給出加權聚類系數平均值的示意圖。對于NK地形，加權聚類系數隨著基因關聯程度而降低，并隨著中性程度而增加。隨著基因關聯的增加，聚類系數的降低與標準NK地形的結果一致。對于高度基因關聯和低中性的情況，相鄰吸引與之間的過渡較少，或者過渡發生的可能性較小。

圖3-8 加權聚類系數平均值的示意圖

對于差異系數來說，其主要衡量節點i對于總權重貢獻的差異值，具體定義如下：

圖3-9給出差異系數的示意圖，對于低K值，高度中性增加了平均差異。當基因關聯高且無論中性程度如何，盆地更均勻地連通，因此我們可以將局部最優網絡描繪為更“隨機”，即更均勻，這對于地形的搜索難度有潛在的影響。

對于最短路徑來說，兩個節點之間的距離定義為d_ij=1/w_ij，那么兩個節點之間路徑的長度就表示為連接各自吸引域邊的距離之和。整個網絡的平均路徑長度是所有可能的最短路徑的平均值。

圖3-10給出最短路徑的示意圖，一般情況下，無論地形家族和中立水平如何，基因關聯對結果具有相同的影響。即使中性很高，吸引域也會更遠，地形的一些結構差異可以由局部最優網絡捕獲。

圖3-9 差異系數的示意圖

圖3-10 最短路徑的示意圖