区域破坏重建的蚁群优化算法

周克良，龚达欣，张宇龙

江西理工大学 电气工程与自动化学院，江西 赣州 341000

1 引言

在众多智能优化算法中，蚁群算法是最成功的算法之一[1]。该算法最先由意大利学者Dorigo于20世纪90年代初提出，首先用于求解著名的旅行商问题（Traveling Salesman Problem，TSP）并取得很好的效果[2]。Dorigo等学者对其的通用性和适用性进一步优化，并对此类框架的算法称为蚁群算法（Ant Colony Optimization，ACO）[3]。蚁群算法具有较强的全局搜索能力、潜在的并行性、自学习能力、易于实现和较强的鲁棒性等特点，被广泛应用于旅行商[4]、多维背包[5]、车辆调度[6]、图像处理[7]和多目标组合优化[8]等问题。但是，基本蚁群算法也存在着缺点，如算法收敛速度慢、收敛精度低等。

针对基本蚁群算法的不足，国内外学者主要在信息素的释放和更新、路径选择和优化、参数的选择和计算效率等方面进行改进。文献[9]提出的方向素协调的蚁群算法，在信息素的释放和更新以及路径的选择方面进行优化，在提升收敛速度的同时增强了全局搜索能力。文献[10]提出面向对象的多角色蚁群算法，利用k-means聚类和TSP的空间信息将城市分类提高收敛速度，并利用精英策略与2-Opt对信息素和路径进行更新优化，提高了蚁群算法收敛精度和鲁棒性。文献[11]提出启发式动态信息素更新策略的蚁群算法，随迭代次数动态调整蚁群算法中的伪随机因子参数并改进信息素的更新规则，增加了解的多样性因此提高了收敛精度。文献[12]提出基于蚁群优化的并行协作混合算法，使用3-Opt算子进行路径优化以避免算法收敛陷入局部最优解从而提高算法收敛精度，并通过并行协作的方式对多个菌落并行计算提升收敛速度。文献[13]提出了一种基于蚁群算法、粒子群算法和k-Opt的求解TSP的混合算法，利用蚁群算法生成初始群粒子群对群算法进行粒子群优化，使算法在寻找最优路径在准确率和运行时间上都有较大提高。文献[14]提出了一种改进的蚁群算法，根据路径中信息素堆积的程度，调节路径中允许通过蚂蚁数量的最大值以避免陷入局部最优的情况并在路径选择方面应用2-Opt算法进行优化，算法的收敛精度和速度相较于基本蚁群算法有较大提升。文献[15]提出一种新的强化信息素更新机制和新颖的信息素平滑机制，利用动态信息进行路径优化并在停滞状态时重新初始化信息素矩阵，增强了信息素边缘信息和全局搜索能力使算法在解的多样性和收敛性方面均有较好的提升。文献[16]提出了一种基于动态局部搜索的蚁群算法，增加每个蚁群的局部搜索能力并以动态策略更新信息素，提高算法的搜索质量和稳定性。

上述算法对蚁群算法本身的参数、信息素更新规则、路径选择等方面进行优化或结合其他启发式算法，在某些方面确实产生很好的效果，但仍存在着问题。文献[10]依赖于k-means聚类和分类的精度，算法提升收敛速度不明显，且在TSP数据过大时产生局限性。文献[11]伪随机因子和动态信息素更新策略在收敛速度和收敛精度上都有提升，但其提升效果不明显且算法鲁棒性降低。文献[13]通过并行计算和3-Opt优化，在收敛速度上有较大提升，但是仅仅依靠3-Opt算子的优化使得算法在收敛精度上提升并不明显。

