协同过滤策略的异构双种群蚁群算法*

朱宏伟，游晓明+，刘 升

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

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

+通讯作者E-mail:305235598@qq.com

1 引言

在自然界中，蚂蚁在发现食物后会释放信息素用于告知其他蚂蚁食物的各种信息，其他蚂蚁会根据信息素的浓度等信息，选择到达食物的最短路径。在20世纪90年代，意大利学者Dorigo、Maniezzo等人从生物进化的机理中受到启发，模拟自然界蚂蚁寻食的行为，提出了蚂蚁系统（ant system，AS）[1]，引起了专家学者的重视，并运用于商旅问题（traveling salesman problem,TSP）。实验证明蚂蚁系统取得了很好的结果。商旅问题是NP 组合优化问题中最经典的问题之一，旅行商需要从一个城市出发，不重复地遍历所有的城市，再回到起点，形成一条闭合回路。在蚁群算法研究过程中，旅行商问题是一个很重要的检测算法性能的基准。

虽然信息素的正反馈作用使算法更具有导向性，但也同时因为一条路径上信息素过大而导致局部最优。1996 年，Dorigo 等人在蚂蚁系统（AS）算法的基础上提出蚁群系统（ant colony system，ACS）[2]算法，提出两种信息素的更新方式，同时算法中加入局部搜索算法，减少了算法陷入局部最优的概率。同样，为了限制信息素过多，Stützle等人提出了最大-最小蚂蚁系统（max-min ant system，MMAS）[3]。MMAS设置一个阈值将信息素的最大值、最小值限制在其中，同时在算法进入停滞后，将信息素重新初始化，很好地改善了ACO（ant colony optimization）的不足。后来，专家学者在这两者的基础上不断地改进[4-10]，文献[4]提出一种基于禁忌搜索的蚁群算法，将禁忌搜索算法的记忆能力和藐视准则融合到蚁群算法中，使改进算法具有跳出局部最优解的能力。文献[5]提出一种新的信息素更新策略，加强了蚂蚁之间的协同作用。

实际上蚂蚁是一种种群活动生物，不同的蚁群有着不一样的信息素调控机制，这种分工组织方式使得蚁群可以完成更加复杂的任务。因此采用多种群的蚁群算法可使多个种群进行信息交换，加速收敛的速度[11-20]。文献[11]提出将蚁群分成两种，分别采用不同的路径构建方式，同时固定代数进行最优解和信息素的交流，提高了解的质量。文献[12]提出一种新的双种群信息素扩散机制，减少算法陷入局部最优的概率。以上文献都是将同构蚁群算法中的蚂蚁进行分类，进行多种群的信息交流，而异构多种群有更优的路径构建和保持种群多样性的能力，如文献[13]。

本文提出一种基于协同过滤策略的异构双种群蚁群算法（dual population ant colony optimization，DPACO），采用MMAS 和ACS 这两种优势互补的异构蚁群算法相结合的策略，既保留MMAS的多样性，同时也保留了ACS 收敛速度快的优势，共同促进算法在大规模问题上找到最优解。引入协同过滤策略，奖励ACS 和MMAS 中蚂蚁都偏爱的路径，以加快算法的收敛速度；当算法停滞后，根据两个种群多样性的动态反馈，自适应控制两个种群交流的频率，以保证蚁群算法发现解的广度。算法停滞后，进行双种群信息素的协同交互，均化每个种群不均匀的信息素，跳出局部最优。最后，引入神经网络中失活的概念，在路径构建时提出一种城市范围失活的思想，减少了程序的运行时间。实验结果表明，本文提出的异构双种群蚁群算法比传统的单种群蚁群算法和其他多种群蚁群算法在TSP 问题上有着更好的实验结果，并且在大规模问题上，这种优势更加明显。

2 相关工作

2.1 基本蚁群算法的TSP问题

对于不同NP难问题，使用蚁群算法建立的模型设计会有所不同。本文以NP难问题中最常用的TSP问题为例说明基本蚁群算法的模型。

