启发式强化学习机制的异构双种群蚁群算法*

刘中强，游晓明，刘 升

1.上海工程技术大学 电子电气工程学院，上海201620

2.上海工程技术大学 管理学院，上海201620

1 引言

蚁群算法最初是由意大利学者Dorigo 等学者在20 世纪90年代受蚂蚁觅食机制的启发而提出的一种新型的进化计算方法。最早被提出的算法有Ant system、Ant quality、Ant destiny[1-2]，用来解决经典的旅行商和分布式优化问题。随着对算法的深入研究，各种对算法的改进的方法也相继被提出，文献[3]通过提出精英蚂蚁策略来对算法的收敛速度和多样性进行改进，而文献[4]中局部信息素更新的提出以及文献[5]中优化算法的提出则很大程度提升了算法的性能，但是为了更好地平衡算法中多样性和收敛速度的关系，可以进行信息交换的多种群蚁群算法[6]被提出，通过让两个不同种群之间进行优势互补的信息交流，进而提高算法的性能。多种群这一概念被提出以后，有人提出通过信息熵来决定种群之间的交流策略，让子群体中解的多样性和收敛性达到动态平衡[7]。张鹏等人则提出了蚁群相似度这一概念，即以最优解为参照，计算出子蚁群的解与其在每条路径上重合度的大小，进而决定种群间的交流策略和交换概率，有效提高了跳出局部最优的能力[8]，Mavrovouniotis 等人则提出用于解决动态TSP 问题（dynamic travelling salesman problem，DTSP）的多种群蚁群算法[9]，每个种群（拥有各自的信息素表）并行运行并将最优解共享给所有种群，以提高解的质量和多样性。何雪莉等人则提出了一种基于异类双种群的蚁群算法，将两种信息素更新机制不同的蚁群分别独立进行进化求解，并定期交换优良解和信息来改善解的多样性，增强了算法跳出局部最优的能力，使算法更容易收敛到最优解[10]。朱宏伟等人则针对两个异构种群，引入协同过滤策略，通过对最优路径上的蚂蚁进行奖赏并自适应地调整两个种群间的交流频率，最后引入城市失活思想降低算法的复杂度，提高收敛速度[11]。袁汪凰等人则结合MMAS（max-min ant system）算法并在信息素的更新方面引入奖惩模型，通过奖励算子来增加收敛速度，通过惩罚算子增加多样性，有效平衡了算法的多样性和收敛速度[12]。张晓伟等人则通过将蚁群分工，然后进行并行搜索，互相影响，以达到多样性和收敛性的动态平衡[13]。接着很多其他的算法和机制也都相继被应用来改进算法，比如聚类方法和交互式机制都被引入改进的算法中，用以改进种群间的交流机制，实验结果也证明算法在性能上有了一定的提升[14-15]。章春芳等人则提出将种群分为若干子种群，让每个子群体的蚂蚁并行地进行优化，自适应地调整交流策略[16]，以让算法在收敛性和多样性方面保持有效的平衡，但是正如上述专家学者所提出的那样，有些在利用双种群进行交互时，两个种群间不能形成优势互补[10]，而有些学者提出让双种群之间进行交流，但是在交流方式上往往比较单一，有的则是在对交流后信息素的更新策略上不能实现很好的自适应更新[11,13]，在一定程度上会影响算法的性能。

本文在结合强化学习[17]思想的基础上，提出了一种基于启发式强化学习的异构双种群算法。将蚁群系统（ant colony system，ACS）作为主种群，将精英蚂蚁系统（elitist ant system，EAS）作为子种群，利用启发算子控制两个种群间是否进行交流，充分发挥种群间的优势互补。同时利用偏离度系数来控制解的交换方式，前期利用子种群最优解去替换主种群的随机解，增加解的多样性，同时利用强化学习机制对主种群最优路径上的信息素进行一定自适应的奖赏，来保证最优公共路径以后被选择的概率。随着解的构建的进行，后期则用子种群的最优解替换主种群的最差解，有效增加最优公共路径上信息素的量，同时对主种群的最优路径上信息素进行进一步自适应奖赏，进一步提高了算法在后期的收敛速度。

