人工神經(jīng)網(wǎng)絡(luò)實(shí)驗(yàn)二

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

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

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

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

5、.6907次優(yōu)解次數(shù)1次優(yōu)解（路線總長(zhǎng)度）2.7693較優(yōu)解（路線總長(zhǎng)度）2.7782較優(yōu)解（路線總長(zhǎng)度）2.8352平均一次運(yùn)行所需時(shí)間(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.)運(yùn)行時(shí)間估計(jì)在城市數(shù)目N及更新步長(zhǎng)lamda固定的情況下，每求解一次V所用的時(shí)間是固定的，因此，比較每次出現(xiàn)合法解所用的時(shí)間可通過(guò)比較循環(huán)次數(shù)進(jìn)行。在下面參數(shù)影響的討論中，均通過(guò)循環(huán)次數(shù)比較相對(duì)時(shí)間長(zhǎng)短。(2.)權(quán)系數(shù)A、B、C權(quán)矩陣A、B、C、D的相對(duì)大小反映了對(duì)解的要求。其中A、B、

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

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

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

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

10、最優(yōu)解。最優(yōu)解為1.8324，其中還多次出現(xiàn)較優(yōu)解1.8904，圖形如下： 圖8五城市TSP問(wèn)題的最優(yōu)解圖9五城市TSP問(wèn)題較優(yōu)解四附頁(yè)（程序代碼）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;%求得一個(gè)合法解%統(tǒng)計(jì)每次求得一個(gè)合法解要經(jīng)過(guò)多少次非法解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)公式第一項(xiàng) for j=1:1:N if j=ui m1=m1+V(ux,j); end end m1=-A*m1; %求導(dǎo)公式第二項(xiàng) for y=1:1:N if y=ux m2=m2+V(y,ui); end end m2=-B*m2; %求導(dǎo)公式第三項(xiàng) for x=1:1:N for j=1:1:N m3=m3+V(x,j); end end m3=-C*(m3-N); %求導(dǎo)公式第四項(xiàng) 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個(gè)1 test1=0; for ux=1:1:N for ui=1:1:N test1=test1+V(ux,ui); end end %城市行約束，每行不多于一個(gè)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 %城市列約束，每列不多于一個(gè)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)為合法解時(shí)，跳出循環(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