TSP问题的遗传算法求解

TSP问题的遗传算法求解一、问题描述假设有一个旅行商人要拜访N个城市，要求他从一个城市出发，每个城市最多拜访一次，最后要回到出发的城市，保证所选择的路径长度最短。二、算法描述（一）算法简介遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。（摘自百度百科）。（二）遗传算子遗传算法中有选择算子、交叉算子和变异算子。选择算子用于在父代种群中选择进入下一代的个体。交叉算子用于对种群中的个体两两进行交叉，有Partial-MappedCrossover、OrderCrossover、Position-basedCrossover等交叉算子。变异算子用于对种群中的个体进行突变。（三）算法步骤描述遗传算法的基本运算过程如下：1.初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P2.个体评价：计算种群P中各个个体的适应度3.选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代4.交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉5.变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整6.经过选择、交叉、变异运算之后得到下一代群体P1。重复以上1-6，直到遗传代数为T，以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。三、求解说明（一）优化目标给定二维数据intpos用于存储各个城市的坐标，采用欧式距离代表城市之间的距离。利用遗传算法，找到不重复遍历所有城市的路径中，所走距离最短的路径。（二）选择算子选择算子采用轮盘赌选择，以每个个体的适应度为基础，为每个个体计算累积概率。个体1、2、3、4的个体适应度如上图所示。适应度计算规则：染色体代表的路径实际距离作为个体的适应度，如下（distencexy表示城市x到y的距离）染色体0213，适应度为distence02+distence21+distence13+distence30qa表示个体a的累积概率，如上图所示个体1、2、3、4的累积概率分别为0.14、0.53、0.69、1随机生成一个0到1的浮点数f，若qaf=qb，则个体b被选中。（三）交叉算子1.Partial-MappedCrossover（部分映射交叉）2.OrderCrossover（顺序交叉）3.Position-basedCrossover（基于位置的交叉）（四）变异算子变异算子随机进行多次，每次在个体基因序列中选择两个位置的基因进行交换。四、参考资料基于遗传算法求解TSP问题（JAVA）用遗传算法求解TSP问题五、源代码function ga_TSP% mainly amended by Chen Zhen, 20122016CityNum=35; %you chan choose 10, 35, 50, 75dislist,Clist=tsp(CityNum); inn=35; %gnmax=500; %最大代数pc=0.8; %交叉概率pm=0.8; %变异概率%产生初始种群s=zeros(inn,CityNum);for i=1:inn s(i,:)=randperm(CityNum);end,p=objf(s,dislist);gn=1;ymean=zeros(gn,1);ymax=zeros(gn,1);xmax=zeros(inn,CityNum);scnew=zeros(inn,CityNum);smnew=zeros(inn,CityNum);while gngnmax+1 for j=1:2:inn seln=sel(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); end s=smnew; %产生了新的种群 f,p=objf(s,dislist); %计算新种群的适应度 %记录当前代最好和平均的适应度 fmax,nmax=max(f); ymean(gn)=1000/mean(f); ymax(gn)=1000/fmax; %记录当前代的最佳个体 x=s(nmax,:); xmax(gn,:)=x; drawTSP(Clist,x,ymax(gn),gn,0); gn=gn+1;endmin_ymax,index=min(ymax);drawTSP(Clist,xmax(index,:),min_ymax,index,1);figure(2);plot(ymax,r); hold on;plot(ymean,b);grid;title(搜索过程);legend(最优解,平均解);fprintf(遗传算法得到的最短距离:%.2fn,min_ymax);fprintf(遗传算法得到的最短路线);disp(xmax(index,:);end%-%计算所有种群的适应度function f,p=objf(s,dislist)inn=size(s,1); %读取种群大小f=zeros(inn,1);for i=1:inn f(i)=CalDist(dislist,s(i,:); %计算函数值，即适应度endf=1000./f; %取距离倒数%根据个体的适应度计算其被选择的概率fsum=0;for i=1:inn fsum=fsum+f(i)15;% 让适应度越好的个体被选择概率越高endps=zeros(inn,1);for i=1:inn ps(i)=f(i)15/fsum;end%计算累积概率p=zeros(inn,1);p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;end%-%根据变异概率判断是否变异function pcc=pro(pc)test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n); end%-%“选择”操作function seln=sel(p)seln=zeros(2,1);%从种群中选择两个个体，最好不要两次选择同一个个体for i=1:2 r=rand; %产生一个随机数 prand=p-r; j=1; while prand(j)0 j=j+1; end seln(i)=j; %选中个体的序号 if i=2&j=seln(i-1) %若相同就再选一次 r=rand; %产生一个随机数 prand=p-r; j=1; while prand(j)0 j=j+1; end endendend%-%“交叉”操作function scro=cro(s,seln,pc)bn=size(s,2);pcc=pro(pc); %根据交叉概率决定是否进行交叉操作，1则是，0则否scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);if pcc=1 c1=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; for i=1:chb1 %似乎有问题 while find(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; end while find(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; end end for i=chb2+1:bn while find(scro(1,1:chb2)=scro(1,i) zhi=logical(scro(1,1:chb2)=scro(1,i); y=scro(2,zhi); scro(1,i)=y; end while find(scro(2,1:chb2)=scro(2,i) zhi=logical(scro(2,1:chb2)=scro(2,i); y=scro(1,zhi); scro(2,i)=y; end endendend%-%“变异”操作function snnew=mut(snew,pm)bn=size(snew,2);snnew=snew;pmm=pro(pm); %根据变异概率决定是否进行变异操作，1则是，0则否if pmm=1 c1=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);endend%-%城市位置坐标function DLn,cityn=tsp(n)DLn=zeros(n,n);if n=10 city10=0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414; 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634;%10 cities d=2.691 for i=1:10 for j=1:10 DLn(i,j)=(city10(i,1)-city10(j,1)2+(city10(i,2)-city10(j,2)2)0.5; end end cityn=city10;endif n=35 city30=116.41667 39.91667;121.43333 34.5;117.2 39.13333;114.1 22.2;113.23333 23.16667;113.51667 22.3114.06667 22.61667;120.2 30.26667;106.45 29.56667;120.33333 36.06667;118.1 24.46667;119.3 26.08333;103.73333 36.03333;106.71667 26.56667;113 28.21667;118.78333 32.05;115.9 28.68333;123.38333 41.8;112.53333 37.86667;104.06667 30.66667;91 29.6;87.68333 43.76667;102.73333 25.05;108.95 34.26667;101.75 36.56667;106.26667 38.46667;122.08333 46.06667;126.63333 45.75;125.35 43.88333;114.31667 30.51667;113.65 34.76667;114.48333 38.03333;109.5 18.2;110.35 20.01667;113.5 22.2;%35 cities d=423.741 by D B Fogel for i=1:35 for j=1:35 DLn(i,j)=(city35(i,1)-city35(j,1)2+(city35(i,2)-city35(j,2)2)0.5; end end cityn=city35;endif n=50 city50=31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67;%50 cities d=427.855 by D B Fogel for i=1:50 for j=1:50 DLn(i,j)=(city50(i,1)-city50(j,1)2+(city50(i,2)-city50(j,2)2)0.5; end end cityn=city50;endif n=75 city75=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30; 55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36; 20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50; 45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15; 44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56; 10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26;%75 cities d=549.18 by D B Fogel for i=1:75 for j=1:75 DLn(i,j)=(city75(i,1)-city75(j,1)2+(city75(i,2)-city75(j,2)2)0.5; end end cityn=city75;endend%-%适应度函数function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=DistanV+dislist(s(n),s(1);F=DistanV;end%-%画图function drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for