用遺傳算法求解中國34個省會TSP的問題

word文檔可自由復制編輯word文檔可自由復制編輯word文檔可自由復制編輯用遺傳算法求解中國34個省會TSP問題一、TSP問題的描述旅行商問題（TSP）可以具體描述為：已知n個城市之間的相互距離，現有一個推銷員從某一個城市出發(fā)，必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回到出發(fā)城市，如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短。現給出中國34個省會數據，要求基于此數據使用遺傳算法解決該TSP問題。中國34省會位置city=1.西藏2.云南3.四川4.青海5.寧夏6.甘肅7.內蒙古8.黑龍江9.吉林10.遼寧11.北京12天津13.河北14.山東15.河南16.山西17.陜西18.安徽19.江蘇20.上海21.浙江22.江西23.湖北24.湖南25.貴州26.廣西27.廣東28.福建29.海南30.澳門31.香港32.臺灣33.重慶34.新疆像素坐標如下：Columns1through111001872011872212022583523463362902112652141581421651216685106127Columns12through22297278296274265239302316334325293135147158177148182203199206215233Columns23through33280271221233275322250277286342220216238253287285254315293290263226Column3410477二、遺傳算法的介紹2.1遺傳算法遺傳算法的基本原理是通過作用于染色體上的基因尋找好的染色體來求解問題，它需要對算法所產生的每個染色體進行評價，并基于適應度值來選擇染色體，使適應性好的染色體有更多的繁殖機會，在遺傳算法中，通過隨機方式產生若干個所求解問題的數字編碼，即染色體，形成初始種群；通過適應度函數給每個個體一個數值評價，淘汰低適應度的個體，選擇高適應度的個體參加遺傳操作，經過遺產操作后的個體集合形成下一代新的種群，對這個新的種群進行下一輪的進化。2.2遺傳算法的過程遺傳算法的基本過程是：初始化群體。計算群體上每個個體的適應度值由個體適應度值所決定的某個規(guī)則選擇將進入下一代個體。按概率Pc進行交叉操作。按概率Pm進行變異操作。沒有滿足某種停止條件，則轉第2步，否則進入第7步。輸出種群中適應度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)界。停止條件有兩種：一是完成了預先給定的進化代數則停止；二是種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應度在連續(xù)若干代基本沒有改進時停止。遺傳算法過程圖如圖2初始化種群初始化種群計算適應度值選擇操作交叉操作變異操作適應度最優(yōu)群體條件停止結束開始圖2遺傳算法過程框圖三、遺傳算法解決TSP問題的Matlab程序實現3.1程序初始化程序首先讀入34個省會城市坐標，計算任意兩個城市的距離：設置遺傳算法控制參數。clearall;clc;clf;load(‘testdata.mat’);nlen=length(x1);xy=[x1;y1]';n=500;%種群數目C=5000;%進化迭代次數m=2;%適應度歸一化淘汰加速指數，取值不宜太大alpha=0.8;%淘汰保護指數，范圍0~1，為1時關閉保護a=meshgrid(1:nlen);%生成nxn矩陣dmat=reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nlen,nlen);%計算城市距離矩陣遺傳算法對求解問題本身是一無所知的，這里采用隨機生成初始化種群，如下：[N,NN]=size(dmat);farm=zeros(n,N);%用于存儲種群fori=1:nfarm(i,:)=randperm(N);%隨機生成初始化種群end3.2計算適應度本程序目標函數為經過34省會的總距離，適應度與目標函數的正相關，取值范圍0~1，適應度計算公式為：lenminlenfit(1maxlenminlen0.0001)m其中，len為某組解的總距離，minlen為該次迭代中最短距離，maxlen為該次迭代中最長距離，m為適應度歸一化淘汰加速指數，源程序如下：functionfitness=fit(len,m,maxlen,minlen)fitness=len;fori=1:length(len)fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.0001))).^m;end3.3選擇操作當個體適應度小于某一隨機數值時，遭到淘汰，保留優(yōu)秀個體，使它們有機會作為父代產生后代個體，源程序如下：FARM=farm;nn=0;%nn為復制的個數fori=1:niffitness(i,1)>=alpha*rand%適應度與隨機數值相比較nn=nn+1;FARM(nn,:)=farm(i,:);endendFARM=FARM(1:nn,:);3.4交叉操作許多生物的繁衍是通過染色體的交叉完成的，在遺傳算法中使用這一概念，并把交叉作為遺傳算法的一個操作算子，其實現過程是對選中用于繁殖下一代的個體，隨機地選擇兩個個體的位置，按交叉概率Pc，在選擇的位置實行交換，目的在于產生新的基因組合，即新的個體，源代碼如下：[aa,bb]=size(FARM);whileaa<n%選擇交叉的片段ifnn<=2nnper=randperm(2);elsennper=randperm(nn);endA=FARM(nnper(1),:);B=FARM(nnper(2),:);[A,B]=intercross(A,B);%使用部分匹配交叉法進行交叉操作FARM=[FARM;A;B];[aa,bb]=size(FARM);endifaa>nFARM=FARM(1:n,:);%保持種群規(guī)模為nendfarm=FARM;clearFARM;以下是交叉函數：%交叉算法采用的是由Goldberg和Lingle于1985年提出的PMX(部分匹配交叉)function[a,b]=intercross(a,b)L=length(a);ifL<=10%確定交叉寬度W=9;elseif((L/10)-floor(L/10))>=rand&&L>10W=ceil(L/10)+8;elseW=floor(L/10)+8;endp=unidrnd(L-W+1);%隨機選擇交叉范圍，從p到p+Wfori=1:W%交叉x=find(a==b(1,p+i-1));y=find(b==a(1,p+i-1));[a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1));[a(1,x),b(1,y)]=exchange(a(1,x),b(1,y));End%交換函數function[x,y]=exchange(x,y)temp=x;x=y;y=temp;本遺傳算法中并未引入變異操作，當程序迭代次數滿足設定條件時，程序得出近似最優(yōu)解。四、程序結果分析初始值種群數目設為500，進化迭代次數為5000，歸一化淘汰加速指數設為2，淘汰保護指數設為0.8時，運行程序，得最短距離為1489.3，結果如下：圖3城市位置坐標（左）、初始解（中）、最終解（右）圖4種群數為500，進化數為5000，TSP問題最優(yōu)路徑圖5種群數為500，進化數為5000，TSP問題尋優(yōu)歷史從圖4可以看出，迭代次數超過500次時，所得的解已接近近似最優(yōu)解。只改變種群數量，進行多次計算，可得下表：種群數量最終解距離502679.71002053.02001747.65001489.310001499.820001624.6表一不同種群數量下最終解綜上所述，種群越大、迭代越多求解的結果越優(yōu)化，但是需要花費大量的運算時間；由于算法中存在多個隨機參數，因此每次計算結果不一定相同，須根據需要設定初值進行多次計算取多組中最優(yōu)解。五、另一種的遺傳算法解決該問題上述算法中，只采用了遺傳算法中交換操作，以下算法，則采用變異操作解決同一問題。算法核心思路是，在每次迭代中，解的個體隨機按4個為1組，每組中只保留最優(yōu)解，然后對此最優(yōu)解進行左右翻轉、交換、向前移位三種變異作，生成三個新個體，再參與下次迭代。整個算法不需要計算歸一化適應度，核心源代碼如下：forp=4:4:pop_sizertes=pop(rand_pair(p-3:p),:);dists=total_dist(rand_pair(p-3:p));[ignore,idx]=min(dists);best_of_4_rte=rtes(idx,:);ins_pts=sort(ceil(n*rand(1,2)));%生成1x2每一列元素按照升序排列矩陣I=ins_pts(1);J=ins_pts(2);fork=1:4%保留最佳個體，繁殖三個新個體tmp_pop(k,:)=best_of_4_rte;switchkcase2%左右翻轉tmp_pop(k,I:J)=fliplr(tmp_pop(k,I:J));case3%交換tmp_pop(k,[IJ])=tmp_pop(k,[JI]);case4%向前移動一位tmp_pop(k,I:J)=tmp_pop(k,[I+1:JI]);otherwiseendendnew_pop(p-3:p,:)=tmp_pop;endpop=new_pop;在此算法中，每次迭代淘汰率固定為75%，三種變異操作覆蓋面比較廣，直接以最短距離為適應函數，省去每次適應度的計算。初始值種群數目設為500，進化迭代次數為5000，尋得最優(yōu)解為1295.72，如下：圖5省會位置（左上）、各省會距離分布（右上）、最優(yōu)路徑（左下）、尋優(yōu)歷史（右下）由上圖及最終結果可以看出，該算法比上一算法所得結果更優(yōu)化，從尋優(yōu)歷史可見，迭代次數在接近1000次才能得到近似最優(yōu)解（見表