2023年遗传算法求解TSP问题实验报告.docx

《2023年遗传算法求解TSP问题实验报告.docx》由会员分享，可在线阅读，更多相关《2023年遗传算法求解TSP问题实验报告.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能实验报告实验六遗传算法实验II一、实验目的：熟悉和掌握遗传算法的原理、流程和编码策略，并运用遗传求解函数优化问题,理解求 解TSP问题的流程并测试重要参数对结果的影响。二、实验原理：旅行商问题，即TS P问题(Tr a ve 1 i n g S a le s man Problem)是数学领域中著名问 题之。假设有一个旅行商人要拜访n个城市，他必须选择所要走的途径,路经的限制是每个 城市只能拜访次，并且最后要回到本来发的城市。途径的选择目的是规定得的途径路程 为所有途径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算 复杂性。因此,任何能使该问题的求解得以简化

2、的方法，都将受到高度的评价和关注。遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代 表,把问题的解用染色体代表(在计算机里用二进制码表达)，从而得到一个由具有不同染色 体的个体组成的群体。这个群体在问题特定的环境里生存竞争,适者有最佳的机会生存和产 生后代。后代随机化地继承了父代的最佳特性，并也在生存环境的控制支配下继续这一过程。 群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得 到问题最优的解。规定运用遗传算法求解TSP问题的最短途径。三、实验内容:1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传 算

3、法求解不同规模T S P问题的算法性能。2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响.3、增长1种变异策略和1种个体选择概率分派策略，比较求解同一 TSP问题时不同变异策 略及不同个体选择分派策略对算法结果的影响。4、上交源代码。四、实验报告规定：1、画出遗传算法求解TSP问题的流程图。开始Y2、 分析遗传算法求解不同规模的TSP问题的算法性能。规模越大，算法的性能越差，所用时间越长。3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。(1)种群规模对算法结果的影响X01.13. 537844. 592y1. 13245. 1844. 59

4、2实验次数：10最大迭代步数:10 0交叉概率：o. 85变异概率：0.15种群规模平均适应度值最优途径1()2 5.2644 5 8-7 6- 3 - 1 - 0 -9-22026.3 4 282-9-1-0-3-6-7-5-8-4302 5.165 21 .3-6-7-5-8-4-2-9-0502 5. 1 6520-1-3-6- 7-5-8-4-2-98 025.16529-0-1-3-6-7-5-8-4-210025.165 21-0-9-2-4-8-5-7-6-31502 5.1 6 525-8-4-2-9-0-1-3-6-72 002 5.165 21-3-6 -7-5- 8-4-

5、 2-9-025 02 5.165 23-1-0-9-2-4- 8 5 7 630025 . 16525-8- 4 -2-9-0-1 3 -6- 7如表所示，显然最短途径为25.1652m,最优途径为1 - 0-9-1 367-5-8-42或31092485 76,注意到这是一圈,顺时针或者逆时针都可以。当种群规模为1 0,20时，并没有找到最优解。因此并不是种群规模越小越好。(2)交叉概率对算法结果的影响X91 . 13 . 53.7844.5325y1 . 13145. 1318.591实验次数:1 5种群规模:25最大迭代步数：1 00变异概率：0.1 5实验结果：交叉概率最佳适应度最差

6、适应度平均适应度最优解0. 00128. 044736.65673 2.60 0 29-2-6- 0-5 -4-8-7-3-10.0127. 0 9 3534. 994332. 149 57-8-3-1-9-2-6-0-5-40. 12 8. 044 735. 303 331.93727 3 - 1 -9- 2 -6-0 5-4-80. 1528. 04 4 734.117531.2 1 830-5-4-8-7- 3-1- 9-260 . 22 8.7 1083 3.95 1 230. 9 0 353 T-9-2-6-5-04-7-80.2528. 044735. 16233 0.74 561

7、-3-7-8- 4 -5-0 -6-2-90. 327.0 9 353 1.994129. 94 2 88-3-1-9-2-6- 0-5-4-70. 352 7 . 09 3 53 2 . 808530. 99459- 1 -3- 8-7-4-5-0-6-20.42 7. 0 9 3532.5 3 1330.15341-3-8-7-4 -5- 0-6-2-90. 4 527. 0 93533. 202 33 0. 1 7578-3- 1 926-0 5-4 70. 528. 0 9 3433. 63073 0 . 9 0 2 6502-6-9 138 7-40. 5 527 . 0 9 3 5

