用遺傳算法求解中國34個(gè)省會(huì)TSP的問題

word文檔可自由復(fù)制編輯word文檔可自由復(fù)制編輯word文檔可自由復(fù)制編輯用遺傳算法求解中國34個(gè)省會(huì)TSP問題一、TSP問題的描述旅行商問題（TSP）可以具體描述為：已知n個(gè)城市之間的相互距離，現(xiàn)有一個(gè)推銷員從某一個(gè)城市出發(fā)，必須遍訪這n個(gè)城市，并且每個(gè)城市只能訪問一次，最后又必須返回到出發(fā)城市，如何安排他對(duì)這些城市的訪問次序，可使其旅行路線的總長度最短?，F(xiàn)給出中國34個(gè)省會(huì)數(shù)據(jù)，要求基于此數(shù)據(jù)使用遺傳算法解決該TSP問題。中國34省會(huì)位置city=1.西藏2.云南3.四川4.青海5.寧夏6.甘肅7.內(nèi)蒙古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.臺(tái)灣33.重慶34.新疆像素坐標(biāo)如下：Columns1through111001872011872212022583523463362902112652141581421651216685106127Columns12through22297278296274265239302316334325293135147158177148182203199206215233Columns23through33280271221233275322250277286342220216238253287285254315293290263226Column3410477二、遺傳算法的介紹2.1遺傳算法遺傳算法的基本原理是通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題，它需要對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)度值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)，在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺產(chǎn)操作后的個(gè)體集合形成下一代新的種群，對(duì)這個(gè)新的種群進(jìn)行下一輪的進(jìn)化。2.2遺傳算法的過程遺傳算法的基本過程是：初始化群體。計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代個(gè)體。按概率Pc進(jìn)行交叉操作。按概率Pm進(jìn)行變異操作。沒有滿足某種停止條件，則轉(zhuǎn)第2步，否則進(jìn)入第7步。輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)界。停止條件有兩種：一是完成了預(yù)先給定的進(jìn)化代數(shù)則停止；二是種群中的最優(yōu)個(gè)體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時(shí)停止。遺傳算法過程圖如圖2初始化種群初始化種群計(jì)算適應(yīng)度值選擇操作交叉操作變異操作適應(yīng)度最優(yōu)群體條件停止結(jié)束開始圖2遺傳算法過程框圖三、遺傳算法解決TSP問題的Matlab程序?qū)崿F(xiàn)3.1程序初始化程序首先讀入34個(gè)省會(huì)城市坐標(biāo)，計(jì)算任意兩個(gè)城市的距離：設(shè)置遺傳算法控制參數(shù)。clearall;clc;clf;load(‘testdata.mat’);nlen=length(x1);xy=[x1;y1]';n=500;%種群數(shù)目C=5000;%進(jìn)化迭代次數(shù)m=2;%適應(yīng)度歸一化淘汰加速指數(shù)，取值不宜太大alpha=0.8;%淘汰保護(hù)指數(shù)，范圍0~1，為1時(shí)關(guān)閉保護(hù)a=meshgrid(1:nlen);%生成nxn矩陣dmat=reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),nlen,nlen);%計(jì)算城市距離矩陣遺傳算法對(duì)求解問題本身是一無所知的，這里采用隨機(jī)生成初始化種群，如下：[N,NN]=size(dmat);farm=zeros(n,N);%用于存儲(chǔ)種群fori=1:nfarm(i,:)=randperm(N);%隨機(jī)生成初始化種群end3.2計(jì)算適應(yīng)度本程序目標(biāo)函數(shù)為經(jīng)過34省會(huì)的總距離，適應(yīng)度與目標(biāo)函數(shù)的正相關(guān)，取值范圍0~1，適應(yīng)度計(jì)算公式為：lenminlenfit(1maxlenminlen0.0001)m其中，len為某組解的總距離，minlen為該次迭代中最短距離，maxlen為該次迭代中最長距離，m為適應(yīng)度歸一化淘汰加速指數(shù)，源程序如下：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選擇操作當(dāng)個(gè)體適應(yīng)度小于某一隨機(jī)數(shù)值時(shí)，遭到淘汰，保留優(yōu)秀個(gè)體，使它們有機(jī)會(huì)作為父代產(chǎn)生后代個(gè)體，源程序如下：FARM=farm;nn=0;%nn為復(fù)制的個(gè)數(shù)fori=1:niffitness(i,1)>=alpha*rand%適應(yīng)度與隨機(jī)數(shù)值相比較nn=nn+1;FARM(nn,:)=farm(i,:);endendFARM=FARM(1:nn,:);3.4交叉操作許多生物的繁衍是通過染色體的交叉完成的，在遺傳算法中使用這一概念，并把交叉作為遺傳算法的一個(gè)操作算子，其實(shí)現(xiàn)過程是對(duì)選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的位置，按交叉概率Pc，在選擇的位置實(shí)行交換，目的在于產(chǎn)生新的基因組合，即新的個(gè)體，源代碼如下：[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);%使用部分匹配交叉法進(jìn)行交叉操作FARM=[FARM;A;B];[aa,bb]=size(FARM);endifaa>nFARM=FARM(1:n,:);%保持種群規(guī)模為nendfarm=FARM;clearFARM;以下是交叉函數(shù)：%交叉算法采用的是由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);%隨機(jī)選擇交叉范圍，從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%交換函數(shù)function[x,y]=exchange(x,y)temp=x;x=y;y=temp;本遺傳算法中并未引入變異操作，當(dāng)程序迭代次數(shù)滿足設(shè)定條件時(shí)，程序得出近似最優(yōu)解。四、程序結(jié)果分析初始值種群數(shù)目設(shè)為500，進(jìn)化迭代次數(shù)為5000，歸一化淘汰加速指數(shù)設(shè)為2，淘汰保護(hù)指數(shù)設(shè)為0.8時(shí)，運(yùn)行程序，得最短距離為1489.3，結(jié)果如下：圖3城市位置坐標(biāo)（左）、初始解（中）、最終解（右）圖4種群數(shù)為500，進(jìn)化數(shù)為5000，TSP問題最優(yōu)路徑圖5種群數(shù)為500，進(jìn)化數(shù)為5000，TSP問題尋優(yōu)歷史從圖4可以看出，迭代次數(shù)超過500次時(shí)，所得的解已接近近似最優(yōu)解。只改變種群數(shù)量，進(jìn)行多次計(jì)算，可得下表：種群數(shù)量最終解距離502679.71002053.02001747.65001489.310001499.820001624.6表一不同種群數(shù)量下最終解綜上所述，種群越大、迭代越多求解的結(jié)果越優(yōu)化，但是需要花費(fèi)大量的運(yùn)算時(shí)間；由于算法中存在多個(gè)隨機(jī)參數(shù)，因此每次計(jì)算結(jié)果不一定相同，須根據(jù)需要設(shè)定初值進(jìn)行多次計(jì)算取多組中最優(yōu)解。五、另一種的遺傳算法解決該問題上述算法中，只采用了遺傳算法中交換操作，以下算法，則采用變異操作解決同一問題。算法核心思路是，在每次迭代中，解的個(gè)體隨機(jī)按4個(gè)為1組，每組中只保留最優(yōu)解，然后對(duì)此最優(yōu)解進(jìn)行左右翻轉(zhuǎn)、交換、向前移位三種變異作，生成三個(gè)新個(gè)體，再參與下次迭代。整個(gè)算法不需要計(jì)算歸一化適應(yīng)度，核心源代碼如下：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%保留最佳個(gè)體，繁殖三個(gè)新個(gè)體tmp_pop(k,:)=best_of_4_rte;switchkcase2%左右翻轉(zhuǎn)tmp_pop(k,I:J)=fliplr(tmp_pop(k,I:J));case3%交換tmp_pop(k,[IJ])=tmp_pop(k,[JI]);case4%向前移動(dòng)一位tmp_pop(k,I:J)=tmp_pop(k,[I+1:JI]);otherwiseendendnew_pop(p-3:p,:)=tmp_pop;endpop=new_pop;在此算法中，每次迭代淘汰率固定為75%，三種變異操作覆蓋面比較廣，直接以最短距離為適應(yīng)函數(shù)，省去每次適應(yīng)度的計(jì)算。初始值種群數(shù)目設(shè)為500，進(jìn)化迭代次數(shù)為5000，尋得最優(yōu)解為1295.72，如下：圖5省會(huì)位置（左上）、各省會(huì)距離分布（右上）、最優(yōu)路徑（左下）、尋優(yōu)歷史（右下）由上圖及最終結(jié)果可以看出，該算法比上一算法所得結(jié)果更優(yōu)化，從尋優(yōu)歷史可見，迭代次數(shù)在接近1000次才能得到近似最優(yōu)解（見表