资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
人工智能实验报告实验六 遗传算法实验 II一、实验目的:熟悉和掌握遗传算法的原理、流程和编码策略,并利用遗传求解函数优化问题,理解求 解TSP问题的流程并测试主要参数对结果的影响。二、实验原理:旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。 假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只 能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有 路径之中的最小值oTSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。 因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代 表,把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染 色体的个体组成的群体。这个群体在问题特定的环境里生存竞争,适者有最好的机会生存和 产生后代。后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过 程。群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体, 即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。三、实验内容:1、参考实验系统给出的遗传算法核心代码,用遗传算法求解TSP的优化问题,分析遗传 算法求解不同规模TSP问题的算法性能。2、对于同一个TSP问题,分析种群规模、交叉概率和变异概率对算法结果的影响。3、增加1种变异策略和1种个体选择概率分配策略,比较求解同一TSP问题时不同变异 策略及不同个体选择分配策略对算法结果的影响。4、上交源代码。四、实验报告要求:1、画出遗传算法求解TSP问题的流程图。2、分析遗传算法求解不同规模的TSP问题的算法性能。规模越大,算法的性能越差,所用时间越长。3、对于同一个TSP问题,分析种群规模、交叉概率和变异概率对算法结果的影响。1) 种群规模对算法结果的影响x01.13.537844.592y1.13245.1844.592实验次数:10 最大迭代步数:100 交叉概率:0.85 变异概率:0.15种群规模平均适应度值最优路径1025.2644-5-8-7-6-3-1-0-9-22026.34282-9-1-0-3-6-7-5-8-43025.16521-3-6-7-5-8-4-2-9-05025.16520-1-3-6-7-5-8-4-2-98025.16529-0-1-3-6-7-5-8-4-210025.16521-0-9-2-4-8-5-7-6-315025.16525-8-4-2-9-0-1-3-6-720025.16521-3-6-7-5-8-4-2-9-025025.16523-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-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6,注意到这是一圈,顺时针或者逆时针都可以。当种群规模为10,20时,并没有找到最优解。因此并不是种群规模越小越好。2) 交叉概率对算法结果的影响x91.13.53.57844.532y1.13145.1318.591实验次数:15种群规模:25 最大迭代步数:100 变异概率:0.15 实验结果:交叉概率最好适应度最差适应度平均适应度最优解0.00128.044736.656732.60029-2-6-0-5-4-8-7-3-10.0127.093534.994332.14957-8-3-1-9-2-6-0-5-40.128.044735.303331.93727-3-1-9-2-6-0-5-4-80.1528.044734.117531.21830-5-4-8-7-3-1-9-2-60.228.710833.951230.90353-1-9-2-6-5-0-4-7-80.2528.044735.162330.74561-3-7-8-4-5-0-6-2-90.327.093531.994129.94288-3-1-9-2-6-0-5-4-70.3527.093532.808530.99459-1-3-8-7-4-5-0-6-20.427.093532.531330.15341-3-8-7-4-5-0-6-2-90.4527.093533.201430.17578-3-1-9-2-6-0-5-4-70.528.093433.630730.90265-0-2-6-9-1-3-8-7-40.5527.093533.523329.13041-9-2-6-0-5-4-7-8-30.627.093533.251230.78363-1-9-2-6-0-5-4-7-80.6528.044733.700330.93715-4-8-7-3-1-9-2-6-00.727.093532.092729.95029-1-3-8-7-4-5-0-6-20.7528.044732.448830.36990-5-4-8-7-3-1-9-2-60.827.093532.155129.93827-4-5-0-6-2-9-1-3-80.8527.093534.539930.35945-0-6-2-9-1-3-8-7-40.927.093532.627330.696-0-5-4-7-8-3-1-9-20.9527.093532.467229.9196-2-9-1-3-8-7-4-5-0注:红色表示非最优解)在该情况下,交叉概率过低将使搜索陷入迟钝状态,得不到最优解。3) 变异概率对算法结果的影响x91.13.53.57844.532y1.13145.1318.591实验次数:10种群规模:25 最大迭代步数:100 交叉概率:0.85 实验结果:变异概率最好适应度最差适应度平均适应度最优解0.00129.471734.73232.49110-6-2-1-9-3-8-7-4-50.0129.044634.659132.37148-4-5-0-2-6-9-1-3-70.128.093434.01130.94175-0-2-6-9-1-3-8-7-40.1527.093532.09330.25686-0-5-4-7-8-3-1-9-20.227.093532.234930.31448-7-4-5-0-6-2-9-1-30.2527.093532.71830.15724-5-0-6-2-9T-3-8-70.327.093532.448830.28540-5-4-7-8-3T-9-2-60.3527.093533.316730.77481-3-8-7-4-5-0-6-2-90.429.044634.370531.30412-0-5-4-8-7-3T-9-60.4527.093531.37429.68162-6-0-5-4-7-8-3T-90.527.093532.375230.22112-9T-3-8-7-4-5-0-60.5527.093533.381930.66231-3-8-7-4-5-0-6-2-90.628.093433.251230.361-3-8-7-4-5-0-2-6-90.6527.093532.749130.02013T-9-2-6-0-5-4-7-80.728.710832.423830.7851-3-8-7-4-0-5-6-2-90.7527.093531.892830.24511-9-2-6-0-5-4-7-8-30.828.093431.613530.34719T-3-8-7-4-5-0-2-60.8529.66233.239231.15852-9T-3-7-8-4-0-5-60.928.044732.038730.41520-5-4-8-7-3T-9-2-60.9528.044731.303630.00679T-3-7-8-4-5-0-6-2从该表可知,当变异概率过大或过低都将导致无法得到最优解。4、增加1种变异策略和1种个体选择概率分配策略,比较求解同一TSP问题时不同变异 策略及不同个体选择分配策略对算法结果的影响。不同变异策略和不同个体选择分配策略几乎不影响算法运行的时间,但会 影响适应度。五、实验心得与体会 通过本实验,更加深入体会了参数设置对算法结果的影响。同一个算法,参 数值不同,获得的结果可能会完全不同。同时通过本次实验,使自己对遗传算法有了更进一步的了解。遗传算法是一 种智能优化算法,它能较好的近似求解 TSP 问题,在问题规模比较大的时候, 遗传算法的优势就明显体现出来,当然不能完全保证能得到最优解。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号