基于遺傳算法的TSP路徑規(guī)劃算法設(shè)計(jì)

------------------------------------------------------------------------基于遺傳算法的TSP路徑規(guī)劃算法設(shè)計(jì)基于遺傳算法的TSP路徑規(guī)劃算法設(shè)計(jì)摘要TSP問題是一個(gè)經(jīng)典的NP難度的組合優(yōu)化問題,遺傳算法是求解TSP問題的有效方法之一。針對(duì)這一問題,首先給出了基于遺傳算法求解TSP問題的一般性流程，設(shè)計(jì)了基于遺傳算法的求解算法,包括編碼設(shè)計(jì)、適應(yīng)度函數(shù)選擇、終止條件設(shè)定、選擇算子設(shè)定、交叉算子設(shè)定以及變異算子設(shè)定等,然后設(shè)計(jì)并實(shí)現(xiàn)了基于遺傳算法的TSP問題求解系統(tǒng),并編制了完整的Matlab程序予以仿真實(shí)現(xiàn)。引言旅行商問題(TravelingSalemanProblem,TSP),又叫貨郎擔(dān)問題,是最基本的路線問題,該問題是在尋求單一旅行者由起點(diǎn)出發(fā),通過所有給定的城市之后,最后再回到原點(diǎn)的最小路徑成本。該問題具有廣泛的應(yīng)用性,如物流中的配送車輛調(diào)度問題就可看成一個(gè)約束性多路旅行商問題.因此,對(duì)TSP問題求解具有一定的現(xiàn)實(shí)意義。TSP問題屬于組合優(yōu)化問題,隨著問題規(guī)模增大,其可行解空間也急劇擴(kuò)大,有時(shí)在當(dāng)前的計(jì)算機(jī)上用枚舉法很難甚至不能求出最優(yōu)解,而用啟發(fā)式算法求解這類問題的滿意解是一個(gè)很好的方式,遺傳算法就是尋求這種滿意解的最佳工具之一。遺傳算法模擬自然進(jìn)化過程來搜索最優(yōu)解[1],其本質(zhì)是一種高效、并行、全局搜索的方法。本文采用遺傳算法求解TSP問題并編制Matlab程序進(jìn)行仿真試驗(yàn)。TSP問題的數(shù)學(xué)模型TSP問題即尋找一條最短的遍歷n個(gè)城市的最短路徑,使得:取最小值,di,i+1表示兩城市i和i+1之間的距離。遺傳算法的運(yùn)行過程遺傳算法是一種"生成+檢測"的迭代搜索算法。其運(yùn)算流程可用圖1來表示。圖1遺傳算法的程序TSP問題的遺傳算法實(shí)現(xiàn)4.1編碼并生成初始種群編碼是應(yīng)用遺傳算法時(shí)要解決的首要問題,也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵環(huán)節(jié)。求解TSP問題時(shí),采用所遍歷城市的順序排列來表示各個(gè)個(gè)體的編碼是最自然的編碼方法[2],而且這種表示方法無需解碼過程,占用的內(nèi)存空間較小。4.2適應(yīng)度評(píng)估適應(yīng)度用來度量群體中各個(gè)體在優(yōu)化過程中達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度較高的個(gè)體被選中遺傳到下一代的概率較大；而適應(yīng)度較低的個(gè)體被選中遺傳到下一代的概率相對(duì)較小一些。本文用個(gè)體所表示的循環(huán)路線的倒數(shù)來作為適應(yīng)度評(píng)估值,路線越短,個(gè)體適應(yīng)度值越大。4.3選擇、交叉、變異選擇操作。是從群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新種群的過程.選擇操作以個(gè)體的適應(yīng)度評(píng)估為基礎(chǔ)。其主要目的是避免有用遺傳信息的丟失。從而提高算法的全局收斂性和計(jì)算效率。常用的選擇算子有賭輪選擇、聯(lián)賽選擇、最佳保留等。其中，最佳個(gè)體保存策略可保證迄今為止所得到的最優(yōu)個(gè)體不會(huì)被交叉、變異等遺傳操作所破壞。它是遺傳算法收斂性的一個(gè)重要保證條件。但它也容易使得某個(gè)局部最優(yōu)個(gè)體不易被淘汰反而快速擴(kuò)散。從而使得算法的全局搜索能力不強(qiáng)。因此，最佳個(gè)體保存一般要與其他選擇方法配合使用方可取得良好的效果[3]。交叉運(yùn)算產(chǎn)生子代,子代繼承父代的基本特征。交叉算子一般包括兩個(gè)內(nèi)容:一是對(duì)種群中的個(gè)體隨機(jī)配對(duì)并按預(yù)先設(shè)定的交叉概率來確定需要進(jìn)行交叉操作的個(gè)體對(duì);二是設(shè)定個(gè)體的交叉點(diǎn),并對(duì)的部分結(jié)構(gòu)進(jìn)行相互交換。交叉算子的設(shè)計(jì)與編碼方式有關(guān)。在TSP問題中幾種有代表性的交叉算子如順序交叉、類OX交叉等,這些交叉算子在產(chǎn)生新個(gè)體的過程中沒有目的性,對(duì)于自然數(shù)編碼的TSP問題,這些交叉可能破壞親代的較優(yōu)基因,從而使交叉算子的搜索能力大大降低。變異操作是對(duì)個(gè)體的某些基因值做變動(dòng)。變異操作的目的有兩個(gè),一是使遺傳算法具有局部的隨機(jī)搜索能力,當(dāng)經(jīng)過交叉操作群體已接近最優(yōu)解領(lǐng)域時(shí),利用變異算子可以加速向最優(yōu)解收斂;二是使遺傳算法可維持群體的多樣性,以防止早熟現(xiàn)象。變異算子的設(shè)計(jì)也與編碼方法有關(guān),對(duì)于自然數(shù)編碼的TSP問題,可采用逆轉(zhuǎn)變異、對(duì)換變異和插入變異等。逆轉(zhuǎn)變異,也稱倒位變異,是指在個(gè)體編碼中,隨機(jī)選擇兩點(diǎn)(兩點(diǎn)間稱為逆轉(zhuǎn)區(qū)域),再將這兩點(diǎn)內(nèi)的字串按反序插入到原位置中.倒位變異考慮了原有邊的鄰接關(guān)系,能將巡回路線上的優(yōu)良基因性能較好地遺傳到下一代,提高尋優(yōu)速度。仿真結(jié)果ans=1.0e+003*Columns1through1002.53892.87382.57532.31812.15872.21663.17403.37113.54022.538901.07350.11130.26680.39500.41010.63790.85361.05502.87381.073500.96450.98861.09431.38271.24011.46031.68702.57530.11130.964500.26210.41670.50360.62470.85491.06842.31810.26680.98860.262100.16340.39510.88501.11091.31822.15870.39501.09430.41670.163400.33861.03031.24861.44772.21660.41011.38270.50360.39510.338600.98411.16031.32373.17400.63791.24010.62470.88501.03030.984100.24340.47383.37110.85361.46030.85491.11091.24861.16030.243400.23213.54021.05501.68701.06841.31821.44771.32370.47380.232101.73700.91021.20170.90720.64850.52260.77621.53201.75941.96511.37541.16381.68711.20410.95200.78970.85711.79871.99892.17571.69600.86901.58000.92860.70140.54190.52071.48981.67751.84441.25081.30881.88371.35951.11590.95260.96661.93542.12462.28981.61722.38893.23942.48192.31392.17191.97942.88062.98153.05662.49300.37090.73060.27900.26830.40770.65510.82801.07001.29532.61740.90790.26700.80670.77440.85941.16831.20741.44381.67572.75761.13630.17131.03181.01271.09671.40681.37271.59981.82912.47800.90800.39830.81580.73730.79781.12251.27761.51831.75032.38691.26350.60211.17951.05981.08031.41831.65771.89772.12982.77531.57210.61221.47351.41081.46211.79291.84162.06752.29593.02311.73230.69241.62811.59671.66391.98681.92822.14162.36422.16310.62910.82000.58240.37760.36680.70541.18551.42461.64502.20371.06020.68120.98950.83220.83101.16941.52721.77062.00052.11601.35040.87881.28401.11201.08911.42261.82472.06792.29812.31271.89661.20851.82261.66671.64891.98222.32382.56422.79621.87652.04971.59201.99831.79241.72882.03372.56712.81043.03882.21442.29001.66762.22582.04482.00272.32312.75632.99853.23001.24181.51081.63591.50991.25101.11871.32392.13462.36172.56571.56101.73911.51521.70551.47341.38321.66192.30882.54922.77041.25542.08951.94932.07001.82311.71101.94992.68682.92333.1382Columns11through201.73701.37541.69601.25081.61722.49302.61742.75762.47802.38690.91021.16380.86901.30882.38890.37090.90791.13630.90801.26351.20171.68711.58001.88373.23940.73060.26700.17130.39830.60210.90721.20410.92861.35952.48190.27900.80671.03180.81581.17950.64850.95200.70141.11592.31390.26830.77441.01270.73731.05980.52260.78970.54190.95262.17190.40770.85941.09670.79781.08030.77620.85710.52070.96661.97940.65511.16831.40681.12251.41831.53201.79871.48981.93542.88060.82801.20741.37271.27761.65771.75941.99891.67752.12462.98151.07001.44381.59981.51831.89771.96512.17571.84442.28983.05661.29531.67571.82911.75032.129800.49380.52670.69162.10510.76590.93471.12730.81000.90400.493800.34830.19791.62441.15561.42041.61991.30061.38440.52670.348300.44711.65940.94571.32301.54701.22631.40360.69160.19790.447101.43621.33401.61721.81771.49821.57822.10511.62441.65941.436202.57782.98163.20202.87993.00670.76591.15560.94571.33402.577800.54060.77370.53790.90080.93471.42041.32301.61722.98160.540600.23860.14190.46671.12731.61991.54701.81773.20200.77370.238600.32240.43760.81001.30061.22631.49822.87990.53790.14190.322400.38050.90401.38441.40361.57823.00670.90080.46670.43760.380501.34091.82291.83152.01653.44471.20170.66830.46910.67370.43841.58152.06742.06142.26213.68651.36760.82740.59630.86620.68500.42650.88020.76471.07342.42260.36700.55910.78290.46430.71410.63841.12531.13331.32112.74340.71970.45200.55400.31390.27030.77631.21611.30171.40042.83661.01700.69990.72070.57860.28941.30461.69031.82971.85613.27411.54781.12871.03801.04610.66661.27201.53021.75521.65923.00781.74591.44641.42291.33070.99361.58561.88482.08892.02193.37931.95831.57641.49691.48321.11000.60270.60120.89940.70052.05761.35281.38451.51611.24351.15240.88611.09161.33501.21662.57531.48181.31081.36161.17520.93161.18991.23401.54171.29902.50521.86851.74071.79601.60321.3650Columns21through302.77533.02312.16312.20372.11602.31271.87652.21441.24181.56101.57211.73230.62911.06021.35041.89662.04972.29001.51081.73910.61220.69240.82000.68120.87881.20851.59201.66761.63591.51521.47351.62810.58240.98951.28401.82261.99832.22581.50991.70551.41081.59670.37760.83221.11201.66671.79242.04481.25101.47341.46211.66390.36680.83101.08911.64891.72882.00271.11871.38321.79291.98680.70541.16941.42261.98222.03372.32311.32391.66191.84161.92821.18551.52721.82472.32382.56712.75632.13462.30882.06752.14161.42461.77062.06792.56422.81042.99852.36172.54922.29592.36421.64502.00052.29812.79623.03883.23002.56572.77041.34091.58150.42650.63840.77631.30461.27201.58560.60270.88611.82292.06740.88021.12531.21611.69031.53021.88480.60121.09161.83152.06140.76471.13331.30171.82971.75522.08890.89941.33502.01652.26211.07341.32111.40041.85611.65922.02190.70051.21663.44473.68652.42262.74342.83663.27413.00783.37932.05762.57531.20171.36760.36700.71971.01701.54781.74591.95831.35281.48180.66830.82740.55910.45200.69991.12871.44641.57641.38451.31080.46910.59630.78290.55400.72071.03801.42291.49691.51611.36160.67370.86620.46430.31390.57861.04611.33071.48321.24351.17520.43840.68500.71410.27030.28940.66660.99361.11001.15240.931600.25181.10680.70310.66430.69271.16551.13901.56001.25110.251801.31990.94320.91550.86711.36351.28231.81141.48871.10681.319900.46560.73581.29301.42071.66720.99151.12540.70310.94320.465600.29820.83681.04371.23860.96210.86150.66430.91550.73580.298200.55980.75310.94190.89590.64260.69270.86711.29300.83680.559800.50550.45961.22950.76001.16551.36351.42071.04370.75310.505500.37170.96530.44281.13901.28231.66721.23860.94190.45960.371701.33310.80951.56001.81140.99150.96210.89591.22950.96531.333100.52371.25111.48871.12540.86150.64260.76000.44280.80950.523701.66461.89351.50331.28941.07651.09260.62410.96100.64230.4344Column311.25542.08951.94932.07001.82311.71101.94992.68682.92333.13821.18991.23401.54171.29902.50521.86851.74071.79601.60321.36501.66461.89351.50331.28941.07651.09260.62410.96100.64230.43440BestShortcut=Columns1through1729313027282625202122183171924168Columns18through31910245762311131214151theMinDistance=1.5727e+004圖231城市搜索圖圖3搜索過程總結(jié)本文針對(duì)TSP問題,首先給出了基于遺傳算法求解TSP問題的一般性流程，設(shè)計(jì)了基于遺傳算法的求解算法,包括編碼設(shè)計(jì)、適應(yīng)度函數(shù)選擇、終止條件設(shè)定、選擇算子設(shè)定、交叉算子設(shè)定以及變異算子設(shè)定等,然后設(shè)計(jì)并實(shí)現(xiàn)了基于遺傳算法的TSP問題求解系統(tǒng),并編制了完整的Matlab程序予以仿真實(shí)現(xiàn)。根據(jù)仿真結(jié)果可知，遺傳算法是尋求這種滿意解的最佳工具之一，是一種高效、并行、全局搜索的方法。參考文獻(xiàn)[1]雷英杰,等.2009MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學(xué)出版社,8-9.[2]儲(chǔ)理才.2001基于MATLAB的遺傳算法程序設(shè)計(jì)及TSP問題求解[J].集美大學(xué)學(xué)報(bào)(自然科學(xué)版),6(1):14-19.[3]郎茂祥.2009配送車輛優(yōu)化調(diào)度模型與算法[M].北京:電子工業(yè)出版社,75.程序清單：31城市坐標(biāo)圖(x)程序：load('x.txt','-ascii');load('y.txt','-ascii');plot(x,y,'x')xlabel('X坐標(biāo)'),ylabel('Y坐標(biāo)');gridonCalDist程序：functionF=CalDist(dislist,s)DistanV=0;n=size(s,2);fori=1:(n-1)DistanV=DistanV+dislist(s(i),s(i+1));endDistanV=DistanV+dislist(s(n),s(1));F=DistanV;drawTSP程序：functionm=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);fori=1:CityNum-1plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');holdon;endplot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');title([num2str(CityNum),'城市TSP']);iff==0text(500,230,['第',int2str(p),'步','最短距離為',num2str(bsf)]);elsetext(500,230,['最終搜索結(jié)果：最短距離',num2str(bsf)]);endholdoff;pause(0.05);genetic_algorithm程序：functiongaTSPCityNum=31;[dislist,Clist]=tsp(CityNum);inn=100;%初始種群大小gnmax=200;%最大代數(shù)pc=0.8;%交叉概率pm=0.8;%變異概率%產(chǎn)生初始種群fori=1:inns(i,:)=randperm(CityNum);end[f,p]=objf(s,dislist);gn=1;whilegn<gnmax+1forj=1:2:innseln=sel(s,p);%選擇操作scro=cro(s,seln,pc);%交叉操作scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);smnew(j,:)=mut(scnew(j,:),pm);%變異操作smnew(j+1,:)=mut(scnew(j+1,:),pm);ends=smnew;%產(chǎn)生了新的種群[f,p]=objf(s,dislist);%計(jì)算新種群的適應(yīng)度%記錄當(dāng)前代最好和平均的適應(yīng)度[fmax,nmax]=max(f);ymean(gn)=1000/mean(f);ymax(gn)=1000/fmax;%記錄當(dāng)前代的最佳個(gè)體x=s(nmax,:);drawTSP(Clist,x,ymax(gn),gn,0);gn=gn+1;pause;endgn=gn-1;figure(2);plot(ymax,'r');holdon;plot(ymean,'b');grid;title('搜索過程');legend('最優(yōu)解','平均解');end%------------------------------------------------%計(jì)算適應(yīng)度函數(shù)function[f,p]=objf(s,dislist);inn=size(s,1);%讀取種群大小fori=1:innf(i)=CalDist(dislist,s(i,:));%計(jì)算函數(shù)值，即適應(yīng)度endf=1000./f';%計(jì)算選擇概率fsum=0;fori=1:innfsum=fsum+f(i)^15;endfori=1:innps(i)=f(i)^15/fsum;end%計(jì)算累積概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';end%--------------------------------------------------functionpcc=pro(pc);test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n);end%--------------------------------------------------%“選擇”操作functionseln=sel(s,p);inn=size(p,1);%從種群中選擇兩個(gè)個(gè)體fori=1:2r=rand;%產(chǎn)生一個(gè)隨機(jī)數(shù)prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%選中個(gè)體的序號(hào)endend%------------------------------------------------%“交叉”操作functionscro=cro(s,seln,pc);bn=size(s,2);pcc=pro(pc);%根據(jù)交叉概率決定是否進(jìn)行交叉操作，1則是，0則否scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);ifpcc==1c1=round(rand*(bn-2))+1;%在[1,bn-1]范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)交叉位c2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);middle=scro(1,chb1+1:chb2);scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);scro(2,chb1+1:chb2)=middle;fori=1:chb1whilefind(scro(1,chb1+1:chb2)==scro(1,i))zhi=find(scro(1,chb1+1:chb2)==scro(1,i));y=scro(2,chb1+zhi);scro(1,i)=y;endwhilefind(scro(2,chb1+1:chb2)==scro(2,i))zhi=find(scro(2,chb1+1:chb2)==scro(2,i));y=scro(1,chb1+zhi);scro(2,i)=y;endendfori=chb2+1:bnwhilefind(scro(1,1:chb2)==scro(1,i))zhi=find(scro(1,1:chb2)==scro(1,i));y=scro(2,zhi);scro(1,i)=y;endwhilefind(scro(2,1:chb2)==scro(2,i))zhi=find(scro(2,1:chb2)==scro(2,i));y=scro(1,zhi);scro(2,i)=y;endendendend%--------------------------------------------------%“變異”操作functionsnnew=mut(snew,pm);bn=size(snew,2);snnew=snew;pmm=pro(pm);%根據(jù)變異概率決定是否進(jìn)行變異操作，1則是，0則否ifpmm==1c1=round(rand*(bn-2))+1;%在[1,bn-1]范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)變異位c2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);x=snew(chb1+1:chb2);snnew(chb1+1:chb2)=fliplr(x);endendtabu_search程序：clear;CityNum=31;[dislist,Clist]=tsp(CityNum);Tlist=zeros(CityNum);%禁忌表(tabulist)cl=100;%保留前cl個(gè)最好候選解bsf=Inf;tl=50;%禁忌長度(tabulength)l1=200;%候選解(candidate),不大于n*(n-1)/2(全部領(lǐng)域解個(gè)數(shù))S0=randperm(CityNum);S=S0;BSF=S0;Si=zeros(l1,CityNum);StopL=200;%終止步數(shù)p=1;clf;figure(1);while(p<StopL+1)ifl1>CityNum*(CityNum)/2disp('候選解個(gè)數(shù),不大于n*(n-1)/2(全部領(lǐng)域解個(gè)數(shù))！系統(tǒng)自動(dòng)退出！');l1=(CityNum*(CityNum)/2)^.5;break;endArrS(p)=CalDist(dislist,S);i=1;A=zeros(l1,2);whilei<=l1M=CityNum*rand(1,2);M=ceil(M);ifM(1)~=M(2)m1=max(M(1),M(2));m2=min(M(1),M(2));A(i,1)=m1;A(i,2)=m2;ifi==1isdel=0;elseforj=1:i-1ifA(i,1)==A(j,1)&&A(i,2)==A(j,2)isdel=1;break;elseisdel=0;endendend