实验六 遗传算法求解TSP问题
一、实验目的
? 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。
二、实验内容
1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。
2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。
1 / 9
三、遗传算法求解TSP问题的流程图
开始初始化种群（随机产生城市坐标）确定种群规模、迭代次数、个体选择方式、交叉概率、变异概率等计算染色体适应度值（城市之间的欧氏距离）YES按某个选择概率选择个体个体交叉个体变异P<迭代总次数NO输入适应度最高的解结束
四、遗传算法求解不同规模的TSP问题的算法性能
（1） 遗传算法执行方式说明：
? 适应度值计算方法：当前路线的路径长度
2 / 9
? 个体选择概率分配方法：适应度比例方法 ? 选择个体方法：轮盘赌选择 ? 交叉类型：PMX交叉 ? 变异类型: 两点互换变异 （2）实验模拟结果：
城市个数 时间（ms） 5 16925 10 16630 15 18833 20 22596 25 24159 30 30289 35 35239 40 38608 45 40032 50 43757 55 47746 60 58143 65 59942 70 64361 75 71417
图1-1
（3）分析
由图1-1可知，遗传算法执行时间随着TSP问题规模的增大而增大，并且大致为线性增长。
五、不同参数下的计算结果对比
（1）种群规模对算法结果的影响
3 / 9
实验次数：10 最大迭代步数:100 交叉概率：0.85 变异概率：0.15
表1-1 种群规模 适应度值 最优路径 10 25.264 4-5-8-7-6-3-1-0-9-2 20 26.3428 2-9-1-0-3-6-7-5-8-4 30 25.1652 1-3-6-7-5-8-4-2-9-0 50 25.1652 0-1-3-6-7-5-8-4-2-9 80 25.1652 9-0-1-3-6-7-5-8-4-2 100 25.1652 1-0-9-2-4-8-5-7-6-3 150 25.1652 5-8-4-2-9-0-1-3-6-7 200 25.1652 1-3-6-7-5-8-4-2-9-0 250 25.1652 3-1-0-9-2-4-8-5-7-6 300 25.1652 5-8-4-2-9-0-1-3-6-7 如表1-1所示，显然最短路径为25.1652m,最优路径为1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20时，并没有找到最优解。
（2）交叉概率对算法结果的影响 实验次数：15 种群规模：25 最大迭代步数:100 变异概率：0.15 实验结果：
表1-2 交叉概率 最好适应度 最差适应度 平均适应度 0.001 28.0447 36.6567 32.6002 0.01 27.0935 34.9943 32.1495 0.1 28.0447 35.3033 31.9372 0.15 28.0447 34.1175 31.2183 0.2 28.7108 33.9512 30.9035 0.25 28.0447 35.1623 30.7456 0.3 27.0935 31.9941 29.9428 0.35 27.0935 32.8085 30.9945 0.4 27.0935 32.5313 30.1534 0.45 27.0935 33.2014 30.1757 0.5 28.0934 33.6307 30.9026 0.55 27.0935 33.5233 29.1304 0.6 27.0935 33.2512 30.7836 0.65 28.0447 33.7003 30.9371 0.7 27.0935 32.0927 29.9502 4 / 9
最优解 运行时间 9-2-6-0-5-4-8-7-3-1 310 7-8-3-1-9-2-6-0-5-4 260 7-3-1-9-2-6-0-5-4-8 300 0-5-4-8-7-3-1-9-2-6 270 3-1-9-2-6-5-0-4-7-8 280 1-3-7-8-4-5-0-6-2-9 260 8-3-1-9-2-6-0-5-4-7 290 9-1-3-8-7-4-5-0-6-2 270 1-3-8-7-4-5-0-6-2-9 279 8-3-1-9-2-6-0-5-4-7 456 5-0-2-6-9-1-3-8-7-4 663 1-9-2-6-0-5-4-7-8-3 520 3-1-9-2-6-0-5-4-7-8 546 5-4-8-7-3-1-9-2-6-0 596 9-1-3-8-7-4-5-0-6-2 571 0.75 28.0447 32.4488 30.3699 0-5-4-8-7-3-1-9-2-6 0.8 27.0935 32.1551 29.9382 7-4-5-0-6-2-9-1-3-8 0.85 27.0935 34.5399 30.3594 5-0-6-2-9-1-3-8-7-4 0.9 27.0935 32.6273 30.69 6-0-5-4-7-8-3-1-9-2 0.95 27.0935 32.4672 29.919 6-2-9-1-3-8-7-4-5-0 （注:红色表示非最优解） 在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。
（3）变异概率对算法结果的影响
559 358 360 375 476 实验次数：10 种群规模：25 最大迭代步数:100 交叉概率：0.85 实验结果：
表1-3 变异概率 最好适应度 最差适应度 平均适应度 最优解 运行时间 0.001 29.4717 34.732 32.4911 0-6-2-1-9-3-8-7-4-5 245 0.01 29.0446 34.6591 32.3714 8-4-5-0-2-6-9-1-3-7 274 0.1 28.0934 34.011 30.9417 5-0-2-6-9-1-3-8-7-4 250 0.15 27.0935 32.093 30.2568 6-0-5-4-7-8-3-1-9-2 246 0.2 27.0935 32.2349 30.3144 8-7-4-5-0-6-2-9-1-3 282 0.25 27.0935 32.718 30.1572 4-5-0-6-2-9-1-3-8-7 245 0.3 27.0935 32.4488 30.2854 0-5-4-7-8-3-1-9-2-6 252 0.35 27.0935 33.3167 30.7748 1-3-8-7-4-5-0-6-2-9 266 0.4 29.0446 34.3705 31.3041 2-0-5-4-8-7-3-1-9-6 362 0.45 27.0935 31.374 29.6816 2-6-0-5-4-7-8-3-1-9 438 0.5 27.0935 32.3752 30.2211 2-9-1-3-8-7-4-5-0-6 431 0.55 27.0935 33.3819 30.6623 1-3-8-7-4-5-0-6-2-9 492 0.6 28.0934 33.2512 30.36 1-3-8-7-4-5-0-2-6-9 417 0.65 27.0935 32.7491 30.0201 3-1-9-2-6-0-5-4-7-8 434 0.7 28.7108 32.4238 30.785 1-3-8-7-4-0-5-6-2-9 432 0.75 27.0935 31.8928 30.2451 1-9-2-6-0-5-4-7-8-3 475 0.8 28.0934 31.6135 30.3471 9-1-3-8-7-4-5-0-2-6 327 0.85 29.662 33.2392 31.1585 2-9-1-3-7-8-4-0-5-6 314 0.9 28.0447 32.0387 30.4152 0-5-4-8-7-3-1-9-2-6 396 0.95 28.0447 31.3036 30.0067 9-1-3-7-8-4-5-0-6-2 436 又表1-3可知，当变异概率过大或过低都将导致无法得到最优解。 注：（2）（3）的实验数据与（1）的实验数据不同，详见附录。
5 / 9
遗传算法求解TSP问题
