旅行商问题(TSP)，即求解城市路线的最优组合，要求每个城市只走一次，目的地城市与出发城市相同，最终行程要最短。在传统遗传算法的基础上，对其进行了改进和优化，提出了一种带精英保留的协同进化遗传算法。以30、50、75城市为例，对两者进行对比。该算法的运行流程如图1所示。
图1协同进化遗传算法的操作过程
初始种群生成后(假设种群数量为POP)，根据适应度值(即总距离的倒数)分为三个子种群，其中子种群1的适应度值最大，子种群3的适应度值最小。然后在每个子种群中进行交叉变异操作，依次产生新子种群1、新子种群2和新子种群3。同时，三个子种群也进行交叉变异，依次产生新子种群4、新子种群5和新子种群6。最后，将这六个新的子种群进行组合，然后从中随机选取POP-1个个体，并根据精英保留策略，将其与其父代的最优个体进行组合，从而获得新的种群，开始下一代操作。
以30、50、75个城市为例，分别进行10次重复实验，比较两种算法在每次实验中最优解的平均值。结果如图2所示。
图2两种算法的优化结果对比
显然，与传统遗传算法相比，协同进化遗传算法具有更强的搜索最优解的能力，尤其是当城市数量较多时(本例中为75个)，可以更有效地避免陷入局部最优，从而找到全局最优解，使总距离更小。以75个城市的数量为例，两种算法确定的最优路径分别如图3(a)和3(b)所示。
(一)传统遗传算法
(二)协同进化遗传算法
图3两种算法确定的最佳路径的比较
在图3中，横轴和纵轴是每个城市的横轴和纵轴，图中的数字是每个城市的数字。显然，协同进化遗传算法确定的最优路径更规则，这表明它比传统遗传算法具有更强的全局寻优能力和更好的鲁棒性。
本文来自傲娇小伙子投稿，不代表舒华文档立场，如若转载，请注明出处：https://www.chinashuhua.cn/24/653183.html
微信扫一扫 