针对在提升收敛速度的同时提高收敛精度和鲁棒性的问题，本文提出区域破坏重建的蚁群优化算法，其主要思想是：（1）局部优化：选取每次迭代后的精英路径对其采用2-Opt算子优化，在增加解的多样性的情况下，提高收敛精度并通过设置算法的截止条件加快收敛速度。（2）改进信息素的更新规则：信息素更新路径的选取采取优胜劣汰的方式进行以提高收敛速度，同时利用路径的收敛情况动态改变信息素保持系数增加算法的全局搜索能力。（3）区域破坏重建：对陷入局部最优解的蚁群路径采取区域破坏重建方式来破坏由信息素堆积而引起的局部最优解，再以插入法重建路径达到少量增加算法时间复杂度的代价，大幅度提高收敛精度和鲁棒性。

2 基本蚁群算法

基本蚁群算法是由Dorigo等受真实蚂蚁觅食行为的启发，提出的一种智能优化方法。原理是利用一群人工蚂蚁来模拟真实蚂蚁进行觅食，人工蚂蚁改变其经过路径上存储的数字信息，碰到从未经过的路口就随机选其后的人工蚂蚁根据残留在其路径上的数字信息选取路径，导致最优路径上面的数字信息增大，人工蚂蚁增多从而产生最优路径。

路径的选择和信息素的更新依照公式（1）～（4），其中τ为信息素，η为启发信息，α为信息素启发因子，β为期望启发因子，N为城市个数，m为蚂蚁个数，Nik为未经过的城市组成的集合，ρ为信息素的保持系数。

第K只蚂蚁当前所在的节点为i，从i到节点 j的概率如式（1）所示：

第K只蚂蚁在途(i,j)上所留下的信息素如式（2）所示：

3 求解TSP的RDRACO算法

相对于基本的ACO，RDRACO主要有3点优化：（1）引入区域破坏重建。对于陷入局部最优的蚁群路径进行区域破坏重建，提高收敛精度。（2）局部优化。使用2-Opt算子对每次迭代后的前20%路径进行优化，加快收敛速度和提高收敛精度。（3）改进信息素更新规则。选取前六和后三的路径进行信息素的更新，根据路径的收敛情况改变信息素保持系数，充分利用路径信息。

3.1 区域破坏重建

破坏重建法（Ruin and Recreate，R&R）是由德国学者Schrimpf G等[17]提出的一种全新的启发算法，特别适用于不连续、目标复杂或约束较多等优化问题。借鉴R&R算法的构造思路并结合蚁群算法的思想，对R&R算法进行改进使其更加匹配本文算法。区域破坏重建算法主要由破坏和重建两部分组成。

3.1.1 破坏

针对完整的路径做空间破坏或者空间消除，采取半径破坏（Radius Ruin）的方法，对完整的路径进行破坏：全部N个节点中，选择一个节点C作为圆心，根据公式（5）随机生成的距离数据R选取距离矩阵D中与节点C距离小于R的节点集，并和点C并为点集S_Ruin作为移除的部分。移除的点都处于点C的附近，因此Radius Ruin在策略上属于局部性破坏，不会对算法本身产生影响。

原圆心选取公式：

原破坏半径公式：

在公式（5）、（6）中I为迭代次数，N 为城市个数，Min_L为距离矩阵中最小值即任意两个节点之间最短距离，Max_L为距离矩阵中的最大值即任意两个节点之间最长距离。

圆心选取公式（5）在圆心的连续选取上没用充分利用破坏半径公式（6）所产生的区域节点破坏，导致选取同一区域的节点为圆心，对一定区域的节点进行多次破坏和重建，大幅度增加了区域破坏算法的运行时间。因此对圆心的选取公式进行改进，利用破坏区域内的节点减少圆心节点的选取范围以降低运算资源的浪费从而提升区域重建的速度。

改进圆心选取公式：

其中，P为最优路径的节点集合，S_Ruin为被破坏区域的节点集合。

