优化旅行商问题：精英保留协同进化遗传算法在30、50、75个城市中的应用

旅行商问题（简称TSP问题）是为了解决城市路线的最优组合。它要求每个城市必须被访问并且只能访问一次。目的地城市和出发城市相同，最终走的距离必须是最短的。在传统遗传算法的基础上，对其进行改进和优化，提出一种保留精英的协同进化遗传算法。分别以30、50、75个城市为例对两者进行比较。该算法的运行流程如图1所示。

图1 协同进化遗传算法运行流程

初始种群生成后（设种群数为POP），根据适应度值（即总距离的倒数）将其分为三个子种群。其中，子群体1适应度值最大，子群体3适应度值最大。最低限度。然后，在每个子群内进行交叉变异操作，依次生成新的子群1、新的子群2、新的子群3。同时，三个子群体之间也进行交叉变异操作，产生新的子群体4、新的子群体5、新的子群体6。最后，将这6个新的子群体组合在一起，然后从其中随机选择POP-1个体，并根据精英保留策略与父代中最好的个体进行合并，得到新的种群并开始下一代运行。 。

以30、50、75个城市为例，进行10次重复测试，每次测试中取两种算法最优解的平均值进行比较。结果如图2所示。

图2 两种算法优化结果对比

显然，与传统遗传算法相比，协同进化遗传算法具有更强大的最优解搜索能力。尤其是当城市数量较多时（如本例中为75个），可以更有效地避免陷入局部最优，从而找到全局最优解，使总距离更小。以75个城市为例，两种算法确定的最优路径分别如图3(a)和3(b)所示。

(a) 传统遗传算法

(b) 共同进化遗传算法

图3 两种算法确定的最优路径对比

图3中，横轴和纵轴分别为各个城市的横坐标和纵坐标，图中的数字为各个城市的编号。显然，协同进化遗传算法确定的最优路径更加规则，这说明其比传统遗传算法具有更强的全局优化能力和更好的鲁棒性。

最后，如果您有相关算法需求，请通过微信公众号联系我们。