官术网_书友最值得收藏!

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)度值fs)的鄰居x,即

978-7-111-65846-7-Chapter03-4.jpg

由式(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ì)于所有的解xy,如果xVy),那么yVx)。在這種情況下,中性網(wǎng)絡(luò)就與Rxy)(當(dāng)且僅當(dāng)xVy)且fx)=fy))是等價(jià)關(guān)系。為了描述方便,將此中性網(wǎng)絡(luò)記作NNs)。

3)局部最優(yōu)解:一個(gè)局部最優(yōu)解,是局部區(qū)域最大的解,即存在一個(gè)解s?,滿足條件?sVs),fs)≤fs?)。

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è)初始解sS

repeat

1.從{ZVsfZ)=max{fxxVs)}}中隨機(jī)選擇一個(gè)解s′

2.iffs)≤fs′then

ss′

end if

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

由于適應(yīng)度地形的大小是有限的,可以將局部最優(yōu)中性網(wǎng)絡(luò)記作NN1NN2NN3NNn,這些局部最優(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è)概率hs)∈NNi,并且將概率Phs)∈NNi)記作pis),對(duì)于每個(gè)sS的解,滿足978-7-111-65846-7-Chapter03-5.jpg

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

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

5)吸引域:局部最優(yōu)中性網(wǎng)絡(luò)i的吸引域是集合bi={sSpis)>0}。吸引域的大小即為978-7-111-65846-7-Chapter03-6.jpg

6)局部最優(yōu)網(wǎng)絡(luò):局部最優(yōu)網(wǎng)絡(luò)G=(NE)是一個(gè)圖,它的節(jié)點(diǎn)都是局部最優(yōu)解NN,而且當(dāng)兩個(gè)解sibisjbj滿足siVsj)時(shí),節(jié)點(diǎn)NNiNNj之間就存在一條連接的邊。

7)邊的權(quán)重:對(duì)于非中性地形的每個(gè)解ss′,將s′s鄰居的概率記作pss′)。那么,對(duì)于sS有一個(gè)鄰域解在吸引域bj中的概率就應(yīng)該為

978-7-111-65846-7-Chapter03-7.jpg

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

978-7-111-65846-7-Chapter03-8.jpg

#bi是吸引域bi的大小。

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

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

978-7-111-65846-7-Chapter03-9.jpg

其中,#bi是吸引域bi的大小。

978-7-111-65846-7-Chapter03-10.jpg

圖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)ij之間的pbibj)>0,那么這條邊eijE就加了權(quán)重wij=pbibj)。這是一個(gè)有向圖,wijwji是兩個(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ì)于給定的NK,標(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é)果。

978-7-111-65846-7-Chapter03-11.jpg

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

978-7-111-65846-7-Chapter03-12.jpg

圖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)重wii和節(jié)點(diǎn)強(qiáng)度sisi=jVi)\{i}wij),并且wii+si=1。節(jié)點(diǎn)強(qiáng)度代表了節(jié)點(diǎn)的連通性。圖3-4給出了權(quán)重的示意圖。網(wǎng)絡(luò)中所有節(jié)點(diǎn)上的權(quán)重wii的平均值(可以認(rèn)為是從盆地中一種結(jié)構(gòu)的突變進(jìn)行爬山算法之后保持在同一盆地中的概率)。可以看出,跳入另一個(gè)盆地的可能性遠(yuǎn)小于在同一盆地中走動(dòng)的概率。權(quán)重wii隨著K的增加而減小,這也是標(biāo)準(zhǔn)NK地形所遵循的趨勢(shì)。

978-7-111-65846-7-Chapter03-13.jpg

圖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ì)下降。

978-7-111-65846-7-Chapter03-14.jpg

圖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)值的吸引域尺寸平均值的示意圖。

978-7-111-65846-7-Chapter03-15.jpg

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

978-7-111-65846-7-Chapter03-16.jpg

圖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ù)。

978-7-111-65846-7-Chapter03-17.jpg

式中,si=jiwij,如果wnm>0,那么anm=1,如果wnm=0,那么anm=0,并且ki=jkaij

對(duì)于在頂點(diǎn)i附近形成的每個(gè)三元組,cwi)計(jì)算頂點(diǎn)i的兩個(gè)參與邊緣的權(quán)重。cw被定義為網(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ā)生的可能性較小。

978-7-111-65846-7-Chapter03-18.jpg

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

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

978-7-111-65846-7-Chapter03-19.jpg

圖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)之間的距離定義為dij=1/wij,那么兩個(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ò)捕獲。

978-7-111-65846-7-Chapter03-20.jpg

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

978-7-111-65846-7-Chapter03-21.jpg

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

主站蜘蛛池模板: 灵宝市| 忻城县| 台前县| 汕头市| 鹿邑县| 怀远县| 翁牛特旗| 兴仁县| 岗巴县| 方正县| 田阳县| 新竹县| 文水县| 宁都县| 杭锦旗| 潼南县| 沛县| 收藏| 荣成市| 临高县| 平果县| 舟山市| 缙云县| 宁晋县| 苏尼特右旗| 彭山县| 米林县| 红原县| 洪泽县| 南丹县| 扬中市| 大埔县| 抚远县| 贡嘎县| 栾城县| 广饶县| 桂林市| 布尔津县| 滨州市| 平顺县| 罗田县|