原破坏半径公式（6）在 rand=0时，产生 Rmin=0.45Min_L的最小半径，运行的区域破坏只对圆心点进行破坏，没有达到区域破坏的目的导致浪费运算资源；半径公式会在rand=1时，产生Rmax=0.45Max_L的最大半径，运行的区域破坏在节点区域上与较小破坏半径的节点区域有较大的重叠部分，同样区域多次进行破坏重建存在运算资源的浪费。Rmax过大导致一次破坏过多的节点会大幅度增加区域重建的时间。因此对破坏半径公式的选取范围进行改进，以降低运算资源的浪费并提升区域重建的速度。

改进破坏半径公式：

3.1.2 重建

针对破坏后所留下的不完整路径，采用插入法对被移除的节点一一插入破坏路径以使路径完整：原始路径经过破坏后产生两个节点的集合S_Ruin（被破坏区域的节点集合）和S_Tour（未经破坏区域的节点集合），在重建时采用插入法将S_Ruin中的元素通过整体最短距离的方式一一插入到S_Tour中，直到S_Ruin中元素为0为止。区域破坏重建算法运行过程如图1所示。

图1 破坏重建示意图

算法详情：

步骤1按照式（7）选取本次迭代最优路径P中的节点C作为圆心，依据式（8）确定破坏半径。

步骤2根据破坏半径和距离矩阵确定破坏区域的节点集S_Ruin，并消除与之相连的连接线。

步骤3采用插入法将被移除的节点集S_Ruin中的元素通过整体最短距离的方式一一插入到节点集S_Tour中，直到S_Ruin中元素为0为止。

步骤4在最优路径P中剔除节点集S_Ruin，并判断P中的元素个数是否为0，若是则结束；否则执行步骤1。

3.2 局部优化

算法迭代一定次数后，较短的路径上容易产生信息素堆积现象，使后续的蚁群选择堆积路径，减少全局搜索而产生局部最优解。局部最优解大多伴随着路径交叉现象，如图2中原始路径所示情况。综合考虑文献[18]中2-Opt和3-Opt搜索所用的时间、收敛效果，本文引用2-Opt算法进行路径优化，解决因路径信息素堆积所产生的点交叉现象，加快收敛的速度并提高收敛精度。

图2 2-Opt示意图

可以看出图2中原始路径存在路径交叉现象，节点序列为a→b→e→d→c→f→g，经过2-Opt算子对原始路径进行点交换优化，优化路径节点序列为a→b→c→d→e→f→g消除路径交叉现象，缩短路径距离。

2-Opt算子时间复杂度较高，因此仅采取排序的方式选取蚁群算法每次迭代前20%的路径进行优化以减少2-Opt算子对收敛速度的影响并有效地提高算法的收敛精度。

3.3 改进的信息素更新

基本蚁群算法的单位信息素Δτ采用的是所有的人工蚂蚁在完成一次迭代后的总和进行更新，这样更新的信息素忽略了太多的路径信息，导致收敛速度较慢、收敛精度差等情况。

对此，本文采用优胜劣汰的方法进行信息素的更新，在每次迭代后对路径进行排序，选取前六和后三的路径进行信息素的更新如式（10）所示。当出现和上次迭代最优路径大小相同时，改变信息素的挥发因子如式（9）所示。优胜劣汰的信息素处理方式，充分地利用了路径信息，较好地提高了收敛速度和算法的求解质量。具体的更新方式如下：优距离，为排序前六的路径信息素的变化之和

ρ为信息素的保持系数，L_best(t+1)为后一次迭代的最为排序后面三个路径的信息素变化之和。

4 仿真实验及结果分析

为了验证RDRACO算法的有效性，实验采用TSPLIB中的20个经典TSP数据集对RDRACO算法进行仿真，实验环境为Windows 10 64位系统，CPU i5-8300H 2.3 GHz，Matlab 2016b软件。算法的流程图如图3所示。

4.1 优化方案分析

ACS[19]是基于ACO改进的一种模型，其在收敛精度和收敛速度上达到了较好的平衡。本文RDRACO相对于基本的ACO主要有3点优化，按照基本ACO和不同的优化相结合分别生成优化方案B和优化方案C并与ACS在收敛精度上进行对比，优化方案的组合和编号如表1所示。

