Hopfield網(wǎng)絡(luò)求解TSP兩種改進(jìn)算法的仿真研究
加入技術(shù)交流群
用Hopfield神經(jīng)網(wǎng)絡(luò)求解旅行商問題(TSP)，給組合優(yōu)化完備性問題的求解提供新的方法。但該算法會(huì)經(jīng)常生成無效解，因此需進(jìn)一步改進(jìn)。有學(xué)者通過TSP網(wǎng)絡(luò)的動(dòng)態(tài)分析修正TSP的能量函數(shù)，從而獲得有效解，但其能量函數(shù)的表達(dá)式過于復(fù)雜。有人簡(jiǎn)化該能量函數(shù)，進(jìn)一步提出改進(jìn)算法。這里擬對(duì)典型的兩種改進(jìn)算法進(jìn)行仿真分析。
2 HopfieId網(wǎng)絡(luò)的能量函數(shù)
為將TSP問題映射成神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)過程，Hopfield采取置換矩陣的表示方法，用N×N個(gè)神經(jīng)元組成Hopfield人工神經(jīng)網(wǎng)絡(luò)表示商人訪問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位置上被訪問，則Vxi=1，否則Vxi=0。Hop-field定義如下形式的能量函數(shù)：
式中，A、B、C、D是實(shí)系數(shù)。dxy為城市x與y之間的距離。
式中前3項(xiàng)是問題的約束項(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ò)，從而開創(chuàng)求解優(yōu)化問題的新方法。但該算法會(huì)以大百分比生成無效解，因此需進(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城市問題進(jìn)行模擬試驗(yàn)，已知其最短路徑為2．690 6。模擬試驗(yàn)采用兩種神經(jīng)元狀態(tài)更新函數(shù)，一種采用S型函數(shù)，即
另一種采用如下定義的軟限幅函數(shù)：
評(píng)論