基于遺傳算法的tsp路徑規(guī)劃算法設(shè)計(jì)(編輯修改稿)
2024-09-01 04:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 0 0 0 0 0 Column 31 0BestShortcut = Columns 1 through 17 29 31 30 27 28 26 25 20 21 22 18 3 17 19 24 16 8 Columns 18 through 31 9 10 2 4 5 7 6 23 11 13 12 14 15 1theMinDistance = +004圖2 31城市搜索圖圖3 搜索過(guò)程6. 總結(jié)本文針對(duì)TSP問(wèn)題,首先給出了基于遺傳算法求解TSP問(wèn)題的一般性流程，設(shè)計(jì)了基于遺傳算法的求解算法,包括編碼設(shè)計(jì)、適應(yīng)度函數(shù)選擇、終止條件設(shè)定、選擇算子設(shè)定、交叉算子設(shè)定以及變異算子設(shè)定等, 然后設(shè)計(jì)并實(shí)現(xiàn)了基于遺傳算法的TSP問(wèn)題求解系統(tǒng), 并編制了完整的Matlab程序予以仿真實(shí)現(xiàn)。根據(jù)仿真結(jié)果可知，遺傳算法是尋求這種滿意解的最佳工具之一，是一種高效、并行、全局搜索的方法。7. 參考文獻(xiàn)[1] 雷英杰, MATLAB 遺傳算法工具箱及應(yīng)用[M].西安: 西安電子科技大學(xué)出版社, 89.[2] 儲(chǔ)理才. 2001 基于MATLAB 的遺傳算法程序設(shè)計(jì)及TSP問(wèn)題求解[J] . 集美大學(xué)學(xué)報(bào)( 自然科學(xué)版) , 6(1) : 1419.[3] 郎茂祥. 2009 配送車(chē)輛優(yōu)化調(diào)度模型與算法[M] . 北京: 電子工業(yè)出版社,75.程序清單：31城市坐標(biāo)圖(x)程序：load(39。39。,39。ascii39。)。load(39。39。,39。ascii39。)。plot(x,y,39。x39。)xlabel(39。X坐標(biāo)39。),ylabel(39。Y坐標(biāo)39。)。grid onCalDist程序：function F=CalDist(dislist,s)DistanV=0。n=size(s,2)。for i=1:(n1) DistanV=DistanV+dislist(s(i),s(i+1))。endDistanV=DistanV+dislist(s(n),s(1))。F=DistanV。drawTSP程序：function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1)。for i=1:CityNum1plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],39。ms39。,39。LineWidth39。,2,39。MarkerEdgeColor39。,39。k39。,39。MarkerFaceColor39。,39。g39。)。 hold on。endplot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],39。ms39。,39。LineWidth39。,2,39。MarkerEdgeColor39。,39。k39。,39。MarkerFaceColor39。,39。g39。)。title([num2str(CityNum),39。城市TSP39。])。if f==0 text(500,230,[39。第 39。,int2str(p),39。 步39。,39。 最短距離為 39。,num2str(bsf)])。else text(500,230,[39。最終搜索結(jié)果：最短距離 39。,num2str(bsf)])。endhold off。pause()。genetic_algorithm程序：function gaTSPCityNum=31。[dislist,Clist]=tsp(CityNum)。inn=100。 %初始種群大小gnmax=200。 %最大代數(shù)pc=。 %交叉概率pm=。 %變異概率%產(chǎn)生初始種群for i=1:inn s(i,:)=randperm(CityNum)。end[f,p]=objf(s,dislist)。gn=1。while gngnmax+1 for j=1:2:inn seln=sel(s,p)。 %選擇操作 scro=cro(s,seln,pc)。 %交叉操作 sew(j,:)=scro(1,:)。 sew(j+1,:)=scro(2,:)。 smnew(j,:)=mut(sew(j,:),pm)。 %變異操作 smnew(j+1,:)=mut(sew(j+1,:),pm)。 end s=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。
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1