遗传算法编程求解TSP问题.DOC

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)，取比较小

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

4、6 509 4 7 1 10 8 2 9 5 3 6 5 409 511 7 5 10 1 3 4 8 9 2 6 6 416 504 4 7 1 10 8 2 9 5 3 6 7 403 505 6 10 9 8 1 7 2 5 3 4 8 416 513 4 7 1 10 8 2 9 5 3 6 9 445 506 10 4 6 5 8 9 2 3 7 1 10 414 509 4 8 7 1 10 5 3 2 9 6 11 453 495 4 8 7 1 6 5 2 3 9 10 12 385 495 7 1 10 2 3 4 8 9 5 6 13 440 518 5 7 9 2 10

5、3 6 8 4 1 14 421 500 4 8 7 1 10 6 2 3 9 5 15 422 499 4 8 10 1 7 5 2 3 9 6 16 421 512 4 8 7 1 10 6 2 3 9 5 17 421 508 4 8 7 1 10 6 2 3 9 5 18 376 504 7 6 10 2 3 4 8 9 1 5 19 421 493 4 8 7 1 10 6 2 3 9 5 20 421 491 4 8 7 1 10 6 2 3 9 5 21 421 490 4 8 7 1 10 6 2 3 9 5 22 421 485 4 8 7 1 10 6 2 3 9 5 23

6、 385 491 7 1 10 2 3 4 8 9 5 6 24 286 481 4 8 7 1 9 5 2 3 10 6 25 286 462 4 8 7 1 9 5 2 3 10 6 26 286 418 4 8 7 1 9 5 2 3 10 6 27 286 404 4 8 7 1 9 5 2 3 10 6 28 286 398 4 8 7 1 9 5 2 3 10 6 29 286 413 4 8 7 1 9 5 2 3 10 6 30 286 401 4 8 7 1 9 5 2 3 10 6 31 286 418 4 8 7 1 9 5 2 3 10 6 32 286 444 4 8

7、 7 1 9 5 2 3 10 6 33 286 421 4 8 7 1 9 5 2 3 10 6 34 286 409 4 8 7 1 9 5 2 3 10 6 35 286 398 4 8 7 1 9 5 2 3 10 6 36 257 416 4 8 7 1 9 5 2 6 10 3 37 286 411 4 8 7 1 9 5 2 3 10 6 38 286 375 4 8 7 1 9 5 2 3 10 6 39 257 392 4 8 7 1 9 5 2 6 10 3 40 257 380 4 8 7 1 9 5 2 6 10 3 41 257 370 4 8 7 1 9 5 2 6

8、 10 3 42 257 381 4 8 7 1 9 5 2 6 10 3 43 257 380 4 8 7 1 9 5 2 6 10 3 44 246 315 4 8 7 1 9 2 5 3 10 6 45 264 300 4 8 7 1 9 5 3 2 10 6 46 264 298 4 8 7 1 9 5 3 2 10 6 47 286 298 4 8 7 1 9 5 2 3 10 6 48 264 296 4 8 7 1 9 5 3 2 10 6 49 264 299 4 8 7 1 9 5 3 2 10 6 50 264 296 4 8 7 1 9 5 3 2 10 6 51 264

9、 324 4 8 7 1 9 5 3 2 10 6 52 264 305 4 8 7 1 9 5 3 2 10 6 53 264 322 4 8 7 1 9 5 3 2 10 6 54 264 331 4 8 7 1 9 5 3 2 10 6 55 264 310 4 8 7 1 9 5 3 2 10 6 56 264 294 4 8 7 1 9 5 3 2 10 6 57 264 300 4 8 7 1 9 5 3 2 10 6 58 264 309 4 8 7 1 9 5 3 2 10 6 59 264 297 4 8 7 1 9 5 3 2 10 6 60 264 316 4 8 7 1

