Hopfield網(wǎng)絡(luò)求解TSP兩種改進(jìn)算法的仿真研究

1 引言
??? 用Hopfield神經(jīng)網(wǎng)絡(luò)求解旅行商問(wèn)題(TSP)，給組合優(yōu)化完備性問(wèn)題的求解提供新的方法。但該算法會(huì)經(jīng)常生成無(wú)效解，因此需進(jìn)一步改進(jìn)。有學(xué)者通過(guò)TSP網(wǎng)絡(luò)的動(dòng)態(tài)分析修正TSP的能量函數(shù)，從而獲得有效解，但其能量函數(shù)的表達(dá)式過(guò)于復(fù)雜。有人簡(jiǎn)化該能量函數(shù)，進(jìn)一步提出改進(jìn)算法。這里擬對(duì)典型的兩種改進(jìn)算法進(jìn)行仿真分析。

2 HopfieId網(wǎng)絡(luò)的能量函數(shù)
??? 為將TSP問(wèn)題映射成神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)過(guò)程，Hopfield采取置換矩陣的表示方法，用N×N個(gè)神經(jīng)元組成Hopfield人工神經(jīng)網(wǎng)絡(luò)表示商人訪問(wèn)N個(gè)城市。
??? 網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)時(shí)各神經(jīng)元的狀態(tài)對(duì)應(yīng)置換矩陣各元素的值(“1”或“0”)。用uxi表示神經(jīng)元(x，i)的輸出，相應(yīng)的輸入用Vxi表示。
??? 若城市x在i位置上被訪問(wèn)，則Vxi=1，否則Vxi=0。Hop-field定義如下形式的能量函數(shù)：
???

???
式中，A、B、C、D是實(shí)系數(shù)。dxy為城市x與y之間的距離。
??? 式中前3項(xiàng)是問(wèn)題的約束項(xiàng)。最后1項(xiàng)是優(yōu)化目標(biāo)項(xiàng)。利用動(dòng)態(tài)方程：
???
式中，VT表示V的轉(zhuǎn)置。
??? 求得A、B、C、D和d描述的連接矩陣和及偏置，的表達(dá)式：

??? Hopfield把能量函數(shù)的概念引入神經(jīng)網(wǎng)絡(luò)，從而開(kāi)創(chuàng)求解優(yōu)化問(wèn)題的新方法。但該算法會(huì)以大百分比生成無(wú)效解，因此需進(jìn)一步改進(jìn)。

3 改進(jìn)算法與仿真
3．1 改進(jìn)算法1
??? Aiyer等人從理論上證明Hopfield網(wǎng)絡(luò)不能生成有效解的原因，并提出一個(gè)新的連接矩陣：

外部輸入
??? 可從理論上證明該算法的有效性，試驗(yàn)也驗(yàn)證它幾乎100％可獲得有效解。利用上述改進(jìn)算法對(duì)Hopfield的10城市問(wèn)題進(jìn)行模擬試驗(yàn)，已知其最短路徑為2．690 6。模擬試驗(yàn)采用兩種神經(jīng)元狀態(tài)更新函數(shù)，一種采用S型函數(shù)，即
???
??? 另一種采用如下定義的軟限幅函數(shù)：
???

