基于遗传算法的旅行商问题求解

1基于遗传算法的旅行商问题求解摘要采用MATLAB，对TSP问题进行基于遗传算法的求解。TSP问题是典型的NP完全问题，通过MATLAB进行遗传算法编程，从而有效提出一个较好的TSP解，实现对问题的解答。进而讨论遗传算法的特点，以及对本问题的可行性。关键词：TSP问题遗传算法2一．问题重述假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。二．遗传算法（GA）概述遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。三．问题分析TSP问题就是寻找一条最短的遍历n个城市的最短路径,即搜索自然数子集W={1,2,⋯,n}(W的元素表示对n个城市的编号)的一个排列π(W)={V1,V2,⋯,Vn},使len=∑d(Vi,Vi+1)+d(V1,Vn)取最小值,式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离.遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图1所示。由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（Selection）、交叉（Crossover）和变异（Mutation）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（geneticoperation），使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下6个基本因素：（1）参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。（2）生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机方法产生。（3）适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，仅用适应度（fitness）值来评估个体或解的优劣，并作为以后遗传操作的依据。（4）选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和（f），再计算每个个体的3适应度所占的比例（iff），并以此作为相应的选择概率sP。（5）交叉操作：交叉操作是遗传算法中最主要的遗传操作。简单的交叉（即一点交叉）可分两步进行：首先对种群中个体进行随机配对;其次，在配对个体中随机设定交叉处，配对个体彼此交换部分信息。（6）变异：变异操作是按位（bit）进行的，即把某一位的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率mP都取得较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。这6个要素构成了遗传算法的核心内容，其流程如图1所示。图1遗传算法的基本流程遗传算法解题的基本步骤如下：Step1：参数设置及种群初始化；Step2：对不可行解进行贪婪修复；Step3：适应度评价；Step4：轮盘赌选择；Step5：交叉；Step6：变异；Step7：对不可行解进行贪婪修复；Step8：适应度评价；Step9：终止条件判断，若未达到终止条件，则转到Step4；Step10：输出结果。选择编码和初始种群生成种群中个体适应度的检测评估交叉变异4图2遗传算法具体步骤开始种群初始化参数设置适应度评价轮盘赌选择，用选择出的个体构成的种群替代旧的种群交叉变异适应度评价是否满足终止条件？输出结果结束对不可行解进行贪婪修复对不可行解进行贪婪修复5四．程序源代码%遗传算法求解旅行商问题%初始化a=[13042312;36391315;41772244;37121399;34881535;33261556;...32381229;41961044;4312790;2864570;19271970;25621756;...27881491;23811676;1332695;37151678;39182179;40612370;...37802212;36762578;15372838;27452931;34291908;35072376;...];%a：假定的24个城市的坐标n=100;%n：种群个数C=200;%C：停止代数m=2;%m：适配值淘汰加速指数,不宜太大Pc=0.9;%Pc：交叉概率Pm=0.2;%Pm：变异概率D=distance(a);%生成距离矩阵[R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pm);%返回值：最优路径R%总距离Rlength%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%D：距离矩阵%n：种群个数%a：31个城市的坐标，在初始化时设定%C:停止代数%m:适值淘汰加速指数,不宜太大(5以下)%Pc：交叉概率%Pm：变异概率%R：最短路径，Rlength：路径长度function[R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pm)[N,NN]=size(D);%(31*31)farm=zeros(n,N);%存储种群%随机生成初始种群，随机产生从1到N的N个初始值，例如,RANDPERM(6),可能结果为：[245613].fori=1:nfarm(i,:)=randperm(N);endR=farm(1,:);%一个随机解(个体)scatter(a(:,1),a(:,2),'x');%画出所有点,a(:,1):X坐标,a(:,2):Y坐标holdonpause(1)%画出随机解得路径图figure;plotaiwa(a,R);6holdonpause(1)%输出随机的解得路径和总距离disp('初始种群中的一个随机值:')Rlength=myLength(D,R)%计算各个个体总距离和适配置len=zeros(n,1);%存储路径长度fitness=zeros(n,1);%存储适配值counter=0;whilecounterCfori=1:nlen(i,1)=myLength(D,farm(i,:));%计算路径长度endminlen=min(len);rr=find(len==minlen);%返回的是在len中路径最短的路径坐标(i,1)R=farm(rr(1,1),:);%更新最短路径FARM=farm;%优胜劣汰，nn记录了复制的个数%选择K=23;[aa,bb]=size(FARM);FARM2=FARM;len2=len;[len]=sort(len);fori=1:aatt=find(len2==len(i,1));FARM(i,:)=FARM2(tt(1,1),:);endfori=1:Kj=aa+1-i;FARM(j,:)=FARM(i,:);end%交叉操作[aa,bb]=size(FARM);FARM2=FARM;fori=1:2:aaifPcrand&&iaa%交叉概率PcA=FARM(i,:);B=FARM(i+1,:);[A,B]=cross(A,B);%交叉算法采用部分匹配交叉FARM(i,:)=A;FARM(i+1,:)=B;end7end%变异FARM2=FARM;fori=1:aaifPm=randFARM(i,:)=mutate(FARM(i,:));endendFARM=[R;FARM];%将随机产生的n-aa个体加入从后面种群,将上次迭代的最优解从前面加入种群[aa,bb]=size(FARM);%保持种群规模为nifaanFARM=FARM(1:n,:);end%更新farmfarm=FARM;clearFARM%更新迭代次数counter=counter+1;end%结果输出Rlength=myLength(D,R)figureplotaiwa(a,R)%画图disp('迭代次数c');disp(C);disp('迭代后结果');Rlength=myLength(D,R)%结果输出%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%计算邻接矩阵%输入参数a是中国31个城市的坐标%输出参数D是无向图的赋权邻接矩阵functionD=distance(a)[c,d]=size(a);%此例中c=24,d=2D=zeros(c,c);%申请一个0阵fori=1:cforj=i:cbb=(a(i,1)-a(j,1)).^2+(a(i,2)-a(j,2)).^2;8D(i,j)=bb^(0.5);%计算第i个城市到j城市的距离D(j,i)=D(i,j);endend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%总路径lenfunctionlen=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));end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%绘制路径示意图R记录路径%a：假定的24个城市的坐标%R：最短路径functionplotaiwa(a,R)scatter(a(:,1),a(:,2),'x')holdonplot([a(R(1),1),a(R(24),1)],[a(R(1),2),a(R(24),2)])holdonfori=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)holdonend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%交叉算法采用部分匹配交叉function[a,b]=cross(a,b)L=length(a);ifL=10%确定交叉宽度W=9;elseif((L/10)-floor(L/10))=rand&&L10W=ceil(L/10)+8;elseW=floor(L/10)+8;endp=unidrnd(L-W+1);%随机选择交叉范围，从p到p+W9%UNIDRNDRandomarraysfromthediscreteuniformdistribution.%R=UNIDRND(N)returnsanarrayofrandomnumberschosenuniformly%fromtheset{1,2,3,...,N}.ThesizeofRisthesizeofN.%%R=UNIDRND(N,MM,NN,...)orR=UNIDRND(N,[MM,NN,...])returnsan%MM-by-NN-by-...array.fori=1:W%交叉x=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