3.3 局部最優(yōu)網(wǎng)絡(luò)

在搜索空間中，研究局部最優(yōu)解的分布對(duì)于理解在不同地形中搜索的難度有很大幫助，也可以指導(dǎo)高效搜索算法。例如，在許多組合優(yōu)化問(wèn)題的適應(yīng)度地形中，局部最優(yōu)解并不是隨機(jī)分布的，相反，它們往往是集中在一個(gè)“中央地段”中（如果是最小化問(wèn)題，則是大峽谷）。在許多組合優(yōu)化的問(wèn)題中，包括旅行商問(wèn)題、流水車(chē)間調(diào)度，還有NK地形，都呈現(xiàn)出了全局凸的地形結(jié)構(gòu)。

為了得到局部最優(yōu)網(wǎng)絡(luò)，文獻(xiàn)[8]給出了相關(guān)的定義和算法。

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

由式（3-2）可以看出，一個(gè)解的中性程度就是它的中性鄰居的數(shù)量。如果有許多解的中性程度都很高，那么該適應(yīng)度地形就是中性的。那么，該地形就可以被分解為擁有相同適應(yīng)度值的幾個(gè)子結(jié)構(gòu)。當(dāng)然，也允許適應(yīng)度值之間有一定的差值，這樣也認(rèn)為是中性的。

2）中性網(wǎng)絡(luò)：一個(gè)頂點(diǎn)擁有相同適應(yīng)度值的連通子圖，記作中性網(wǎng)絡(luò)（Neutral Net-work，NN）。

通過(guò)位翻轉(zhuǎn)變異算子，對(duì)于所有的解x和y，如果x∈V（y），那么y∈V（x）。在這種情況下，中性網(wǎng)絡(luò)就與R（x，y）（當(dāng)且僅當(dāng)x∈V（y）且f（x）=f（y））是等價(jià)關(guān)系。為了描述方便，將此中性網(wǎng)絡(luò)記作NN（s）。

3）局部最優(yōu)解：一個(gè)局部最優(yōu)解，是局部區(qū)域最大的解，即存在一個(gè)解s^?，滿足條件?s∈V（s），f（s）≤f（s^?）。

4）局部最優(yōu)中性網(wǎng)絡(luò)：如果中性網(wǎng)絡(luò)的所有配置都是局部最優(yōu)的，則該中性網(wǎng)絡(luò)就是局部最優(yōu)的。

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

選擇一個(gè)初始解s∈S

repeat

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

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

s←s′

end if

untils在一個(gè)局部最優(yōu)中性網(wǎng)絡(luò)中

由于適應(yīng)度地形的大小是有限的，可以將局部最優(yōu)中性網(wǎng)絡(luò)記作NN₁，NN₂，NN₃…NN_n，這些局部最優(yōu)中性網(wǎng)絡(luò)是局部最優(yōu)網(wǎng)絡(luò)的端點(diǎn)。因此，在這樣的情況下，就形成了一個(gè)固有網(wǎng)絡(luò)，其節(jié)點(diǎn)本身就是網(wǎng)絡(luò)。對(duì)于每個(gè)解s，都有一個(gè)概率h（s）∈NN_i，并且將概率P（h（s）∈NN_i）記作p_i（s），對(duì)于每個(gè)s∈S的解，滿足。

在非中性適應(yīng)度地形中，其中每個(gè)中性網(wǎng)絡(luò)的大小是1，對(duì)于每個(gè)解s，只有一個(gè)中性網(wǎng)絡(luò)（實(shí)際上是一個(gè)解）NN_i，使得p_i（s）=1使得p_i（s）=1。

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

5）吸引域：局部最優(yōu)中性網(wǎng)絡(luò)i的吸引域是集合b_i={s∈S｜p_i（s）>0}。吸引域的大小即為。

6）局部最優(yōu)網(wǎng)絡(luò)：局部最優(yōu)網(wǎng)絡(luò)G=（N，E）是一個(gè)圖，它的節(jié)點(diǎn)都是局部最優(yōu)解NN，而且當(dāng)兩個(gè)解s_i∈b_i且s_j∈b_j滿足s_i∈V（s_j）時(shí)，節(jié)點(diǎn)NN_i和NN_j之間就存在一條連接的邊。

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

從吸引域b_i移動(dòng)到吸引域b_j的總概率是所有s∈b_i到s′∈b_j的轉(zhuǎn)移概率的平均值。

#b_i是吸引域b_i的大小。

圖3-1給出了加權(quán)局部最優(yōu)網(wǎng)絡(luò)的示意圖。其中，圓形表示局部最優(yōu)盆地（直徑表示盆地大小），加權(quán)邊表示轉(zhuǎn)移的概率。

對(duì)于中性地形，定義解s屬于盆地i的概率p_i（s）。因此，需要對(duì)下面兩個(gè)公式做一定的調(diào)整。

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

圖3-1加權(quán)局部最優(yōu)網(wǎng)絡(luò)示意圖NK地形（N=6，K=2）

