歐陽玲

(中原工學(xué)院， 鄭州 450007)

某公司決定派遣調(diào)查員調(diào)查市場行情，現(xiàn)有N個(gè)城市，要求調(diào)查員調(diào)查每一個(gè)城市，并且不能重復(fù)，最后返回公司所在城市。如何安排調(diào)查順序，使其路程最短呢? 這正是旅行商問題(Traveling Salesman Problem，TSP)[1]研究的范疇。由于路徑數(shù)目會隨著城市數(shù)目的增加呈指數(shù)增長，當(dāng)N很大時(shí)，用常規(guī)方法在龐大的搜索空間尋找最優(yōu)解變得非常困難。本文基于Hopfield神經(jīng)網(wǎng)絡(luò)對旅行商問題進(jìn)行研究，建立能量函數(shù)，提出設(shè)計(jì)方法，給出路徑優(yōu)化的解決算法，并對城市數(shù)目N分別為8、20、40的旅行路徑進(jìn)行計(jì)算機(jī)MATLAB模擬仿真。

1 Hopfield神經(jīng)網(wǎng)絡(luò)模型能量函數(shù)

Hopfield神經(jīng)網(wǎng)絡(luò)模型由許多互聯(lián)的神經(jīng)元組成，如圖1所示。

對于一個(gè)神經(jīng)元i，ui為其狀態(tài)輸入；R與Ci分別為輸入電阻和輸入電容；Ii為輸入電流；wij為j神經(jīng)元和i神經(jīng)元之間的連接權(quán)值；vi為神經(jīng)元的輸出，是神經(jīng)元狀態(tài)變量ui的非線性函數(shù)。

對于Hopfield神經(jīng)網(wǎng)絡(luò)的第i個(gè)神經(jīng)元，可采用微分方程建立其輸入、輸出關(guān)系[2]，即：

(1)

圖1 Hopfield 人工神經(jīng)網(wǎng)絡(luò)模型

在狀態(tài)空間中考慮Hopfield神經(jīng)網(wǎng)絡(luò)的動態(tài)特性，分別令U=(u1,u2,…,un)T為具有n個(gè)神經(jīng)元的Hopfield神經(jīng)網(wǎng)絡(luò)的狀態(tài)向量，V=(v1,v2,…,vn)T為輸出向量，I=(I1,I2,…,In)T為網(wǎng)絡(luò)的外加輸入向量。為了描述Hopfield網(wǎng)絡(luò)的動態(tài)穩(wěn)定性，可定義標(biāo)準(zhǔn)能量函數(shù)為[2]：

(2)

針對旅行商問題，將式(2)轉(zhuǎn)化，以便與神經(jīng)網(wǎng)絡(luò)對應(yīng)。這里，采用N階換位矩陣表示調(diào)查者訪問N個(gè)城市[1]。例如，當(dāng)城市數(shù)目N=4時(shí)，集合表示為{A，B，C，D}，要求經(jīng)過的路線是從城市D出發(fā)，中間依次經(jīng)過城市C、B、A，最終返回城市D。若用矩陣來表示輸出的有效解，“1”代表到達(dá)，“0”代表未到達(dá)，則有表1所示4個(gè)城市訪問路線的二維矩陣。

表1 4個(gè)城市的訪問路線

如果訪問路線是一個(gè)有效的路徑，矩陣中每一行每一列的元素是有規(guī)律的，即每行每列中“1”的個(gè)數(shù)為1，其余的都為0。如果不是這樣的矩陣，則說明這個(gè)訪問路線是無效的。對于一個(gè)神經(jīng)元(x，i)，用Vxi表示這個(gè)神經(jīng)元的輸出，Uxi表示相應(yīng)的輸入。如果在i位置到達(dá)城市x，則神經(jīng)元的輸出為1，否則為0。

Hopfield定義了針對TSP問題的能量函數(shù)[3]：

(3)

式中：A、B、C和D是權(quán)值；dxy是城市x與城市y之間的距離。

在該能量函數(shù)中，E的第一項(xiàng)是行能量函數(shù)，第二項(xiàng)是列能量函數(shù)，第三項(xiàng)是全局約束函數(shù)，這3項(xiàng)是約束項(xiàng)，最后一項(xiàng)是優(yōu)化目標(biāo)項(xiàng)。