表1 优化方案编号表

优化方案的仿真实验从20组数据集中选取较为经典的数据集att48，eil51，kroA100，bier127，kroA200，ts225共6组数据集。每组数据集都采用三种方案优化方案进行5次寻优实验，寻优实验的结束条件为达到最大迭代次数或连续30次迭代最优解相同。从5次寻优实验中选取最小值作为每组数据和实验优化方案的最优解并根据获取的实验数据求解5次实验的平均值，通过已知的数据集最优解得出相对误差、平均误差，实验结果如表2所示。

图3 算法流程图

表2 优化方案数据对比表

实验RDRACO算法的参数设定为：城市规模n从数据中读取，蚂蚁个数m=round(n/1.5)，信息素重要程度参数Alpha=1.5，启发式因子重要程度参数Beta=4，信息素增加强度系数Q=100，最大迭代次数NC_max=1 000。

从表2可以看出，优化方案A求解TSP问题不论是收敛精度还是鲁棒性上都不是很理想，在较少的数据集att48上都存在2.56%的相对误差，平均误差也达到3.99%。

从优化方案B的实验数据可以看出，对基本ACS的信息素更新规则和路径2-Opt进行优化后，无论是收敛精度还是鲁棒性都得到了极大的提高。在数据点小于100的情况下采用优化方案B可以得到数据集已知的最优解，在数据较大时也有较好的优化。

从优化方案C的实验数据可以看出，在方案B的基础上加入区域破坏重建，明显地提高了在数据集100～200的全局最优解的搜索能力，在数据集小于200的情况下可以得到数据集已知的最优解，且鲁棒性也进一步提升。

4.2 收敛情况分析

为了确定RDRACO算法在TSP问题上的收敛精度，选取来源于TSPLIB[20]标准库中的20组TSP实例数据进行本次实验分析。从数据库中找出20组TSP实例已知的最优解作为标准与本次实验算法所求数据进行比较得出相对误差。

由以往的文献总结可得，ACS算法在寻优过程中，其寻优的结果集精确度在很大程度上都会受到数据类型及数据点数量的影响。由表3分析可得，ACS算法随着数据点数量的增大，寻优的精确度并不是很理想，ACS算法在样本数量及类型为berlin52时，精度可高达99.36%，在样本数量及类型为rat783时，精度仅有82.1%。而本文所提出的RDRACO算法虽然也会受到数据类型及数据点数量的影响，但是在数据点数量小于等于200时，其精度可高达100%，当寻优数据点数量在200到800范围内，其精度最低可达97.51%，最高精度仍可维持在100%。在实验仿真过程中，RDRACO算法相对于ACS算法收敛速度较快、收敛精度及鲁棒性显著提高。

为查验RDRACO实验仿真结果中是否还存在点交叉或明显的可交换现象，选取TSP实例中部分不同类别、数据点数的RDRACO仿真实验结果图进行验证，如图4所示。

结合表3中RDRACO的收敛数据和图4中的图形可以证明，本文利用局部优化、改进的信息素更新规则和破坏重建所优化的ACO算法在精确度方面得到了很大的提高。

5 结束语

图4 RAR最优路径

表3 收敛情况表

针对传统蚁群收敛速度慢、易陷入局部最优等问题，提出区域破坏重建的蚁群优化算法（RDRACO）。RDRACO充分利用每次迭代产生的路径信息对信息素更新规则和全局更新策略进行了调整，极大程度上提升收敛速度。RDRACO引入2-Opt进行部分路径优化，在少量增加时间复杂度的情况下极大减小迭代次数明显提高收敛速度。适时的插入破坏重建算法有效地提升了算法的收敛精度。实验结果表明，RDRACO算法对收敛精度有显著影响，在处理数据点少于200的TSP可以寻找到其最优路径并在数据点增多时也具有优秀的搜索能力，整体来说RDRACO具有较高的精度和鲁棒性。