Hopfield網絡求解TSP兩種改進算法的仿真研究

1 引言
??? 用Hopfield神經網絡求解旅行商問題(TSP)，給組合優化完備性問題的求解提供新的方法。但該算法會經常生成無效解，因此需進一步改進。有學者通過TSP網絡的動態分析修正TSP的能量函數，從而獲得有效解，但其能量函數的表達式過于復雜。有人簡化該能量函數，進一步提出改進算法。這里擬對典型的兩種改進算法進行仿真分析。

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

???
式中，A、B、C、D是實系數。dxy為城市x與y之間的距離。
??? 式中前3項是問題的約束項。最后1項是優化目標項。利用動態方程：
???
式中，VT表示V的轉置。
??? 求得A、B、C、D和d描述的連接矩陣和及偏置，的表達式：

??? Hopfield把能量函數的概念引入神經網絡，從而開創求解優化問題的新方法。但該算法會以大百分比生成無效解，因此需進一步改進。

3 改進算法與仿真
3．1 改進算法1
??? Aiyer等人從理論上證明Hopfield網絡不能生成有效解的原因，并提出一個新的連接矩陣：

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

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

3．2 改進算法2
??? Aiyer通過TSP網絡的動態分析修正TSP的連接矩陣，從而獲得有效解，但其表達式過于復雜，影響優化效果。簡化該能量函數：

首先檢查式(1)的前3項，其中，第3項僅在網絡輸出全為0時起約束作用，否則前2項已保證第3項成立。對前2項作如下修改：
???
??? 則第3項完全可省去。將優化目標項寫成：

?

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

??? 從測試結果可以看出，該方法獲得的最優解的個數明顯的多于改進算法1。軟限幅的效果明顯優于sigmold函數的效果。但所需的收斂次數較多。這一點與改進算法1是一致的。在使用軟限幅時獲得最優解的概率大于95％，只是所需迭代次數稍多。

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