基于Ｈｏｐｆｉｅｌｄ網解決ＴＳＰ問題
2008-04-12 00:00:00崔學忠宋玉珍曲付勇
現代電子技術 2008年7期
摘 要：利用神經網絡解決組合優化問題是神經網絡應用的一個重要方面。組合優化問題，就是在給定約束條件下，使目標函數極小(或極大)的變量組合問題。首先介紹了Hopfield神經網絡的工作原理，然后具體介紹了TSP問題，然后給出了Hopfield神經網絡解決TSP問題的實例，最后的結果表明利用Hopfield神經網絡解決TSP問題可以求得問題最優解的次優解。
關鍵詞：神經網絡；Hopfield網；TSP問題；能量函數
中圖分類號：TP18文獻標識碼：B
文章編號：1004-373X(2008)07-027-02
Using Hopfield Network to Solve TSP Problem
CUI Xuezhong1，SONG Yuzhen2，3，QU Fuyong2
(1.91 Team of 92941 Army，Huludao，125001，China;
2.The Management of Graduates Students，Naval Aeronautical Engineering Institute，Yantai，264001，China;
3.91 Team of 91550 Army，Liaoning，116023，China)
Abstract：Using neural network to solve combination optimize problem is one importance side of neural networks′ application.Combination optimize problem is the variable combination problem which makes the goal function minimum or maximum under the given constraint condition.Firstly，this paper introduces the operating principle of Hopfield neural network.Secondly，this paper introduces travelling salesman problem.Thirdly，this paper gives the example of travelling salesman problem using Hopfield neural network.The result shows that using Hopfield neural network to solve travelling salesman problem can obtain optimum solution′s second-rate solution.
Keywords：neural network;Hopfield network;TSP problem;energy function
利用神經網絡解決組合優化問題是神經網絡應用的一個重要方面。所謂組合優化問題，就是在給定約束條件下，使目標函數極小(或極大)的變量組合問題。將Hopfield網絡應用于求解組合優化問題，把目標函數轉化為網絡的能量函數，把問題的變量對應到網絡的狀態，這樣，當網絡的能量函數收斂于極小值時，問題的最優解也隨之求出。由于神經網絡是并行計算的，其計算量不隨維數的增加而發生指數性“爆炸”，因而對于優化問題的高速計算特別有效。
1 Hopfield網的工作原理
目前，人工神經網絡常利用漸進穩定點來解決某些問題［1，2］。例如，如果把系統的穩定點視為一個記憶的話，那么從初態朝這個穩定點的演變過程就是尋找記憶的過程。初態可以認為是給定的有關記憶的部分信息。如果把系統的穩定點視為一個能量函數的極小點，把能量函數視為一個優化問題的目標函數，那么從初態朝這個穩定點的演變過程就是一個求該優化問題的過程。這樣的優點在于他的解并不需要真的去計算，而只要構成這種反饋網絡，適當的設計其連接值和輸入就可達到目的。
循環網絡對輸入信號的處理是一個逐漸“修復”、“加強”的過程，稱為Hopfield網。
圖1 最基本的Hopfield網(n=m=h)
聯接：神經元之間都是互聯的wij，每個神經元都沒有到自身的聯接wii=0。
神經元個數h，輸入向量維數n，輸出向量維數m，h≥n，h≥m，n≥1，m≥1。
神經元：輸入、輸出、隱藏。
狀態變化：非同步、同步。
輸入向量：X=(x1，x2，…，xn)。
輸出向量：O=(o1，o2，…，om)。
2 TSP問題
TSP問題，即所謂的旅行商問題(Traveling Salesman Problem)。問題的提法是：在N個城市中各經歷一次后回到出發點，使所經過的路程最短。其不同選擇方案有N!/2N種，在城市數較少的情況下可以用枚舉等方法，但如果城市數量較大時，使用枚舉法求解就要考慮的情況是數量級，計算量之大是不可想象的。將Hopfield網絡應用于求解TSP問題，效果是顯著的［3，4］。
在1985年，J.J.Hopfield和D.W.Tank用循環網求解TSP。試驗表明，當城市的個數較少時，可以給出最優解；當城市個數較多而不超過30時，多可以給出最優解的近似解。而當城市的個數超過30時，最終的結果就不太理想了。
解決問題需要說明的是以下幾個量：
設問題中含有N個城市，用N*N個神經元構成網絡。
N個城市間存在N!/2N條可能路徑。
dxy為城市x與城市y之間的距離；
yxi為城市x的第i個神經元的狀態；
yxi=1 城市x在第i個被訪問0 城市x不在第i個被訪問
wxi，yj為城市x的第i個神經元到城市y的第j個神經元的連接權。
網絡的能量函數E:
E=A2∑x∑i∑j≠iyxiyxj+B2∑i∑x∑x≠zyxiyzi+ C2∑x∑iyxi－n2+D2∑x∑z≠x∑idxzyxi(yzi+1+yzi－1)
其中A，B，C，D為懲罰因子。
A2∑x∑i∑j≠iyxiyxj僅當所有的城市最多只被訪問一次時取得極小值0。
+B2∑i∑x∑x≠zyxiyzi僅當每次最多只訪問一個城市時取得極小值0。
+C2∑x∑iyxi－n2當且僅當所有的n個城市一共被訪問n次時才取得最小值0。
+D2∑x∑z≠x∑idxzyxiyzi+1+yzi－1表示按照當前的訪問路線的安排，所需要走的路徑的總長度。
3 Hopfield網解決TSP問題實例
部分源程序：
NumCity = length(loc);
distance = zeros(NumCity);
for i = 1:NumCity，
for j = 1:NumCity，
distance(i，j) =sqrt(loc(i，:) - loc(j，:));
end
end
count = 20;
all[CD#*2]dE = zeros(count，1);
for i = 1:count
path = randperm(NumCity);
energy = sum(distance((path-1)*NumCity + ［path(2:NumCity) path(1)］));
new[CD#*2]path = path;
index = round(rand(2，1)*NumCity+.5);
inversion[CD#*2]index = (min(index):max(index));
new[CD#*2]path(inversion[CD#*2]index) = fliplr(path(inversion[CD#*2]index));
all[CD#*2]dE(i) = abs(energy - ...
sum(sum(diff(loc(［new[CD#*2]path new[CD#*2]path(1)］，:))'.^2)));
end
dE = max(all[CD#*2]dE);
運行結果:
Initial energy = 12.896411
path = 23 27 29 12 13 20 19 18 5 4 2 30 8 16 7 3 1 6 9 17 21 11 10 14 22 24 26 28 25 15
energy = 4.260261
［minE maxE］ = ［4.260261 4.281659］
ans=
最小路徑的次優解(即最優解的次優解)
path=23 27 29 12 13 20 19 18 5 4 2 30 8 16 7 3 1 6 9 17 21 11 10 14 22 24 26 28 25 15 23
如圖2所示。
圖2 Matlab運行結果的圖形
由圖2可以看出，最小路徑的走法沒有重疊的，也充分說明了Hopfield網解決TSP問題的有效性。因為取的城市個數為30，個數較多，所求得的解是最優解的次優解。
圖3 初始點的分布圖
4 結 語
本文主要通過利用Hopfield網絡求解TSP問題，在給定要求下求得問題的最優解。該系統的擴展性能也比較好，當改變神經元個數，適當改變參數，也能達到比較好的效果。
參 考 文 獻［1］胡守仁.神經網絡應用技術［M］.長沙:國防科技大學出版社，1993.
［2］張乃堯，閻平凡.神經網絡與模糊控制[M].北京:清華大學出版社，1998.
［3］黨建武，靳蕃.神經網絡方法在解C-TSP中的應用[J].蘭州鐵道學院學報，1994，13(1):65-71.
［4］郭鵬.Hopfield 網絡在優化計算中的應用［J］.計算機仿真，2002(3):37-40.
［5］張建航，李國.模擬退火算法及其在求解TSP中的應用［J］.現代電子技術，2006，29(22):157-158.
作者簡介 崔學忠 男，1965年出生，湖北石首人，軍事學碩士，工程師。主要從事靶場試驗測控總體技術方面的研究。宋玉珍 女，1980年出生，山東濰坊人，博士研究生。主要從事雷達信號恒虛警檢測的研究，海雜波建模分析等。曲付勇 男，1984年出生，山東聊城人，碩士研究生。主要從事雷達分布式檢測等研究。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
