王 穎

（哈爾濱遠東理工學院，黑龍江 哈爾濱 150025）

組合優化問題中的一個典型就是旅行商問題（TSP），其可能的城市數目N和路徑數目呈指數型增長，由于計算量太大，常規方法無法求解出最優解，所以針對旅行商問題（TSP）尋找有效的近似求解算法具有非常重要的理論意義.另外，現今可以將很多實際應用問題進行簡化處理，處理后的結果均可用旅行商問題（TSP）進行表示，因而對旅行商問題（TSP）求解方法的研究具有重要的應用價值.

1 求解TSP問題的Hop field網絡設計

TSP問題是在一個城市集合｛Ac，Bc，Cc，……｝中找出一個最短路徑，該路徑必須經過并只經過每個城市一次，最終回到起點的路徑的方法.Hopfield采取了換位矩陣的表示方法，從而將TSP問題映射為一個神經網絡的動態過程，用N×N矩陣表示旅行商訪問N個城市.[1]例如，有四個城市｛Ac，Bc，Cc，Dc｝，旅行商訪問的路線是 Bc→Cc→Ac→Dc→Bc，則Hopfield網絡輸出所代表有效解用下面的二維矩陣表表1進行表示.

表1 四個城市的訪問路線

表1中是一個4×4二維矩陣，矩陣中每行每列只有一個元素為1，其余均為0，否則路徑是無效的.神經元（x,i）的輸出用Vxi表示，神經元（x,i）的輸入用Uxi表示.如果城市x在i位置上被訪問，則Vxi=1，否則Vxi=0.

針對TSP問題，Hopfield宣言了如下形式的能量函數：

公式1.1中A，B，C，D是權值，dxy表示城市x到城市y之間的距離.[1]

公式1.1中，E的前三項用于約束問題，最后一項用于優化目標.E的第一項用于保證矩陣V的每一行1的個數>=0且<=1時E最小（即每個城市只去一次），E的第二項保證矩陣V的每一列1的個數>=0且<=1時E最小（即每次只訪問一個城市），E的第三項保證矩陣V中的1的個數恰好為N時E最小.

在神經網絡中引入Hopfield能量函數的概念，從而產生新的方法進行求解優化問題.但新方法在求解上仍然存在一些不足，如局部極小、不穩定等問題.為此，將TSP的能量函數定義為：

取式1.2，Hopfield網絡的動態方程為：

2 采用Hopfield網絡求解TSP問題的算法

采用Hopfield網絡求解TSP問題的算法描述如下:

(1)設置初始值，t=0，A=1.5，D=1.0，μ=50；

(2)計算N個城市之間的距離dxy(x,y=1,2,…,N)；

(3)在0附近設置神經網絡輸入Uxi(t)的初始化數值；

(5)采用一階歐拉法計算Uxi(t+1)

(6)為了保證收斂于正確解，即矩陣V每行每列只有一個元素為1，其余為0，應用Sigmoid函數計算Vxi(t)

Sigmoid函數的形狀由μ>0值的大小決定；

(7)應用公式（1.2），計算能量函數 E；

(8)進行路徑合法性的檢查，根據迭代次數判斷是否結束，如果結束，則終止，否則返回到第（4）步；

(9)輸出并顯示迭代次數、最優能量函數、最優路徑、路徑長度的值，同時給出能量函數隨時間變化的曲線圖.[3]

3 仿真實例

在TSP的Hopfield網絡能量函數公式（1.2）中，取A=B=1.5，D=1.0.設置公式（1.4）離散的間隔時間為 =0.01，在[-0.001,+0.001]間選擇網絡輸入Uxi(t)初始值的隨機值，在公式（1.5）的Sigmoid函數中，取較大的μ，使Sigmoid函數比較陡峭，從而穩態時Vxi(t)能夠趨于1或趨于0.

仿真中，取M=1時，對8個城市的路徑進行優化，城市路徑坐標為：

如果初始化的尋優路徑有效，即路徑矩陣中每行每列只有一個元素為1，其余均為0，則給出最后的優化路徑，否則停止優化，需要重新運行優化程序.如果本次尋優路徑有效，經過2000次迭代，最優能量函數為Final_E=1.4468，初始路程為Initial_Length=4.1419，最終路程為Final_Length=2.8937.

仿真中取M=2時，對20個城市的路徑進行優化，城市路徑坐標為：

如果初始化的尋優路徑有效，即路徑矩陣中每行每列只有一個元素為1，其余均為0，則給出最后的優化路徑，否則停止優化，需要重新運行優化程序.如果本次尋優路徑有效，經過2000次迭代，最優能量函數為Final_E=1.6744，初始路程為Initial_Length=10.0523，最終路程為Final_Length=3.3487.

由于隨機性對網絡輸入Uxi(t)進行初始化的選擇，初始化的尋優路徑最終可能會導致無效，即路徑矩陣中每行元素1的個數超過1個或每列元素中1的個數超過1個，如果矩陣中每行每列不僅僅只是一個元素1就表明尋優失敗，即刻停止優化，需要重新運行優化程序.

以8個城市為例進行路徑優化實驗，仿真實驗100次，最終達到收斂最優解的有90次以上.仿真結果如圖1和圖2所示，其中圖1為初始路徑及優化后的路徑的比較，圖2為能量函數隨時間的變化過程.由仿真結果可見，能量函數E單調下降，E的最小點對應問題的最優解.[2]

圖1 初始路徑及優化后的路徑（8個城市）

圖2 能量函數隨迭代次數的變化（8個城市）

以20個城市為例進行路徑優化實驗，仿真實驗100次，最終達到收斂最優解的有90次以上.仿真結果如圖3和圖4所示，其中圖3為初始路徑及優化后的路徑的比較，圖4為能量函數隨時間的變化過程.由仿真結果可見，能量函數E單調下降，E的最小點對應問題的最優解.[2]

圖3 初始路徑及優化后的路徑（20個城市）

圖4 能量函數隨迭代次數的變化（20個城市）

4 小結

本文應用Hopfield網絡解決了旅行商問題中的路徑優化問題.對于旅行商路徑優化問題提出了新的設計和算法，使路徑更加優化，并通過計算機仿真得到了理想的結果.

〔1〕張弘.Hopfield神經網絡在機器人路徑規劃中的應用[J].西安郵電學院學報，2009（5）.

〔2〕劉金琨.智能控制[M].北京：電子工業出版社，2005.

〔3〕張濤濤，吳俊林，張巖.基于Hopfield神經網絡的WSN分布式拓撲[J].計算機與現代化，2010（1）.