设蚂蚁的数量为m，城市的数量为n，dij(i,j=1,2,…)代表i城市和j城市之间的距离，τij(t)代表着t时刻i城市和j城市之间的信息素的浓度大小。在ACS 和MMAS 算法中，每条边上的起始浓度都是相同的，记为τ0。

2.2 ACS蚁群算法

2.2.1 路径构建

ACS中每只蚂蚁从i城市到j城市的选择公式：

其中，ηij代表的是i、j城市之间距离的倒数，即q0是一定值，q是随机数，S代表将要被选择的下一个城市。s是另一种轮盘赌的选择方式。公式表明，城市之间信息素高的城市和距离相对近的城市被选择的概率更大，当q＜q0时，选用式（1），当不符合上述条件，采用轮盘赌进行路径构建。公式如下：

式中，allowed为蚂蚁当前可行城市集。

2.2.2 信息素更新

ACS算法中分为全局信息素更新以及局部信息素更新部分。

全局信息素更新：当所有的蚂蚁都完成一次周游以后，算法只允许每一代的最优蚂蚁释放信息素。全局释放信息素主要是用于增加蚁群算法的收敛速度，使蚂蚁们的选择更具有方向性。公式为：

其中，ρ是全局信息素的蒸发率，Δτij是信息素增量，Lgb是当前最优路径长度。

局部信息素更新：当所有的蚂蚁都完成一次周游后，算法允许每只蚂蚁都对其走过的路径进行信息素的更新。局部信息素主要是缩小最优路径上与非最优的信息素的差距，从而增加ACS 算法的多样性。公式为：

式中，Δτij是信息素增量，τ0为每条边上的起始浓度，ρ是局部信息素的蒸发率。

2.3 MMAS蚁群算法

2.3.1 MMAS算法信息素范围限制

为了避免算法收敛过快、停滞，MMAS算法将各边的信息素限制在一定范围[τmin,τmax]，若τij≤τmin，则τij=τmin；若τij≥τmax，则τij=τmax,其中τmax和τmin的计算公式如式（6）和式（7）所示。

其中，Tgb是全局最优路径。

2.3.2 MMAS算法信息素更新

当迭代完成一代时，有且仅有一只蚂蚁进行信息素更新，对当前最优路径或者全局最优路径进行信息素更新，使最优解得到有效的利用，算法的探索能力也会增强。信息素更新规则如式（8）和式（9）：

其中，f(sbest)为当前最优或者全局最优的路径长度。

3 改进的蚁群算法

本文采用两种目前性能较优的蚁群算法ACS和MMAS作为双种群的两种蚁群算法，ACS主要负责算法的收敛速度，MMAS主要负责蚁群算法的多样性。

3.1 协同过滤策略

推荐算法是通过数学公式、算法等方式，推测出用户更加偏好的东西，同时可以集中偏好相同的用户。推荐算法又可以分成基于内容、基于协同、基于知识、基于效应的推荐算法。其中基于协同过滤策略的推荐算法是效果最好的。

故本文引入协同过滤策略，搜索ACS 和MMAS中最优解蚂蚁都偏爱的路径，每隔w次迭代，对该路径进行信息素奖励。协同的作用使算法在路径构造时，最优解蚂蚁带动非最优蚂蚁向偏爱路径上靠拢，使算法更具有导向性；过滤的作用是去除一些相对较差的路径，加快算法的收敛速度。协同过滤策略将两个种群从前期到后期完全联系在一起，不再是独立地进行解的构建，而是形成两个种群相互学习、共同促进的局面，使算法能以较少的迭代次数找到最优解，提高算法的性能。由于两种算法中路径构建的差异，在算法前期信息素浓度差距不大时，若存在偏爱路径，说明最优解收敛在其附近的概率很大。这里仅对ACS的路径进行信息素奖励。这样做有两点原因：（1）根据文献[3]，MMAS 对信息素的最高值设有阈值，因此对信息素的奖励作用不敏感；（2）控制变量，仅对ACS进行信息素的奖励，可以协调奖励所带来的各种影响：与没有奖励策略的MMAS算法进行交流，既可以照顾到奖励所带来快速收敛的特性，也可以弥补奖励所带来的负面影响。两种算法相互制约，减少算法陷入局部最优的概率。

