基于Matlab的协同进化遗传算法求解旅行商问题

旅行商问题开yun体育app入口登录，亦称TSP问题，其核心在于寻找一条最优的城市路线组合。该组合需满足每个城市仅被访问一次，且起始和结束的城市相同。目标是在所有可能的路线中，确保行程的总长度达到最小。本研究在经典遗传算法的基础上进行了改良与提升，创造性地引入了精英保留机制的协同进化遗传算法。通过选取30、50和75个城市的案例，对改进后的算法与原算法进行了详细的比较。具体的算法执行步骤可参考图1。

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

在构建出初始种群（记作POP）之后，便依照适应度值（即总路程的倒数）的从高到低，将其划分成了三个不同的子种群。在这三个子种群中，子种群1的适应度值位居首位，而子种群3的适应度值则处于最低。随后，在各个子种群内部开展交叉变异操作，依次生成了新子种群1、新子种群2以及新子种群3。同时，三个子种群间相互进行交叉变异实验，依次孕育出新子种群4、新子种群5以及新子种群6。随后，将这六个新形成的子种群进行整合，从中随机选取POP-1个个体，再依据精英保留原则，将所选个体与父代中最优秀的个体合并，以此形成新的种群，并启动下一轮的操作。

选取了30个、50个以及75个城市作为样本，对这些城市进行了10轮的重复实验，最后取每轮实验中两种算法所得最佳解的平均值进行比较开元ky888棋牌官方版，具体结果可以参考图2。

图2 两种算法的寻优结果对比

显然，相较于传统的遗传算法，协同进化遗传算法在寻求最优解方面展现出更卓越的效能，特别是在城市数量众多的情况下，比如本例中的75个城市。它能够更有效地防止陷入局部最优的陷阱，进而寻找到全局最优解，并使得总行程得到显著缩短。以75个城市为例开yun体育官网入口登录app，两种算法确定的最优路径分别如图3(a)和图3(b)所示。

(a) 传统遗传算法

(b) 协同进化遗传算法

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

图3展示了城市的横纵坐标，横轴和纵轴分别对应各城市的坐标值，而图中的数字则是各城市的标识。显而易见，协同进化遗传算法所计算出的最优路径呈现出更为整齐的形态，这一特点显示出与传统遗传算法相比，它拥有更卓越的全局搜索能力，并且展现出更佳的适应性。

最后，有相关算法需求，欢迎通过微信公众号联系我们。