2 相关工作2.1 精英蚂蚁系统（EAS）

在EAS 算法中，通过并行地构建TSP 路径，并且在每一次迭代完成之后给予最优路径上的信息素以额外的奖励，以加强最优路径的每条边的影响比重，从而加快收敛速度，其状态转移公式如式（1）所示：

信息素更新公式为：

e为一个参数，它定义了给予路径Tbs的权值的大小，Cbs为最优路径上的长度，由公式可知，EAS 通过在每次迭代过后给予最优路径增加以一定权重的信息素，从而有效增加算法的收敛速度。

2.2 蚁群系统（ACS）

ACS 相对于EAS 来说，主要在几个地方进行了改进：（1）在对下一路径的选取规则上；（2）全局信息素的更新规则；（3）为了降低每次迭代过后最优路径上的信息素的影响力，新增加了局部更新规则。

ACS 中下一段路径的选择规则如式（4）所示：

其中，q是一个分布在区间[0,1]的随机数，并且0 ≤q0≤1，这样就可通过调整参数q0来调节蚂蚁对路径的探索。

在信息素的全局更新上，ACS 的更新规则如下：

局部信息素更新规则如下：

式中，τ0为初始信息素的值，取值为1/nCnn，Cnn为由近邻算法得到的路径长度，ξ为一常数，即信息素的蒸发率，局部信息素更新规则的引入，可以防止每条边的信息素无限累积，并且降低最优路径上信息素的浓度，增加蚂蚁探索其他路径的可能性，从而增加了解的多样性。

2.3 两种群之间的优势互补分析

EAS 算法在每次迭代完成之后，通过全局信息素的更新增加最优路径上的信息素，这样算法就能在前期很快寻找到较好的路径，但是缺点就是比较容易陷入局部最优。ACS 则通过引入局部信息素更新机制有效地削弱了算法前期最优解路径上信息素的影响力，使算法在前期能够有效扩大搜索范围，提高解的质量，因此EAS 与ACS 两种算法有着较好的互补性。

2.4 强化学习算法

强化学习是指从环境状态到动作映射的学习，以使动作获得累积奖赏值最大，强化学习机制如图1所示。该方法不同于监督学习技术那样通过正例、反例来告知采取何种行为，而是通过试错来发现最优行为策略，通常采用评估函数Qt(st,at)表示在状态st下，执行动作at，该状态-动作对得到的最大累积折扣回报。该函数有界且逼近Q值，每个状态-动作对作为策略都会被访问有限次。Q值更新规则如式（7）所示：

其中，s表示当前状态；a表示在状态s下采取的动作；r表示立即回报；s1为新的状态；γ为折扣因子；α为学习率。

Fig.1 Reinforcement learning mechanism图1 强化学习机制

3 启发式强化学习双种群蚁群算法

鉴于EAS 和ACS 之间优势互补的关系，将二者放在一起组成异构的双种群算法，将ACS 作为主种群，EAS 作为子种群。通过启发式算法控制子种群与主种群间的交流频率，即前期通过降低两种群间的交流频率，扩大种群前期的搜索空间，有效提高算法的多样性，并通过强化学习机制对交流后主种群最优路径上的信息素进行自适应的奖赏，让最优公共路径上的信息素得到累积，提高其在后期被选择的概率。后期则自适应地提高种群间交流频率，同时强化最优公共路径上的信息素的量，提高算法在后期的收敛速度。

3.1 偏离度系数

在每次迭代过后，两个种群参与解的构建的m只蚂蚁都会形成各自的解集mi={m1,m2,…,mm}，mj={mi+1,mi+2,…,m2m}，为了衡量出每次迭代后两个种群的解与TSPLIB（traveling salesman problem library）中最优解的偏离程度，以下提出了偏离度系数的概念，如式（8）所示：

