王 穎

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

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

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

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

表1 四個(gè)城市的訪問(wèn)路線

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

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

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

公式1.1中，E的前三項(xiàng)用于約束問(wèn)題，最后一項(xiàng)用于優(yōu)化目標(biāo).E的第一項(xiàng)用于保證矩陣V的每一行1的個(gè)數(shù)>=0且<=1時(shí)E最?。疵總€(gè)城市只去一次），E的第二項(xiàng)保證矩陣V的每一列1的個(gè)數(shù)>=0且<=1時(shí)E最?。疵看沃辉L問(wèn)一個(gè)城市），E的第三項(xiàng)保證矩陣V中的1的個(gè)數(shù)恰好為N時(shí)E最小.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)例

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

仿真中，取M=1時(shí)，對(duì)8個(gè)城市的路徑進(jìn)行優(yōu)化，城市路徑坐標(biāo)為：

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

仿真中取M=2時(shí)，對(duì)20個(gè)城市的路徑進(jìn)行優(yōu)化，城市路徑坐標(biāo)為：

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

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

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

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

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

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

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

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

4 小結(jié)

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

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

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

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