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

精品word 可编辑资料 - - - - - - - - - - - - -人工智能试验报告试验六遗传算法试验II一.试验目的：熟识和把握遗传算法的原理.流程和编码策略，并利用遗传求解函数优化问题，懂得求解 TSP问题的流程并测试主要参数对结果的影响；二.试验原理：旅行商问题， 即 TSP问题（ Traveling Salesman Problem ）为数学领域中闻名问题之一；假设有一个旅行商人要拜望 n 个城市， 他必需挑选所要走的路径， 路经的限制为每个城市只能拜望一次， 而且最终要回到原先动身的城市； 路径的挑选目标为要求得的路径路程为全部路径之中的最小值； TSP问题为一个组合优化问题；该问题可以被证明具有NPC运算复杂性；因此，任何能使该问题的求解得以简化的方法，都将受到高度的评判和关注；遗传算法的基本思想正为基于仿照生物界遗传学的遗传过程；它把问题的参数用基因代表，把问题的解用染色体代表（在运算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体；这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代； 后代随机化地继承了父代的最好特点，并也在生存环境的掌握支配下连续这一过程；群体的染色体都将逐步适应环境，不断进化，最终收敛到一族最适应环境的类似个体，即得到问题最优的解；要求利用遗传算法求解TSP问题的最短路径；三.试验内容：1.参考试验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能；2 .对于同一个TSP问题，分析种群规模.交叉概率和变异概率对算法结果的影响；3 .增加 1 种变异策略和1 种个体挑选概率安排策略，比较求解同一TSP问题时不同变异策略及不同个体挑选安排策略对算法结果的影响；4 .上交源代码；第 1 页，共 5 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -四.试验报告要求：1 .画出遗传算法求解TSP问题的流程图；开头初始化种群（随机产生城市坐标）确定种群规模.迭代次数.个体挑选方式.交叉概率.变异概率等运算染色体适应度值（城市之间的欧氏距离）YES按某个挑选概率挑选个体个体交叉个体变异P<迭代总次数NO输入适应度最高的解终止第 2 页，共 5 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -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试验结果：第 3 页，共 5 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -交叉概率最好适应度最差适应度平均适应度最优解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.202130.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-3第 4 页，共 5 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -0.2527.093532.71830.15724-5-0-6-2-9-1-3-8-70.327.093532.448830.28540-5-4-7-8-3-1-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-3-1-9-60.4527.093531.37429.68162-6-0-5-4-7-8-3-1-90.527.093532.375230.22112-9-1-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.02013-1-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.34719-1-3-8-7-4-5-0-2-60.8529.66233.239231.15852-9-1-3-7-8-4-0-5-60.928.044732.038730.41520-5-4-8-7-3-1-9-2-60.9528.044731.303630.00679-1-3-7-8-4-5-0-6-2从该表可知，当变异概率过大或过低都将导致无法得到最优解；4 .增加 1 种变异策略和1 种个体挑选概率安排策略，比较求解同一TSP问题时不同变异策略及不同个体挑选安排策略对算法结果的影响；不同变异策略和不同个体挑选安排策略几乎不影响算法运行的时间，但会影响适应度；五.试验心得与体会通过本试验， 更加深化体会了参数设置对算法结果的影响；同一个算法， 参数值不同，获得的结果可能会完全不同；同时通过本次试验，使自己对遗传算法有了更进一步的明白；遗传算法为一 种智能优化算法，它能较好的近似求解TSP 问题，在问题规模比较大的时候，遗传算法的优势就明显表达出来，当然不能完全保证能得到最优解；第 5 页，共 5 页 - - - - - - - - - -