其中，Lexp为期望路径（TSPLIB 库中的标准值）；li为种群i与种群j每只蚂蚁在每次迭代过后解的值；mi、mj分别为种群i与种群j在每次迭代过后的解集。由上式可知，每次迭代后，种群中的每只蚂蚁的解偏离Lexp越多并且较为分散时，σ的值也就越大；反之当解的值较优并且较为集中时，σ的值也就越小。根据每次迭代过后σ值的大小，可以有效得出并行搜索时两个种群总体解的情况。

为了比较直观看出δ值随迭代次数的变化，分别对Eil51 和KroA100 实验中δ的值与迭代次数进行拟合，得出σ的拟合曲线如图2 所示。

由图2 中的拟合曲线可以看出，δ的值在算法运行初期由于解的多样性较好，因此相对最优解来说，总体的偏离度也就较大，即δ的值也相对较大。但是随着算法迭代的进行，每次迭代过后的解则逐渐向最优解附近靠近，因此δ的值也就会出现明显的下降，直到最后算法在达到收敛或者找到最优解后，δ的值则变得平稳，或者趋向于0。

Fig.2 Eil51 and KroA100 deviation fitting curve图2 Eil51 和KroA100 偏离度拟合曲线

3.2 启发式交流频率

蚂蚁在每次完成解的构建后，需要根据解的情况来判定解的交换方式，但是如果每次迭代完成后都进行解的交换，再对最优路径上的信息素进行奖惩，就会增加算法复杂度，同时也会造成最优路径上的信息素累积过快，使算法陷入局部最优，因此可以通过引入启发式算法来限制两个种群的交流频率，以此降低算法的复杂度。

启发式函数如式（9）所示：

其中，Q代表两个种群间进行解的替换，则表示不进行替换，q∈rand(0,1),k为一个不确定常数。如图3所示，图中黑色线段部分为当k取一定值时，事情Q可能发生的临界值，左边的部分代表不会发生，右边部分代表有一定的概率发生。当测试集规模较小时，偏离度σ的下降趋势也就相对明显，因此此时通过将常数k设置为较大的常数，来控制事情Q的发生概率。例如，在Eil51 中将k值设定为50，在算法刚开始运行时，由于kσ∈(1,+∞)，那么就不会发生解的替换，而随着σ值的降低，事件Q就会有一定的概率发生，且发生的概率越来越大，直到最后算法达到收敛。当测试集规模较大时，前期偏离度也相对较大，此时为了控制事件Q的发生概率，则需要将k设定为较大的值，以控制事件Q发生的时间节点。

Fig.3 Threshold value of event Q图3 事件Q 发生的临界值

由式（9）并结合图3 可知，由于前期解的偏离程度较大，因此事件Q发生的概率也就较小或者基本不会发生。种群此时基本不会进行解的交换，不需要对解的交流方式进行判定，双种群间只需要各自去构建自己的解，因此更多的未知路径就可以被探索到，有效地增加了解的多样性并且降低了算法的复杂度。而随着算法的运行，解的质量的改善，kσ的值也就越来越小，事件Q发生的概率也就越来越大，此时种群间会对交流的方式进行判定，通过有效的交流方式来进一步提高算法的多样性和收敛速度。

3.3 子群体间的交流方式

为了发挥两个种群优势互补的优势，让优良的解能在两种群之间传播，两种群间需要根据各自解的优劣定期地以不同的方式进行解的替换，如式（10）：

3.4 强化学习机制

EAS 和ACS 在前期完成路径上信息素的随机替换后，会使有些未知路径上的信息素得到加强，增加了解的多样性的同时，也会因为解集过多而导致最优公共路径上信息素的影响比重下降，进而影响算法的收敛速度。并且随着迭代的进行，EAS 用最优路径上信息素替换ACS 最差路径上的信息素后，使公共路径上信息素的影响力进一步加强，其他路径上的信息素的影响微乎其微，此时可以通过调节ACS的全局信息素更新方式来提高最优公共路径上信息素的影响比重以及算法后期的收敛速度。提出以下基于强化学习机制的全局信息素更新公式：