??? 它是線(xiàn)性化近似的一種合理選擇。圖1給出軟限幅函數(shù)及雙曲正切函Uo取0．02時(shí)的曲線(xiàn)圖。對(duì)于每種情況，從起始條件出發(fā)模擬運(yùn)行200次，每次模擬在達(dá)到下列兩條件之一時(shí)終止運(yùn)行：(1)網(wǎng)絡(luò)中的每個(gè)神經(jīng)元均在[0．9，1]或[0，0．1]之間取值，分別對(duì)應(yīng)神經(jīng)元的“激活”(取值落在[0．9，1]中)或“抑制”狀態(tài)(取值落在[0，0．1]中)，并且矩陣的每行每列恰有一個(gè)非零元素；(2)運(yùn)行迭代次數(shù)大于10 000次。注意，沒(méi)有以dE／dt=0判別迭代結(jié)束。因?yàn)闈M(mǎn)足dE／dt=0的點(diǎn)不一定是E的極小點(diǎn)或最小點(diǎn)，也可能是拐點(diǎn)。其次，即使是E的極小點(diǎn)，繼續(xù)迭代有可能跳出這個(gè)極小點(diǎn)。取A=B=8，A1=7．75，D=2，步長(zhǎng)δt=0．02，測(cè)試結(jié)果如表1和圖1所示。由測(cè)試結(jié)果可知，軟限幅的效果明顯優(yōu)于硬限幅，因?yàn)檐浵薹c線(xiàn)性化近似極為相似，但所需的收斂次數(shù)較多。
??? 研究表明，在S型函數(shù)UO=2情況下，網(wǎng)絡(luò)給不出任何有效的解答。因?yàn)榫W(wǎng)絡(luò)中的神經(jīng)元無(wú)法收斂于其穩(wěn)態(tài)(“激活”或“抑制”)。

3．2 改進(jìn)算法2
??? Aiyer通過(guò)TSP網(wǎng)絡(luò)的動(dòng)態(tài)分析修正TSP的連接矩陣，從而獲得有效解，但其表達(dá)式過(guò)于復(fù)雜，影響優(yōu)化效果。簡(jiǎn)化該能量函數(shù)：

首先檢查式(1)的前3項(xiàng)，其中，第3項(xiàng)僅在網(wǎng)絡(luò)輸出全為0時(shí)起約束作用，否則前2項(xiàng)已保證第3項(xiàng)成立。對(duì)前2項(xiàng)作如下修改：
???
??? 則第3項(xiàng)完全可省去。將優(yōu)化目標(biāo)項(xiàng)寫(xiě)成：

?

??? 或
??? 也可滿(mǎn)足優(yōu)化要求。則TSP的能量函數(shù)簡(jiǎn)化為：
???
??? 下面以式(13)作為研究對(duì)象，其對(duì)應(yīng)的網(wǎng)絡(luò)連接矩陣和外部輸入分別是：
???
??? 該算法可從理論上證明其有效性，仿真研究如下：取A=B=3，D=1，步長(zhǎng)δt=0．05，對(duì)Uo=0．02和軟限幅兩種情況進(jìn)行仿真，仿真終止條件與改進(jìn)算法2相同。測(cè)試的統(tǒng)計(jì)結(jié)果如表2和圖2所示。

??? 從測(cè)試結(jié)果可以看出，該方法獲得的最優(yōu)解的個(gè)數(shù)明顯的多于改進(jìn)算法1。軟限幅的效果明顯優(yōu)于sigmold函數(shù)的效果。但所需的收斂次數(shù)較多。這一點(diǎn)與改進(jìn)算法1是一致的。在使用軟限幅時(shí)獲得最優(yōu)解的概率大于95％，只是所需迭代次數(shù)稍多。

4 結(jié)束語(yǔ)
??? 對(duì)兩種求解TSP的改進(jìn)算法進(jìn)行仿真研究，結(jié)果表明他們具有非常好的優(yōu)化效果，在10城市問(wèn)題上可近似100％的獲得最優(yōu)解。
??? 另外，該算法還具有對(duì)參數(shù)敏感度低的優(yōu)點(diǎn)。改進(jìn)算法的缺點(diǎn)是所需迭代次數(shù)較多。當(dāng)采用大步長(zhǎng)迭代時(shí)，可降低收斂所需的迭代次數(shù)，但會(huì)影響優(yōu)化效果。
??? 這種影響對(duì)Uo=0．02的情況不明顯，例如，在δt=0．5時(shí)，其優(yōu)化效果與δt=0．05時(shí)幾乎相同，所需迭代次數(shù)可降到450次左右。而對(duì)于軟限幅的情況，步長(zhǎng)的影響就明顯了，δt= 0．5時(shí)，優(yōu)化效果與圖中Uo=0．02的情況差不多。下一步的工作擬采用變步長(zhǎng)的方法，估計(jì)可大大降低所需的迭代次數(shù)。