遗传算法编程求解TSP问题

1、遗传算法编程求解TSP问题摘要 本文利用基本遗传算法的思路寻找双峰或多峰函数的最大值，选择仍然采用轮盘选择方法；交叉算法采用一个启发式交叉算法，交叉位置随机，该算法以一定的概率生成一个比父代好的解，交叉概率取0.1；变异概率0.005。经多次运行，求得最优值。停止法则为循环最大遗传代数为止，另外如果30代解没有改进则停止。的编程环境为Matlab6.5。关键字 遗传算法 TSP遗传算法是一种通用性非常强，计算性能非常好的算法，解决TSP问题却存在很多问题，主要问题是解的可行性问题，在交叉，变异操作过程中，可能产生不可行的解，因此交叉和变异算子的设计是本程序的关键。本程序中交叉算子采用一个启发式

2、交叉算法，该算法以一定概率计算出一个比父代好的子代算法思路：设父代F1：10 4 3 2 9 7 8 1 5 6 F2：9 1 3 5 2 6 7 8 4 10 。随机确定交叉点，如4。查找F1中第四位为2。将F1向左旋转3位，使第四位在成为第一位，得到F1：2 9 7 8 1 5 6 10 4 3。在F2中找到2所在位置，进行类似旋转，使2成为第一位，得到 F2：2 6 7 8 4 10 9 1 3 5。然后比较两个模式中第一位与第二位的距离：disance(2-9)，disance(2-6)，取比较小的如2-6所在父代F2不变，另外一个为，将F1进行旋转操作，使6在第2位，得到F2:：2

3、6 10 4 3 9 7 8 1 5。这样就形成了2 6 *的模式，如此往复，直到最后一位。另外将这个交叉算子的效率和普通单点交叉算子的效率进行了比较，发现该方法确实使得算法搜索能力增强。多次运行程序，得到一个相对好的解。以下是得到最优解的数据：代数最优值平均值-最 优 解-126250857192648103241451059281374106338551271102348956441650947110829536540951175101348926641650447110829536740350561098172534841651347110829536944550610465892371

4、104145094871105329611453495487165239101238549571102348956134405185792103684114421500487110623951542249948101752396164215124871106239517421508487110623951837650476102348915194214934871106239520421491487110623952142149048711062395224214854871106239523385491711023489562428648148719523106252864624871952

5、310626286418487195231062728640448719523106282863984871952310629286413487195231063028640148719523106312864184871952310632286444487195231063328642148719523106342864094871952310635286398487195231063625741648719526103372864114871952310638286375487195231063925739248719526103402573804871952610341257370487

6、195261034225738148719526103432573804871952610344246315487192531064526430048719532106462642984871953210647286298487195231064826429648719532106492642994871953210650264296487195321065126432448719532106522643054871953210653264322487195321065426433148719532106552643104871953210656264294487195321065726430

7、048719532106582643094871953210659264297487195321066026431648719532106612643364871953210662264334487195321066326435048719532106642643314871953210665264315487195321066626433348719532106672463184871925310668264323487195321066925731148719526103702572954871952610371257293487195261037225731048719526103732

8、573104871952610374264305487195321067526429848719532106762442924871953102677257300487195261037826430848719532106792573264871952610380264307487195321068126429748719532106822642854871953210683264304487195321068426430448719532106852643164871953210686264320487195321068726430048719532106882633004871953261

9、089264295487195321069026428248719532106912642964871953210692264285487195321069326427948719532106942642774871953210695264279487195321069626428448719532106972442854871953102698263301487195326109926429248719532106264269487195321062642674871953210624426748719531026264280487195321062642804871953210626427

10、448719532106263294487195326102462834871925310624628148719253106264279487195321062572854871359210626430348719532106264300487195321062572924871359210625729748713592106257290487135921062572884871359210625729448713592106257300487135921062573094871359210625729848713592106257308487135921062643244871953210

11、6264305487195321062643234871953210626433048719532106263315487195326102643234871953210626430048719532106最短路径为: 244最优解为: 4 8 7 1 9 5 3 10 2 6代数： 76该问题采用禁忌搜索算法得到的最优解为229。可见遗传算法虽然是很好的方法，但是如果设计不好则不一定能够收敛到全局最优值，有文章也表明简单遗传算法是不收敛的。遗传算法的改进方法有很多，但是究竟使用什么方法则需要具体问题具体分析，这正是遗传算法的困难之处，虽然遗传算法上手很快，但是要想设计出好的算法却需要更多的努

12、力。本程序文件名为：SGA_TSP.m源程序如下：function SGA_TSP()%旅行商问题的遗传算法解法disp('此次计算的距离矩阵如下')%此矩阵为一个演示矩阵，上面的代码产生了一个随机的距离矩阵，但又被此矩阵暂时覆盖distance= Inf 76 45 81 34 99 12 70 10 21 76 Inf 61 72 2 9 100 84 19 5 45 61 Inf 44 15 96 83 86 80 40 81 72 44 Inf 98 21 53 46 41 16 34 2 15 98 Inf 23 8 99 13 57 99 9 96 21 23 In

