基于种群相似度的自适应改进蚁群算法及应用

张松灿，普杰信，司彦娜，孙力帆

1.河南科技大学 信息工程学院，河南 洛阳471000

2.河南科技大学 电气工程学院，河南 洛阳471000

蚁群算法是意大利学者Dorigo 等受自然界蚂蚁群体的觅食行为启发而提出的启发式搜索算法，具有并行计算、正反馈、鲁棒性好、全局搜索能力强等优点[1]，并广泛用于各种组合优化问题。经过学者们的深入研究与不断探索，蚁群算法在指派问题（Assignment Problem）[2]、调度问题（Scheduling Problem）[3]、连续优化（Continuous Optimization）[4]、约束满足问题（Constraint Satisfaction Problems）[5-6]以及参数优化[7]等领域也得到成功应用，但是在求解过程中存在效率低、收敛速度慢及易陷入局部最优值等不足。

针对这些问题，许多学者提出了许多富有成效的改进策略，如ACS[8]、MMAS[9]、带精英策略的蚂蚁系统（Ant System with elitist strategy，ASelite）[10]、基于排序的蚂蚁系统（Ant System with elitist strategy and ranking，ASrank）[11]等改进算法，但是这些方法是从蚁群的基本框架和结构上进行改进，依然存在收敛速度与早熟收敛的矛盾。

除前述的结构改进外，蚁群算法的参数对其优化性能有重要的影响，也是蚁群算法的研究热点。文献[12]分析了蚁群算法参数之间的关系，并针对所研究问题给出了参数值的优化组合。由于蚁群优化（Ant Colony Optimization，ACO）算法参数众多且存在紧密的耦合作用，通常是根据实验者的个人经验和大量的前期实验给出算法参数，这种方式效率较低，适应能力差。为了避免反复试凑进行参数取值的耗时工作，文献[13]提出一种基于粒子群优化（Particle Swarm Optimization，PSO）与ACO 的融合算法，通过粒子搜索自动选取参数值的优质组合，仿真实验验证了算法的有效性，但是在优化过程中，粒子群算法将重复调用蚁群算法，时间开销较大，此外不同的实例具有不同的最佳参数组合，算法缺乏适应性。文献[14]通过粒子群算法来优化蚂蚁子群的参数，更好地控制蚂蚁子群的开发能力和探索能力。针对多次调用蚁群算法存在时间开销较大的问题，文献[15]采用全局异步与精英策略相结合的信息素更新方式，有效减少蚁群算法被粒子群算法调用一次所需的迭代代数，但是选取的参数缺乏适应能力。上述研究均采用静态参数，在算法运行前通过大量实验找到合适的参数组合，虽然能取得较好的优化结果，但是参数与具体问题密切相关，适应能力较弱。

事实上，蚁群算法的优化过程是动态的，不同的运行阶段有不同的优化需求，如起始阶段希望在更广泛的问题空间构建候选解，增大得到最优解的概率，而在优化后期，希望加快算法的收敛速度，进一步提高解的精度，所以前述的静态参数组合不适合搜索过程各个阶段。如果在算法运行时能改变算法参数，适应不同的优化目标，将有助于进一步增强算法的优化能力。

文献[16]提出了一种自适应调节信息素挥发系数的方法来平衡算法全局性和收敛速度之间的矛盾。文献[17-18]通过设定迭代阈值，自适应调节信息素挥发系数解决全局寻优能力与收敛速度的矛盾，在保证算法收敛速度的条件下提高解的全局性。文献[19]采用参数自适应伪随机转移策略，算法前期q0取值较大使得蚂蚁根据全局路径信息选择有利路径，后期q0取值较小有利于蚂蚁随机搜索，避免算法停滞。文献[20]采用自适应状态转移策略和自适应信息素更新策略来改进蚁群算法，确保信息素强度与期望在算法进化过程中的相对重要性，提高了算法的全局搜索能力。卜新苹等[21]为了提高蚁群算法接受随机解的概率，跳出局部最优，自适应改变算法q0的取值。为了避免陷入局部最优，文献[22]采用动态调整信息素启发因子与期望启发因子的策略进行算法改进，有效减少了蚂蚁前期到达最优路径的迭代次数，但是动态调整策略需要人为设定算法的运行状态，缺乏灵活性。这些改进方法是根据蚁群算法不同阶段的期望目标来动态调整算法参数，用较小的计算负担提高优化能力，但是需要事先设定参数的调整规律，缺乏适应能力。