其中，ρ为一常数，为最优路径的长度，li为第i代ACS 的最优路径长度，li-w为前w代ACS 最优路径的长度。由式（11）可知，相隔w代后，信息素奖赏的量与w代之间解的差值成正比，即如果w代之后最优解有了明显的改善，说明此时路径上出现最优解的概率就越大，那么就对此时路径的信息素给予相对较大比例的奖赏，从而有效提高最优公共路径以后被选择的概率。后期则由于交换频率的加快，信息素的累积也相对较快，解的增加幅度也相对较小，从而对最优路径上的信息素进行少量的奖赏，进一步提高算法后期的收敛速度。

3.5 算法的流程

算法ACA-HRAL for TSP

3.6 算法性能特点分析

3.6.1 时间复杂度分析

由算法流程图可以计算出ACA-HRAL（ant colony algorithm-heuristic reinforcement learning）的时间复杂度为O((2m×(n-1)+2n)×(NC-k)+(2m×(n-1)+n)×k)，即ACA-HRAL 的时间复杂度为O(2m×n×NC)，而对于传统的单种群算法EAS 和ACS 来说，可知其时间复杂度为O(n3)。因此对比可知，ACA-HRAL 的时间复杂度在量级上并未发生改变。

3.6.2 算法性能特点分析

ACA-HRAL 算法结合了两种经典单种群蚁群算法的优势，通过引入启发式算子控制种群间的交流频率，比如算法刚开始运行时，主要进行对未知路径的探索，此时应该以较低的频率去进行解的交流，以增加解的多样性；当偏离度系数大于一定阈值时，就不需要进行交流方式的判定，从而降低算法的复杂度。

当算法达到可以进行交流的条件时，会根据偏离度的大小，选择对应的交流方式。当偏离度较大时，说明算法主要偏重于探索未知路径，此时用EAS的最优解替换ACS 随机解，有效地增加主种群ACS非最优解路径上信息素的比例，从而增加解的多样性，再利用强化学习机制对最优路径上信息素的量进行一定比例的强化，以增加最优公共路径被选中的概率。当进入迭代后期时，算法偏离度则比较小，同时两个单种群的最优路径的重合度也比较高，此时利用EAS 的最优解去替换ACS 的最差解，再利用强化机制对最优路径上的信息素进行更新，能够有效增加后期的收敛速度。

综合来看，相对于传统的单种群蚁群算法，ACAHRAL 能够在不增加时间复杂度的情况下，利用种群间的交流机制和对信息素的自适应强化机制，能够有效提高前期解的多样性和后期的收敛速度。

4 实验仿真与分析

为了检验改进后双种群蚁群算法的性能，选取标准的TSP 测试集，并与EAS、ACS 的性能进行比较。最后在Matlab2018a版本下对每个测试集进行15次实验仿真，通过测试结果检验改进后算法的性能。

4.1 参数设定

在进行实验仿真前，首先参考文献[3]和文献[4]，对EAS和ACS进行实验参数设定，针对ACA-HRAL，由式（9）和式（10）可知，由于前期双种群在完成解的替换后，公共路径上信息素的累积相对较大，因此为了减小前期信息素的影响比重，防止过早陷入局部最优，赋予β较大的值，具体参数如表1。

Table 1 Algorithm parameters setting表1 算法参数设置

4.2 实验结果与分析

为了测试改进后的算法性能，本实验中选取了12个中小规模城市的TSP 测试集，如Eil51、Eil76、KroB200和Lin318等作为实验对象，分别进行10次的测试，得出了算法在收敛性上的对比图以及误差率、迭代次数等具体参数，具体结果如图4 和表2 所示。

4.2.1 整体性能分析

为了体现ACA-HRAL 在性能上的改变，选取Eil51、KroA100、KroA150、KroB150、D198、KroB200和Lin318 城市作为测试集，得出其在收敛性以及所得解的对比曲线，如图4 所示。