13、f 70 87 89 8 12 100 83 53 8 70 Inf 73 24 84 70 84 86 46 99 87 73 Inf 90 82 10 19 80 41 13 89 24 90 Inf 41 21 5 40 16 57 8 84 82 41 Inf; %输出距离矩阵 %遗传算法开始gen_len=guimo; %基因长度cross_probability=0.01;%交叉概率mutate_probability=0.005;%变异概率Maxgen=300; %最大遗传代数NIND=gen_len*10; %个体数目%生成初始种群 关键是生成可行解Chrom=rand(NIN

14、D,gen_len);for i=1:NIND a indexa=sort(Chrom(i,:);%排序值是不会重复的 Chrom(i,:)=indexa; end%计算目标函数值Obj(1:NIND)=0;for j=1:NIND for i=1:9 Obj(j)=Obj(j)+distance(Chrom(j,i),Chrom(j,i+1); end Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1);end%记录每一代的最小值,平均值ma(1,1)=1;ma(1,2) index=min(Obj);most_min=ma(1,2);%全局最优值mo

15、st_min_index=1;%种群平均值ma(1,3)=round(mean(Obj);ma(1,4:3+gen_len)=Chrom(index,:);for gen=1:Maxgen %终止判断 %最近30代的最优值都比前面的最优值大则结束 if gen>29+most_min_index & gen>100 m n=find(ma(gen-30:gen,2)>most_min); if length(n)>29 break; end end %计算适应度 mmm=max(Obj)+1; Obj=mmm-Obj+1; sumObj=sum(Obj);%所有

16、个体的目标函数值之和 fitness=Obj/sumObj;%每个个体的选择概率 fitness2=cumsum(fitness);%累计概率 %轮盘选择 tempChrom=Chrom;%储存一个原始的个体值 父代 index=1; for k=1:NIND for j=1:NIND if rand<fitness2(j) Chrom(index,:)=tempChrom(j,:); index=index+1; break; end end end %交叉运算 关键是如何产生可行解 n1=0; for i=1:NIND if rand(1)<cross_probability

17、if n1=0 n1=1; temindex=i;%纪录第一个交叉个体 continue; else %选够两个个体则交叉 temp1=Chrom(temindex,:);%记录父代1 temp2=Chrom(i,:);%记录父代2 Chrom(i,:)=tsp_cross_func1(temp1,temp1,distance);%TSP的一个启发式交叉算法函数产生一个子代 %另一个子代从父代中继承一个较好的 if Obj(i)>Obj(temindex) Chrom(temindex,:)=temp2; else Chrom(temindex,:)=temp1; end n1=0; e

18、nd end end %Chrom %检查交叉运算是否正确,解是否可行解 %变异运算 实际上是交换位置 for i=1:NIND for j=1:gen_len if rand<mutate_probability value=round(rand*(gen_len-1)+1; tt=Chrom(i,value); Chrom(i,value)=Chrom(i,j); Chrom(i,j)=tt; end end end %计算目标函数值 Obj(1:NIND)=0; for j=1:NIND for i=1:9 Obj(j)=Obj(j)+distance(Chrom(j,i),Chr

19、om(j,i+1); end Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1); end %记录每一代的最小值,平均值 ma(gen+1,1)=gen+1; ma(gen+1,2) index=min(Obj); %各代种群平均值 ma(gen+1,3)=round(mean(Obj); ma(gen+1,4:3+gen_len)=Chrom(index,:); most_min index=min(ma(:,2); most_min_index=index;enddisp('计算过程中的最优值记录')disp('代数 最优值

20、平均值 |最优解-')disp(num2str(ma)best_Y =min(ma(:,2);str='最短路径为: ' num2str(best_Y) ;disp(str)X=ma(index,4:3+gen_len);str='最优解为: ' num2str(X) '代数： ' num2str(index);disp(str)function child=tsp_cross_func1(father1,father2,distance)%TSP的一个启发式交叉算法函数%该算法以一定概率计算出一个比父代好的子代%算法思路：F1：10 4

21、 3 2 9 7 8 1 5 6 F2：9 1 3 5 2 6 7 8 4 10 。%随机确定交叉点，如4,F1中第四位为2。%将F1向左旋转3位，使第四位在成为第一位 F1：2 9 7 8 1 5 6 10 4 3。%在F2中找到2所在位置，进行旋转2成为第一个 F2：2 6 7 8 4 10 9 1 3 5。%然后比较disance(2-9) disance(2-6),取比较小的如2-6所在父代F2,F2不变,%将F1的后9位旋转,使6在第2位 成为F2: 2 6 10 4 3 9 7 8 1 5%这样就形成了2 6 *的模式,如此往复,%演示的例子%distance= Inf 76 45 81 34 99 12 70 10 21% 76 Inf 61 72 2 9 100 84 19 5% 45 61 Inf 44 15 96 83 86 80 40 % 81 72 44 Inf 98 21 53 46 41 16% 34 2 15 98 Inf 23 8 99 13 57% 99 9 96 21 23 Inf 70 87 89 8% 12 100 83 53 8 70 Inf 73 24 84% 70 84 86 46 99 87 73 Inf 9