遗传算法求解TSP问题

        采用遗传算法进行25个城市的TSP问题求解，通过遗传算法求解得出的最短路径值为29085.91，最优路径为24→15→25→20→19→6→8→17→3→13→7→5→11→1→2→14→4→9→12→21→10→16→22→18→23→24（数字为城市序号）。同时根据不同参数下的实验结果，得出结论，随着种群数量的增长及迭代次数的越来越多，遗传算法寻优的结果越来越好。当然，由于遗传算法本身具有一定的随机性，能否快速收敛得看具体参数设定。

        遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象。

        在利用遗传算法求解问题时，问题的每一个可能解都被编码成一个“染色体”，即个体，若干个个体构成了群体(所有可能解)。在遗传算法开始时，总是随机的产生一些个体(即初始解)，根据预定的目标函数对每一个个体进行评估给出一个适应度值。基于此适应度值，选择一些个体用来产生下一代，选择操作体现了“适者生存"的原理，“好”的个体被用来产生下一代，“坏”的个体则被淘汰，然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代，这一代的个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着最优解的方向进化。

        因此，遗传算法可以看成是一个由可行解组成的群体初步进化的过程。

        步骤一：设置 TSP 问题中25个城市的坐标值，限制每个城市只能拜访一次，并且回到出发的城市。本实验中25个城市坐标如下：

        步骤二：设置种群数量 P=100，染色体基因数 N=25，迭代次数 maxIter=1000，变异概率 Pm=0.1；

        步骤三：初始化种群，计算每个个体的适应度值（即路径长短），执行交叉、变异、选择操作，生成新的种群；

        步骤四：判断终止条件（如果满足，则迭代结束。输出最终最短路径值以及绘制最优路径图；否则继续迭代优化，并实时更新最短路径值以及最优路径图）。

源代码如下：