人工神經(jīng)網(wǎng)絡試驗二

1、 人工神經(jīng)網(wǎng)絡實驗二用CHNN算法求解TSP問題一問題描述利用連續(xù)型Hopfield反饋網(wǎng)絡求解10城市的旅行商(TSP)問題。其中10個城市的坐標給定如下：cityl=(0.4000,0.4439),city2=(0.2439,0.1463),city3=(0.1707,0.2293),city4=(0.2293,0.7610),city5=(0.5171,0.9414),city6=(0.8732,0.6536),city7=(0.6878,0.5219),city8=(0.8488,0.3609),city9=(0.6683,0.2536),city10=(0.6195,0.2634)基

2、本網(wǎng)絡參數(shù)為：A二B=D=500,C=200,卩。二0.02二算法實現(xiàn)1CHNN算法應用CHNN網(wǎng)絡解決優(yōu)化問題一般需要以下步驟：(1.)對于特定的問題，要選擇一種合適的表示方法，使得神經(jīng)網(wǎng)絡的輸出與問題的解相對應。(2.)構造網(wǎng)絡的能量函數(shù)，使其最小值對應于問題的最佳解。(3.)將能量函數(shù)與CHNN算法標準形式相比較，推出神經(jīng)網(wǎng)絡權值與偏流表達式。(4.)推出網(wǎng)絡狀態(tài)更新公式，并利用更新公式迭代求問題的最優(yōu)解。2TSP問題為使用CHNN網(wǎng)絡進行TSP問題的求解，根據(jù)上述步驟，可將問題轉化為：(1.)對N個城市的TSP問題，用一個NxN的換位陣描述旅行路線，換位陣中每行每列有且只有一個元素為1

3、，其余全為0。為1的元素其橫坐標x表示城市名，縱坐標i表示該城市在訪問路線中的位置。(2.)網(wǎng)絡的能量函數(shù)由四部分組成，分別用來保證換位陣的合法性以及最終路線長度的最短。y,i-1)E=Amv+BHZVv+C-n)2+Dmdv(v2xixj2xiyi2xi2xyxiy,i+1xi聲ixyHxxixiyHx(3.)將能量函數(shù)與標準形式相比較，得到網(wǎng)絡權值與偏流表達式為：W=-A5(1-5)-B5(1-5)-C-Dd(5+5)彳xi,yjxyijijxyxyj,i+1j,i-1I=C-nTOC o 1-5 h zVxi(4.)從而，網(wǎng)絡更新公式為：duuyyxi=xiAvBJvdttxjyiVji

4、yHx HYPERLINK l bookmark14 -C空v-n)-D工d(v+v)xixyy,i+1y,i-1xiy豐xv=g(u)=1+tanh(u/u)xixi2xi03程序設計根據(jù)上述推導在MATLAB中設計CHNN網(wǎng)絡求解TSP問題的程序(程序代碼見附頁)。(1.)程序說明本程序中有以下兩點需要說明。迭代結束條件：理論上來說，當網(wǎng)絡的能量函數(shù)不再減小時網(wǎng)絡達到最優(yōu)狀態(tài)，但在實際中如果用能量函數(shù)的變化來判斷程序的結束存在潛在的問題(如計算能量函數(shù)的復雜性以及誤差導致判斷不準確等)，因此，本實驗利用迭代次數(shù)控制程序結束，當?shù)?000次時，一次運行結束。程序輸出規(guī)則：由于不能保證每次