(1)行能量函數(shù)：每行只有一個(gè)1，其余元素都是 0，假設(shè)第x行滿足這個(gè)條件，那么第x行的所有元素兩兩相乘再求和，結(jié)果應(yīng)該是0。根據(jù)這個(gè)約束，可構(gòu)建出能量函數(shù)中的第一項(xiàng)：

(4)

式中：A>0，是常數(shù)；當(dāng)矩陣每一行1的個(gè)數(shù)不大于1時(shí)，E1達(dá)到最小，即E1min=0。

(2)列能量函數(shù)：每列只有一個(gè)1，其余元素都是 0，假設(shè)第x列滿足這個(gè)條件，那么第x列的所有元素兩兩相乘再求和，結(jié)果應(yīng)該是0。根據(jù)這個(gè)約束，可構(gòu)建出能量函數(shù)中的第二項(xiàng)：

(5)

式中：B>0，是常數(shù)；當(dāng)矩陣每一列1的個(gè)數(shù)不大于1時(shí)，E2達(dá)到最小，即E2min=0。

(3)全局約束函數(shù)即能量函數(shù)的第三項(xiàng)：

(6)

式中：C>0，為常數(shù)。全局約束表示當(dāng)矩陣中1的個(gè)數(shù)恰好為N時(shí)，E3min=0。

(4)考慮路徑最短的優(yōu)化目標(biāo)，可以構(gòu)建出能量函數(shù)的第四項(xiàng)：

(7)

式中：D>0，為常數(shù)；dxy表示城市x到城市y的距離。從式(7)可以看出：若城市x和城市y在路徑中相鄰的話，Vy，i+1和Vy，i-1必定有一項(xiàng)為0，一項(xiàng)為1；若城市x和城市y在路徑中不相鄰的話，Vy，i+1和Vy，i-1全為0。通過式(7)可以計(jì)算出路徑的長度。

由式(4)-式(7)可以構(gòu)成用Hopfield網(wǎng)絡(luò)求解TSP問題的能量函數(shù)式(3)。

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

表2 城市數(shù)與路徑數(shù)

當(dāng)N比較大時(shí)，很難求取精確解。若直接采用能量函數(shù)式(3)進(jìn)行求解，則可能存在局部極小值的問題。為此，可將式(3)優(yōu)化為[4]：

(8)

由式(2)和式(8)，分別對時(shí)間t微分，可得如下動態(tài)方程：

(9)

采用MATLAB進(jìn)行計(jì)算機(jī)模擬，具體步驟如下：

(1)令網(wǎng)絡(luò)的初始值t=0，設(shè)置相關(guān)參數(shù)A、D、μ的值；

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

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

(5)根據(jù)一階歐拉法，求解

(10)

(6)采用Sigmoid函數(shù)計(jì)算Vxi(t)，滿足上述行、列能量函數(shù)及全局約束最小的條件(即矩陣每一行只有一個(gè)1，每一列也只有一個(gè)1，其余都為0)，即：

(11)

式中，μ>0，μ的大小決定了Sigmoid函數(shù)的形狀；

(7)根據(jù)式(8)計(jì)算能量函數(shù)E；

(8)若路徑合法或迭代結(jié)束，則終止仿真，否則返回步驟(4)；

(9)輸出原始路徑及最終的優(yōu)化路徑，以及能量函數(shù)隨迭代次數(shù)變化的曲線[5]。

3 仿真實(shí)例

首先需要設(shè)置實(shí)驗(yàn)中用到的網(wǎng)絡(luò)參數(shù)，并令式(8)中A=1.5，B=1.5，D=1.0；取式(10)中ΔT=0.01，Uxi(t)初始值在±0.001之間；在式(11)中，只有取較大的μ值(μ=50)，才能保證穩(wěn)態(tài)時(shí)Vxi(t)趨向于1或者0。

路徑矩陣中的元素是對應(yīng)于實(shí)驗(yàn)結(jié)果的。在程序運(yùn)行后，如果仿真成功，即尋優(yōu)路徑有效，矩陣中的每一行只有一個(gè)1，每一列也只有一個(gè)1，即代表每個(gè)城市只去一次；若尋優(yōu)路徑無效，則需要重新進(jìn)行優(yōu)化實(shí)驗(yàn)。