文献[23]设定迭代阈值来判断是否陷入局部最优，进而调整信息素挥发系数和信息素浓度，使算法在迭代后期依然具有较强的搜索能力，但是迭代阈值的引入使算法缺乏适应能力。文献[24]提出一种基于聚度的自适应动态混沌蚁群算法，在迭代前期利用种群聚度衡量种群的分布情况，自适应地更新局部信息素，平衡了多样性和收敛性之间的矛盾，但是需要人为设定迭代阈值与聚度阈值，缺乏适应能力。文献[25]采用信息熵描述每一条边上信息素的不确定性，采用种群信息熵来衡量算法的进化程度，自适应地调整路径选择策略和信息素更新策略，但是引入的新参数增加了参数整定的复杂度。

通过对蚁群算法优化过程的分析，候选解的分布特征不仅会随着迭代数发生变化，还与算法的优化过程有关。一般来说，在优化起始阶段，由于均匀分布信息素，候选解尽可能地分布在问题空间，种群个体多样性较好，相似度较低；随着迭代过程的进行，在正反馈的作用下，候选解快速地集中在最优解或次优解附近，多样性变差，个体间相似度较高。蚁群算法的全局寻优性要求蚁群在问题空间尽可能地进行随机搜索，增大找到全局最优解的概率，而蚁群算法的快速收敛性要求蚁群尽可能在潜在的较优区域进行搜索，二者对蚁群算法性能的影响既矛盾又密切相关。为此，提出了一种基于种群相似度的自适应改进蚁群算法，首先利用种群相似度对种群多样性进行度量，并根据优化过程中种群相似度的变化自适应地调整蚁群算法状态转移规则的控制参数和信息素更新策略，在加快算法收敛速度的同时防止陷入局部最优，有效地平衡了种群多样性与收敛速度的矛盾。

1 蚁群算法简述

蚁群系统[8]是蚁群优化算法中的经典算法，它改进了蚂蚁系统（Ant System，AS）的状态转移规则和信息素更新方法，利用最优选择和随机选择相结合的伪随机比例规则选择下一个节点，信息素更新采用局部和全局更新相结合的方式，不仅提高了算法多样性，还加快了算法的收敛速度。

1.1 状态转移规则

状态转移规则是蚁群算法在解空间构建候选解的依据，蚁群系统利用最优选择和随机选择相结合的伪随机方式选择下一个节点，节点选择规则如公式（1）和（2）所示：

式中，s表示选择的下一节点，τij为边(i,j)上的信息素值，用来记录积累的经验信息，ηij=1/dij为从节点i转移到节点j的启发信息，dij表示节点i到节点j的距离，allowedk为蚂蚁k下一步允许访问的节点集合，α和β分别表示信息素和启发信息在构建候选解时的相对重要程度。q是[0,1]之间的一个随机数，q0∈[0,1]是概率选择的控制参数。

上式表明，当随机生成的数小于q0时，蚂蚁选择信息素和启发式因子综合因素最大的节点，否则按照pkij进行计算各个可行节点的选择概率，然后按照轮盘赌方法选择下一节点。可知，ACS 通过参数q0来调整算法探索与利用的比例，当q0越大时，后续蚂蚁越有可能接受先行蚂蚁的经验，否则去探索未知的问题空间。

1.2 全局信息素更新

解构建完成后需要进行信息素更新。信息素更新是蚁群的信息交流通道，反映了个体与群体之间智能行为，是蚁群算法最重要的环节。蚁群系统只在全局最优解上进行信息素增强，保证算法对最优解的持续利用，更新规则如公式（3）和（4）所示：

式中，ρ是全局信息素挥发系数，表示全局最优解上的信息素增量，Lgb是全局最优路径的长度，Tgb是全局最优路径节点序列。

