基于遗传算法的TSP问题解决

基于遗传算法的TSP问题解决—余小欢B07330230概述：TSP问题是一个经典的运筹学的组合优化问题，针对此问题，研究人员提出了个中各样的算法，主要有贪婪算法，遗传算法，混沌搜索算法等。在本文中分别用贪婪算法和遗传算法去解决30个城市的最短路径问题，并把两者得到了最优解进行比较，发现用遗传算法解决TSP问题非常具有优越性，同时在文章的最后提出了对此遗传算法进行改进的方向。1.贪婪算法x=[188774712558413182471646883585451374127222562879183414544];y=[5476787138355040404042446058696962678494996460623273846262135];a=zeros(30,30);fori=1:30forj=1:30a(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);%求取距离矩阵的值enda(i,i)=1000;%主对角线上的元素置为1000作为惩罚endb=0;c=zeros(30);forj=1:30[m,n]=min(a(:,j));b=b+m;%得到的b值即为贪婪最佳路径的总距离a(n,:)=1000;%已经选择的最小值对应的行的所有值置为1000作为惩罚c(j)=n;endx1=zeros(30);y1=zeros(30);fort=1:30x1(t)=x(c(t));y1(t)=y(c(t));endplot(x1,y1,'-or');xlabel('Xaxis'),ylabel('Yaxis'),title('Ì°À·Â·¾¶');axis([0,1,0,1]);axis([0,100,0,100]);axison用贪婪算法得出的最佳路径走遍30个城市所走的路程为449.3845km其具体的路径图如下：2.遗传算法1主函数部分clc;clearall;closeall;globalxycityfile=fopen('city30.txt','rt');%取30个城市的样本cities=fscanf(cityfile,'%f%f',[2,inf]);%fscanf返回数据的个数fclose(cityfile);t=30+1;%城市的数目是30个s=1500;%样本的数目是1400个G=300;%运算的代数c=25;%选择算子中每次替代的样本的数量x=cities(1,:);y=cities(2,:);pc=0.10;%交叉的概率pm=0.8;%变异的概率pop=zeros(s,t);%得初始的pop矩阵，矩阵的最后一列表示所在行的样本的路径距离fori=1:spop(i,1:t-1)=randperm(t-1);%随机产生1—（t-1）的t-1个数endfork=1:1:G%GA开始ifmod(k,50)==1kendpop=distance(pop);%调用距离函数求距离pop=select(pop,c);%调用选择函数p1=rand;ifp1=pcpop=cross(pop);%调用交叉函数endp2=rand;ifp2=pmpop=mutate(pop);%调用变异函数endend%GA结束%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%bestL=min(pop(:,t))J=pop(:,t);fi=1./J;[Oderfi,Indexfi]=sort(fi);%对于fi进行排序BestS=pop(Indexfi(s),:);%得到最短路I=BestS;fori=1:1:t-1x1(i)=x(I(i));y1(i)=y(I(i));endx1(t)=x(I(1));y1(t)=y(I(1));cities_new=[x1;y1];disp('BestRouteis:');disp(cities_new);pos=[cities_newcities_new(:,1)];lentemp=0;fori=1:1:t-1temp=sqrt((pos(1,i)-pos(1,i+1))^2+(pos(2,i)-pos(2,i+1))^2);lentemp=lentemp+temp;enddisp('ShortestLengthis:');disp(lentemp);figure(1);subplot(1,2,1);%窗口分割的左边部分x(t)=x(1);y(t)=y(1);plot(x,y,'-or');xlabel('Xaxis'),ylabel('Yaxis'),title('原始路径');axis([0,1,0,1]);axis([0,100,0,100]);axisonholdon;subplot(1,2,2);%窗口分割的右边部分plot(x1,y1,'-or');xlabel('Xaxis'),ylabel('Yaxis'),title('最新的路径');axis([0,1,0,1]);axis([0,100,0,100]);axison2距离函数function[pop]=distance(pop)globalxy[s,t]=size(pop);fori=1:1:sdd=0;pos=pop(i,1:t-1);pos=[pospos(:,1)];forj=1:1:t-1m=pos(j);n=pos(j+1);dd=dd+sqrt((x(m)-x(n))^2+(y(m)-y(n))^2);endpop(i,t)=dd;end3选择函数unction[pop]=select(pop,c)[s,t]=size(pop);m11=(pop(:,t));m11=m11';mmax=zeros(1,c);mmin=zeros(1,c);num=1;whilenumc+1%取距离大的C个样本[a,mmax(num)]=max(m11);%选取当前样本的最大值并记录样本编号给mmax(num)m11(mmax(num))=0;num=num+1;endnum=1;whilenumc+1%取距离小的C个样本[b,mmin(num)]=min(m11);m11(mmin(num))=a;num=num+1;endfori=1:cpop(mmax(i),:)=pop(mmin(i),:);%用距离小的C个样本替换距离大的C个样本end4交叉函数function[pop]=cross(pop)[s,t]=size(pop);pop_1=pop;n=randperm(s);%将种群随机排序fori=1:2:s%随机选择两个交叉点m=randperm(t-3)+1;crosspoint(1)=min(m(1),m(2));crosspoint(2)=max(m(1),m(2));%任意两行交叉x1=n(i);x2=n(i+1);%将x1左边与x2的左边互换middle=pop(x1,1:crosspoint(1));pop(x1,1:crosspoint(1))=pop(x2,1:crosspoint(1));pop(x2,1:crosspoint(1))=middle;%将x1右边与x2的右边互换middle=pop(x1,crosspoint(2)+1:t);pop(x1,crosspoint(2)+1:t)=pop(x2,crosspoint(2)+1:t);pop(x2,crosspoint(2)+1:t)=middle;%检查x1左边的重复性并得到x1的左边forj=1:crosspoint(1)whilefind(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j))zhi=find(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j));%确定重复位置temp=pop(x2,crosspoint(1)+zhi);pop(x1,j)=temp;endend%检查x1的右边的重复性并得到x1的右边forj=crosspoint(2)+1:t-1whilefind(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j))zhi=find(pop(x1,crosspoint(1)+1:crosspoint(2))==pop(x1,j));%确定重复的位置temp=pop(x2,crosspoint(1)+zhi);pop(x1,j)=temp;endend%检查x2左边的重复性并得到x2的左边forj=1:crosspoint(1)whilefind(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j))zhi=find(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j));%确定重复位置temp=pop(x1,crosspoint(1)+zhi);pop(x2,j)=temp;endend%检查x2的右边的重复性并得到x2的右边forj=crosspoint(2)+1:t-1whilefind(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j))zhi=find(pop(x2,crosspoint(1)+1:crosspoint(2))==pop(x2,j));%确定重复的位置temp=pop(x1,crosspoint(1)+zhi);pop(x2,j)=temp;endendend%生成的新的种群与交叉前进行比较，并取两者最优[pop]=distance(pop);fori=1:sifpop_1(i,t)pop(i,t)pop(i,:)=pop_1(i,:);endend5变异函数function[pop]=mutate(pop)[s,t]=size(pop);pop_1=pop;fori=1:2:sm=randperm(t-3)+1;%随机取两个点mutatepoint(1)=min(m(1),m(2));mutatepoint(2)=max(m(1),m(2));%用倒置变异的方法倒置两个点中间部分的位置mutate=round((mutatepoint(2)-mutatepoint(1))/2-0.5);forj=1:mutatezhong=pop(i,mutatepoint(1)+j);pop(i,mutatepoint(1)+j)=pop(i,mutatepoint(2)-j);pop(i,mutatepoint(2)-j)=zhong;endend[pop]=distance(pop);%生成的新的种群与变异前比较，并取两者最优fori=1:sifpop_1(i,t)pop(i,t)pop(i,:)=pop_1(i,:);endend用上面的贪婪算法在matlab里运算的结果如下：30个城市的初始路线和优化后的路线如下：从上面的结果可以很明显的发现用遗传算法得到的结果远比用贪婪算法解得的好。3、上面的算法改进的方向1对于TSP,好的路径中城市一般都和其临近城市相连接,很少出现直接同较远城市连接的情况。故而可以采用贪婪法生成初始种群:以每一城市为起点,选择比较临近城市作为下站,然后将固定的两城市经过移位操作移动到编码末尾,这样以提高初始种群质量,使搜索的复杂度降低。2、采用精英保留策略，把当前代中适应度最好的个体保留到下一代群体,而不被交叉变异算法破坏掉,从而保证遗传算法的全局收敛性,而且根据精英个体可能产生适应度更高新个体。