基于遗传算法的TSP路径规划算法设计

------------------------------------------------------------------------基于遗传算法的TSP路径规划算法设计基于遗传算法的TSP路径规划算法设计摘要TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。针对这一问题,首先给出了基于遗传算法求解TSP问题的一般性流程，设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,然后设计并实现了基于遗传算法的TSP问题求解系统,并编制了完整的Matlab程序予以仿真实现。引言旅行商问题(TravelingSalemanProblem,TSP),又叫货郎担问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的城市之后,最后再回到原点的最小路径成本。该问题具有广泛的应用性,如物流中的配送车辆调度问题就可看成一个约束性多路旅行商问题.因此,对TSP问题求解具有一定的现实意义。TSP问题属于组合优化问题,随着问题规模增大,其可行解空间也急剧扩大,有时在当前的计算机上用枚举法很难甚至不能求出最优解,而用启发式算法求解这类问题的满意解是一个很好的方式,遗传算法就是寻求这种满意解的最佳工具之一。遗传算法模拟自然进化过程来搜索最优解[1],其本质是一种高效、并行、全局搜索的方法。本文采用遗传算法求解TSP问题并编制Matlab程序进行仿真试验。TSP问题的数学模型TSP问题即寻找一条最短的遍历n个城市的最短路径,使得:取最小值,di,i+1表示两城市i和i+1之间的距离。遗传算法的运行过程遗传算法是一种"生成+检测"的迭代搜索算法。其运算流程可用图1来表示。图1遗传算法的程序TSP问题的遗传算法实现4.1编码并生成初始种群编码是应用遗传算法时要解决的首要问题,也是设计遗传算法时的一个关键环节。求解TSP问题时,采用所遍历城市的顺序排列来表示各个个体的编码是最自然的编码方法[2],而且这种表示方法无需解码过程,占用的内存空间较小。4.2适应度评估适应度用来度量群体中各个体在优化过程中达到或接近于或有助于找到最优解的优良程度。适应度较高的个体被选中遗传到下一代的概率较大；而适应度较低的个体被选中遗传到下一代的概率相对较小一些。本文用个体所表示的循环路线的倒数来作为适应度评估值,路线越短,个体适应度值越大。4.3选择、交叉、变异选择操作。是从群体中选择生命力强的个体产生新种群的过程.选择操作以个体的适应度评估为基础。其主要目的是避免有用遗传信息的丢失。从而提高算法的全局收敛性和计算效率。常用的选择算子有赌轮选择、联赛选择、最佳保留等。其中，最佳个体保存策略可保证迄今为止所得到的最优个体不会被交叉、变异等遗传操作所破坏。它是遗传算法收敛性的一个重要保证条件。但它也容易使得某个局部最优个体不易被淘汰反而快速扩散。从而使得算法的全局搜索能力不强。因此，最佳个体保存一般要与其他选择方法配合使用方可取得良好的效果[3]。交叉运算产生子代,子代继承父代的基本特征。交叉算子一般包括两个内容:一是对种群中的个体随机配对并按预先设定的交叉概率来确定需要进行交叉操作的个体对;二是设定个体的交叉点,并对的部分结构进行相互交换。交叉算子的设计与编码方式有关。在TSP问题中几种有代表性的交叉算子如顺序交叉、类OX交叉等,这些交叉算子在产生新个体的过程中没有目的性,对于自然数编码的TSP问题,这些交叉可能破坏亲代的较优基因,从而使交叉算子的搜索能力大大降低。变异操作是对个体的某些基因值做变动。变异操作的目的有两个,一是使遗传算法具有局部的随机搜索能力,当经过交叉操作群体已接近最优解领域时,利用变异算子可以加速向最优解收敛;二是使遗传算法可维持群体的多样性,以防止早熟现象。变异算子的设计也与编码方法有关,对于自然数编码的TSP问题,可采用逆转变异、对换变异和插入变异等。逆转变异,也称倒位变异,是指在个体编码中,随机选择两点(两点间称为逆转区域),再将这两点内的字串按反序插入到原位置中.倒位变异考虑了原有边的邻接关系,能将巡回路线上的优良基因性能较好地遗传到下一代,提高寻优速度。仿真结果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搜索过程总结本文针对TSP问题,首先给出了基于遗传算法求解TSP问题的一般性流程，设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,然后设计并实现了基于遗传算法的TSP问题求解系统,并编制了完整的Matlab程序予以仿真实现。根据仿真结果可知，遗传算法是寻求这种满意解的最佳工具之一，是一种高效、并行、全局搜索的方法。参考文献[1]雷英杰,等.2009MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,8-9.[2]储理才.2001基于MATLAB的遗传算法程序设计及TSP问题求解[J].集美大学学报(自然科学版),6(1):14-19.[3]郎茂祥.2009配送车辆优化调度模型与算法[M].北京:电子工业出版社,75.程序清单：31城市坐标图(x)程序：load('x.txt','-ascii');load('y.txt','-ascii');plot(x,y,'x')xlabel('X坐标'),ylabel('Y坐标');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,['最终搜索结果：最短距离',num2str(bsf)]);endholdoff;pause(0.05);genetic_algorithm程序：functiongaTSPCityNum=31;[dislist,Clist]=tsp(CityNum);inn=100;%初始种群大小gnmax=200;%最大代数pc=0.8;%交叉概率pm=0.8;%变异概率%产生初始种群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;%产生了新的种群[f,p]=objf(s,dislist);%计算新种群的适应度%记录当前代最好和平均的适应度[fmax,nmax]=max(f);ymean(gn)=1000/mean(f);ymax(gn)=1000/fmax;%记录当前代的最佳个体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('最优解','平均解');end%------------------------------------------------%计算适应度函数function[f,p]=objf(s,dislist);inn=size(s,1);%读取种群大小fori=1:innf(i)=CalDist(dislist,s(i,:));%计算函数值，即适应度endf=1000./f';%计算选择概率fsum=0;fori=1:innfsum=fsum+f(i)^15;endfori=1:innps(i)=f(i)^15/fsum;end%计算累积概率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);%从种群中选择两个个体fori=1:2r=rand;%产生一个随机数prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%选中个体的序号endend%------------------------------------------------%“交叉”操作functionscro=cro(s,seln,pc);bn=size(s,2);pcc=pro(pc);%根据交叉概率决定是否进行交叉操作，1则是，0则否scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);ifpcc==1c1=round(rand*(bn-2))+1;%在[1,bn-1]范围内随机产生一个交叉位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);%根据变异概率决定是否进行变异操作，1则是，0则否ifpmm==1c1=round(rand*(bn-2))+1;%在[1,bn-1]范围内随机产生一个变异位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个最好候选解bsf=Inf;tl=50;%禁忌长度(tabulength)l1=200;%候选解(candidate),不大于n*(n-1)/2(全部领域解个数)S0=randperm(CityNum);S=S0;BSF=S0;Si=zeros(l1,CityNum);StopL=200;%终止步数p=1;clf;figure(1);while(p<StopL+1)ifl1>CityNum*(CityNum)/2disp('候选解个数,不大于n*(n-1)/2(全部领域解个数)！系统自动退出！');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