由上式可知，当所有蚂蚁完成候选解构建任务后，只有最优路径上的信息素得到加强，增大后续蚂蚁选择最优路径的概率，提高算法的收敛速度。

1.3 局部信息素更新

在蚁群系统中，除全局信息素更新外，还需要局部信息素更新，以减少已访问路径被再次选择的概率，增加对未访问区域的探索。蚂蚁每选择一个新节点，就按照公式（5）进行局部信息素更新。

式中，δ是局部信息素挥发系数，τ0是信息素初始值。

2 种群相似度测量

文献[26]用个体间的汉明距离描述种群的相似度。如果个体间汉明距离小，说明个体离得近，相似度高，否则说明个体相距较远，相似度低。然而用汉明距离表示相似度时存在一些问题。对TSP问题来说，个体由节点的访问顺序组成，并不代表节点的实际位置，因此汉明距离并不能描述个体间的真实距离；此外，该方法也没有考虑问题规模。考虑到个体是由节点的访问顺序组成，那么个体间总会有一些相同的路径段，因此可采用个体间相同路径段的多少来描述个体间的相似度[27]。一般来说，个体间相同路径段的数目越多，说明个体在问题空间分布越集中，相似度就越高；反之，个体在问题空间分布更广，相似度则越低。设两个个体分别用R1(x1,x2,…,xn)和R2(y1,y2,…,yn)表示，其中n表示个体的元素数量。其相似度计算过程如下：

（1）建立个体所代表路径的连接矩阵

假设个体R1对应的连接矩阵用A表示，个体R2对应的连接矩阵为B，则有：

矩阵A中，如果R1中包含有节点i到节点j的路径段，则aij=1，否则aij=0。同理，可建立R2的连接矩阵B。

（2）根据连接矩阵A、B计算个体间相似度

如果两条路径重合的边数目越多，相似度就越高，反之，相似度就越低。极限情况下，如果两个个体的路线完全一致或者重合，则其相同的边个数为n；如果没有相同的边，则相同的边个数为0。由于TSP问题的规模不同，为使种群相似度具有可比性且能够用于下文的自适应蚁群算法，将计算出的相似度进行归一化处理，使其始终处于0～1 之间。个体R1和R2之间的相似度计算方法如公式（7）：

（3）种群相似度

种群相似度描述了种群中个体的聚集程度。采用个体与全局最优个体间的相对相似度之和的均值来描述种群的相似度，其计算方法如公式（8）所示：

其中，m是种群的大小，Rk为种群中的第k个个体，Rbest表示种群内的最优个体，mean()表示均值计算。

如果种群相似度高，说明个体集中于最优解附近，多样性较差，反之，个体分散于解空间，多样性较好。因此可用种群的相似度来衡量其多样性。

3 基于种群相似度的自适应改进蚁群算法

群智能算法在求解优化问题时，都会遇到多样性与收敛速度的矛盾，蚁群算法也不例外。加大最优解的利用，能加快算法的收敛速度，但是导致解的多样性变差，易陷入局部最优；如果算法倾向于探索问题空间，虽然可增强种群的多样性，增大找到全局最优解的可能性，跳出局部最优，但会降低算法的收敛速度。为此提出一种基于种群相似度的自适应改进蚁群算法（An adaptive improved ant colony algorithm based on population similarity，简称IAACS），利用种群相似度描述种群的多样性，并根据迭代过程中相似度的变化自动调整蚁群算法状态转移规则的控制参数和信息素更新策略，提高解的质量与算法稳定性，有效地平衡种群多样性与收敛速度的矛盾。

3.1 基于相似度的参数自适应调整

蚁群系统采用伪随机比例转移规则来构建候选解，参数q0决定蚁群系统采用最优选择方式还是随机方式构建候选解的概率。q0越大，蚁群系统倾向于最优模式构建候选解，侧重于最优解的利用，候选解比较集中，为避免算法早熟收敛，应减小q0的值；q0越小，蚁群系统倾向于随机模式构建候选解，侧重于未知空间的探索，候选解分布比较分散，为了提高算法的收敛速度，应该向信息量较大的路径上集中以加速进化速度，即增大q0。为了有效平衡蚁群算法的收敛速度与多样性的矛盾，提出一种自适应调整参数q0的伪随机比例策略。具体来说，每次迭代结束后，蚁群算法根据相似度自动调整参数q0的值，同时为了避免q0过大或者过小，还设定其上下界。