建立一个数学模型，通过矩阵的运算来描述本文的协同过滤策略。在T次迭代时（T是w的整数倍），为ACS 蚁群算法在T次迭代时，所有蚂蚁遍历所有城市的位置矩阵，为MMAS蚁群算法在第T次迭代时所有蚂蚁的位置矩阵，如下所示。

式中，n为城市的数量，m为蚂蚁的个数。

设k和h分别为ACS和MMAS算法在第T次迭代中所找到最优解的蚂蚁，故公共偏爱路径为：

式中，S（ACS,MMAS)表示两个种群共有的连续相同三个元素保存下来，并设为公共偏爱路径。

3.1.1 奖励算子

对公共偏爱路径进行奖励，额外的信息素奖励因子：

式中，n为城市的数量，iter为交流时的迭代次数。故对于公共偏爱路径部分的信息素更新为：

在算法前期，一条路径被两个种群都选到且作为当前最优路径中的一部分，即可认为此路径或者此路径周围一定存在全局最优解的组成部分。故在算法初期，奖励的信息素较多，可以加快算法收敛速度，随着迭代次数的增加，由式（13）可知，奖励会越来越少，从而保证算法后期的多样性。

3.1.2 自适应调节交流频率

由于信息素的正反馈作用，当两个种群信息交流过于频繁时，过多的信息素奖励会导致双种群都陷入局部最优，故需要控制异构蚁群算法的交流的频率。因此，这里通过两个种群之间的动态反馈，自适应调整交流的次数，从而减少算法陷入局部最优的概率。设每隔w次迭代，交换概率PDPACO决定两个种群是否进行信息交流。公式如下：

式中，T为迭代次数，k为最优解蚂蚁。式（15）表示公共模式的路径在总的路径中比例大小。当交换概率大于等于0.5时，则表明双种群算法的多样性已经降低，故将不进行种群之间的交流，否则进行交流。因此，整个DPACO算法的交流频率为：

当交流频率过于频繁时，奖励作用会导致算法很快收敛到一条路径上，造成算法多样性下降，可能会使算法得不到满意解；但是信息交流间隔过低时，会减弱两个种群之间的促进作用，降低种群之间的学习效率。因此，按照式（16）自适应调整交流频率，既可以加快算法的收敛速度，保证双种群之间的交流与学习的机制，同时使信息素较为平稳地增长，使蚁群稳步地向最优解方向迈进，减少算法陷入局部最优的概率。

3.2 信息素的交流与均化

当两种算法停滞后，交换ACS 和MMAS 的信息素表，从而有效地跳出局部最优。原因如下：

（1）MMAS有限制最大和最小信息素的特点，故每个城市之间信息素差距不是过于明显，由于ACS的信息素的奖励，导致其中几条边上的信息素增长速度较快，当交换了信息素表后，ACS就可以得到MMAS较为均匀的信息素，从而增加算法的种群多样性。

（2）利用MMAS 信息素初始化的特点，可以将ACS 上的边的不均匀的信息素重新初始化，有利于算法跳出局部最优。

在蚁群算法的中后期，信息素的浓度在路径构建中所在的权重不断增大，因此本文提出的信息素交换方式不断均化和调节两个种群之间的信息素，使算法跳出局部最优的能力更强。与典型的跳出局部最优的方式相比（如MMAS，当算法停滞时，将所有信息素重新初始化），本文提出种群间信息素的交换既将信息素回归到一个合理的范围，增加了蚁群的多样性，同时也保留了算法在前期所积累的经验，增加算法的收敛速度，而MMAS 蚁群算法的信息素重新初始化，就会否定所有的先前经验。故信息素的交流和均化很好地平衡了蚁群算法的多样性和收敛性。

3.3 城市的范围失活

