基于Hopfield網(wǎng)絡(luò)的TSP路徑優(yōu)化研究

王 穎

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

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

1 求解TSP問題的Hop field網(wǎng)絡(luò)設(shè)計

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

表1 四個城市的訪問路線

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

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

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

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

在神經(jīng)網(wǎng)絡(luò)中引入Hopfield能量函數(shù)的概念，從而產(chǎn)生新的方法進行求解優(yōu)化問題.但新方法在求解上仍然存在一些不足，如局部極小、不穩(wěn)定等問題.為此，將TSP的能量函數(shù)定義為：

取式1.2，Hopfield網(wǎng)絡(luò)的動態(tài)方程為：

2 采用Hopfield網(wǎng)絡(luò)求解TSP問題的算法

采用Hopfield網(wǎng)絡(luò)求解TSP問題的算法描述如下:

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

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

(3)在0附近設(shè)置神經(jīng)網(wǎng)絡(luò)輸入Uxi(t)的初始化數(shù)值；

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

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

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

(7)應(yīng)用公式（1.2），計算能量函數(shù) E；

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

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

3 仿真實例

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

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

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

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

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

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

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

圖1 初始路徑及優(yōu)化后的路徑（8個城市）

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

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

圖3 初始路徑及優(yōu)化后的路徑（20個城市）

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

4 小結(jié)

本文應(yīng)用Hopfield網(wǎng)絡(luò)解決了旅行商問題中的路徑優(yōu)化問題.對于旅行商路徑優(yōu)化問題提出了新的設(shè)計和算法，使路徑更加優(yōu)化，并通過計算機仿真得到了理想的結(jié)果.

〔1〕張弘.Hopfield神經(jīng)網(wǎng)絡(luò)在機器人路徑規(guī)劃中的應(yīng)用[J].西安郵電學(xué)院學(xué)報，2009（5）.

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

〔3〕張濤濤，吳俊林，張巖.基于Hopfield神經(jīng)網(wǎng)絡(luò)的WSN分布式拓撲[J].計算機與現(xiàn)代化，2010（1）.