8、33. 523 32 9. 13 0 41-9-2-6-0-5 - 4-7-8- 30 . 62 7 . 09 3 533.2 5 1 230. 783 63-1-9-2-6-0-5-4-7-80. 652 8.04 473 3 . 700330. 9 3 7 15- 4 - 8 - 7-3-1-9-2-6-00. 727. 0 93 532. 0 92729. 950 29-1-3-8-7-4-5-0-6-20. 7528. 044732. 448 83 0.3 6 9905-4 - 8-7 3-（注:红色表达非最优解）1-9-2-60.827. 093532. 15 5 12 9.9382

9、7-4-5- 0 6 -2- 9 - 1-3-80. 8527. 093534. 53993 0. 35945-0-6-2- 9-1-3-8-7-40. 927. 093532. 62 7 330. 696-0 5-4- 7 -8-31-9-20.9527. 0 9 3532. 4 6 7 229 . 9 196-2-9-1-3-8-7 -4 50在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。（3）变异概率对算法结果的影响实验次数：10X91. 13. 53. 57844. 532y1. 13145. 1318.591种群规模：2 5最大迭代步数:100交叉概率：0.8 5 实验

10、结果：变异概率最佳适应度最差适应度平均适应度最优解0.00 12 9 . 471734.73 23 2.49 1 10-6- 2-1 938- 7-4-50.0129. 044 634. 6 59132.3 7 1484-5- 0 - 2 - 6 - 9-1-3-70. 128. 0 9 3434.01130. 941 75-0- 2 -6-9-1 - 3-8-7-40. 1527. 0 93 532. 0 9 330. 2 5 686-0-5-4-7-8- 3-1 -9-20. 22 7.093 532. 2 34 930. 3 1448 7-4-5-0-6- 2-9-1-30.252 7.

11、09 3 532.71830 . 1 57 24-5-0-6- 2-91 1 3-8-70. 327. 093 532. 4 4 883 0. 285 40-5-4-7-8 31-9-从该表可知，当变异概率过大或过低都将导致无法得到最优解。2 -60.3 52 7 . 09353 3.316730.774813- 8 -7-4-5-0-6- 2 -90.429. 0 44634.370531.30412-0-5-4-8-7-3-1-9-60. 4 527. 09 3 53 1 . 37429.681 62 -6- 0 - 5 - 4-7-8-3-1-90.52 7.09 3 53 2. 375

12、 230. 22112- 9 -1-3-8 -7-4-5-0-60. 5527. 09 3 533. 3 8 1 930. 66231 -3- 8 -7-45-0-6-2-90.628. 0 9 3433.25 1230. 361-3-8-7-4-5-0-2-6-90. 6 52 7. 093532.74913 0. 02013 1- 9 -2 - 6- 0 -5- 4-7-80.728. 710832. 42 3 830. 7851-3-8 7-4-0-5-6290. 7527. 0 9 3531.89 2 83 0. 2 4511-9-2-6-0 5-4-7-8-30. 82 8. 0 9

13、 3431. 6 1353 0 . 34 7 19 -1-3-8-7-4-5-0-2-60. 8529. 6623 3.2 3 9231. 1 5852-9- 1 -3-7-8-4-0-5 60.92 8 . 0 4 4732. 038 730.41520 -54-8- 7-3-1-9-2-60. 9 52 8. 04 4 73 1 . 30363 0 . 0 0679-1- 3 -7 8-450-6-24、增长1种变异策略和1种个体选择概率分派策略，比较求解同一 TSP问题时不同变异策 略及不同个体选择分派策略对算法结果的影响。不同变异策略和不同个体选择分派策略几乎不影响算法运营的时间，但会 影响适应度。五、实验心得与体会通过本实验，更加进一步体会了参数设立对算法结果的影响。同一个算法, 参数值不同，获得的结果也许会完全不同。同时通过本次实验，使自己对遗传算法有了更进一步的了解。遗传算法是一种 智能优化算法，它能较好的近似求解T SP问题，在问题规模比较大的时候，遗传 算法的优势就明显体现出来，当然不能完全保证能得到最优解。