失活的思想最先被提出在神经网络中。随机失活的目的是减少神经网络由于节点过多而产生的大量计算，以及造成网络的过拟合作用。过拟合与陷入局部最优的概念相类似，故本文将失活的思想引入蚁群算法中。针对城市规模大造成的计算过多、较慢的问题，本文提出一种城市范围失活的方法，与可访问城市表（Allowed）相结合，使得算法每次迭代中每只蚂蚁的计算城市的数目都会大量减少。如图1，中心点为蚂蚁正处于的城市，以这个城市的中心画一个半径为r的圆，会将Allowed城市表中的城市分成两种：一种在圆的范围中，一种在圆的范围外。将圆范围外的城市失活，即不再计算它们的转移概率，这样很大程度上减少了每次计算的城市的数目。由于本文所选TSP城市数目较多而紧密，同时给出半径相对较大，蚁群在路径构建时，即使计算了半径外的节点，最终也不会选择其作为下一城市，故城市范围失活的方法不会影响算法的构造解的精度，却可以极大地减少程序的运行时间。半径r的大小的选择：

式中，i为蚂蚁当前所在的城市，din表示第i和第n城市之间的距离。当使用r1半径大小的圆与Allowed城市表相结合而没有可选点时，使用r2的半径大小。

Fig.1 Current city and other cities图1 当前城市与其他城市

3.4 算法流程

DPACO algorithm for TSP

3.5 时间复杂度

从上述算法流程的分析可以看出，两个种群是并行实现的，因此DPACO 的时间复杂度为O((m1×(n-1)+m2×(n-1))×R)，式中m1为MMAS 算法中蚂蚁的数量，m2为ACS 算法中蚂蚁的数量，R为最大迭代次数。设所有蚂蚁的总数为m，故DPACO的最大时间复杂度为O(m×n×R)，MMAS 的最大时间复杂度为O(m×n×R)，ACS最大时间复杂度为O(m×n×R)。由此看出，本文提出的DPACO蚁群算法没有改变算法的最大复杂度。

4 实验仿真

本实验在Matlab R2014a 的环境下仿真运行，为了检测改进算法的有效性，以及显示本文算法在解决中大规模TSP 问题上的优势，选取Eil76、ch130、KroB150、KroA200、KroB200、lin318 等中大规模TSP算例来进行算法的验证。与经典单种群ACS、MMAS算法以及其他多种群蚁群算法进行数据对比，每种算法都进行15 次仿真实验，不同的测试集蚂蚁的数量、启发式的值等会有所调整。DPACO 在各个测试集中的参数设置如表1所示。

4.1 节展示了DPACO、ACS、MMAS 3 种蚁群算法的性能分析和对比，以及奖励算子对信息素分布的影响。实验表明DPACO 无论是收敛速度还是最优解都优于其他两种算法，在前期DPACO可以快速地收敛，算法后期可以跳出局部最优，提高解的质量。

4.2 节展示了DPACO 算法与其他多种群蚁群算法之间的对比实验，算法实验数据皆来自于其相应论文，实验表明，本文提出的改进算法的最优解要优于其他3种双种群蚁群算法。

4.3 节展示了城市范围失活方法对仿真实验的时间的影响。实验表明城市范围失活方法可以大量减少程序的运行时间。同时增加了对比实验，验证了本文所选的失活半径具有较好的特性。

4.4 节展示了DPACO 所找到的最优解以及与ACS、MMAS的迭代对比图。

Table 1 Parameters setting in each test set of DPACO表1 DPACO在各个测试集中的参数设置

4.1 不同TSP问题求解与比较

为了对比MMAS、ACS 和DPACO 的算法性能，本文选取Eil76、ch130、KroB150、KroA200、KroB200、lin318等中大规模TSP算例来进行分析，同时从最优解、平均解、误差率J、收敛速度等几个方向进行实验分析，如表2 所示。使用式（20）衡量每种ACO 与测试集最优解之间的差距，即误差率，公式如下：

式中,LACO为3 种ACO 算法所找到的最优解,Lmin为测试集的最优解。