式中，q0min是参数q0的取值下限，q0max是参数q0的取值上限，Simi(P)是蚁群的相似度。

3.2 基于相似度的信息素更新策略

蚁群算法具有正反馈的特点，虽然使系统向最优解方向迅速进化，但是导致种群相似度迅速增大，易陷入局部最优，且难以跳出局部最优。由于蚁群系统的伪随机转移策略，每次迭代所获得的最优解并不相同，可能包含更优质的解成分，且与全局最优解也可能不一致。因此在全局信息素更新时，不仅考虑全局最优解的信息素增强，还应对每次迭代所得到的最优解进行增强，以提高蚁群的多样性。据此提出了根据蚁群相似度自适应调整信息素的更新策略，更新规则如公式（10）所示：

式中，ρ是全局信息素挥发系数，Simi_pop(t)是蚁群在第t次迭代后的相似度，Δτibij(t)表示迭代最优路径对应的信息素增量，Lib是迭代最优路径的长度，Tib是迭代最优路径。

在上述的信息素更新策略中，不仅对每次迭代所得到的最优解进行信息素更新，而且增强幅度与蚁群的相似度有关。蚁群的相似度越大，说明个体越集中，应加大迭代最优解的更新强度，避免早熟收敛，反之，说明候选解分布较均匀，减少迭代最优解上的更新强度，以加快算法收敛。通过这种自适应信息素更新机制，使得信息素不会过于集中或者分散，从而平衡多样性和收敛性之间的矛盾。

4 仿真实验及数据结果分析

由于TSP问题已成为测试智能算法的标准测试集，因此采用TSPLIB中的测试算例对所提出的自适应改进蚁群算法进行仿真实验，算例名称后面的数字表示TSP问题的节点数量。实验中对每个算例均独立测试10次，取其平均值作为实验结果。算法参数α、β、ρ、δ与q0等参数取值与文献[8]保持一致，如表1 所示。信息素初值τ0=(n×Lnn)-1，n为测试算例的节点数量，Lnn是按照最近邻算法得到的最优路径长度。蚁群中蚂蚁个数与算例的节点数量相等，最大迭代次数为500 次，终止条件为达到设定迭代次数。根据文献[28]确定q0的取值范围为[ ]0.4,0.9 。所有蚁群算法均采用3-Opt局部搜索方法[29]来优化蚁群的寻优结果。

表1 算法参数设置

4.1 自适应改进蚁群算法的敏感性分析

参数q0对蚁群系统的优化性能具有重要的影响。通过对比实验研究自适应改进蚁群算法的参数敏感性。首先从最优解、标准差、首遇迭代次数及成功率等指标分析改进策略对蚁群系统性能的影响。最优解反映了算法的优化能力，标准差反映了算法的稳定性，首遇迭代次数是算法首次获得已知最优解所需的平均迭代次数，成功率是算法多次运行中获得已知最优解的比例。为了说明改进算法的适应能力，选择eil51、kroB100、kroB150 以及kroA2000 等不同规模的TSP 算例进行实验，实验结果如表2～5所示。为了方便对比和深入理解q0对蚁群性能的影响，在表2～5中给出经典蚁群系统在不同q0值时的实验结果。同时还分别给出了算法在优化过程中的参数q0、相似度的变化以及最优路径的收敛曲线，如图1～4所示。

由表2和3可看出：对于小规模的TSP问题，如eil51及kroB100 测试集，ACS 算法在各个q0值均获得最优解，同时改进算法也都获得最优解。对于首遇迭代次数，eil51 在q0=0.6 时最小，kroB100 在q0=0.9 时最小；改进算法的首遇迭代次数在eil51的所有测试中虽不是最小，但排名也较靠前，在kroB100 测试中取得最小的首遇迭代次数。由图1 和2 的收敛曲线可知，随着节点规模的增大，改进算法的首遇迭代次数逐渐减小，体现出算法的寻优能力的提升。由图1、2 的相似度变化曲线可知，两种算法的相似度差别不大，改进算法的相似度略小于ACS算法。