10、 9 5 3 2 10 6 61 264 336 4 8 7 1 9 5 3 2 10 6 62 264 334 4 8 7 1 9 5 3 2 10 6 63 264 350 4 8 7 1 9 5 3 2 10 6 64 264 331 4 8 7 1 9 5 3 2 10 6 65 264 315 4 8 7 1 9 5 3 2 10 6 66 264 333 4 8 7 1 9 5 3 2 10 6 67 246 318 4 8 7 1 9 2 5 3 10 6 68 264 323 4 8 7 1 9 5 3 2 10 6 69 257 311 4 8 7 1 9 5 2 6 10

11、3 70 257 295 4 8 7 1 9 5 2 6 10 3 71 257 293 4 8 7 1 9 5 2 6 10 3 72 257 310 4 8 7 1 9 5 2 6 10 3 73 257 310 4 8 7 1 9 5 2 6 10 3 74 264 305 4 8 7 1 9 5 3 2 10 6 75 264 298 4 8 7 1 9 5 3 2 10 6 76 244 292 4 8 7 1 9 5 3 10 2 6 77 257 300 4 8 7 1 9 5 2 6 10 3 78 264 308 4 8 7 1 9 5 3 2 10 6 79 257 326

12、 4 8 7 1 9 5 2 6 10 3 80 264 307 4 8 7 1 9 5 3 2 10 6 81 264 297 4 8 7 1 9 5 3 2 10 6 82 264 285 4 8 7 1 9 5 3 2 10 6 83 264 304 4 8 7 1 9 5 3 2 10 6 84 264 304 4 8 7 1 9 5 3 2 10 6 85 264 316 4 8 7 1 9 5 3 2 10 6 86 264 320 4 8 7 1 9 5 3 2 10 6 87 264 300 4 8 7 1 9 5 3 2 10 6 88 263 300 4 8 7 1 9 5

13、 3 2 6 10 89 264 295 4 8 7 1 9 5 3 2 10 6 90 264 282 4 8 7 1 9 5 3 2 10 6 91 264 296 4 8 7 1 9 5 3 2 10 6 92 264 285 4 8 7 1 9 5 3 2 10 6 93 264 279 4 8 7 1 9 5 3 2 10 6 94 264 277 4 8 7 1 9 5 3 2 10 6 95 264 279 4 8 7 1 9 5 3 2 10 6 96 264 284 4 8 7 1 9 5 3 2 10 6 97 244 285 4 8 7 1 9 5 3 10 2 6 98

14、 263 301 4 8 7 1 9 5 3 2 6 10 99 264 292 4 8 7 1 9 5 3 2 10 6 264 269 4 8 7 1 9 5 3 2 10 6 264 267 4 8 7 1 9 5 3 2 10 6 244 267 4 8 7 1 9 5 3 10 2 6 264 280 4 8 7 1 9 5 3 2 10 6 264 280 4 8 7 1 9 5 3 2 10 6 264 274 4 8 7 1 9 5 3 2 10 6 263 294 4 8 7 1 9 5 3 2 6 10 246 283 4 8 7 1 9 2 5 3 10 6 246 28

15、1 4 8 7 1 9 2 5 3 10 6 264 279 4 8 7 1 9 5 3 2 10 6 257 285 4 8 7 1 3 5 9 2 10 6 264 303 4 8 7 1 9 5 3 2 10 6 264 300 4 8 7 1 9 5 3 2 10 6 257 292 4 8 7 1 3 5 9 2 10 6 257 297 4 8 7 1 3 5 9 2 10 6 257 290 4 8 7 1 3 5 9 2 10 6 257 288 4 8 7 1 3 5 9 2 10 6 257 294 4 8 7 1 3 5 9 2 10 6 257 300 4 8 7 1

16、3 5 9 2 10 6 257 309 4 8 7 1 3 5 9 2 10 6 257 298 4 8 7 1 3 5 9 2 10 6 257 308 4 8 7 1 3 5 9 2 10 6 264 324 4 8 7 1 9 5 3 2 10 6 264 305 4 8 7 1 9 5 3 2 10 6 264 323 4 8 7 1 9 5 3 2 10 6 264 330 4 8 7 1 9 5 3 2 10 6 263 315 4 8 7 1 9 5 3 2 6 10 264 323 4 8 7 1 9 5 3 2 10 6 264 300 4 8 7 1 9 5 3 2 10