从表2 结果可以看出，DPACO 在所有规模测试集中，无论是最优解、平均解，还是误差率等方面都优于ACS 和MMAS。同时从最终迭代数分析，DPACO在中小规模测试集上由于两个种群信息的交换以及其奖励策略，其收敛速度相对于其他ACO 算法速度最快；对于大规模测试集问题，由于最优解较难寻找，所有蚁群算法皆易陷入局部最优，本文提出的DPACO算法在没有找到最优解时，两个种群就会一直进行信息交流，算法在前期很快收敛到最优解附近。同时，在算法陷入局部最优后，由于控制双种群交流频率和信息素的交换，使得DPACO中两个种群的信息素的值都被限制，增加了跳出局部最优的概率，故算法总可以找到最优解。

Table 2 Performance comparison of DPACO,MMAS,ACS in different test sets表2 DPACO、MMAS、ACS在不同测试集的性能对比

3.1 节提出仅对ACS信息素更新部分进行奖励，下面举例分析奖励算子对信息素浓度的影响。图2和图3为在KroA200测试集中，双种群中每个种群在算法停滞前信息素浓度与城市之间的关系。X轴和Y轴代表城市，Z轴代表信息素浓度。从图2可以看出，MMAS 蚁群算法中每个城市之间信息素浓度差距不大，仅对ACS 的偏爱路径进行奖励，是由于MMAS限制了信息素浓度的最大最小值，故对MMAS进行信息素奖励效果一般。

Fig.2 MMAS pheromone图2 MMAS信息素浓度

Fig.3 ACS pheromone with reward图3 带有奖励的ACS信息素浓度

图3 为ACS 的信息素浓度，由于奖励的作用，导致几个城市之间信息素浓度增加较为明显。在蚁群算法前期，信息素的权重对路径构建产生的影响相对较小，若两个种群却产生了偏爱路径，故该路径有很高的概率为全局最优解组成部分，奖励该路径增强了算法在前期的收敛速度，使算法快速收敛到最优解附近。

同时本文在3.2 节提出，当算法停滞时，交换双种群信息素浓度表，以达到跳出局部最优的目的。从图2 和图3 可以看出，交换后，ACS 会得到MMAS的相对均匀的信息素浓度表，同时MMAS 也会将ACS的信息素浓度重置，并且均匀化。

4.2 与其他多种群蚁群算法的对比

本文改进算法还与其他异构多种群蚁群算法进行比较。其中文献[13]提出一种多交流策略的双种群算法（heuristic communication heterogeneous dual population ant colony optimization，HHACO）；文献[14]提出基于优胜劣汰规则的异类多种群蚁群算法（heterogeneous multiple ant colony algorithm based on survival of fittest rules，HMACSF）；文献[15]提出基于相似度的自适应异类多种群蚁群（adaptive heterogeneous multiple ant colonies algorithm based on similarity，AHMACAS）。表3中的数据皆来自于上述文献。实验结果显示，在Eil51和Eil76测试集上，本文DPACO算法的精度要优于其他3种算法；在KroA100测试集上虽然4种算法都找到了测试集最优解，但是本文算法的收敛速度要更快。

Table 3 Comparison of DPACO with other algorithms表3 DPACO与其他多种群的对比

根据4.1节和4.2节的实验结果，可以得出DPACO算法优于其他蚁群算法。与单种群相比，提升了解的质量，增加了算法的多样性，使算法收敛速度更快；跟多种群相比，DPACO算法提高了解的精度。

4.3 城市失活策略

4.3.1 城市范围失活的时间对比

本文提出的城市范围失活方法，在大规模问题上可以非常明显地减少整个程序的运行时间，即程序完成迭代次数所花费的总时间。本文设置一个对比实验，对于DPACO 蚁群算法，使用城市范围失活的方法，这里称为DPACO-1；不使用失活的方法，称为DPACO-2。表4 为DPACO-1 和DPACO-2 运行到最大迭代次数在不同测试集的时间差。

Table 4 Time comparison表4 时间对比