5、迭代結束所到的解都是合法解，而當城市個數(shù)較多時人為檢查合法性又非常的不方便，因此每次迭結束后在程序中檢查該次解的合法性，若為合法解，則輸出該解，程序結束；否則，再次求解。參數(shù)調(diào)整：在實驗中發(fā)現(xiàn)，當網(wǎng)絡參數(shù)取為最初給定的值A=B=D=500,C=200,卩=0.02時，幾乎得不到合法解，觀察每次迭代結束后的解，發(fā)現(xiàn)大部分下只有8個每行每列有且只有一個1的情況，另外還有兩列全部為0。這說明在能量函數(shù)中保證有N個1的合法性所占的比重相對較小，也就是參數(shù)C相對于A、B、D來說較小，因此，將基本參數(shù)C調(diào)整為1000，其余不變。（2.）程序流程初始化：城市個數(shù)、城市坐標、網(wǎng)絡參數(shù)用隨機數(shù)初始化換位陣及狀態(tài)

6、陣對狀態(tài)陣及換位陣，進行1000步同步更新，得最終換位陣的解V判斷所得V的合法性，若為合法解，給出訪問次序，旅行路線圖及路線總長度，程序結束；否則，轉到第ii步。三實驗結果1基本結果在城市個數(shù)取為10，網(wǎng)絡的基本參數(shù)取為A二B=D二500,C二1000,卩o二0.02,lamda=0.0001時運行程序并統(tǒng)計實驗結果，得：圖見下頁）運行次數(shù)200合法解次數(shù)29最優(yōu)解次數(shù)1最優(yōu)解（路線總長度）2.6907次優(yōu)解次數(shù)1次優(yōu)解（路線總長度）2.7693較優(yōu)解（路線總長度）2.7782較優(yōu)解（路線總長度）2.8352平均一次運行所需時間1.6613010000000000000000011000000

7、0000010000000000100000000001000000000010000000000100000000001000000000010圖1最優(yōu)路線(2.6907)圖2最優(yōu)解換位陣11111111V二0001000000001000000001000000000000100000000001000000000010000000000100000000001000000000011000000000圖3次優(yōu)路線(2.7693)圖4次優(yōu)換位陣11111111V二0100000000001000000000010000000000100000000001000000000010000000

