- 智能優(yōu)化技術(shù):適應(yīng)度地形理論及組合優(yōu)化問(wèn)題的應(yīng)用
- 路輝 周容容 石津華 孫升杰編著
- 3819字
- 2021-08-24 11:50:30
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ò)記作NN1,NN2,NN3…NNn,這些局部最優(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)∈NNi,并且將概率P(h(s)∈NNi)記作pi(s),對(duì)于每個(gè)s∈S的解,滿足。
在非中性適應(yīng)度地形中,其中每個(gè)中性網(wǎng)絡(luò)的大小是1,對(duì)于每個(gè)解s,只有一個(gè)中性網(wǎng)絡(luò)(實(shí)際上是一個(gè)解)NNi,使得pi(s)=1使得pi(s)=1。
在這種情況下,局部最優(yōu)中性網(wǎng)絡(luò)i的吸引域是集合bi={s∈S|pi(s)>0},但是這個(gè)定義不能直接在中性適應(yīng)度地形中使用,需要按照以下方式擴(kuò)展該定義[8]。
5)吸引域:局部最優(yōu)中性網(wǎng)絡(luò)i的吸引域是集合bi={s∈S|pi(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è)解si∈bi且sj∈bj滿足si∈V(sj)時(shí),節(jié)點(diǎn)NNi和NNj之間就存在一條連接的邊。
7)邊的權(quán)重:對(duì)于非中性地形的每個(gè)解s和s′,將s′是s鄰居的概率記作p(s→s′)。那么,對(duì)于s∈S有一個(gè)鄰域解在吸引域bj中的概率就應(yīng)該為
從吸引域bi移動(dòng)到吸引域bj的總概率是所有s∈bi到s′∈bj的轉(zhuǎn)移概率的平均值。
#bi是吸引域bi的大小。
圖3-1給出了加權(quán)局部最優(yōu)網(wǎng)絡(luò)的示意圖。其中,圓形表示局部最優(yōu)盆地(直徑表示盆地大小),加權(quán)邊表示轉(zhuǎn)移的概率。
對(duì)于中性地形,定義解s屬于盆地i的概率pi(s)。因此,需要對(duì)下面兩個(gè)公式做一定的調(diào)整。
其中,#bi是吸引域bi的大小。
圖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(bi→bj)>0,那么這條邊eij∈E就加了權(quán)重wij=p(bi→bj)。這是一個(gè)有向圖,wij與wji是兩個(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)重wii和節(jié)點(diǎn)強(qiáng)度si(si=∑j∈V(i)\{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ì)。
圖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ù)。
式中,si=∑j≠iwij,如果wnm>0,那么anm=1,如果wnm=0,那么anm=0,并且ki=∑j≠kaij。
對(duì)于在頂點(diǎn)i附近形成的每個(gè)三元組,cw(i)計(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ā)生的可能性較小。
圖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)之間的距離定義為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ò)捕獲。
圖3-9 差異系數(shù)的示意圖
圖3-10 最短路徑的示意圖
- 深度探索:解碼DeepSeek及人工智能的未來(lái)
- 解構(gòu)ChatGPT
- 機(jī)器人制作從入門(mén)到精通(第3版)
- 2019年華北五省(市、自治區(qū))大學(xué)生機(jī)器人大賽:人工智能與機(jī)器人創(chuàng)意設(shè)計(jì)賽論文集
- 秒懂AI編程:零基礎(chǔ)搞定辦公自動(dòng)化
- 可解釋人工智能導(dǎo)論
- AI繁榮
- 人工智能算法
- Unity虛擬現(xiàn)實(shí)開(kāi)發(fā)實(shí)戰(zhàn)
- 自動(dòng)調(diào)節(jié)系統(tǒng)解析與PID整定
- 人工智能注意力機(jī)制:體系、模型與算法剖析
- VR簡(jiǎn)史:一本書(shū)讀懂虛擬現(xiàn)實(shí)
- AIGC提示詞美學(xué)定義
- 智能體設(shè)計(jì)指南:成為提示詞高手和AI Agent設(shè)計(jì)師
- 生成式人工智能