人工神經(jīng)網(wǎng)絡(luò)實驗與tsp問題_百度文庫

1、人工神經(jīng)網(wǎng)絡(luò)實驗二用CHNN算法求解TSP問題一 問題描述利用連續(xù)型Hopfield反饋網(wǎng)絡(luò)求解10城市的旅行商（TSP）問題。其中10個城市的坐標給定如下：基本網(wǎng)絡(luò)參數(shù)為：二 算法實現(xiàn)1CHNN算法應(yīng)用CHNN網(wǎng)絡(luò)解決優(yōu)化問題一般需要以下步驟：(1.對于特定的問題，要選擇一種合適的表示方法，使得神經(jīng)網(wǎng)絡(luò)的輸出與問題的解相對應(yīng)。(2.構(gòu)造網(wǎng)絡(luò)的能量函數(shù)，使其最小值對應(yīng)于問題的最佳解。(3.將能量函數(shù)與CHNN算法標準形式相比較，推出神經(jīng)網(wǎng)絡(luò)權(quán)值與偏流表達式。(4.推出網(wǎng)絡(luò)狀態(tài)更新公式，并利用更新公式迭代求問題的最優(yōu)解。2TSP問題為使用CHNN網(wǎng)絡(luò)進行TSP問題的求解，根據(jù)上述步驟，可將問題轉(zhuǎn)

2、化為：(1.對N個城市的TSP問題，用一個的換位陣描述旅行路線，換位陣中每行每列有且只有一個元素為1，其余全為0。為1的元素其橫坐標x表示城市名，縱坐標i表示該城市在訪問路線中的位置。(2.網(wǎng)絡(luò)的能量函數(shù)由四部分組成，分別用來保證換位陣的合法性以及最終路線長度的最短。(3.將能量函數(shù)與標準形式相比較，得到網(wǎng)絡(luò)權(quán)值與偏流表達式為： (4.從而，網(wǎng)絡(luò)更新公式為：3 程序設(shè)計 根據(jù)上述推導(dǎo)在MATLAB中設(shè)計CHNN網(wǎng)絡(luò)求解TSP問題的程序（程序代碼見附頁）。(1. 程序說明本程序中有以下兩點需要說明。Ø 迭代結(jié)束條件：理論上來說，當網(wǎng)絡(luò)的能量函數(shù)不再減小時網(wǎng)絡(luò)達到最優(yōu)狀態(tài)，但在實際中如果

3、用能量函數(shù)的變化來判斷程序的結(jié)束存在潛在的問題（如計算能量函數(shù)的復(fù)雜性以及誤差導(dǎo)致判斷不準確等），因此，本實驗利用迭代次數(shù)控制程序結(jié)束，當?shù)?000次時，一次運行結(jié)束。Ø 程序輸出規(guī)則：由于不能保證每次迭代結(jié)束所到的解都是合法解，而當城市個數(shù)較多時人為檢查合法性又非常的不方便，因此每次迭結(jié)束后在程序中檢查該次解的合法性，若為合法解，則輸出該解，程序結(jié)束；否則，再次求解。Ø 參數(shù)調(diào)整：在實驗中發(fā)現(xiàn)，當網(wǎng)絡(luò)參數(shù)取為最初給定的值時，幾乎得不到合法解，觀察每次迭代結(jié)束后的解，發(fā)現(xiàn)大部分下只有8個每行每列有且只有一個1的情況，另外還有兩列全部為0。這說明在能量函數(shù)中保證有N個1的

4、合法性所占的比重相對較小，也就是參數(shù)C相對于A、B、D來說較小，因此，將基本參數(shù)C調(diào)整為1000，其余不變。(2. 程序流程i. 初始化：城市個數(shù)、城市坐標、網(wǎng)絡(luò)參數(shù)ii. 用隨機數(shù)初始化換位陣及狀態(tài)陣iii. 對狀態(tài)陣及換位陣，進行1000步同步更新，得最終換位陣的解Viv. 判斷所得V的合法性，若為合法解，給出訪問次序，旅行路線圖及路線總長度，程序結(jié)束；否則，轉(zhuǎn)到第ii步。三 實驗結(jié)果1基本結(jié)果在城市個數(shù)取為10，網(wǎng)絡(luò)的基本參數(shù)取為時運行程序并統(tǒng)計實驗結(jié)果，得：（圖見下頁） 運行次數(shù)200合法解次數(shù)29最優(yōu)解次數(shù)1最優(yōu)解（路線總長度）2.6907次優(yōu)解次數(shù)1次優(yōu)解（路線總長度）2.7693

5、較優(yōu)解（路線總長度）2.7782較優(yōu)解（路線總長度）2.8352平均一次運行所需時間(s0.8813圖1 最優(yōu)路線（2.6907）圖2 最優(yōu)解換位陣圖3次優(yōu)路線(2.7693 圖4次優(yōu)換位陣圖5較優(yōu)路線(2.7782 圖6較優(yōu)換位陣2參數(shù)影響(1.運行時間估計在城市數(shù)目N及更新步長lamda固定的情況下，每求解一次V所用的時間是固定的，因此，比較每次出現(xiàn)合法解所用的時間可通過比較循環(huán)次數(shù)進行。在下面參數(shù)影響的討論中，均通過循環(huán)次數(shù)比較相對時間長短。(2.權(quán)系數(shù)A、B、C權(quán)矩陣A、B、C、D的相對大小反映了對解的要求。其中A、B、C是為了保證合法解的項的權(quán)系數(shù)，A是保證每行最多一個1的權(quán)系數(shù)；B

6、是保證每列最多一個1的權(quán)系數(shù)；C是保證共有N個1；D是保證路線總長度最短的項的權(quán)系數(shù)。當C相對于A和B較?。ˋ=B=500，C=200）時，實驗很難出現(xiàn)合法解，多數(shù)解都有兩列全為0，程序往往陷入死循環(huán)。這說明，解的合法性的第三項沒有得到足夠的重視。因此，逐漸加大C并觀察實驗結(jié)果，當C為500時，上述情況仍沒有明顯改善；當C取為1000時，合法解出現(xiàn)頻率明顯提高（200次實驗中，平均每6.7次出現(xiàn)一次合法解），其中也出現(xiàn)了最優(yōu)解（見1中的實驗結(jié)果）；當C取為2000是，平均每6次出現(xiàn)一次全法解，其中同樣出現(xiàn)一次最優(yōu)解?？偨Y(jié)，C較小不能保證解的合法性，C較大時出現(xiàn)合法解的頻率明顯提高，但同時C較大

7、時路線最短項的權(quán)系數(shù)D相對較小，因此，出現(xiàn)最優(yōu)解的頻率將有所下降。(3. 權(quán)系數(shù)D權(quán)系數(shù)D反映了路線長度在能量函數(shù)中所占的比重。當D取為200時，平均每1.5次出現(xiàn)一次合法解，但路線長度非常大，一般在4.0左右，幾乎不能出現(xiàn)最優(yōu)解；當D取為500時，平均每6.7次出現(xiàn)一次合法解，其中也出現(xiàn)了最優(yōu)解（見1中的實驗結(jié)果）；當D取為600時，出現(xiàn)合法解的頻率有所下降；當D取為700時，151次運行中出現(xiàn)一次較優(yōu)解；當D取為1000時，程序幾乎陷于死循環(huán)，出現(xiàn)合法解的幾率極低?？偨Y(jié)，D較小時，相對更強調(diào)解的合法性，因此出現(xiàn)合法解的頻率較大，但路線長度很大；D較大時，出現(xiàn)合法解的頻率有所降低，但路線長度

8、明顯變小，出現(xiàn)最優(yōu)解的可能性相對增加；而當D過大時，由于過度強調(diào)路線長度，很難出現(xiàn)合法解，因此程序易凍結(jié)。(4. 步長lamda當lamda為0.0001時運行結(jié)果如1中所述；當lamda取為0.001時，平均每2.5次出現(xiàn)一次合法解?？梢?，lamda較大時，狀態(tài)矩陣變化較大，會提高出現(xiàn)合法解的頻率；但lamda過大時狀態(tài)矩陣會由于變化劇烈而難以出現(xiàn)合法解；lamda較小時會導(dǎo)致更新速度過慢甚至凍結(jié)。(5. 初值取為0.02時運行結(jié)果如1中所述；當取為0.005時，平均每3.6次出現(xiàn)一次最優(yōu)解；取為0.3時，平均每41次出現(xiàn)一次全法解?？梢?，較小，激勵函數(shù)趨近于離散值，縮短出現(xiàn)尋優(yōu)時間，但不易

9、出現(xiàn)最優(yōu)解；較大，激勵函數(shù)過于平坦，不利于收斂。3改變城市數(shù)目下面分別給出城市數(shù)目為5和11，網(wǎng)絡(luò)參數(shù)不變時的實驗結(jié)果。由實驗結(jié)果可知，城市數(shù)目下降，尋優(yōu)時間縮短，得到合法解和最優(yōu)解的頻率明顯增加。另外，由于網(wǎng)絡(luò)參數(shù)對實驗的影響同前面類似，此處不再贅述。(1. 城市數(shù)目為11（第11個城市的坐標為(0.9125,0.9568）平均每7.5次出現(xiàn)一次合法解，其中一次較優(yōu)解路線長度為3.1382，圖形如下：圖7十一城市TSP問題較優(yōu)解(2. 城市數(shù)目為5（取前5個城市的坐標）平均每5次出現(xiàn)一次合法解，35次實驗中出現(xiàn)3次最優(yōu)解。最優(yōu)解為1.8324，其中還多次出現(xiàn)較優(yōu)解1.8904，圖形如下： 圖

10、8五城市TSP問題的最優(yōu)解圖9五城市TSP問題較優(yōu)解四附頁（程序代碼）function myTSP1%城市數(shù)目N=10;%5%11%城市坐標及城市間距離cityx=0.4,0.2439,0.1707,0.2293,0.5171,0.8732,0.6878,0.8488,0.6683,0.6195,0.9125;cityy=0.4439,0.1463,0.2293,0.761,0.9414,0.6536,0.5219,0.3609,0.2536,0.2634, 0.9568;for i=1:1:Nfor j=1:1:Nd(i,j=sqrt(cityx(i-cityx(j2+(cityy(i-ci

11、tyy(j2;endend%網(wǎng)絡(luò)參數(shù)A=500;B=500;C=1000;D=500;u0=0.02;tao=1;lamda=0.0001;%求得一個合法解%統(tǒng)計每次求得一個合法解要經(jīng)過多少次非法解total=0;%結(jié)束標志toend=0;time=clock;display('current time is ',num2str(time(1,4:6while toend=0total=total+1%換位陣及初始化V=rand(N,N;U=atanh(2*V-1*u0;%狀態(tài)更新for renew=1:1:1000%同步更新for ux=1:1:Nfor ui=1:1:Nm1

12、=0;m2=0;m3=0;m4=0;%求導(dǎo)公式第一項for j=1:1:Nif j=uim1=m1+V(ux,j;end endm1=-A*m1;%求導(dǎo)公式第二項for y=1:1:Nif y=uxm2=m2+V(y,ui;endendm2=-B*m2;%求導(dǎo)公式第三項for x=1:1:Nfor j=1:1:Nm3=m3+V(x,j;endendm3=-C*(m3-N;%求導(dǎo)公式第四項for y=1:1:Nif y=uxif ui=1m4=m4+d(ux,y*(V(y,ui+1+V(y,N;elseif ui=Nm4=m4+d(ux,y*(V(y,ui-1+V(y,1;elsem4=m4+d

13、(ux,y*(V(y,ui+1+V(y,ui-1;endend endm4=-D*m4;Udao(ux,ui=-U(ux,ui+m1+m2+m3+m4;endend%導(dǎo)數(shù)及狀態(tài)更新 U=U+lamda*Udao;V=(1+tanh(U/u0/2;for ux=1:1:Nfor ui=1:1:Nif V(ux,ui<0.3V(ux,ui=0;endif V(ux,ui>0.7V(ux,ui=1;end endendendV;%判斷是否為合法解%換位陣全局約束，要求總共有N個1test1=0;for ux=1:1:Nfor ui=1:1:Ntest1=test1+V(ux,ui;end

14、end %城市行約束，每行不多于一個1 test2=0;for x=1:1:Nfor i=1:1:N-1for j=i+1:1:Ntest2=test2+V(x,i*V(x,j;endendend %城市列約束，每列不多于一個1 test3=0;for i=1:1:Nfor x=1:1:N-1for y=x+1:1:Ntest3=test3+V(x,i*V(y,i;endendend%當為合法解時，跳出循環(huán)if test1=N && test2=0 && test3=0toend = 1;elsetoend=0;endendtime=clock;display('end time is ',num2str(time(1,4:6Vtotal%按結(jié)果重新排列城市坐標for j=1:1:Nfor i=1:1:Nif V(i,j=1cityx_final(j=cityx(i;cityy_final(j=cityy(i;endendendcityx_final(N+1=cityx_final(1;cityy_final(N+1=cityy_final(1;city