实验四遗传算法实验一、实验目的：熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。二、实验原理：旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。三、实验内容及要求1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。4、上交源代码。四、实验结果（根据实验报告要求）1、画出遗传算法求解TSP问题的流程图。2、分析遗传算法求解不同规模的TSP问题的算法性能。(1)遗传算法执行方式说明：适应度值计算方法：当前路线的路径长度个体选择概率分配方法：适应度比例方法选择个体方法：轮盘赌选择交叉类型：PMX交叉变异类型：两点互换变异(2)实验模拟结果:城市个数历欢最好适应度历次最差适应度运行时间/血688.854388.3543379910146.009154.679352515210.027250.067429720278.942366.18L644025392.002■168,03630430513.155567.738704735627.6336S4.323855240745.577735,756927245727.03S25.06810434图2由图1和图2可知，遗传算法执行时间随着TSP问题规模的增大而增大，并且大致为线性增长。3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。（1）种群规模对算法结果的影响城市数：15实验次数：10最大迭代步数:100交叉概率：0.85变异概率：0.15实验结果:种群规棋历挖怎差适应度最优蔬径运纾时间F图10245.617288.1122-0-5-7-3-6-4-10-12-L3-9-11-14-S-114520猶.93251.6142-3-7-C-&-6-5-L0-1-4-S-LL-14-12-1390330222.496272.6574-1-0-6-&-S-5-2-10-1L-12-7-3-13-127840236^631305.0353-7-1-6-11-9-12-0-2-4-10-8-13-14-5132250254-63927L21S7-12-8-L-9-2-3-L1-0-4-13-5-6-14-10221880165.36197.74111-3-4-12-9-5-L4-1-0-7-2-6-10-13-3577100210,26324L.S950-7-3--9-L1-4-?-10-L-12-14-8-6-134422150236.541262.9170-6-1-3-4-9-7-12-11-5-S-2-10-13-H6941200201,£91236.soe3-fl-o-1-7-11-4-C-l3-9-2-L2-8-10-14944&(2)交叉概率对算法结果的影响城市数：15实验次数：10种群规模：100最大迭代步数:100变异概率：0.15实验结果:厉诜直号适应艮平均适叵艮最世路径运行时间mm0229.3132S1.733353.1阳6-11-2-S-L3-7-9-L4-5-1-3-l-12-f-10痴帥0.25169.153221.765199.9944-6-0-2-5-10-11-L-3-7-3-14-9-13-13319265222.428252.2242.4SQ10-2-0-5-0-3-14-4-7-12-1-6-13-11-93B25D.75189.649214.89&200-786■^13-2-5-12-^-8-1-4-14-6-0^7-10-1141.3J0.S5177.946203.S511S8.6SGl-7-4-3-14-O-lCF2-12-g-ll-5-13-6-S461ai0.95214.762249.S952S2„763-2-4-L-9-6-U-0-S-7-12-LJ-5-13465S11B5.42209.774197.56213-10-0-5-3-11-1-0-14-42知-；3-64791在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。(3)变异概率对算法结果的影响城市数：15实验次数：10种群规模：100最...
