基于改进蚁群算法在TSP 问题中的应用

2023-12-13刘子墨

科技与创新 2023年23期

刘子墨

（首都经济贸易大学管理工程学院，北京 100070）

蚁群算法从大自然中诞生，是寻优问题中一种优秀的解决策略[1]。最初是由DORⅠGO 等[2]首次向世人介绍了蚁群算法。由于蚂蚁的移动是随机的，当种群规模达到一定程度时，蚁群算法需要很长时间才能找到较优的解决方案。因此，GAMBARDELLA 等[3]又对经典的AS 算法进行了改进，提出了一种更为通用的算法“Ant-Q System”。针对蚁群算法易过早停滞的缺陷，1997 年，STUTZLE 等[4]提出了MAX-MⅠN Ant System，为其中每条边可允许拥有的跟踪信息素的量设置了范围限制。而后GAMBARDELLA 等[5]提出了HAS，在HAS 的迭代中，利用蚂蚁获取的每个解，对局部进行检测，寻找局部最优，从而提升解的品质。如今，蚁群算法已频繁出现在专业学术会议上，许多关于蚁群算法的论文也被发表在Nature、Generation Computer System等专业的学术刊物上，许多计算机学者对其研究十分热切。

针对蚁群算法的缺陷，国内的研究人员也有着不同的解决策略，其中吴庆洪等[6]提出将突变机制应用于蚁群算法中，提高算法收敛速率；王颖等[7]提出针对参数的自适应调整，解决不易求得全局最优的不足；李擎等[8]利用蚁群算法易于与其他方法结合的特点，结合粒子群与蚁群，改进了信息素的更新策略，对性能进行了一定的提升。

1 相关理论与技术基础

1.1 ACO 算法

1.1.1 ACO 算法简述

对ACO 算法的具体过程进行参数设置，设τij为0，蚂蚁数目为m。第k（k=1，2，…，m）只的每一步选择由信息素浓度决定，其状态转移概率为，计算公式为：

其中，ak={1，2，…，n}－tabuk为下一次可选择的所有城市的集合，tabuk则是蚂蚁k当前已经过的城市，它会随着ACO 算法的运行而有一定变化。i代表蚂蚁当前所位于的城市，j为集合tabuk中的一员，为蚂蚁k由城市i转移至下一个城市j的概率，为蚂蚁从城市i去往j的期望程度，τij为路径（i，j）上的信息素轨迹强度。由公式1 可知，与[τij（t）]α[ηij（t）]β的关系成正比例，因此当蚂蚁进行路径的选择时会优先挑选信息素浓度较高的城市进行转移[9]。

1.1.2 ACO 算法优点与缺陷

ACO 算法作为仿生算法，继承了蚂蚁行为的诸多特点，有以下几点优点：①本质并行性。多个蚂蚁个体可位于多点同时进行搜索，相当于多项代理的分布式系统，具有较高的算法运行效率。②易与其他算法相结合。以ACO 算法为基础，引入其他算法的优秀机制与之进行互补，可进一步提升算法质量。③强鲁棒性。ACO 算法只需进行很小的改动便能使用在其他方面，有助于拓宽使用领域范围。

ACO 算法作为新生代仿生算法，仍有着一些缺陷，主要有：①不易取得最优解。由于ACO 算法的特性，信息素在运行时较易集群在个别路段上，从而陷入局部最优。②求解时间长。构造解的过程需要很大的计算量，当待解决问题需要构造的可行解数目增多时，蚂蚁寻找最优解所需要的时间将会变长。③参数的设置理论不足。ACO 算法的性能与关键参数息息相关，目前还没有对参数的设置给出严密的理论认证，多依赖实验经验而定[10-11]。

1.2 GA 算法

1.2.1 GA 算法简述

GA 算法由HOLLAND 在1975 时首次提出，该算法参照的是达尔文的“优胜劣汰” 进化论原则。在遗传算法的实现过程中，通过计算适应度函数所获取的结果可较为直观地判断出种群个体（染色体）适应度的强弱程度，从而决定它们的存留[12]。

1.2.2 遗传算法步骤

遗传算法步骤如下。

步骤1：初始化种群。设置参数，选择合适的编码方式，产生非固定数据并进行组合来获取初始种群。

步骤2：计算适应度值。使用适应度函数获取值后，选择后续操作个体。

步骤3：执行交叉运算。

步骤4：执行变异运算。

步骤5：判断是否能够结束，若满足条件则输出结果，否则回到步骤2，最终得出最优解。

1.3 TSP 问题

TSP 问题指有N个城市，由初始位置出发，遍历每一个城市，不能重复，且最终回到原来出发点的问题，同时需找到在过程中所付出的代价最小，即最短的路径。TSP 问题虽然描述起来并不困难，但是要获取其精确的解却并不是一件容易的事情，单是其所有可行路径就有（n－1）！/2 条，学术界将其称为NP-Hard问题[13-14]。

TSP 是NP 完全问题，若一种算法在对解决TSP应用而言表现良好，则通常在解决其他的应用上也可以获得不错的结果，因此以TSP 问题来验证算法的改进是否有效是比较可靠的[15-16]。