遗传算法解决旅行商问题
作为NP难的经典问题，旅行商问题有多种算法可以解决。
我学习的过程中，首先看到了模拟退火算法解决旅行商问题的过程，模拟退火算法可以保证100%的找到全局最小值。
在我研究遗传算法的过程中，我突然想试一下怎样用遗传算法中选择、交叉的变异的思路来解决这个问题。
以52城的题目为例
使用遗传算法进行解题
首先考虑如何初始化种群，我选择用randperm（52）直接生成一个1到52的随机序列，作为我的一个个体。种群的规模为200.
然后考虑遗传算法的适应值怎么确定，这里取每一个个体的总路径的倒数作为适应度。
我用下面这段程序求目标函数和适应度，并用模拟退火方法求出的最优解代入，以确定代码是正确的。
clc;clear all;w=[565 575;25 185;345 750;945 685;845 655;880 660;25 230;525 1000;580 1175;650 1130;1605 620;1220 580;1465 200;1530 5;845 680;725 370;145 665;415 635;510 875;560 365;300 465;520 585;480 415;835 625;975 580;1215 245;1320 315; %坐标输入1250 400;660 180;410 250;420 555;575 665;1150 1160;700 580;685 595;685 610;770 610;795 645;720 635;760 650;475 960;95 260;875 920;700 500;555 815;830 485;1170 65;830 610;605 625;595 360;1340 725;1740 245];a=w(:,1); %x坐标b=w(:,2); %y坐标ctamount=size(w,1);d=zeros(ctamount,ctamount);for i=1:ctamountfor j=1:ctamountd(i,j)=sqrt((a(i)-a(j)).^2+(b(i)-b(j)).^2);%求出两城之间的距离矩阵endenda=[17 21 42 7 2 30 23 20 50 29 16 46 44 34 35 36 39 ...40 37 38 48 24 5 15 6 4 25 12 28 27 26 47 13 14 ...52 11 51 33 43 10 9 8 41 19 45 32 49 1 22 31 18 3];e=0;for i=1:ctamount-1e=e+d(a(i),a(i+1));endf=e+d(a(ctamount),a(1)); %最后求解出的结果是7554，和模拟退火的结果一致，说明目标函数的求解方法是正确的syd=1/f;
当然，重要的部分是如何产生新种群的过程
选择方式
我的思路是对于规模为200的种群，每次选四个个体，其中最优的被选择，最差的被淘汰，且最优的替代最差的。
交叉方式
交叉方式我是参考这篇文章：
/woaixuexihhh/article/details/83826256
这是二交叉的方法，代码也比较好实现。
变异方式
变异方式也是参考以上链接，随机产生两个变异位，将两变异位之间的序列进行倒序。
代码如下：（求距离矩阵的代码在最上面，就不重复啦）
popsize=200;sydmax=0;xbest=ones(1,ctamount); %初始化genmax=100000;generation=1;for k=1:popsizee=0;U(k,:)=randperm(ctamount); %产生第一组规模为200 的种群for i=1:ctamount-1e=e+d(U(k,i),U(k,i+1)); endf=e+d(U(k,ctamount),U(1));syd=1/f;W(k)=syd;end[sydmax,plan]=max(W) %将这个种群的适应度和最优解保存下来xbest=U(plan,:);
下面开始迭代啦
while generation<=genmaxfor k=1:4:popsize-3%每次取四个个体M=W(k:k+3);[maxom,maxnum]=max(M);[minom,minnum]=min(M);Umax=U(maxnum+k-1,:);%最大的那个直接保留Umin=U(minnum+k-1,:);%最优的代替最差的；M(maxnum)=0;M(minnum)=0;[maxom2,maxnum2]=max(M);M(maxnum2)=0;[minom2,minnum2]=max(M); %代码到现在其实是在对四个适应度值进行排序，然后把适应度值对应的W矩阵的索引取出注意：取M的索引就错啦，因为M的索引只能是1到4long=zeros(2,ctamount);long(1,:)=U(maxnum2+k-1,:); %适应度值居中的两个个体进行交叉long(2,:)=U(minnum2+k-1,:); %用long矩阵来表示需要进行交叉的两个个体size(long);u=sj(ctamount); %随机产生两个介于0，52的不同的数，作为交叉点，sj函数代码附在后面short=zeros(2,max(u)-min(u)+1);short(1,:)=long(1,min(u):max(u));short(2,:)=long(2,min(u):max(u)); %将原个体介于交叉点之间的序列保存在short矩阵里size(short);for i=min(u):max(u)long(:,i)=0; %先把long交叉点之间的序列清零endtep=long(1,:);long(1,:)=long(2,:); %除中间字串之外的对位交换long(2,:)=tep;for j=1:ctamountpanduan=long(1,j);while ismember(panduan,short(2,:))tep=find(short(2,:)==long(1,j));%然后把short矩阵里面的数交叉赋值给long的全0段long(1,j)=short(1,tep);endendfor j=1:ctamountwhile ismember(long(2,j),short(1,:)) % 用ismember函数来保证交叉之后的数不与中间序列重复tep=find(short(1,:)==long(2,j)); % 如果重复就把另一个个体中与重复位对应的数值取过来long(1,j)=short(2,tep);endendlong(1,min(u):max(u))=short(2,:);long(2,min(u):max(u))=short(1,:); %产生交叉后的群体U(k,:)=bianyi(Umax);U(k+3,:)=bianyi(Umax);U(k+1,:)=bianyi(long(1,:)); %每个个体都有一定概率的变异率，所以小于变异概率的就认为该个体发生变异。U(k+2,:)=bianyi(long(2,:)); %bianyi函数附在后面end for m=1:popsizee=0;for i=1:ctamount-1e=e+d(U(m,i),U(m,i+1));endf=e+d(U(m,ctamount),U(1));syd=1/f;W(m)=syd;end[sydnew,plannew]=max(W);if sydnew>sydmaxsydmax=sydnewxbest=U(plannew,:) %最后就是把每次迭代中的最优值保存下来与当前最优值作比较。endsydzhi(generation)=sydmax;generation=generation+1;endpathleast=1/sydmaxx=1:genmax; %我这里把迭代过程中最优值得变化做了一个图plot(x,sydzhi,'x')
下面是子函数
1.变异函数
function v=bianyi(Q)ctamount=size(Q,2);pby=0.1;r=rand;if r<pbyu=sjby(ctamount);%产生两个随机变异位tep=Q(min(u):max(u));Q(min(u):max(u))=fliplr(tep);endv=Q;
2.随机产生两个交叉点，且非头尾两点
function u=sj(ctamount)count =1;f=[1,ctamount];while count<=2u(count)=ceil(rand*ctamount);if ~ismember(u(count),f)count=count+1;endend
3.随机产生两个变异位函数
function u=sjby(ctamount)count =1;f=[1,ctamount];while count<=2u(count)=ceil(rand*ctamount);if ~ismember(u(count),f)count=count+1;endend
运行以上代码得结果为：在迭代19700次的时候找到最优。迭代次数还是挺多的，这说明选择的产生新种群的办法还有待优化。
最终求出来52城的最小路径为：7846.8。
对52城的问题模拟退火算法为7544.4，还有更小的解7542。
说明这个结果还有待优化。
接下来调整参数，因为种群规模一般选0-100，我选的200明显太大了，种群规模大容易造成结果难收敛且浪费。
最后选的种群数量是80 ，结果为7670 。
但是就先这样吧，我去啃别的算法啦
如果觉得《遗传算法解决旅行商（TSP）问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
