收藏 分享(赏)

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

上传人:g****t 文档编号:752457 上传时间:2023-04-15 格式:DOC 页数:3 大小:12KB
下载 相关 举报
2023年遗传算法求解TSP问题实验报告.doc_第1页
第1页 / 共3页
2023年遗传算法求解TSP问题实验报告.doc_第2页
第2页 / 共3页
2023年遗传算法求解TSP问题实验报告.doc_第3页
第3页 / 共3页
亲,该文档总共3页,全部预览完了,如果喜欢就下载吧!
资源描述

1、遗传算法求解遗传算法求解 TSPTSP 问题实验报告问题实验报告 人工智能实验报告 实验六 遗传算法实验 II 一、实验目的:熟悉和掌握遗传算法的原理、流程和编码策略,并利用遗传求解函数优化问题,理解求解 TSP 问题的流程并测试主要参数对结果的影响。二、实验原理:旅行商问题,即 TSP 问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP 问题是一个组合优化问题。该问题可以

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

3、传算法核心代码,用遗传算法求解 TSP 的优化问题,分析遗传算法求解不同规模 TSP 问题的算法性能。2、对于同一个 TSP 问题,分析种群规模、交叉概率和变异概率对算法结果的影响。3、增加 1 种变异策略和 1 种个体选择概率分配策略,比较求解同一 TSP 问题时不同变异策略及不同个体选择分配策略对算法结果的影响。4、上交源代码。四、实验报告要求:1、画出遗传算法求解 TSP 问题的流程图。2、分析遗传算法求解不同规模的 TSP 问题的算法性能。规模越大,算法的性能越差,所用时间越长。3、对于同一个 TSP 问题,分析种群规模、交叉概率和变异概率对算法结果的影响。(1)种群规模对算法结果的影

4、响 x 0 1.1 3.5 3 7 8 4 4.5 9 2 y 1.1 3 2 4 5.1 8 4 4.5 9 2 实验次数:10 最大迭代步数:100 交叉概率:0.85 变异概率:0.15 种群规模 平均适应度值 最优路径 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

5、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 如表所示,显然最短路径为 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)交叉概率对算法结果的影响 x 9 1.1 3.5 3.5 7 8 4 4.5

6、3 2 y 1.1 3 1 4 5.1 3 1 8.5 9 1 实验次数:15 种群规模:25 最大迭代步数:100 变异概率:0.15 实验结果:交叉概率 最好适应度 最差适应度 平均适应度 最优解 0.001 28.0447 36.6567 32.6002 9-2-6-0-5-4-8-7-3-1 0.01 27.0935 34.9943 32.1495 7-8-3-1-9-2-6-0-5-4 0.1 28.0447 35.3033 31.9372 7-3-1-9-2-6-0-5-4-8 0.15 28.0447 34.1175 31.2183 0-5-4-8-7-3-1-9-2-6 0.2

7、 28.7108 33.9512 30.9035 3-1-9-2-6-5-0-4-7-8 0.25 28.0447 35.1623 30.7456 1-3-7-8-4-5-0-6-2-9 0.3 27.0935 31.9941 29.9428 8-3-1-9-2-6-0-5-4-7 0.35 27.0935 32.8085 30.9945 9-1-3-8-7-4-5-0-6-2 0.4 27.0935 32.5313 30.1534 1-3-8-7-4-5-0-6-2-9 0.45 27.0935 33.2014 30.1757 8-3-1-9-2-6-0-5-4-7 0.5 28.0934

8、33.6307 30.9026 5-0-2-6-9-1-3-8-7-4 0.55 27.0935 33.5233 29.1304 1-9-2-6-0-5-4-7-8-3 0.6 27.0935 33.2512 30.7836 3-1-9-2-6-0-5-4-7-8 0.65 28.0447 33.7003 30.9371 5-4-8-7-3-1-9-2-6-0 0.7 27.0935 32.0927 29.9502 9-1-3-8-7-4-5-0-6-2 0.75 28.0447 32.4488 30.3699 0-5-4-8-7-3-1-9-2-6 0.8 27.0935 32.1551 2

9、9.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)变异概率对算法结果的影响 x 9 1.1 3.5 3.5 7 8 4 4.5 3 2 y 1.1 3 1 4 5.1 3 1 8.5 9 1 实验次数:10 种群规模:25

10、 最大迭代步数:100 交叉概率:0.85 实验结果:变异概率 最好适应度 最差适应度 平均适应度 最优解 0.001 29.4717 34.732 32.4911 0-6-2-1-9-3-8-7-4-5 0.01 29.0446 34.6591 32.3714 8-4-5-0-2-6-9-1-3-7 0.1 28.0934 34.011 30.9417 5-0-2-6-9-1-3-8-7-4 0.15 27.0935 32.093 30.2568 6-0-5-4-7-8-3-1-9-2 0.2 27.0935 32.2349 30.3144 8-7-4-5-0-6-2-9-1-3 0.25

11、27.0935 32.718 30.1572 4-5-0-6-2-9-1-3-8-7 0.3 27.0935 32.4488 30.2854 0-5-4-7-8-3-1-9-2-6 0.35 27.0935 33.3167 30.7748 1-3-8-7-4-5-0-6-2-9 0.4 29.0446 34.3705 31.3041 2-0-5-4-8-7-3-1-9-6 0.45 27.0935 31.374 29.6816 2-6-0-5-4-7-8-3-1-9 0.5 27.0935 32.3752 30.2211 2-9-1-3-8-7-4-5-0-6 0.55 27.0935 33.

12、3819 30.6623 1-3-8-7-4-5-0-6-2-9 0.6 28.0934 33.2512 30.36 1-3-8-7-4-5-0-2-6-9 0.65 27.0935 32.7491 30.0201 3-1-9-2-6-0-5-4-7-8 0.7 28.7108 32.4238 30.785 1-3-8-7-4-0-5-6-2-9 0.75 27.0935 31.8928 30.2451 1-9-2-6-0-5-4-7-8-3 0.8 28.0934 31.6135 30.3471 9-1-3-8-7-4-5-0-2-6 0.85 29.662 33.2392 31.1585

13、2-9-1-3-7-8-4-0-5-6 0.9 28.0447 32.0387 30.4152 0-5-4-8-7-3-1-9-2-6 0.95 28.0447 31.3036 30.0067 9-1-3-7-8-4-5-0-6-2 从该表可知,当变异概率过大或过低都将导致无法得到最优解。4、增加 1 种变异策略和 1 种个体选择概率分配策略,比较求解同一 TSP 问题时不同变异策略及不同个体选择分配策略对算法结果的影响。不同变异策略和不同个体选择分配策略几乎不影响算法运行的时间,但会影响适应度。五、实验心得与体会 通过本实验,更加深入体会了参数设置对算法结果的影响。同一个算法,参数值不同,获得的结果可能会完全不同。同时通过本次实验,使自己对遗传算法有了更进一步的了解。遗传算法是一种智能优化算法,它能较好的近似求解 TSP 问题,在问题规模比较大的时候,遗传算法的优势就明显体现出来,当然不能完全保证能得到最优解。

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 政务民生 > 其它

copyright@ 2008-2023 wnwk.com网站版权所有

经营许可证编号:浙ICP备2024059924号-2