人工神經(jīng)網(wǎng)絡(luò)實驗二

1、人工神經(jīng)網(wǎng)絡(luò)實驗二用CHNN算法求解TSP問題李琳琳自研422004211068一 問題描述利用連續(xù)型Hopfield反饋網(wǎng)絡(luò)求解10城市的旅行商（TSP）問題。其中10個城市的坐標(biāo)給定如下：基本網(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算法標(biāo)準(zhǔn)形式相比較，推出神經(jīng)網(wǎng)絡(luò)權(quán)值與偏流表達式。(4.)推出網(wǎng)絡(luò)狀態(tài)更新公式，并利用更新公式迭代求問題的最優(yōu)解。2TSP問題為使用CHNN網(wǎng)絡(luò)進行

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

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

4、外還有兩列全部為0。這說明在能量函數(shù)中保證有N個1的合法性所占的比重相對較小，也就是參數(shù)C相對于A、B、D來說較小，因此，將基本參數(shù)C調(diào)整為1000，其余不變。(2.) 程序流程i. 初始化：城市個數(shù)、城市坐標(biāo)、網(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

5、.6907次優(yōu)解次數(shù)1次優(yōu)解（路線總長度）2.7693較優(yōu)解（路線總長度）2.7782較優(yōu)解（路線總長度）2.8352平均一次運行所需時間(s)0.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、

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

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

8、較大，但路線長度很大；D較大時，出現(xiàn)合法解的頻率有所降低，但路線長度明顯變小，出現(xiàn)最優(yōu)解的可能性相對增加；而當(dāng)D過大時，由于過度強調(diào)路線長度，很難出現(xiàn)合法解，因此程序易凍結(jié)。(4.) 步長lamda當(dāng)lamda為0.0001時運行結(jié)果如1中所述；當(dāng)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中所述；當(dāng)取為0.005時，平均每3.6次出現(xiàn)一次最優(yōu)解；取為0.3時，平均每41次出

9、現(xiàn)一次全法解。可見，較小，激勵函數(shù)趨近于離散值，縮短出現(xiàn)尋優(yōu)時間，但不易出現(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個城市的坐標(biāo)為(0.9125,0.9568)）平均每7.5次出現(xiàn)一次合法解，其中一次較優(yōu)解路線長度為3.1382，圖形如下：圖7十一城市TSP問題較優(yōu)解(2.) 城市數(shù)目為5（取前5個城市的坐標(biāo)）平均每5次出現(xiàn)一次合法解，35次實驗中出現(xiàn)3次

10、最優(yōu)解。最優(yōu)解為1.8324，其中還多次出現(xiàn)較優(yōu)解1.8904，圖形如下： 圖8五城市TSP問題的最優(yōu)解圖9五城市TSP問題較優(yōu)解四附頁（程序代碼）function myTSP1%城市數(shù)目N=10;%5%11%城市坐標(biāo)及城市間距離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:N for j=1:1:

11、N d(i,j)=sqrt(cityx(i)-cityx(j)2+(cityy(i)-cityy(j)2); 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é)束標(biāo)志toend=0;time=clock;display('current time is ',num2str(time(1,4:6)while toend=0 total=total+1 %換位陣及初始化 V=rand(N,N); U=atanh(2*V-1)*u0

12、; %狀態(tài)更新 for renew=1:1:1000 %同步更新 for ux=1:1:N for ui=1:1:N m1=0; m2=0; m3=0; m4=0; %求導(dǎo)公式第一項 for j=1:1:N if j=ui m1=m1+V(ux,j); end end m1=-A*m1; %求導(dǎo)公式第二項 for y=1:1:N if y=ux m2=m2+V(y,ui); end end m2=-B*m2; %求導(dǎo)公式第三項 for x=1:1:N for j=1:1:N m3=m3+V(x,j); end end m3=-C*(m3-N); %求導(dǎo)公式第四項 for y=1:1:N if

13、y=ux if ui=1 m4=m4+d(ux,y)*(V(y,ui+1)+V(y,N); elseif ui=N m4=m4+d(ux,y)*(V(y,ui-1)+V(y,1); else m4=m4+d(ux,y)*(V(y,ui+1)+V(y,ui-1); end end end m4=-D*m4; Udao(ux,ui)=-U(ux,ui)+m1+m2+m3+m4; end end %導(dǎo)數(shù)及狀態(tài)更新 U=U+lamda*Udao; V=(1+tanh(U/u0)/2; for ux=1:1:N for ui=1:1:N if V(ux,ui)<0.3 V(ux,ui)=0; en

14、d if V(ux,ui)>0.7 V(ux,ui)=1; end end end end V; %判斷是否為合法解 %換位陣全局約束，要求總共有N個1 test1=0; for ux=1:1:N for ui=1:1:N test1=test1+V(ux,ui); end end %城市行約束，每行不多于一個1 test2=0; for x=1:1:N for i=1:1:N-1 for j=i+1:1:N test2=test2+V(x,i)*V(x,j); end end end %城市列約束，每列不多于一個1 test3=0; for i=1:1:N for x=1:1:N-1

15、for y=x+1:1:N test3=test3+V(x,i)*V(y,i); end end end %當(dāng)為合法解時，跳出循環(huán) if test1=N && test2=0 && test3=0 toend = 1; else toend=0; endendtime=clock;display('end time is ',num2str(time(1,4:6)Vtotal%按結(jié)果重新排列城市坐標(biāo)for j=1:1:N for i=1:1:N if V(i,j)=1 cityx_final(j)=cityx(i); cityy_final(j)=cityy(i); end endendcityx_final(N+1)=cityx_final(1);cityy_final(N+1)=cityy_final(1);cityx_fi