旅行商问题作为组合优化研究中最具挑战的问题之一, 自被提出以来就引起了学术界的广泛关注并提出了大量的方法来解决它. 蚁群算法是求解复杂组合优化问题的一种启发式仿生进化算法, 是求解旅行商问题的有效手段. 本文分别介绍蚁群算法中几个有代表性的算法, 综述了蚁群算法的改进、融合和应用的文献研究进展, 以评价近年来不同版本的蚁群算法为解决旅行商问题的发展和研究成果, 并针对改进蚁群算法结构框架、算法参数的设置及优化、信息素优化和混合算法等方面, 对现被提出的改进算法进行了分类综述. 对蚁群算法在未来对旅行商问题及其他不同领域的研究内容和研究热点的进一步发展提供了展望和依据.
As one of the most challenging problems in combinatorial optimization, the traveling salesman problem has attracted extensive attention from the academic community since its birth, and a large number of methods have been proposed to solve it. The ant colony optimization (ACO) is a heuristic bionic evolutionary algorithm for solving complex combinatorial optimization problems, which is effective in solving the traveling salesman problem. This study introduces several representative ACOs and makes a literature review of the improvement, fusion, and application progress of ACOs to evaluate the development and research achievements of different versions of ACOs in solving the traveling salesman problem in recent years. Moreover, the improved ACOs are summarized in categories in terms of the framework structure, setting and optimization of algorithm parameters, pheromone optimization, and hybrid algorithms. The research provides an outlook and basis for the ACO application to solve the traveling salesman problem and further develop the research content and focuses of other fields.
旅行商问题 (traveling salesman problem, TSP)[
群智能算法(swarm intelligence, SI)[
步骤1. 算法构建一个或一组初始解.
步骤2. 在关键参数控制下通过邻域函数产生若干邻域解.
步骤3. 按照接受准则(确定性, 概率性或混沌方式)更新当前状态.
步骤4. 按关键参数修改准则来调整关键参数的值.
如此重复上述步骤直到满足算法的收敛准则, 最终得到问题的最优解. 启发式算法的优化流程如
许多已知的方法已被应用于解决TSP问题, 如线性规划法、回溯算法、分支限界方法等精确算法. 精确的方法并不总是适用于较大的实例, 因此, 近几年对TSP的研究主要集中在使用先进的启发式和元启发式算法, 如遗传算法(genetic algorithm, GA)[
群智能算法优化流程图
蚁群算法自被提出以来就被成功应用, 许多研究者利用蚁群算法作为基准来寻找更好的解决方案. 本文概括地介绍了蚁群算法从诞生到成熟过程中几个代表性的算法, 给出了TSP问题的数学模型和蚁群算法的数学背景; 对解决TSP问题而提出的算法优化方案和一些最优化算法的实现方法进行了综述. 以评价不同版本的蚁群算法在TSP问题领域中的应用.
在优化问题中, 我们的目标是遵守特定的约束来寻找最接近最优解的结论. TSP问题是组合优化问题中最经典的问题之一, 它可表述为在
按照图论方法对其解释, TSP问题也意味着在赋权完全图中找到最小权重的哈密顿(Hamilton)回路. 解决方法是将图中的每个节点表示为一个城市, 每条路径都有一个对应于城市之间的距离的权重, 优化目标是使总距离最小化(按距离计算达到最佳路径). 搜索空间是
当
ACO模仿了真实蚂蚁的觅食行为, 利用人工蚂蚁通过信息素作为分布式传播的媒介. 它的灵感来自于Goss等人使用真实蚂蚁进行的双桥实验[
蚂蚁系统(ant system, AS)作为最初Dorigo等人[
蚂蚁系统的基本结构
现从蚁周模型的角度说明基本蚁群算法求解TSP问题的具体步骤.
步骤1. 初始化. 将等于或小于
步骤2. 路径构建. 在每一次迭代循环中, 每只蚂蚁
其中,
步骤3. 更新信息素. 为了防止剩余信息素过多而引起的残留信息淹没启发因子, 当
其中,
ACS模型:
AQS模型:
ADS模型:
其中,
AQS模型和ADS模型采用局部更新的方式在每只蚂蚁遍历节点(
计算并比较所有
步骤4. 判断是否满足终止条件. 当迭代计数器
蚁群系统(ant colony system, ACS)是对蚂蚁系统的主要改进之一[
(1) 状态转移规则的不同
在ACS算法中, 位于城市
(2) 更改信息素全局更新规则
与AS不同的是, ACS只对当前循环中找到的最优路径的边根据式(10)进行信息素更新:
其中,
(3) 引入信息素局部更新规则
当蚂蚁
其中,
若
若
在之后的研究中, ACS还引入了3-opt启发式策略, 明显地提高了算法的性能.
根据信息素更新策略的差异, 德国学者Stützle等人[
(1)与ACS一样, MMAS在每次迭代完成后, 只允许本次迭代中最优蚂蚁(在此迭代中构造最短路径的蚂蚁)或迄今为止的最优蚂蚁按照式(12)更新信息素, 加快了算法的收敛速度. MMAS取消了信息素的局部更新规则:
其中,
(2) MMAS中约束路径信息素浓度值介于
既增加了对最优解探索的可能性, 又避免了信息素为零或持续积累的现象.
(3)在算法开始时设置信息素初始化为其浓度上限
随着移动环境的复杂性和任务难度的增加, 传统的蚁群算法在很多应用场合已然达不到预期的效果. 随后, 许多国内外专业研究人员对蚁群算法的缺陷问题进行了深入的研究分析. 为提高其稳定性, 旨在降低其复杂度及深度来优化算法, 对蚁群算法的发展做出了重大贡献. 针对蚁群算法在求解过程中具有收敛速度慢、难以扩展搜索空间、容易停滞和陷入局部最优等缺点, 本文从几个方面介绍了蚁群算法的改进形式, 主要从蚁群算法的路径构建和信息素更新两个主要阶段来构建最优路径进行切入, 改进策略主要从算法结构改进, 信息素初始化与更新策略的改进, 参数选择与优化策略, 融合蚁群算法等提高算法的优化能力方面来进行综述, 并介绍了几个蚁群算法在其他领域的扩展应用, 以期为之后蚁群算法的进一步改进优化提供理论依据.
许多学者将基本蚁群算法提供的基础框架作为研究基础, 在其框架和结构上提出了许多性能优异的改进措施, 目标是获得比AS更好的性能. 如Dorigo等人提出的蚁群系统(ACS)[
Pendharkar[
Escario等人[
Duan等人[
Rokbani等人[
对于动态优化问题(DOPs), 传统的ACO算法不能很好地适应动态变化, 可能会随着目标函数、决策变量、问题实例、约束时间等而发生变化, 这种不确定性可能会改变最优状态. Mavrovouniotis等人[
此外, 还有一些研究者利用机器学习的方法来优化蚁群算法的结构. 如王原等人[
反向学习是机器学习中的一种新概念, 其主要思想是在当前迭代后计算所有相反的解, 然后在生成的解及其相反的解中, 选择最优解进行下一轮迭代. Zhang等人[
如果采用单一的固定模式去改变蚁群算法的路径构建策略和信息素更新策略不具有灵活性, 不能很好地解决算法过早收敛等问题. 上述改进方法主要都是以基本蚁群算法为基础, 通过平衡求解效率和求解质量[
蚁群算法对参数的变化很敏感, 蚂蚁通过重要参数值来扩展其路径,
无论选择元启发式或者仿生技术来解决问题, 性能总是受算法参数的影响. 在蚁群算法中, 蚂蚁的行为主要由路径上的启发信息和信息素决定. 在优化过程中, 基本蚁群算法的参数值通常是固定的, 参数值的设置直接影响到了算法的收敛性. 如果参数值不协调的话, 蚂蚁要么依赖启发式信息, 要么依赖信息素. 在这种情况下, 算法通常会陷入局部极小值. 此外, 对于不同的问题, 甚至同一问题的不同实例, 参数值也往往有所不同. 通常给定一个问题, 为了确定算法参数的最佳组合, 需要进行大量的实验来选取.
近年来, 蚁群算法的参数设置已经被广泛研究. 吴春明等人[
Cheong等人[
向永靖[
Gan等人[
Peker等人[
Blagoveshchenskaya等人[
针对参数对蚁群算法性能的影响, Wang等人[
Salem等人[
上述研究的一般都是将算法中的参数由固定不变模式改为动态调整模式的改进策略, 采用参数自适应的优化方法来影响蚁群算法的行为, 用较少的实验次数和成本来获取比较好的参数配置. 在考虑蚁群算法对不同问题的不同变化时, 参数值自适应的主要方法有预先设定参数的变化[
ACO的关键参数
参数 | 定义 | 描述 |
|
启发式函数 | 蚂蚁在每一步移动的最佳路径, 计算为从节点 |
|
信息素强度 | 节点( |
信息素影响因子 | 信息素轨迹的相对重要程度, 反映了蚂蚁在选择路径时积累的信息素的影响程度. |
|
启发式函数影响因子 | 能见度的相对重要程度, 反映了蚂蚁在运动过程中启发信息(两个节点位置之间的距离)在蚂蚁选择路径中的影响程度. |
|
信息素挥发系数 | 这个系数控制信息素挥发的速度. |
首先通过介绍一个著名的双桥实验, 来说明信息素的作用机制和对路径选择的影响. 这个实验是Goss等人[
从实验中得出, 90%以上的实验运行中, 大部分蚂蚁(80%–100%)的流量最终集中在短分支上, 数据如
方案2中如
方案1
方案2
大多数蚂蚁继续选择长路径的现象可以用两个原因来解释: 长路径上信息素浓度高和信息素蒸发缓慢. 首先, 即使提供了一个更短的路径, 长路径上的高水平信息素浓度(与短分支上的信息素浓度相比)导致了一种自催化行为, 会继续强化长路径. 其次, 缓慢的信息素蒸发速率不会使蚁群忘记他们最初选择的次优路径, 从而阻止了新的和更短的路径被发现和学习.
因此, 信息素浓度和信息素蒸发速率是这个过程中的关键参数, 因为它们控制了新的(希望是更好的)路径的路径探索和已经建立的路径的路径开发之间的权衡.
传统的ACO算法中, 初始阶段主要使用固定数量的信息素来更新, 这就造成了蚂蚁在对初始路径的搜索中缺乏信息素有一定的盲目性, 忽略了解的分布特征, 从而使算法收敛缓慢.
为使算法在初始阶段能够具有良好的搜索性能, 乔东平等人[
陈颖杰等人[
Ning等人[
Luo等人[
针对ACO初始阶段缺乏信息素和收敛缓慢的缺点, Fei等人[
传统的ACO算法主要使用固定数量来更新信息素, 正反馈会加速算法的收敛速度, 使蚂蚁沿着特定的路径移动, 失去探索其他潜在路径的能力, 使算法易于陷入局部最优, 从而导致过早收敛.
Gao[
顾竞豪等人[
Ekmekci[
传递函数
上述文献大多数都是对信息素更新进行动态调整或在信息素初始分布阶段进行调整, 仍然属于单一正反馈机制下的改进. 然而过度使用正反馈机制来提高收敛速度仍然存在容易获得局部最优解而不易跳出的问题, 如果正反馈信息素过度集中在良好路径上, 来引导大量蚂蚁选择高信息素路径, 导致其他信息素边缘被选择的概率降低, 即探索未知区域的概率可以忽略不计.
针对正反馈机制对算法的影响, Ye等人[
冯振辉等人[
上述文献都在一定程度上避免算法陷入局部最优解等缺点上进行了相关改进, 主要是通过改进信息素更新规则和算法的启发式信息来有效地提升算法的收敛速度等, 但引入启发式信息可能会造成算法规模和复杂度的增加. 单策略的改进模式不够满足现在问题对算法的要求, 大部分学者对路径构建和信息素进行多策略的改进方法, 通过对初始信息素分布、路径选择概率、信息素更新等几个方面的改进来提高算法的求解性能和求解效率. 此外还有众多针对信息素调整策略的改进算法被不断提出. 如采用信息素二次更新策略[
另一种算法的最近的趋势是蚁群算法与其他优化算法的结合. 由于蚁群算法优良的分布式并行计算特性, 使其易于与其他优化方法相结合, 他们都试图将原始算法组合后的最佳特征进行挖掘, 融合后的优化算法在寻找最佳路径的过程中能够同时兼顾全局和局部, 增强了算法对解决优化问题的整体性能, 研究者们对蚁群算法与其他算法的融合方面展开了大量的研究工作.
遗传算法和蚁群算法可以在可接受的时间内找到高质量的解决方案, 很多研究者利用遗传算法交叉、变异和较强的全局寻优能力和蚁群算法的正反馈、分布式、并行计算机制进行结合来克服各自缺陷进行优势互补, 融合成新的混合启发式算法. Aydoğan等人[
每只蚂蚁获得的旅行染色体演示
但是这种先蚁群后遗传的静态融合算法中具有MMAS对种群的影响会随遗传代数增加而减少的局限性. Chen等人[
虽然粒子群算法(PSO)和蚁群算法通常能找到较好的TSP的解, 但它们的解仍然受到随机初始化种群和参数配置等因素的影响. Mahi等人[
Stodola等人[
由于某些边缘上的高信息素轨迹可能会导致算法的快速收敛并进入局部最优, Zhang等人[
由于MMAS的性能很大程度上受相关参数的影响, 而共生生物搜索算法(SOS)本身不包含参数, 因此, Sheng[
虽然一般的ACO算法能够给出高质量的解, 但是在某些情况下, 混合算法被证明也是必要的, 能够与蚁群算法融合的算法还包括萤火虫算法[
蚁群算法在解决实际优化问题中的改进策略在不断被研究者们提出, 使算法的模型越来越丰富和完善. 并且随着对蚁群算法的不断深入研究和改进, 使其从最开始应用于经典的TSP求解最短路径问题, 到求解各领域的优化问题以及具有不同边界条件的优化问题. 使其功能更强大、应用领域更广泛. 而不同的应用场合各具有不同的特点和需求,
在企业生产中常遇到的车间调度问题(job-shop scheduling problem, JSP)[
车辆路径问题(vehicle routing problem, VRP)[
机器人路径规划问题[
目前蚁群算法的研究大多针对与二维平面的路径规划, 对三维空间的研究相对较少, 如将蚁群算法应用于无人机三维路径规划[
虽然在上述文献中针对TSP问题提出了诸多不同版本的改进蚁群算法, 但这些改进算法主要包括3个方面: 首先, 路径选择是蚁群算法的一个重要组成部分, 因此许多研究者关注蚂蚁的状态转移规则设计[
改进蚁群算法的方法及优缺点
改进类型 | 改进措施 | 文献 | 优点 | 缺点 |
状态转移规则 | 动态运动概率规则 | [ |
提高全局寻优能力, 扩大搜索空间 | 搜索时间较长, 优化效率不高 |
伪动态搜索机制 | [ |
|||
路径构建 | 基于状态空间探索 | [ |
通过种群的平衡控制搜索的平衡 | |
反向路径构造 | [ |
不局限于局部最优解, 避免过早收敛 | 信息素更新复杂, 适应性比较局限 | |
参数选择与优化 | 枚举法实验分析不同参数配置 | [ |
得到不同参数配置对算法结果的影响 | 没有找到设置最优参数的方法 |
结合其他方法得到最优参数配置 | [ |
用较少的实验次数和成本获取比较好的参数配置 | 没有分配参数的理论依据 | |
参数动态自适应 | [ |
|||
信息素初始化 | 非均匀分布初始信息素浓度 | [ |
使信息素的分布在搜索初期就起到指导作用 | 不利于搜索多样性, 易限于局部最优 |
次优路径构建初始分布 | [ |
|||
信息素更新策略 | 信息素自适应调整 | [ |
解决了扩展搜索与寻找最优解之间的矛盾 | 算法结构复杂, 长时间搜索, 降低了收敛速度 |
信息素平滑机制 | [ |
解决算法的停滞状态 | ||
增加信息素多样性 | [ |
避免过早收敛 | ||
带导向信息素 | [ |
加强全局寻优能力 | ||
用不同传递函数更新信息素 | [ |
提高探索能力和开发能力 | ||
增强负反馈机制 | [ |
抑制算法向局部最优的收敛速度 | ||
增强最优路径信息素浓度 | [ |
提高收敛速度和精度 | 易限于局部最优 | |
融合蚁群算法 | 初始解构建初始路径分布 | [ |
使算法在初始阶段就具有良好的搜索性能 | 增加了算法的复杂度, 需要更长的执行时间 |
改变信息素分布或更新规则 | [ |
提高了寻优能力和搜索效率 | ||
优化参数 | [ |
使算法具有较好的优化效果和较强的鲁棒性 | 参数变化规律缺乏通用性 |
由于文献中通过蚁群算法解决NP困难问题的初步结果令人鼓舞, 尽管蚁群算法没有为这类问题提供最佳的解决方案, 但它仍然在算法和应用学科的进一步研究中发挥着重要作用.
改进传统算法或者探索新的融合算法已成为当前研究的重点, 未来的研究还应包括对最近的启发式技术和仿生技术等算法的融合等. 其他未来工作可能包括调查蚂蚁的数量和最近邻集如何影响算法的性能; 预测蚂蚁行为从好到差的波动对算法性能的影响等都是值得研究的, 并将所提出的算法扩展到TSP问题的其他变化.
Huang L, Wang GC, Bai T,
Dorigo M, Birattari M, Stutzle T. Ant colony optimization. IEEE Computational Intelligence Magazine, 2006, 1(4): 28–39, doi: 10.1109/MCI.2006.329691.
Goss S, Aron S, Deneubourg JL,
Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29–41.
Stützle T, Hoos HH. MAX-MIN ant system. Future Generation Computer Systems, 2000, 16(8): 889–914.
Bullnheimer B, Hartl RF, Strauss C. An improved Ant System algorithm for theVehicle routing problem. Annals of Operations Research, 1999, 89: 319–328.
Escario JB, Jimenez JF, Giron-Sierra JM. Ant colony extended: Experiments on the travelling salesman problem. Expert Systems with Applications, 2015, 42(1): 390–410.
Duan P, Yong AI. Research on an improved ant colony optimization algorithm and its application. International Journal of Hybrid Information Technology, 2016, 9(4): 223–234.
Rokbani N, Kumar R, Abraham A,
Mavrovouniotis M, Yang SX. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Applied Soft Computing, 2013, 13(10): 4023–4037.
Chowdhury S, Marufuzzaman M, Tunc H,
王原, 陈名, 邢立宁, 等. 用于求解旅行商问题的深度智慧型蚁群优化算法. 计算机研究与发展, 2021, 58(8): 1586–1598.
Zhang ZJ, Xu ZX, Luan SY,
吴春明, 陈治, 姜明. 蚁群算法中系统初始化及系统参数的研究. 电子学报, 2006, 34(8): 1530–1533.
et al. Variation of ant colony optimization parameters for solving the travelling salesman problem. Proceedings of the 2017 IEEE 4th International Conference on Soft Computing & Machine Intelligence (ISCMI). Mauritius: IEEE, 2017. 60–65.]]>
向永靖. 蚁群算法中参数设置的研究——以TSP为例. 现代信息科技, 2020, 4(22): 95–98, 102, doi: 10.19850/j.cnki.2096-4706.2020.22.025.
Gan Y, Lan LW, Li S. Study on parameters configuration for ant colony optimization. Advanced Materials Research, 2011, 279: 371–376.
Peker M, Şen B, Kumru PY. An efficient solving of the traveling salesman problem: The ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, 2013, 21(7): 2015–2036.
Wang Y, Han ZP. Ant colony optimization for traveling salesman problem based on parameters optimization. Applied Soft Computing, 2021, 107: 107439.
Salem A, Sleit A. Analysis of ant colony optimization algorithm solutions for travelling salesman problem. International Journal of Scientific & Engineering Research, 2018, 9(2): 570–575.
Merkle D, Middendorf M, Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333–346.
李万庆, 李彦苍. 求解复杂优化问题的基于信息熵的自适应蚁群算法. 数学的实践与认识, 2005, 35(2): 134–139.
Cai ZQ, Huang H, Qin Y,
et al. Performance evaluation of an adaptive ant colony optimization applied to single machine scheduling. Proceedings of the 7th Asia-Pacific Conference on Simulated Evolution and Learning. Melbourne: Springer, 2008. 411–420.]]>
乔东平, 裴杰, 李浩, 等. 改进蚁群算法求解TSP问题研究. 机械设计与制造, 2019, (10): 144–149, doi: 10.3969/j.issn.1001-3997.2019.10.036.
陈颖杰, 高茂庭. 基于信息素初始分配和动态更新的蚁群算法. 计算机工程与应用, 2022, 58(2): 95–101.
et al. A best-path-updating information-guided ant colony optimization algorithm. Information Sciences, 2018, 433–434: 142–162.]]>
Luo Q, Wang HB, Zheng Y,
Fei T, Wu XX, Zhang LY,
Gao W. Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem. Soft Computing, 2021, 25(4): 3263–3289.
顾竞豪, 王晓丹, 贾琪. 求解大规模TSP问题的带导向信息素蚁群算法. 火力与指挥控制, 2018, 43(8): 111–115.
et al. Ant-colony algorithm with a strengthened negative-feedback mechanism for constraint-satisfaction problems. Information Sciences, 2017, 406–407: 29–41.]]>
Li J, Xia Y, Li B,
许凯波, 鲁海燕, 程毕芸, 等. 求解TSP的改进信息素二次更新与局部优化蚁群算法. 计算机应用, 2017, 37(6): 1686–1691.
Liang BL, Yang ZM, Qin Y,
马学森, 宫帅, 朱建, 等. 动态凸包引导的偏优规划蚁群算法求解TSP问题. 通信学报, 2018, 39(10): 59–71.
Aydoğan T, Al-Badri R. A hybrid model of max-min ant system with genetic algorithm for improved to travelling salesman problem. International Journal of Engineering and Technology, 2018, 10(3): 254–258.
陶丽华, 马振楠, 史朋涛, 等. 基于TSP问题的动态蚁群遗传算法. 机械设计与制造, 2019(12): 147–149, 154, doi: 10.3969/j.issn.1001-3997.2019.12.037.
Mahi M, Baykan ÖK, Kodaz H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem. Applied Soft Computing, 2015, 30: 484–490.
Rokbani N, Kromer P, Twir I,
Stodola P, Michenka K, Nohel J,
Zhang XX, Shen X, Yu ZQ. A novel hybrid ant colony optimization for a multicast routing problem. Algorithms, 2019, 12(1): 18, doi: 10.3390/a12010018.
Sheng YF. A computational optimization research on ant colony optimization for the traveling salesman problem. Journal of Physics: Conference Series, 2022, 2258: 012006.
杜力, 徐光辉, 汪繁荣. 自适应萤火虫算法改进蚁群算法的移动机器人路径规划. 河南理工大学学报(自然科学版), 2022, 41(2): 124–130, doi: 10.16186/j.cnki.1673-9787.2021010073.
张烈平, 何佳洁, 于滟琳, 等. 基于蚁群算法优化的布谷鸟搜索算法. 微电子学与计算机, 2018, 35(12): 21–26, doi: 10.19304/j.cnki.issn1000-7180.2018.12.005.
Nazif H. Solving job shop scheduling problem using an ant colony algorithm. Journal of Asian Scientific Research, 2015, 5(5): 261–268.
Deepalakshmi P, Shankar K. Role and impacts of ant colony optimization in job shop scheduling problems: A detailed analysis. Evolutionary Computation in Scheduling, 2020, 11–35.
蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展. 电子学报, 2022, 50(2): 480–492.
刘紫玉, 赵丽霞, 薛建越, 等. 面向车辆路径问题的改进蚁群算法研究. 河北科技大学学报, 2022, 43(1): 80–89.
Miao CW, Chen GZ, Yan CL,
http://kns.cnki.net/kcms/detail/41.1227.tn.20220517.1822.002.html. [2022-09-06].]]>
陈超, 张莉. 基于改进蚁群算法的三维路径规划. 计算机工程与应用, 2019, 55(20): 192–196.