实验六：遗传算法求解TSP问题实验一、实验目的熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题， 理解求解 TSP问题的流程并测试主要参数对结果的影响。用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程，证明遗传算法在求解TSP问题时具有可行性。二、实验内容参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。对于同一个 TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。增加 1 种变异策略和 1 种个体选择概率分配策略，比较求解同一TSP 问题时不同变异策略及不同个体选择分配策略对算法结果的影响。1. 最短路径问题所谓旅行商问题 (Travelling Salesman Problem , TSP)，即最短路径问题，就是在给定的起始点S到终止点 T 的通路集合中， 寻求距离最小的通路，这样的通路成为S点到 T 点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法，用遗传算法解决这类问题， 没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。假设平面上有 n 个点代表 n 个城市的位置 , 寻找一条最短的闭合路径 , 使得可以遍历每一个城市恰好一次。这就是旅行商问题。 旅行商的路线可以看作是对 n 个城市所设计的一个环形, 或者是对一列 n 个城市的排列。由于对n 个城市所有可能的遍历数目可达(n- 1)!个, 因此解决这个问题需要0(n!)的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。 也就是说 , 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。2. 遗传算法遗传算法是由美国J.Holland教授于 1975 年在他的专著《自然界和人工系统的适应性》 中首先提出的， 它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象， 在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异 )对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 遗传算法在本质上是一种不依赖具体问题的直接搜索方法， 是一种...
