Hopfield神經網絡解TSP問題及能量函數參數分析

吳高航

（北京交通大學計算機與信息技術學院，北京　100044）

?

Hopfield神經網絡解TSP問題及能量函數參數分析

吳高航

（北京交通大學計算機與信息技術學院，北京100044）

摘要：TSP問題是一個具有NP計算復雜性的問題，傳統的算法難以高效地計算出TSP問題的近似最優解。Hopfield神經網絡是人工神經網絡中一種重要的網絡模型，它為求解TSP問題提供新的思路。通過使用Hopfield神經網絡，我們可以更加高效而準確地求解TSP問題的近似最優解。在Hopfield神經網絡中，能量函數的參數對實驗結果有較大影響。將基于Hopfield神經網絡的方法對TSP問題進行實驗，并分析不同參數對結果的影響。

關鍵詞：TSP問題；Hopfield神經網絡；參數選擇

1　 TSP問題簡介

TSP問題（Travelling Salesman Problem），又稱旅行商問題，是數學領域中的一個著名的問題。一名旅行商人要不重復不遺漏地訪問n個城市，并最終回到出發點。求解目標是選擇任意一個城市作為出發點，要求訪問路徑盡可能短。TSP問題是一個NP-Complete問題，它容易描述但難以優化，目前還沒有一個算法能夠保證在多項式時間內找到問題的最優解。目前對于TSP問題的優化研究主要有兩個方向[1]：完全算法能夠保證得到最優解，但是這類算法的時間復雜度隨著問題的規模的增大而指數增加，因而難以適應較大規模的問題；近似算法只要求找到最優解，并且算法能在多項式時間內結束。傳統的方法主要有窮舉法和貪心算法等。窮舉法列出所有的可行路徑，并從中選出一條最短路徑。理論上這種方法是可行的，但是窮舉法的時間復雜度達到了O（n!），不能適應大規模的問題。貪心算法的思想是每一次都選擇離當前城市最近且未被訪問過的城市作為下一個目的地。這種算法時間復雜度只有O （n），即使問題規模很大，算法也能較快得到結果。但貪心法往往得到的結果與最優解差距較大，算法不能令人滿意。1985年，Hopfield和Tank提出了用Hopfield神經網絡求解TSP問題的方法[2]。在他們的研究基礎上，Wilson和Pawley等對Hopfield算法進行了進一步的研究和改進[3]。Hopfield神經網絡算法比窮舉法的效率更高，比貪心法得到的解更優，是一個求解TSP問題十分優秀的算法。

國內眾多專家學者也針對Hopfield神經網絡在TSP問題上的應用做了相應的研究分析。文獻[4]中介紹了Hopfield神經網絡的算法并進行了實驗分析；文獻[5]中針對TSP問題，將Hopfield神經網絡與遺傳算法進行了分析比較。Hopfield神經網絡求解TSP問題的求解過程中，能量函數的參數選擇會對結果造成重要影響，而上述研究工作并未對Hopfield神經網絡能量函數的參數選擇問題進行深入的研究，因此本文在利用Hopfield神經網絡解決TSP問題的基礎上，通過實驗對Hopfield神經網絡能量函數的參數選擇問題進行探討，分析Hopfield神經網絡能量函數的參數選擇對最終結果的影響。

2　 Hopfield神經網絡解TSP問題的主要思路

在神經網絡中，本文把遍歷序列表示成圖1這樣一個矩陣。如圖所示的矩陣就表示CAEBDC的路徑。本文設計的用Hopfield求解TSP問題的主要思路，也就是通過這一網絡的逐漸收斂而自動搜索出優化的解。

表1　神經元矩陣

考慮到TSP問題的的規則，對于一條合法的路徑，它所對應的矩陣有這樣幾個特點，首先，因為每個城市只能被訪問一次，因此每行只能有一個1，其余元素都是0；其次，因為每一步只能訪問一個城市，因此每列只能有一個1，其余元素都是0；最后，每個城市應該都要被訪問一次，因此矩陣中所有元素的和應該是城市的個數n。

考慮到上面幾個約束條件，可以開始構建神經網絡的能量函數。首先，每行只有一個1，其余元素都是0，假設第x行滿足這個條件，那么第x行的所有元素兩兩相乘再求和，結果應該是0，根據這個約束，可以構建出能量函數中的第一項。

同樣的，每列只有一個1，其余元素都是0，根據這個約束，可以構建出能量函數中的第二項。

根據全部元素和為n這個約束，本文構建出了能量函數中的第三項。

根據路徑最短這個目標，本文構建出了能量函數中的第四項。dxy表示城市x到城市y的距離，從式子中可以看出，若城市x和城市y在路徑中相鄰的話，Vy（i-1）和Vy（i+1）必定有一項為0，一項為1，若城市x和城市y在路徑中不相鄰的話，Vy（i-1）和Vy（i+1）全為0。通過這個式子，可以計算出路徑的長度。

將之前的幾項乘以系數，再進行相加，就得到了最終的能量函數。

能量函數中，前三項是基于TSP規則的約束，最后一項是基于最優解。因此，我們可以認為，能量函數中的前三項是懲罰項，如果某個狀態不滿足TSP問題的約束，對應的項就不為0，例如如果不滿足每行都只有一個1，其他都是0這個規則，那么E1項就不為0，乘以常數2分之A之后，就會很大，這樣能量函數的結果就會很大。最后一項是目標項，路徑越短，這一部分的值就越小。

網絡更新公式中，第一個是根據能量函數計算ΔU的公式，第二個公式是根據u的值更新神經元矩陣的公式。通過這兩個公式，我們可以通過能量函數計算出網絡的更新值。