Fig.4 Experimental comparison图4 实验对比图

Table 2 EAS,ACS and ACA-HRAL experimental simulation data表2 EAS、ACS 和ACA-HRAL 实验仿真数据

（1）多样性分析

当算法前期多样性较好时，其解集的范围也就越大，在一定的迭代次数内找到较优解的可能性也就越大，偏离度也就相对会较小。为了比较改进后算法在前期多样性上的改进，对前200 次迭代解的偏离度系数进行了分析比较，如表3。

Table 3 Deviation degree of the first 200 generations表3 前200 代偏离度大小

结合表3 可以看出，EAS 和ACS 在前期由于没有发生解的替换，解的多样性相对较差，在前200 次的迭代中，总体解的偏离度系数都要大于ACA-HRAL；ACA-HRAL 由于交流机制和信息素强化机制的存在，其在前期探索的范围相对较广，解的多样性较好，能够以较快的速度找到较优路径的集合，因此解的偏离度系数相对其他两种算法来说也就越小。

（2）收敛性分析

结合图4 可以发现，在小规模的测试集Eil51 上，EAS 的收敛速度要快于ACA-HRAL，但是从结果可以发现，EAS 是由于陷入局部最优而导致收敛速度较快。在D198 的测试集上，ACS 的收敛速度也是快于ACA-HRAL，也是由于未能跳出局部最优而导致提前收敛，而ACA-HRAL 由于增加了对信息素的强化机制，使最优公共路径上的信息素能够在后期得到较快的累积。因此在其他的测试集中ACA-HRAL 都能以较快的速度达到收敛，并且解的质量也有着很大的提高，说明ACA-HRAL 能够在跳出局部最优的情况下有效提高后期的收敛速度。

综合来看，改进后的算法前期在解的多样性方面和后期在收敛速度上都有了一定的提高。

4.2.2 具体结果分析

为了进一步得出算法在解的质量和收敛性方面的提升，依照表2 中的实验数据，选取每种算法达到最优解时候的误差率和达到收敛时的实验数据，做出了如图5 和图6 所示的柱状图，分别表示每种算法在不同测试集下相对最优解的误差率和达到最优解时的收敛次数对比。

Fig.5 Error rate of solution图5 解的误差率

Fig.6 Number of iterations图6 迭代次数

由图5 的对比可以看出，在对小规模的城市集进行测试时，ACA-HRAL 能够有着较优的表现，都能找寻到最优解，随着城市规模的慢慢扩大，EAS 和ACS的误差率则越来越高，而ACA-HRAL 则可以将误差率控制在1%左右。根据图6 的迭代次数可以看出，前期EAS 和ACS 虽然用了较少的迭代就达到收敛，但是并未找到最优解，即算法在前期陷入了局部收敛，而ACA-HRAL 相对二者来说，虽然迭代次数较多，但是能找寻到最优解，说明其能有效跳出局部最优。另外随着测试集规模的扩大，结合图5 和图6 可以看出，ACA-HRAL 在规模较大一点的测试集中不仅所取得的效果较好，而且迭代次数也相对较少，因此综合来说，相对于经典的单种群，算法在跳出局部最优和寻优能力方面都有了很大的提高。

5 结束语

本文基于经典单种群间的优势互补关系提出了一种基于启发式强化学习的双种群蚁群算法。通过启发式算法自适应地控制种群间的交流频率与交流方法，让两个种群在前期能够充分地进行解的构建，扩大搜索空间，并引入强化学习机制对交流后的主种群最优路径上的信息素进行强化，提高最优公共路径以后被选中的概率，后期通过控制增加最优路径上信息素的比例来进一步加快算法的收敛速度。实验结果表明，算法的整体性能相较传统单种群有了很大提高，尤其是在解决部分大规模问题上。在以后工作中，将在双种群的基础上进一步研究多种群蚁群算法之间的交流合作机制，以提高其在解决大规模TSP 问题上的性能，并能有效地应用到实际问题中。