17、 6 最短路径为 : 244 最优解为 : 4 8 7 1 9 5 3 10 2 6 代数： 76 该问题采用禁忌搜索算法得到的最优解为 229。可见遗传算法虽然是很好的方法，但是如果设计不好则不一定能够收敛到全局最优值，有文章也表明简单遗传算法是不收敛的。遗传算法的改进方法有很多，但是究竟使用什么方法则需要具体问题具体分析，这正是遗传算法的困难之处，虽然遗传算法上手很快，但是要想设计出好的算法却需要更多的努力。 本程序文件名为： SGA_TSP.m 源程序如下： function SGA_TSP() %旅行商问题的遗传算法解法 disp(此次计算的距离矩阵如下 ) %此矩阵为一个演示矩阵，上

18、面的代码产生了一个随机的距离矩阵，但又被此矩阵暂时覆盖 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 90 82 10 19 80 41 13 89 24

19、 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(NIND,gen_len); for i=1:NIND a indexa=sort(Chrom(i,:);%排序值是不会重复的 Chrom(i,:)=indexa; end %计算目

20、标函数值 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);%全局最优值 most_min_index=1; %种群平均值 ma(1,3)=round(mean(Obj); ma(1,4:3+gen_len)=Chrom(index

21、,:); for gen=1:Maxgen %终止判断 %最近 30 代的最优值都比前面的最优值大则结束 if gen29+most_min_index if length(n)29 break; end end %计算适应度 mmm=max(Obj)+1; Obj=mmm-Obj+1; sumObj=sum(Obj);%所有个体的目标函数值之和 fitness=Obj/sumObj;%每个个体的选择概率 fitness2=cumsum(fitness);%累计概率 %轮盘选择 tempChrom=Chrom;%储存一个原始的个体值 父代 index=1; for k=1:NIND for j

22、=1:NIND if randObj(temindex) Chrom(temindex,:)=temp2; else Chrom(temindex,:)=temp1; end n1=0; end end end %Chrom %检查交叉运算是否正确 ,解是否可行解 %变异运算 实际上是交换位置 for i=1:NIND for j=1:gen_len if randmutate_probability value=round(rand*(gen_len-1)+1; tt=Chrom(i,value); Chrom(i,value)=Chrom(i,j); Chrom(i,j)=tt; end

23、end 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(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,:); mos

24、t_min index=min(ma(:,2); most_min_index=index; end disp(计算过程中的最优值记录 ) disp(代数 最优值 平均值 |最优解 -) 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,dist

25、ance) %TSP 的一个启发式交叉算法函数 %该算法以一定概率计算出一个比父代好的子代 %算法思路： 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,F2 不变 , %将 F

26、1 的后 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 7

27、0 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; %father1=10 4 3 2 9 7 8 1 5 6; %father2=9 1 3 5 2 6 7 8 4 10; len=length(father1); pos=round(rand*(len-1)+1;%交叉点 %pos=3; pos2=find(father2=father1(pos); %以下完成第一次旋转移动 tem1=father1(pos:len)

28、; tem2=father1(1:pos-1); father1=tem1 tem2; tem1=father2(pos2:len); tem2=father2(1:pos2-1); father2=tem1 tem2; %一下完成剩下的旋转移动生成一个后代 for i=2:len if distance(father1(i-1),father1(i)=distance(father2(i-1),father2(i) pos2=find(father2=father1(i); tem0=father2(1:i-1); tem1=father2(pos2:len); tem2=father2(i:pos2-1); father2=tem0 tem1 tem2; else pos2=find(father1=father2(i); tem0=father1(1:i-1); tem1=father1(pos2:len); tem2=father1(i:pos2-1); father1=tem0 tem1 tem2; end end child=father1;