圖1是算法的主要流程。首先設置初始參數，也就是給A，B，C，D，Δ，u0等參數賦值，然后計算初始的u 和u0，本文一般將u0的值設為0.02，u的所有元素的初始值設為-0.1到0.1之間的隨機值。V矩陣的初始值本文設為0矩陣。然后開始循環。用前面提到的網絡更新公式計算Δu，更新u矩陣的值，再用u矩陣的值更新神經元矩陣V的值。最后，終止的條件就是TSP問題的幾個約束條件，即V的每行每列只有一個1，其他都是0，V的元素和為n。因為這個算法不一定能夠在較短的時間內計算出合法路徑，因此在編程中，一般設置一個最大迭代次數，避免程序死循環。

圖1　算法主要流程

3　 Hopfield神經網絡解TSP問題在MATLAB上的實現

本次實驗使用MATLAB語言，軟件平臺為MATLAB R2013a，操作系統為Windows7，硬件環境：CPU：Intel Core2 Duo T6570 2.10GHz，內存：2GB，硬盤：250G。

測試數據如圖2所示，共有9個城市，第i行第j列表示第i座城市到第j座城市的距離。本文中的距離采用的是二位空間中點的歐氏距離。

運行100次Hopfield神經網絡程序，得到結果為：平均運行時間0.17933859秒，平均路徑長度為4.019666。

4　能量函數的參數對結果的影響分析

Hopfield神經網絡的能量函數如上文所示，其中有四個參數A、B、C、D。本文將對這四個參數首先默認賦值為A=500，B=500，C=500，D=200，之后固定其中三個參數的值，對第四個參數進行不同的賦值，設置最大迭代次數為1000，對每種賦值進行100次實驗求出平均TSP問題路徑和平均迭代次數，并根據結果分析這些參數的影響。

從上表的實驗結果中可以看出，隨著A、B、C三個參數的增大，求解TSP問題的平均迭代次數減小，運行時間也相應減小，平均TSP路徑增大。隨著D的增大，求解TSP問題的平均迭代次數增大，運行時間也相應增大，平均TSP路徑減小。

圖2　測試數據

在上文中設計能量函數時本文曾經討論過，參數A體現了“矩陣中每行只有1”這個約束對結果的重要性，參數B體現了“矩陣中每列只有1”這個約束對結果的重要性、參數C體現了“矩陣所有元素和為n”這個約束對結果的重要性，即A、B、C三個參數體現了TSP問題中限制條件的權重大小；而參數D體現了路徑長度，即問題的優化目標對結果的重要性。

這里ABCD都是大于0的常數，如果增大A、B、C的值，相當于增大問題約束在結果中的比重，這樣得出的結果往往是合法的，在迭代過程中，一旦得到合法的結果，即使路徑長度較長，也將其選為最終結果，因此迭代次數較少。相對應地，由于目標函數的比重較低，導致結果往往里最優解差距較遠，也就是說算出來的路徑都比較長。

相反，如果增大D的值，就增大了尋找盡可能短的路徑這一優化目標的權重，體現在程序中，即使算出了合法的解，也很可能因為路徑不夠短而被棄用，因此迭代次數較多，而迭代次數較多換來的結果是，平均解的路徑一般較短。

綜上所述，A、B、C、D四個參數對結果的影響可以總結為表3：

表3　

表2　不同參數下的實驗結果

表4　

5結語

本文給出了基于Hopfield神經網絡解TSP問題的基本思路，利用MATLAB語言編程實現了該算法并用9個點模擬城市進行了100次重復實驗。在探討Hopfield神經網絡中能量函數的參數選擇問題上，本文從理論上分析了參數變化對實驗結果可能造成的影響，并對能量函數中的四個參數分別取了不同值進行重復實驗，從實驗結果中印證了理論分析的結論。

參考文獻：

[1]沈慶濤,張振宇.高效求解TSP問題的近似算法[J].計算機工程與應用, 2008, 44（35）

[2]Hopfield J J, Tank D W.“Neural”Computation of Decisions in Optimization Problems[J]. Biological Cybernetics, 1985, 52（3）: 141-152.

[3]Wilson G V, Pawley G S. On the Stability of the Travelling Salesman Problem Algorithm of Hopfield and Tank[J]. Biological Cybernetics, 1988, 58（1）: 63-70.

[4]宋玉珍,劉煉,曲付勇.利用Hopfield神經網絡解決TSP問題[J].艦船電子工程. 2010.

[5]余一嬌.用Hopfield神經網絡與遺傳算法求解TSP問題的實驗比較與分析[J].華中師范大學學報（自然科學版）, 2001.

吳高航，男，福建福州人，在讀研究生，研究方向為機器學習

Using Hopfield Neural Networks to Solve TSP and the Analysis of Energy Function Parameters

WU Gao-hang
（School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044）

Abstract：The travelling salesman problem (TSP) is a problem with NP computational complexity. It is difficult to calculate the approximately optimal solution efficiently with traditional algorithm. Hopfield neural networks are an important model of artificial neural networks. It offers a new way of solving TSP. By using Hopfield neural networks, we can calculate the approximately optimal solution of TSP more efficiently. In Hopfield neural networks, the parameters of energy function have a great influence on the result. Uses Hopfield neural networks to solve TSP, and analyzes how the variable values of parameter impact the result.

Keywords：TSP; Hopfield Neural Networks; Parameters Selection

收稿日期：2015-12-31修稿日期:2016-02-28

作者簡介：

文章編號：1007-1423（2016）09-0009-04

DOI：10.3969/j.issn.1007-1423.2016.09.002