由表4 可知，随着测试集中城市数量的增加，运行时间是增加的；在同一测试集中，由于范围失活算法所带来的计算城市数目的减少，DPACO-1的运行时间要明显少于DPACO-2。设时间比t′=tDPACO-1/tDPACO-2，通过表4中数据计算，发现在大多数测试集中时间比一直在[0.67,0.71]之间浮动，且随着城市数目增加，时间比呈现略微增长趋势。这些测试集中的城市分布较均匀，但是在d198 和lin318 测试集中，时间比t却增加明显，这与测试集规模大小、城市之间密集程度有关。这两个测试集城市分布十分密集，范围失活的城市数量比较有限，故造成时间比增加。图4为不同测试集的时间比对比图。

Fig.4 Time ratio trend for different test sets图4 不同测试集的时间比趋势

4.3.2 不同的失活判定标准的影响

为了验证不同的判定标准对时间比和最优解的影响，本文设置了几组不同的判定标准与本文标准r1（式（18））进行对比。同时当范围内没有城市可以选时，都选择r2的半径大小（式（19））。对比实验半径如下：

这些判定标准中，半径大小为r3＜r4＜r1＜r5，不同的r在不同测试集中对时间比的影响如图5所示。

Fig.5 Influence of different judgments on time ratio of test set图5 不同判定标准对测试集时间比影响

由图5可以看出，不同的判定标准在各种测试集中时间比为t3＜t4＜t1＜t5。当半径不断缩小时，失活的城市会越来越多，会减少大量计算，导致时间比进一步减少，即程序运行时间变短。相反，当半径变大时，时间比会相应增加。故在缩短程序运行时间方面，以r3和r4的半径大小会使程序运行时间更短。但是当以r3和r4的半径值时，会使算法找到最优解有所下降，这是由于当失活半径过小时，部分测试集中城市分布较为松散，如berlin52、d198等，会造成最优城市的丢失。而r1和更大半径r5把最优城市以及其周边城市都包在其中，故蚁群所找到最优解几乎没有多大差别。表5 为部分测试集中4 种失活半径所找到的最优解。

Table 5 Influence of different radii on optimal solution表5 不同半径大小对最优解影响

4.4 DPACO最优解与收敛速度对比

图6～图15 为DPACO 的最优解，以及与ACS 和MMAS 的收敛速度对比。由图6～图15 可以看出，DPACO在前期保留了比ACS更快的收敛速度，使解快速收敛到最优解附近；同时在后期算法停滞时，本文算法由于采用信息素交换和控制交流的频率等策略，易跳出局部最优，提高解的精度，从而实验结果比单种群ACS和MMAS更好。

Fig.6 Eil51 test set图6 Eil51测试集

Fig.7 berlin52 test set图7 berlin52测试集

Fig.8 Eil76 test set图8 Eil76测试集

Fig.9 KroA100 test set图9 KroA100测试集

Fig.10 ch130 test set图10 ch130测试集

Fig.11 KroB150 test set图11 KroB150测试集

5 结束语

本文提出了一种使用ACS 和MMAS 作为两个种群，引入协同过滤的思想，奖励双种群中蚂蚁都偏爱的路径，提高了解的质量，同时自适应调整双种群的交流频率，减少算法陷入局部最优的概率。算法的后期，当双种群算法停滞后，双种群信息素协同交流，应用MMAS信息素初始化和设定的阈值等特点，极大增强了算法跳出局部最优的能力。在路径构造阶段每个种群都使用城市范围失活的方法，使整个程序的运行时间大大减少。虽然本文算法在所有规模测试集中，解的质量提升较多，且中小规模测试集中收敛速度提升明显，但对于大规模TSP问题上，算法后期收敛速度较慢，为此下一步继续优化多种群蚁群算法的奖励算子，以加快算法在大规模问题上的收敛速度。

Fig.12 KroA200 test set图12 KroA200测试集

Fig.13 KroB200 test set图13 KroB200测试集

Fig.14 d198 test set图14 d198测试集

Fig.15 lin318 test set图15 lin318测试集