8）加權(quán)局部最優(yōu)網(wǎng)絡(luò)：在一個(gè)局部最優(yōu)中性網(wǎng)絡(luò)，如果兩個(gè)節(jié)點(diǎn)i和j之間的p（b_i→b_j）>0，那么這條邊e_ij∈E就加了權(quán)重w_ij=p（b_i→b_j）。這是一個(gè)有向圖，w_ij與w_ji是兩個(gè)不同的值。

通過(guò)隨機(jī)爬山算法獲得了局部最優(yōu)中性網(wǎng)絡(luò)，需要對(duì)該網(wǎng)絡(luò)進(jìn)行一定的評(píng)估，才能達(dá)到分析問(wèn)題、指導(dǎo)算法的目的。以下評(píng)估方法從不同的角度對(duì)網(wǎng)絡(luò)特征進(jìn)行了分析。

Verel等人^[8]利用NK地形開(kāi)展分析工作，采用不同的參數(shù)組合進(jìn)行相應(yīng)的實(shí)驗(yàn)，從而得出了一些非常有意義的結(jié)論。在他們的實(shí)驗(yàn)中，將N設(shè)置為其最大的可能值。他們分別探討了標(biāo)準(zhǔn)的網(wǎng)絡(luò)特性、吸引域和高級(jí)網(wǎng)絡(luò)特性的三種情況。

1.標(biāo)準(zhǔn)的網(wǎng)絡(luò)特性

對(duì)于標(biāo)準(zhǔn)的網(wǎng)絡(luò)特性，主要探討節(jié)點(diǎn)、邊緣的數(shù)量以及邊緣的權(quán)重分布。標(biāo)準(zhǔn)網(wǎng)絡(luò)特性與相應(yīng)地形的搜索難度有關(guān)，它們既反映了盆地的數(shù)量，又反映了探索地形的能力。

在不同的實(shí)驗(yàn)條件下得到的數(shù)值不同，在圖3-2給出節(jié)點(diǎn)數(shù)量與K之間的示意圖，沒(méi)有具體數(shù)值意義，具體的曲線形狀和參數(shù)取值、地形類(lèi)型有關(guān)。從節(jié)點(diǎn)數(shù)量來(lái)看，節(jié)點(diǎn)數(shù)量隨著參數(shù)K的增加而快速增加。對(duì)于給定的N和K，標(biāo)準(zhǔn)NK地形總是比相應(yīng)的中性地形具有更多的節(jié)點(diǎn)。由于非中性地形中適應(yīng)度地形改變的概率要比中性地形中的高，所以對(duì)于給定的K，節(jié)點(diǎn)的數(shù)量隨著中性的增加而減少。在其他條件相同的情況下，節(jié)點(diǎn)數(shù)量越多，搜索將越困難。一般情況下，隨著K的增加，搜索更加困難，并且對(duì)于給定的K，在中性低的情況下，搜索將更加困難。也就是說(shuō)，對(duì)于較低的K值和高中性，搜索可能會(huì)更加容易。

從邊的數(shù)量來(lái)看，邊的數(shù)量隨著K的增加而增長(zhǎng)。一般情況下，對(duì)于NK地形邊數(shù)隨著所有K的中性增加而減小，當(dāng)然也存在邊數(shù)隨著中性增加而增加的情況。需要說(shuō)明的是，具體的曲線形狀和參數(shù)取值、地形類(lèi)型有關(guān)。圖3-3僅為示意圖，不代表具體某一參數(shù)下的實(shí)驗(yàn)結(jié)果。

圖3-2 節(jié)點(diǎn)數(shù)示意圖

圖3-3 邊的數(shù)量示意圖

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

圖3-4 權(quán)重的示意圖

關(guān)于中性的趨勢(shì)更加復(fù)雜，一般情況下，對(duì)于固定的K，保持在同一盆地的平均權(quán)重隨著中性的增加而降低。相反，也存在保持在同一盆地的平均權(quán)重隨著中性而增加的情況。中性增加了給定結(jié)構(gòu)逃離其盆地并到達(dá)另一個(gè)盆地的可能性，但中性也增加了當(dāng)前結(jié)構(gòu)所連接盆地的數(shù)量。

2.吸引域

對(duì)于啟發(fā)式搜索算法來(lái)說(shuō)，吸引域和局部最優(yōu)網(wǎng)絡(luò)同樣重要。同時(shí)，吸引域的某些特征可能和局部最優(yōu)網(wǎng)絡(luò)特征有關(guān)。對(duì)于吸引域，Verel等人分別分析了給定大小的吸引域數(shù)量、局部最優(yōu)解的適應(yīng)度值和全局最優(yōu)的吸引域大小。

對(duì)于給定大小的吸引域數(shù)量來(lái)說(shuō)，主要觀測(cè)所研究地形中吸引域尺寸的平均值和方差。圖3-5給出均值和方差變化曲線的示意圖。吸引域的大小隨著K的增加而呈指數(shù)下降。當(dāng)?shù)匦蔚闹行蕴卣鳒p少時(shí)，吸引域的大小也會(huì)減少。方差同樣隨著K的增加而呈指數(shù)下降，并且在中性下降時(shí)也會(huì)下降。

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