然后，在仿真中對N分別為8、20、40的旅行路徑進(jìn)行優(yōu)化(見圖2-圖7，表3-表5)[6]。

注：(X,Y)為坐標(biāo)。圖2 初始路徑及優(yōu)化后的路徑(N=8)

注：E為能量函數(shù)；k為迭代次數(shù)。圖3 能量函數(shù)隨迭代次數(shù)的變化(N=8)

注：(X,Y)為坐標(biāo)。圖4 初始路徑及優(yōu)化后的路徑(N=20)

注：E為能量函數(shù)；k為迭代次數(shù)。圖5 能量函數(shù)隨迭代次數(shù)的變化(N=20)

注：(X,Y)為坐標(biāo)。圖6 初始路徑及優(yōu)化后的路徑(N=40)

注：E為能量函數(shù)；k為迭代次數(shù)。圖7 能量函數(shù)隨迭代次數(shù)的變化(N=40)

表3 各城市坐標(biāo)(N=8)

表4 各城市坐標(biāo)(N=20)

表5 各城市坐標(biāo)(N=40)

上述仿真實(shí)驗(yàn)，在100次中，基本上有90次以上可收斂到最優(yōu)解，表明算法有穩(wěn)定性。以N=8為例，最后的仿真結(jié)果如圖2和圖3所示。在圖2中，左邊為初始路徑(Original Route)，右邊為優(yōu)化后路徑(New Route)?？擅黠@看出，優(yōu)化后相互交叉的路徑大大減少，路徑規(guī)劃更為合理。圖3顯示的是能量函數(shù)隨迭代次數(shù)的變化情況?？梢钥闯?，E的值隨著迭代次數(shù)的增大而減小。N=20及N=40時(shí)，結(jié)論相似。

對N=8、20、40時(shí)進(jìn)行的計(jì)算機(jī)MATLAB仿真表明，最終能量函數(shù)都是最小的，即收斂到了極小點(diǎn)。這與仿真之前的原理分析是一致的，路徑優(yōu)化的原理與研究方法是正確的。實(shí)驗(yàn)證明，無論是Hopfield網(wǎng)絡(luò)的設(shè)計(jì)還是算法都是有效的，而且實(shí)用價(jià)值很高。

4 結(jié) 語

本文在分析Hopfield神經(jīng)網(wǎng)絡(luò)和TSP算法的基礎(chǔ)上，進(jìn)行了求解TSP問題的Hopfield網(wǎng)絡(luò)設(shè)計(jì)，并采用MATLAB針對不同城市數(shù)N的路徑優(yōu)化問題進(jìn)行了仿真，獲得了經(jīng)典組合優(yōu)化問題的最優(yōu)解，驗(yàn)證了算法的有效性。針對標(biāo)準(zhǔn)TSP能量函數(shù)易引入局部極小值的問題，后續(xù)將展開深入研究，進(jìn)一步優(yōu)化能量函數(shù),以提高在N值更大時(shí)TSP最優(yōu)解收斂的成功率。

[1] 吳高航.Hopfield神經(jīng)網(wǎng)絡(luò)解TSP問題及能量函數(shù)參數(shù)分析[J].現(xiàn)代計(jì)算機(jī)，2016(9)：90-92.

[2] 劉金琨.智能控制(第三版)[M].北京：電子工業(yè)出版社，2014：167-172.

[3] Hopfield J，Tank D W. Neural Computation of Decision in Decision in Optimization Problems[J]. Biological Cybernetics，1985,52：141-152.

[4] 孫守宇，鄭君里.Hopfield網(wǎng)絡(luò)求解TSP的一種改進(jìn)算法和理論證明[J].電子學(xué)報(bào)，1995，23(1)：73-78.

[5] 張麗霞，趙又群，潘福全. Hopfield神經(jīng)網(wǎng)絡(luò)算法求解路網(wǎng)最優(yōu)路徑[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2009,41(9)：222-224.

[6] 聞新，李新，張興旺,等.應(yīng)用MATLAB實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)[M].北京：國防工業(yè)出版社,2015:202-247.