遗传算法实现TSP问题

遗传算法实现TSP问题问题提出旅行商问题(travelingsalemanproblem,简称tsp)：已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？解题思路用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1=t1，则旅行商问题的数学模型为：minl=σd(t(i),t(i+1))（i=1,…,n）旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。遗传算法求解TSP的基本步骤1.种群初始化个体编码方法有二进制编码和实数编码，在解决TSP问题过程中个体编码方法为实数编码。对于TSP问题，实数编码为1-n的实数的随机排列，初始化的参数有种群个数M、染色体基因个数N（即城市的个数）、迭代次数C、交叉概率Pc、变异概率Pmutation。2.适应度函数在TSP问题中，对于任意两个城市之间的距离D(i,j)已知，每个染色体（即n个城市的随机排列）可计算出总距离，因此可将一个随机全排列的总距离的倒数作为适应度函数，即距离越短，适应度函数越好，满足TSP要求。3.选择操作遗传算法选择操作有轮盘赌法、锦标赛法等多种方法，本程序采用基于适应度比例的选择策略，即适应度越好的个体被选择的概率越大，同时在选择中保存适应度最高的个体。4.交叉操作遗传算法中交叉操作有多种方法。本程序中对于个体，随机选择两个个体，在对应位置交换若干个基因片段，同时保证每个个体依然是1-n的随机排列，防止进入局部收敛。5.变异操作本程序中对于变异操作，随机选取个体，同时随机选取个体的两个基因进行交换以实现变异操作。流程图产生初始种群开始个体评价选择交叉变异满足终止条件输出最优结果结束NY实验结果MATLAB实现程序如下：（1）适应度函数fit.mfunctionfitness=fit(len,m,maxlen,minlen)fitness=len;fori=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.0001)).^m;end(2)个体距离计算函数mylength.mfunctionlen=myLength(D,p)[N,NN]=size(D);len=D(p(1,N),p(1,1));fori=1:(N-1)len=len+D(p(1,i),p(1,i+1));endend(3)交叉操作函数cross.mfunction[A,B]=cross(A,B)L=length(A);ifL10W=L;elseif((L/10)-floor(L/10))=rand&&L10W=ceil(L/10)+8;elseW=floor(L/10)+8;endp=unidrnd(L-W+1);fprintf('p=%d',p);fori=1:Wx=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));endend(4)对调函数exchange.mfunction[x,y]=exchange(x,y)temp=x;x=y;y=temp;end(5)变异函数Mutation.mfunctiona=Mutation(A)index1=0;index2=0;nnper=randperm(size(A,2));index1=nnper(1);index2=nnper(2);%fprintf('index1=%d',index1);%fprintf('index2=%d',index2);temp=0;temp=A(index1);A(index1)=A(index2);A(index2)=temp;a=A;end(6)连点画图函数plot_route.mfunctionplot_route(a,R)scatter(a(:,1),a(:,2),'rx');holdon;plot([a(R(1),1),a(R(length(R)),1)],[a(R(1),2),a(R(length(R)),2)]);holdon;fori=2:length(R)x0=a(R(i-1),1);y0=a(R(i-1),2);x1=a(R(i),1);y1=a(R(i),2);xx=[x0,x1];yy=[y0,y1];plot(xx,yy);holdon;endend(7)主函数clear;clc;%%%%%%%%%%%%%%%输入参数%%%%%%%%N=50;%%城市的个数M=100;%%种群的个数C=100;%%迭代次数C_old=C;m=2;%%适应值归一化淘汰加速指数Pc=0.4;%%交叉概率Pmutation=0.2;%%变异概率%%生成城市的坐标pos=randn(N,2);%%生成城市之间距离矩阵D=zeros(N,N);fori=1:Nforj=i+1:Ndis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;D(i,j)=dis^(0.5);D(j,i)=D(i,j);endend%%生成初始群体popm=zeros(M,N);fori=1:Mpopm(i,:)=randperm(N);end%%随机选择一个种群R=popm(1,:);figure(1);scatter(pos(:,1),pos(:,2),'rx');axis([-33-33]);figure(2);plot_route(pos,R);%%画出种群各城市之间的连线axis([-33-33]);%%初始化种群及其适应函数fitness=zeros(M,1);len=zeros(M,1);fori=1:Mlen(i,1)=myLength(D,popm(i,:));endmaxlen=max(len);minlen=min(len);fitness=fit(len,m,maxlen,minlen);rr=find(len==minlen);R=popm(rr(1,1),:);fori=1:Nfprintf('%d',R(i));endfprintf('\n');fitness=fitness/sum(fitness);distance_min=zeros(C+1,1);%%各次迭代的最小的种群的距离whileC=0fprintf('迭代第%d次\n',C);%%选择操作nn=0;fori=1:size(popm,1)len_1(i,1)=myLength(D,popm(i,:));jc=rand*0.3;forj=1:size(popm,1)iffitness(j,1)=jcnn=nn+1;popm_sel(nn,:)=popm(j,:);break;endendend%%每次选择都保存最优的种群popm_sel=popm_sel(1:nn,:);[len_mlen_index]=min(len_1);popm_sel=[popm_sel;popm(len_index,:)];%%交叉操作nnper=randperm(nn);A=popm_sel(nnper(1),:);B=popm_sel(nnper(2),:);fori=1:nn*Pc[A,B]=cross(A,B);popm_sel(nnper(1),:)=A;popm_sel(nnper(2),:)=B;end%%变异操作fori=1:nnpick=rand;whilepick==0pick=rand;endifpick=Pmutationpopm_sel(i,:)=Mutation(popm_sel(i,:));endend%%求适应度函数NN=size(popm_sel,1);len=zeros(NN,1);fori=1:NNlen(i,1)=myLength(D,popm_sel(i,:));endmaxlen=max(len);minlen=min(len);distance_min(C+1,1)=minlen;fitness=fit(len,m,maxlen,minlen);rr=find(len==minlen);fprintf('minlen=%d\n',minlen);R=popm_sel(rr(1,1),:);fori=1:Nfprintf('%d',R(i));endfprintf('\n');popm=[];popm=popm_sel;C=C-1;%pause(1);endfigure(3)plot_route(pos,R);axis([-33-33]);结论分析本文采用MATLAB实现遗传算法求解TSP问题,并根据实验结果进行了分析,遗传算法是一种智能优化算法,它的实现有些关键点,一是串的编码方式,本质就是问题编码,串长度及编码形式对算法收敛影响极大;二是适应函数的确定,这是选择的基础;三是自身参数的设定,其中重要的是群体大小,最大迭代次数,交叉概率和变异概率,通过实验我们可以看到最大迭代次数对问题求解的精度有影响,交叉概率和变异概率的设定对问题的收敛速度和求解精度都有极大的影响,目前很多研究都是根据具体的领域问题,改进交叉算子,变异算子,寻找最优的参数设定来提高算法收敛速度和保证最优解的得到,对算子的改进和保证最优解的得到,对算子的改进和参数值的设定这是将来的研究工作。