8、000100000000001000000000011000000000圖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.)權系數(shù)A、B、C權矩陣A、B、C、D的相對大小反映了對解的要求。其中A、B、C是為了保證合法解的項的權系數(shù)，A是保證每行最多一個1的權系數(shù)；B是保證每列最多一個1的權系數(shù)；C是保證共有N個1；D是保證路線總長度最短的項的權系數(shù)。當C相對于A和B較小(A=B

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

10、占的比重。當D取為200時，平均每2次出現(xiàn)一次合法解，但路線長度非常大，一般在4.0左右，幾乎不能出現(xiàn)最優(yōu)解；當D取為500時，平均每7次出現(xiàn)一次合法解，其中也出現(xiàn)了最優(yōu)解(見1中的實驗結果)；當D取為600時，出現(xiàn)合法解的頻率有所下降；當D取為700時，151次運行中出現(xiàn)一次較優(yōu)解；當D取為1000時，程序幾乎陷于死循環(huán)，出現(xiàn)合法解的幾率極低?？偨Y，D較小時，相對更強調(diào)解的合法性，因此出現(xiàn)合法解的頻率較大，但路線長度很大；D較大時，出現(xiàn)合法解的頻率有所降低，但路線長度明顯變小，出現(xiàn)最優(yōu)解的可能性相對增加；而當D過大時，由于過度強調(diào)路線長度，很難出現(xiàn)合法解，因此程序易凍結。(4.)步長lamd

11、a當lamda為0.0001時運行結果如1中所述；當lamda取為0.001時，平均每3次出現(xiàn)一次合法解。可見，lamda較大時，狀態(tài)矩陣變化較大，會提高出現(xiàn)合法解的頻率；但lamda過大時狀態(tài)矩陣會由于變化劇烈而難以出現(xiàn)合法解；lamda較小時會導致更新速度過慢甚至凍結。(5.)初值卩0卩為控制Sigmoid函數(shù)陡度的參數(shù)，取為0.02時運行結果0如1中所述；當卩取為0.005時，平均每4次出現(xiàn)一次最優(yōu)解；0卩取為0.3時，平均每41次出現(xiàn)一次全法解?？梢姡噍^小，00激勵函數(shù)趨近于離散值，縮短出現(xiàn)尋優(yōu)時間，但不易出現(xiàn)最優(yōu)解；卩較大，激勵函數(shù)過于平坦，不利于收斂。03改變城市數(shù)目下面分別給出

12、城市數(shù)目為5和11，網(wǎng)絡參數(shù)不變時的實驗結果。由實驗結果可知，城市數(shù)目下降，尋優(yōu)時間縮短，得到合法解和最優(yōu)解的頻率明顯增加。另外，由于網(wǎng)絡參數(shù)對實驗的影響同前面類似，此處不再贅述。(1.)城市數(shù)目為11(第11個城市的坐標為(0.9125,0.9568)，為隨機產(chǎn)生)平均每7次出現(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，圖形如下：圖8五城市TSP問題的最優(yōu)解圖9五城市TSP問題較優(yōu)解四附頁(程序代

13、碼)functionmyTSP1%城市數(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;fori=1:1:Nforj=1:1:Nd(i,j)=sqrt(cityx(i)-cityx(j)人2+(cityy(i)-cityy(j)人2);endend%網(wǎng)絡參數(shù)A=500;B=500

14、;C=1000;D=500;u0=0.02;tao=1;lamda=0.0001;%求得一個合法解%統(tǒng)計每次求得一個合法解要經(jīng)過多少次非法解total=0;%結束標志toend=0;time=clock;display(currenttimeis,num2str(time(1,4:6)whiletoend=0total=total+1%換位陣及初始化V=rand(N,N);U=atanh(2*V-1)*u0;%狀態(tài)更新forrenew=1:1:1000%同步更新forux=1:1:Nforui=1:1:Nm1=0;m2=0;m3=0;m4=0;%求導公式第一項forj=1:1:Nifj=uim

15、1=m1+V(ux,j);endendm1=-A*m1;%求導公式第二項fory=1:1:Nify=uxm2=m2+V(y,ui);endendm2=-B*m2;%求導公式第三項forx=1:1:Nforj=1:1:Nm3=m3+V(x,j);endendm3=-C*(m3-N);%求導公式第四項fory=1:1:Nify=uxifui=1m4=m4+d(ux,y)*(V(y,ui+1)+V(y,N);elseifui=Nm4=m4+d(ux,y)*(V(y,ui-1)+V(y,1);elsem4=m4+d(ux,y)*(V(y,ui+1)+V(y,ui-1);endendendm4=-D*m

16、4;Udao(ux,ui)=-U(ux,ui)+m1+m2+m3+m4;endend%導數(shù)及狀態(tài)更新U=U+lamda*Udao;V=(1+tanh(U/u0)/2;forux=1:1:Nforui=1:1:NifV(ux,ui)0.7V(ux,ui)=1;endl2 #end endendendV;%判斷是否為合法解%換位陣全局約束，要求總共有N個1test1=0;forux=1:1:Nforui=1:1:Ntest1=test1+V(ux,ui);endend%城市行約束，每行不多于一個1test2=0;forx=1:1:Nfori=1:1:N-1forj=i+1:1:Ntest2=tes

17、t2+V(x,i)*V(x,j);endendend%城市列約束，每列不多于一個1test3=0;fori=1:1:Nforx=1:1:N-1fory=x+1:1:Ntest3=test3+V(x,i)*V(y,i);endend%當為合法解時，跳出循環(huán)iftest1=N&test2=0&test3=0toend=1;elsetoend=0;endendtime=clock;display(endtimeis,num2str(time(1,4:6)Vtotal%按結果重新排列城市坐標forj=1:1:Nfori=1:1:NifV(i,j)=1cityx_final(j)=cityx(i);cityy_final(j)=cityy(i);endendendcityx_final(N+1)=cityx_final(1);ci