基于改进的乌鸦搜索算法求解旅行商问题

孟范立

关键词：旅行商；乌鸦优化算法；运算符；消除机制

中图分类号：TP18 文献标识码：A

文章编号：1009-3044（2023）12-0022-04

旅行商问题（TSP）是指求解经过多个城市的最短路径问题，适用于许多工程应用，如计算机网络、硬件设计、交通路线设计、基因排序和电子控制系统等。例如解决n个城市在内的一个TSP问题的求解空间是n的阶乘，因此TSP问题是一个典型的NP难问题。

TSP问题解决方案主要分为两类：一种是精确求解法，可以确保获得最优解，如分支界定法[1]。然而，随着城市数量增加，这些方法求解时间呈指数增长。因此，精确求解法仅适用于解决小规模问题。另一种是近似求解法，虽不能保证获得最优解但能够在较短时间内求得近似解。如蚁群优化算法[2]、遗传算法[3] 等算法。这些方法适用于解决大规模TSP问题。

一般来说，影响求解TSP问题近似算法的主要因素有两个方面，一是对搜索求解空间的扩展能力，二是算法收斂到最优解的收敛能力。在研究了各种群体智能算法并对其测试结果进行评估后，发现乌鸦优化算法模拟了乌鸦追随觅食的过程，涌现出了较好的全局搜索能力。但是，原始乌鸦算法[4]的追随过程易于使算法陷入局部最优。因此，本文提出了基于消除机制的乌鸦优化算法[5]求解TSP 问题（ECSA）。在ECSA中，消除机制增加了种群的多样性，避免算法陷入局部最优，使得ECSA提高了算法的扩展能力和融合能力。通过对TSPLIB中的标准测试集进行实验，与其他算法相比，ECSA结果较好，能够在较短的时间内搜索到更好的解。

1 乌鸦优化算法

CSA 是伊朗学者Askarzadeh 根据乌鸦智能行为于2016年提出的一种新群体智能优化算法[6]。乌鸦的智能行为表现为将多余的食物存放在藏身地方，并在需要食物时将其收回。乌鸦由于贪婪而相互追随，以获得更好的食物源。寻找其他乌鸦隐藏食物来源并不容易，因为如果一只乌鸦发现另一只在跟随它，就会尝试通过其他位置来欺骗乌鸦。与粒子群优化算法（PSO），蚁群算法（ACO）等群智能优化算法相比，该算法具有易于理解和实现简单优点。步骤如下：

步骤1：初始化种群大小，算法迭代的最大次数和种群的原始位置；

步骤2：初始化每个乌鸦的记忆；

步骤3：评估每个乌鸦所在位置的食物质量；

步骤4：随机选择其中一只乌鸦；

步骤5：按照认知概率，追随这只乌鸦；

步骤6：迭代优化。

在步骤5中，其他乌鸦个体将直接飞向最佳个体。意味着在这之后，该群体中所有个体将达到最佳个体。所以步骤5很容易导致算法陷入局部最优，导致低优化精度。

2 基于消除机制的乌鸦优化算法

在文中，对乌鸦觅食行为增加了消除机制。即淘汰种群中一些较差个体，同时在乌鸦觅食过程中产生一些新个体。既提高算法收敛性，又增加种群多样性，从而提高算法搜索空间，同时减少运行时间和陷入局部最优概率。

基于消除的乌鸦优化算法步骤如下：

步骤1：初始化定义乌鸦种群大小，最大迭代次数和种群的初始位置，飞行长度和认知概率。

步骤2：初始化乌鸦的记忆，即为种群初始位置。

步骤3：评估每个乌鸦所在位置食物质量。

图1和图2给出了原始乌鸦算法和改进乌鸦算法在Berlin52等数据集的迭代过程结果。其中，蓝线表示ECSA，而红线代表CSA。可以看出，在改进的乌鸦算法中，40次迭代后Y轴值没有改变，而原始版本中的值即使经过100次迭代也在变化。最后蓝色曲线低于红色曲线。这表明，改进算法可以在40次迭代之后即可找到最优解，而原始算法则需要100次迭代，因此在求解TSP问题时前者比后者能够得到更高精度。这是由于ECSA更加重视乌鸦搜索行为的追随行为，并为CSA增加了消除机制，可以加快收敛速度。

图3和图4给出的是改进的乌鸦搜索算法获得的优化结果和理论最优值之间的比较结果（其中每项数据对比中，左侧为红色柱条，右侧为蓝色柱条）。其中，红色表示理论值，而蓝色表示ECSA得到的优化结果。可以看出，改进的乌鸦优化算法所得的优化值和理论值几乎没有差别，并且在数据集Berlin52，Eil51，St70，KroA100和Lin105上改进算法均达到了理论值。

表2给出了使用基于消除机制的乌鸦优化算法和其他群智能算法的比较结果。在每个数据集中，各算法求得结果中最小值标记为红色。通过分析，改进算法得到的结果为7542.00，427.53， 677.26， 1237.20，62.05，与数据集Berlin52，Eil51，St70，Rat99，Eil101和Ch150上的其他优化算法相比，优化效果最好。对于数据集Eil76，Kroa100，Krob100和Lin105，尽管获得最优结果的算法分别是CGAS，DWIO，DWIO 和改进RABNET，ECSA所得的结果与其他三种算法的差异很小。例如，在数据集Krob100 上，最好的结果是22336.20，而ECSA 的结果为22355.00，差别小于0.1％。通过比较看出，ECSA结果更加精确，也提高了优化精度。

5 结论

本文在乌鸦搜索算法中加入了一种消除机制，其觅食行为更加注重乌鸦的追索搜索能力，避免了算法被局部优化的困扰。此方法不仅可以帮助乌鸦不断追随其他乌鸦飞行，而且可以提高收敛速度及算法优化精度。最后，测试了TSPLIB中的10个数据集以验证此文方法，结果表明，本文所阐述的方法比其他方法具有更好的优化精度和稳定性。