Verel等人還通過(guò)將吸引域的尺寸的某些分布利用對(duì)數(shù)正態(tài)分布進(jìn)行擬合。對(duì)數(shù)正態(tài)分布意味著大多數(shù)盆地的大小接近平均值，并且?guī)缀鯖](méi)有大于平均尺寸的盆地，這可能與潛在地形的搜索難度有關(guān)。

對(duì)于局部最優(yōu)解的適應(yīng)度值來(lái)說(shuō)，一般用吸引域大小與其適應(yīng)度值之間的相關(guān)性進(jìn)行刻畫(huà)。正值較大的相關(guān)系數(shù)意味著較大的吸引域具有較高的適應(yīng)值，所以一般會(huì)更關(guān)注較大尺寸的吸引域。因?yàn)槲虺叽缰g的大小差異隨著基因關(guān)聯(lián)的增加而減少，所以隨著崎嶇度的增加，找到具有更高適應(yīng)性的盆地的難度也增加。就中性而言，全局最大盆地的規(guī)模隨著中性的增加而增大。圖3-6給出相關(guān)性的示意圖。

對(duì)于全局最優(yōu)的吸引域大小來(lái)說(shuō)，其關(guān)注的是具有全局最優(yōu)值的吸引域的平均大小。隨著K的減小，全局最優(yōu)的吸引域尺寸也減少。就中性而言，全局最大吸引域的規(guī)模隨著中性的增加而增大。圖3-7給出全局最優(yōu)值的吸引域尺寸平均值的示意圖。

圖3-6 相關(guān)性示意圖

圖3-7 全局最優(yōu)值的吸引域尺寸平均值的示意圖

3.高級(jí)網(wǎng)絡(luò)特性

高級(jí)網(wǎng)絡(luò)特性主要包括加權(quán)聚類(lèi)系數(shù)、節(jié)點(diǎn)之間的平均路徑長(zhǎng)度以及差異系數(shù)三個(gè)方面。

對(duì)于加權(quán)聚類(lèi)系數(shù)，Verel等人考慮到標(biāo)準(zhǔn)的聚類(lèi)系數(shù)沒(méi)有考慮加權(quán)的邊值，結(jié)合拓?fù)湫畔⒑途W(wǎng)絡(luò)權(quán)值分布的加權(quán)聚類(lèi)系數(shù)。

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

對(duì)于在頂點(diǎn)i附近形成的每個(gè)三元組，c^w（i）計(jì)算頂點(diǎn)i的兩個(gè)參與邊緣的權(quán)重。c^w被定義為網(wǎng)絡(luò)所有頂點(diǎn)上平均的加權(quán)聚類(lèi)系數(shù)。

圖3-8給出加權(quán)聚類(lèi)系數(shù)平均值的示意圖。對(duì)于NK地形，加權(quán)聚類(lèi)系數(shù)隨著基因關(guān)聯(lián)程度而降低，并隨著中性程度而增加。隨著基因關(guān)聯(lián)的增加，聚類(lèi)系數(shù)的降低與標(biāo)準(zhǔn)NK地形的結(jié)果一致。對(duì)于高度基因關(guān)聯(lián)和低中性的情況，相鄰吸引與之間的過(guò)渡較少，或者過(guò)渡發(fā)生的可能性較小。

圖3-8 加權(quán)聚類(lèi)系數(shù)平均值的示意圖

對(duì)于差異系數(shù)來(lái)說(shuō)，其主要衡量節(jié)點(diǎn)i對(duì)于總權(quán)重貢獻(xiàn)的差異值，具體定義如下：

圖3-9給出差異系數(shù)的示意圖，對(duì)于低K值，高度中性增加了平均差異。當(dāng)基因關(guān)聯(lián)高且無(wú)論中性程度如何，盆地更均勻地連通，因此我們可以將局部最優(yōu)網(wǎng)絡(luò)描繪為更“隨機(jī)”，即更均勻，這對(duì)于地形的搜索難度有潛在的影響。

對(duì)于最短路徑來(lái)說(shuō)，兩個(gè)節(jié)點(diǎn)之間的距離定義為d_ij=1/w_ij，那么兩個(gè)節(jié)點(diǎn)之間路徑的長(zhǎng)度就表示為連接各自吸引域邊的距離之和。整個(gè)網(wǎng)絡(luò)的平均路徑長(zhǎng)度是所有可能的最短路徑的平均值。

圖3-10給出最短路徑的示意圖，一般情況下，無(wú)論地形家族和中立水平如何，基因關(guān)聯(lián)對(duì)結(jié)果具有相同的影響。即使中性很高，吸引域也會(huì)更遠(yuǎn)，地形的一些結(jié)構(gòu)差異可以由局部最優(yōu)網(wǎng)絡(luò)捕獲。

圖3-9 差異系數(shù)的示意圖

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