基于Ｈｏｐｆｉｅｌｄ網(wǎng)解決ＴＳＰ問題
2008-04-12 00:00:00崔學(xué)忠宋玉珍曲付勇
現(xiàn)代電子技術(shù) 2008年7期
摘 要：利用神經(jīng)網(wǎng)絡(luò)解決組合優(yōu)化問題是神經(jīng)網(wǎng)絡(luò)應(yīng)用的一個(gè)重要方面。組合優(yōu)化問題，就是在給定約束條件下，使目標(biāo)函數(shù)極小(或極大)的變量組合問題。首先介紹了Hopfield神經(jīng)網(wǎng)絡(luò)的工作原理，然后具體介紹了TSP問題，然后給出了Hopfield神經(jīng)網(wǎng)絡(luò)解決TSP問題的實(shí)例，最后的結(jié)果表明利用Hopfield神經(jīng)網(wǎng)絡(luò)解決TSP問題可以求得問題最優(yōu)解的次優(yōu)解。
關(guān)鍵詞：神經(jīng)網(wǎng)絡(luò)；Hopfield網(wǎng)；TSP問題；能量函數(shù)
中圖分類號(hào)：TP18文獻(xiàn)標(biāo)識(shí)碼：B
文章編號(hào)：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
利用神經(jīng)網(wǎng)絡(luò)解決組合優(yōu)化問題是神經(jīng)網(wǎng)絡(luò)應(yīng)用的一個(gè)重要方面。所謂組合優(yōu)化問題，就是在給定約束條件下，使目標(biāo)函數(shù)極小(或極大)的變量組合問題。將Hopfield網(wǎng)絡(luò)應(yīng)用于求解組合優(yōu)化問題，把目標(biāo)函數(shù)轉(zhuǎn)化為網(wǎng)絡(luò)的能量函數(shù)，把問題的變量對應(yīng)到網(wǎng)絡(luò)的狀態(tài)，這樣，當(dāng)網(wǎng)絡(luò)的能量函數(shù)收斂于極小值時(shí)，問題的最優(yōu)解也隨之求出。由于神經(jīng)網(wǎng)絡(luò)是并行計(jì)算的，其計(jì)算量不隨維數(shù)的增加而發(fā)生指數(shù)性“爆炸”，因而對于優(yōu)化問題的高速計(jì)算特別有效。
1 Hopfield網(wǎng)的工作原理
目前，人工神經(jīng)網(wǎng)絡(luò)常利用漸進(jìn)穩(wěn)定點(diǎn)來解決某些問題［1，2］。例如，如果把系統(tǒng)的穩(wěn)定點(diǎn)視為一個(gè)記憶的話，那么從初態(tài)朝這個(gè)穩(wěn)定點(diǎn)的演變過程就是尋找記憶的過程。初態(tài)可以認(rèn)為是給定的有關(guān)記憶的部分信息。如果把系統(tǒng)的穩(wěn)定點(diǎn)視為一個(gè)能量函數(shù)的極小點(diǎn)，把能量函數(shù)視為一個(gè)優(yōu)化問題的目標(biāo)函數(shù)，那么從初態(tài)朝這個(gè)穩(wěn)定點(diǎn)的演變過程就是一個(gè)求該優(yōu)化問題的過程。這樣的優(yōu)點(diǎn)在于他的解并不需要真的去計(jì)算，而只要構(gòu)成這種反饋網(wǎng)絡(luò)，適當(dāng)?shù)脑O(shè)計(jì)其連接值和輸入就可達(dá)到目的。
循環(huán)網(wǎng)絡(luò)對輸入信號(hào)的處理是一個(gè)逐漸“修復(fù)”、“加強(qiáng)”的過程，稱為Hopfield網(wǎng)。
圖1 最基本的Hopfield網(wǎng)(n=m=h)
聯(lián)接：神經(jīng)元之間都是互聯(lián)的wij，每個(gè)神經(jīng)元都沒有到自身的聯(lián)接wii=0。
神經(jīng)元個(gè)數(shù)h，輸入向量維數(shù)n，輸出向量維數(shù)m，h≥n，h≥m，n≥1，m≥1。
神經(jīng)元：輸入、輸出、隱藏。
狀態(tài)變化：非同步、同步。
輸入向量：X=(x1，x2，…，xn)。
輸出向量：O=(o1，o2，…，om)。
2 TSP問題
TSP問題，即所謂的旅行商問題(Traveling Salesman Problem)。問題的提法是：在N個(gè)城市中各經(jīng)歷一次后回到出發(fā)點(diǎn)，使所經(jīng)過的路程最短。其不同選擇方案有N!/2N種，在城市數(shù)較少的情況下可以用枚舉等方法，但如果城市數(shù)量較大時(shí)，使用枚舉法求解就要考慮的情況是數(shù)量級(jí)，計(jì)算量之大是不可想象的。將Hopfield網(wǎng)絡(luò)應(yīng)用于求解TSP問題，效果是顯著的［3，4］。
在1985年，J.J.Hopfield和D.W.Tank用循環(huán)網(wǎng)求解TSP。試驗(yàn)表明，當(dāng)城市的個(gè)數(shù)較少時(shí)，可以給出最優(yōu)解；當(dāng)城市個(gè)數(shù)較多而不超過30時(shí)，多可以給出最優(yōu)解的近似解。而當(dāng)城市的個(gè)數(shù)超過30時(shí)，最終的結(jié)果就不太理想了。
解決問題需要說明的是以下幾個(gè)量：
設(shè)問題中含有N個(gè)城市，用N*N個(gè)神經(jīng)元構(gòu)成網(wǎng)絡(luò)。
N個(gè)城市間存在N!/2N條可能路徑。
dxy為城市x與城市y之間的距離；
yxi為城市x的第i個(gè)神經(jīng)元的狀態(tài)；
yxi=1 城市x在第i個(gè)被訪問0 城市x不在第i個(gè)被訪問
wxi，yj為城市x的第i個(gè)神經(jīng)元到城市y的第j個(gè)神經(jīng)元的連接權(quán)。
網(wǎng)絡(luò)的能量函數(shù)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僅當(dāng)所有的城市最多只被訪問一次時(shí)取得極小值0。
+B2∑i∑x∑x≠zyxiyzi僅當(dāng)每次最多只訪問一個(gè)城市時(shí)取得極小值0。
+C2∑x∑iyxi－n2當(dāng)且僅當(dāng)所有的n個(gè)城市一共被訪問n次時(shí)才取得最小值0。
+D2∑x∑z≠x∑idxzyxiyzi+1+yzi－1表示按照當(dāng)前的訪問路線的安排，所需要走的路徑的總長度。
3 Hopfield網(wǎng)解決TSP問題實(shí)例
部分源程序：
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);
運(yùn)行結(jié)果:
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=
最小路徑的次優(yōu)解(即最優(yōu)解的次優(yōu)解)
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運(yùn)行結(jié)果的圖形
由圖2可以看出，最小路徑的走法沒有重疊的，也充分說明了Hopfield網(wǎng)解決TSP問題的有效性。因?yàn)槿〉某鞘袀€(gè)數(shù)為30，個(gè)數(shù)較多，所求得的解是最優(yōu)解的次優(yōu)解。
圖3 初始點(diǎn)的分布圖
4 結(jié) 語
本文主要通過利用Hopfield網(wǎng)絡(luò)求解TSP問題，在給定要求下求得問題的最優(yōu)解。該系統(tǒng)的擴(kuò)展性能也比較好，當(dāng)改變神經(jīng)元個(gè)數(shù)，適當(dāng)改變參數(shù)，也能達(dá)到比較好的效果。
參 考 文 獻(xiàn)［1］胡守仁.神經(jīng)網(wǎng)絡(luò)應(yīng)用技術(shù)［M］.長沙:國防科技大學(xué)出版社，1993.
［2］張乃堯，閻平凡.神經(jīng)網(wǎng)絡(luò)與模糊控制[M].北京:清華大學(xué)出版社，1998.
［3］黨建武，靳蕃.神經(jīng)網(wǎng)絡(luò)方法在解C-TSP中的應(yīng)用[J].蘭州鐵道學(xué)院學(xué)報(bào)，1994，13(1):65-71.
［4］郭鵬.Hopfield 網(wǎng)絡(luò)在優(yōu)化計(jì)算中的應(yīng)用［J］.計(jì)算機(jī)仿真，2002(3):37-40.
［5］張建航，李國.模擬退火算法及其在求解TSP中的應(yīng)用［J］.現(xiàn)代電子技術(shù)，2006，29(22):157-158.
作者簡介 崔學(xué)忠 男，1965年出生，湖北石首人，軍事學(xué)碩士，工程師。主要從事靶場試驗(yàn)測控總體技術(shù)方面的研究。宋玉珍 女，1980年出生，山東濰坊人，博士研究生。主要從事雷達(dá)信號(hào)恒虛警檢測的研究，海雜波建模分析等。曲付勇 男，1984年出生，山東聊城人，碩士研究生。主要從事雷達(dá)分布式檢測等研究。
注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。