表2 eil51算例的实验结果（已知最优解为426）

表3 kroB100算例的实验结果（已知最优解为22 141）

表4 kroB150算例的实验结果（已知最优解为26 130）

表5 kroA200算例的实验结果（已知最优解为29 368）

图1 eil51算例时q0、相似度与收敛曲线对比

图2 kroB100算例时q0、相似度与收敛曲线对比

由表4可知，对于kroB150测试集，两种算法的成功率均为50%。ACS 算法仅在q0=0.9 时获得最优解，平均值与标准差最小，在其他值时无法获得最优解。改进算法也获得最优解，虽然其标准差和平均解略大于ACS算法在q0=0.9 时的值，但在都获取最优解的前提下，改进算法的首遇迭代次数远小于ACS 算法，说明改进算法在具有较好寻优能力的前提下，具有较快的收敛速度，图3（b）的最优路径收敛曲线给出进一步的验证。由图3（a）可知，改进算法的相似度好于ACS算法，体现出自适应调整策略的作用。

图3 kroB150算例时q0、相似度与收敛曲线对比

对于kroA200测试集，由表5可知，改进算法用较少的迭代次数获得已知最优解，而ACS 算法在各个q0值均未能取得已知最优解。由图4可知，在整个迭代过程中改进算法的相似度明显小于ACS 算法，说明自适应调整策略使算法呈现较好的多样性，同时改进算法解的质量优于ACS算法。

总的来说，虽然ACS 算法在某个q0值取得了较好的性能，但是这一参数值对于不同的TSP问题缺乏适应能力，通用性较差。对于改进蚁群算法，只需要设定参数变化范围，在大多数情况下都均能取得良好的优化性能，显著提高解的质量，有效平衡多样性和收敛速度之间的矛盾，说明了自适应调整策略的有效性，同时自适应调整策略也有效降低了蚁群算法的参数敏感性，使算法具有更好的适应能力。

4.2 改进算法性能测试与分析

图4 kroA200算例时q0、相似度与收敛曲线对比

为了验证自适应改进蚁群算法的有效性及优化能力，选择与文献[24]相同的TSP测试算例进行仿真实验，并与其结果进行对比。其中，改进算法参数如表1 所示，其他算法参数见文献[24]。表6 给出了本文算法与文献[24]的求解结果。

由表6 可以看出：在解决较少节点TSP 问题（如eil51、berlin52、st70、eil76 和pr107 等）时，各算法的搜索能力均很强，但是改进算法的平均解，标准偏差优于对比算法，表明改进算法不仅寻优能力强，而且具有较好的稳定性；随着TSP 问题规模增大（如kroB150 和kroA200）时，改进算法的解质量优于对比算法，无论是最优解、最差解、平均解、标准偏差还是误差，本文算法均显示出一定优势。对于kroB200，虽然所有算法均未能找到已知最优解，但是改进算法解偏差最小，最差解、平均解、标准偏差也最小，说明改进算法具有良好的优化性能。

利用所设计的自适应改进蚁群算法对TSPLIB 中eil51、st70、eil76、pr107、ch130、kroA100、kroB150 和kroA200测试算例进行优化，各算例所获得的最优路线如图5所示。

5 结束语

本文利用种群相似度对种群内个体的多样性进行度量，根据迭代优化过程中种群相似度的变化自动调整蚁群算法状态转移规则的控制参数和信息素更新策略。通过状态转移规则控制参数的自适应调整，使得蚁群算法能够始终保持一定的探索能力，改进的信息素更新策略不仅强化了蚁群对历史最优解邻域内的搜索，而且使得算法对迭代最优解邻域进行搜索，在加快算法收敛速度的同时防止陷入局部最优，有效地平衡了种群多样性与收敛速度的矛盾。最后通过仿真实验验证了该算法的有效性。由于蚁群算法参数多且存在一定的关联性，今后将深入研究算法其他参数与信息素更新机制对优化性能的影响，并完善理论模型，提高蚁群算法的适用性。

表6 不同测试集下的算法性能对比实验结果

图5 自适应改进蚁群算法最优路线图