结合ABC算法动态分级的双蚁态蚁群算法

李顺东，游晓明，刘 升

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

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

1 引言

旅行商问题[1]（Traveling Salesman Problem，TSP）是经典NP-hard组合优化问题，它可以简单地描述为：旅行商从规定的城市列表中选择一个城市作为起点，不重复地遍历完所有城市，最终再返回到初始位置，从而找到一条最短的闭合回路。目前解决TSP问题的算法[2-5]有很多，其中蚁群算法由于良好的并行性、正反馈性以及极强的鲁棒性等特点，成为最有效的方法之一。

20世纪90年代，意大利学者Dorigo等人受自然界蚁群觅食行为的启发创新性地提出了蚁群算法（Ant System，AS）[6]，但算法存在收敛速度慢，易陷于局部最优等问题。在此基础上，1996年Dorigo等[7]结合Q-learning思想提出了全新机制的ACS算法。该算法沿用了两种信息素更新方式，加快了算法收敛速度。同期，Stutzle等人[8]又提出了最大最小蚂蚁系统（Max-Min Ant System，MMAS），为每条路径上信息素浓度设定了上、下限阈值区间，避免信息素浓度无限累加而停滞，提高了算法的多样性。此后，众多专家学者在这两者算法的基础上做出了改进：文献[9]提出了一种动态信息素策略的改进算法，通过动态改变伪随机因子的阈值，来平衡算法的多样性和收敛速度。文献[10]通过融合模拟退火算法，提出了一种自适应模拟退火蚁群算法，提高了解的质量。以上改进算法，虽然在一定程度上取得了进步，但在蚁群协同分工机制方面仍然存在着不足。

针对不足，Dorigo等人曾提出过精英蚂蚁系统（Elitist Ant System，EAS），通过对蚂蚁分级，分别执行不同的信息素更新策略，突出了最优路径蚂蚁的精英作用，为蚁群的路径选择增加导向性，加快了系统的收敛速度。Bullnheimer等人[11]还提出过RAS形式的蚂蚁分级系统等。实验证明，在蚁群算法的基础上实行分级机制，效果良好，改善了群智能优化算法本身存在的收敛性和多样性的矛盾。此后，很多其他分级机制的算法应运而生。其中，人工蜂群算法表现较为突出。

自然界中蜂群采蜜以分工协作而闻名，不同级别的蜂种各司其职共同完成采蜜任务。根据这一特性，Karaboga等[12]提出了人工蜂群算法（Artificial Bee Colony，ABC），算法通过适应度不同将蜂群进行分级、分工协作，既凸显了精英蜂群的引领作用，加快找到优质蜜源速度，又通过侦察蜂群随机搜索更多优质蜜源，提高了算法解的精度。

鉴于此，本文在ACS算法基础上，融合了人工蜂群算法分级思想，提出了一种动态分级的改进蚁群算法（ABC-ACS）。通过引入适应度分级算子，将蚁群划分为两种蚁态：寻优蚁和侦查蚁。寻优蚁的作用是搜索较优路径，经过若干次迭代最终找到最优解；侦查蚁则负责开发其他路径，搜索更多优化解。两类蚂蚁分别执行不同加权系数的动态信息素更新策略，使得较优路径和非较优路径之间的信息素产生一定的浓度差，既突出了寻优蚁的导向作用，又不会影响侦查蚁继续搜索其他更优解的能力，从而不仅增加了算法导向性，加快收敛速度，又保持了算法的多样性，避免陷入局部最优。此外，在每次迭代结束后两类蚂蚁执行优良解交换策略，提高了解的质量。最后，通过ACS全局最优路径信息素更新策略，使算法收敛速度进一步提高。另外，为了使所得解的质量更优，算法还融合3-opt算子对其继续优化。

2 相关工作

2.1 ACS蚁群算法

2.1.1 路径构建

ACS算法模型中每只蚂蚁从城市i到城市j之间转移，是利用伪随机概率公式进行选择的，公式如下：

其中，τij为城市i和城市j之间信息素浓度的大小；allowedk∈{ }n-tabuk表示蚂蚁k下一步可选择的城市；ηij(t)是启发式函数，表示蚂蚁k从城市i转移到城市j的期望度，且表示相邻城市i和j之间的距离；αβ分别表示信息启发式因子和期望启发式因子，αβ值越大，对下一条路径的选择影响越大。q是区间[0，1]上均匀分布的随机变量；q0是区间[0，1]上的可调参数；当q≤q0时，蚂蚁k根据伪随机比例公式（1）选择最优路径；当q＞q0时，则按照s即轮盘赌公式进行路径选择，如式（2）所示：

本文ABC-ACS沿用了ACS的伪随机比例规则，其先进之处在于：算法在路径构建时，蚂蚁以q0概率选择当前可能最优的移动方式，又以1-q0概率有偏向性地探索各条边。通过合理调整参数q0，就可以有效地调节算法对于每条新路径选择的优先级和探索度，从而决定算法应该集中探索当前最优区域还是其他区域，确保在局部加权信息素更新时，对不同探索度的路径引入相应比例的权重进行更新，即较优路径加权大，其他路径加权小，进而保证了局部信息素动态加权更新规则的准确性。

2.1.2 信息素更新

ACS蚁群算法的更新机制分为局部信息素更新和全局信息素更新两部分。

局部信息素更新：当每只蚂蚁完成一次周游后，算法便会对其走过的路径进行局部信息素更新。局部信息素更新是对所有蚂蚁都进行更新，其作用是为了缩短最优路径和非最优路径之间信息素的差距，增加算法的多样性，提高算法全局搜索能力，避免陷入局部最优。其公式如（3）所示：

式中，τ0为每条路径上的初始信息素浓度；ρ是局部信息素挥发率。

全局信息素更新：当所有蚂蚁都完成一次迭代之后，算法只对当前最优路径上的信息素进行更新，通过算法的正反馈作用，使得最优路径和非最优路径上的信息素的差距逐渐拉大，为蚁群的路径选择增加指向性，加快了算法的收敛速度，如式（4）所示：

式中：

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

2.2 3-opt搜索算子

K-opt是TSP问题中广泛应用的启发式搜索方法。其中，3-opt[13](K=3)是效率较高的局部优化算法。该算法主要通过对蚂蚁构建的路径进行局部优化，提高解的质量，从而得到最优解。其流程大致为：

步骤1蚂蚁完成路径构建，生成Hamilton回路T。

步骤2在回路T上随机选取三个点切开重组，形成新的闭合回路，如图1所示。

步骤3将新的回路和旧的回路T进行解的比较，保留其中较优解。

步骤4重复执行该算法，直到找到最优解。

图1 3-opt路径重组

3 改进蚁群算法

3.1 ABC算法动态分级策略

3.1.1 ABC算法分级思想

人工蜂群（ABC）算法是由土耳其学者Karaboga于2005年提出的，它是受到自然界中蜂群采蜜行为启发的群智能优化算法，其模型主要是由：蜜源、引领蜂、跟随蜂和侦查蜂四个要素组成。在求解TSP[14-17]时，ABC算法首先根据蜜源i(i=1,2,…,NP)的质量计算对应的适应度fiti；然后根据适应度值的大小将蜂群划分为引领蜂、侦查蜂和跟随蜂三种类型：引领蜂负责搜索蜜源；引领蜂归巢分享蜜源信息，跟随蜂按一定比例选择是否跟随；侦查蜂负责搜索空间内其他蜜源。

3.1.2 动态适应度分级算子

蚁群算法自提出以来就存在着收敛速度慢、易陷入局部最优、协同机制不够完善等问题，而目前单种群单形态蚁群算法无法实现收敛速度和多样性之间的平衡，因此本文借鉴了人工蜂群算法分级的思想，引入动态适应度分级算子，将蚁群划分为寻优蚁和侦查蚁两种蚁态并行搜索。其中寻优蚁负责较优路径的搜索，通过较高加权系数的信息素更新规则，突出较优路径上的信息素强度，增强其导向性，提高算法的收敛速度；而侦查蚁则负责开发较优路径以外的其他路径，寻找更多优质解，保证了算法的多样性，增强其跳出局部最优的能力，提高了解的质量。因此，通过动态分级蚁群进行并行搜索，实现了多样性与收敛速度之间的平衡。

定义动态适应度分级算子如公式（6）、（7）所示：

式中，fiti表示每只蚂蚁对应的适应度值(0＜fiti≤1)，如公式（6）所示，其值由lengthmin和lengthi的比值所决定，lengthmin表示当前迭代中的最短路径；lengthi表示每只蚂蚁迭代一次的路径长度；根据所计算的适应度fiti值的不同，将整个蚁群划分为两类，如公式（7）所示，M为侦查蚁与寻优蚁的分级阈值界点(0＜M＜1)：当0＜fiti≤M时，为侦查蚁；当M＜fiti≤1时，则为寻优蚁。M值并非任意选取，其大小直接影响算法整体的求解精度。因为M值过大时，侦查蚁的数量则会增多，从而导致大量的无用搜索，影响算法的收敛速度；而当M值过小时，寻优蚁的数量过多又会导致某些较优路径上的信息素过度累积而陷入局部最优，影响算法的多样性以及解的质量。本文通过大量的实验对比，验证了当M=0.7时，算法的性能表现最佳，求解精度最优。

3.2 改进的动态信息素更新策略

为了更好地平衡蚁群算法多样性和收敛速度之间的矛盾，本文在ACS局部信息素更新策略的基础上，引入了加权[18]系数和适应度值，使得不同级别的蚂蚁执行不同加权系数的动态信息素更新策略，如公式（8）～（10）所示：

式中：

其中，λ1λ2为加权系数；fiti为对应蚂蚁计算的适应度值。

需要说明的是，原ACS算法的局部信息素更新策略对于每只蚂蚁都是相同的，整个算法只依靠全局更新策略来增强较优路径上的信息素浓度，不能很好地突出其导向作用，从而在较短的时间内找到最优解，因此，本文融合了EAS的精英思想对局部信息素更新公式进行加权改进：

（1）当M＜fiti≤1时，为寻优蚁，其局部信息素更新公式为式（8）、（9）。

（2）当0＜fiti≤M时，为侦查蚁，其局部信息素更新公式为式（8）、（10）。

其中，λ1为寻优蚁群的局部信息素加权系数，λ2为侦查蚁群局部信息素加权系数，并定义λ1＞λ2，目的是为了区分两类蚁群搜索路径上的信息素浓度，突出较优路径的精英导向作用，从而缩短算法找到最优解的周期。通常λ1只能略大于λ2，因为λ1与λ2之间相差过大都会导致算法过早停滞而陷入局部最优，影响算法求解的精度。因此，本文在进行大量实验对比之后，验证了当λ1=4、λ2=2时效果最好，故取之为两类蚂蚁局部信息素更新改进策略的加权系数。

此外，改进的局部信息素更新策略还引入了蚂蚁的适应度值fiti，目的是为了让每只蚂蚁能够根据自身适应度值的大小动态地进行局部信息素更新，因为适应度值大的蚂蚁，搜索的路径相对较优，通过改进的局部信息素更新策略便会获得更高浓度的信息素更新，导向作用也随之增强。

整体而言，在原ACS算法的基础上，动态改进局部信息素更新策略，既保持了每条路径上都有信息素增加的特性，又使其浓度和影响力根据自身适应度的不同动态变化，从而形成路径间的浓度差，即适应度高的较优路径增加的信息素高，适应度低的次之。当算法陷入局部最优时，侦查蚁依然具备搜索其他更优路径的能力，保证了算法的多样性，提高全局寻优的能力，从而有效地帮助算法跳出局部最优；进一步，通过较优路径的精英导向作用加快了收敛速度，从而使全局寻优能力与局部寻优能力之间达到平衡。此外，算法的全局更新依然沿用ACS算法的更新策略，即在所有蚂蚁完成一次迭代之后，只更新当前最优路径上的信息素，如式（4）所示，目的是为了进一步突出最优路径的导向作用，从而加快收敛速度。

3.3 优良解的交换策略

当iter=1时，算法利用ACS的路径构建公式和信息素更新公式完成第一次迭代，并计算相应的适应度值来将蚁群进行划分：当0＜fiti≤M时，为侦查蚁；当M＜fiti≤1时，则为寻优蚁。

从第二代开始(iters≥2)，算法首先会对上一代划分的两类蚂蚁进行路径构建，然后再通过不同加权系数的局部信息素公式进行信息素更新，且在每一次迭代之后，都要判断两类蚂蚁是否需要进行优良解的交换，主要思路为：若侦查蚁构建的路径集合中存在‖ length ‖＜‖ length ‖，则对两类蚂蚁执行优良解的交换：

交换后的两类蚂蚁身份职能互换，即原来较优的侦查蚁转变为新的寻优蚁，而被替换掉的寻优蚁则沦为侦查蚁，执行侦查蚁的职能。在完成优良解交换之后，系统开始进行下一轮迭代；若一次迭代中不存在侦查蚁优于寻优蚁的解情况，算法则不进行优良解交换，直接进入下一轮迭代。优良解交换策略的大致过程如图2所示。

图2 优良解交换

通过优良解的交换策略，可以使每一代寻优蚁解的集合不断更新，始终保持较优路径集合的质量更优；侦查蚁不受寻优蚁导向作用的影响，继续搜索当前较优路径以外的其他路径，保证了算法的多样性，增强了算法全局寻优能力。当侦查蚁寻得更优解时，则与当前较优路径集合进行优良解交换，从而帮助算法跳出局部最优，提高了解的精度。优良解的交换设定是从第二代开始，直到寻优蚁解的集合不再发生变化或者达到最大迭代数为止。

3.4 ABC-ACS算法流程

本文所提出的结合ABC算法动态分级的双蚁态蚁群算法的算法流程可以简单地描述如下。

步骤1参数初始化。

步骤2 NC=1，将m只蚂蚁分别分配n个城市。

步骤3蚂蚁k根据式（1）和轮盘赌的方式（2）进行下一城市的转移。

步骤4所有蚂蚁完成第一次迭代，根据公式（6）、（7）计算相应的适应度值，并将蚁群分级为寻优蚁和侦查蚁，NC=NC+1。

步骤5完成第NC次迭代，算法根据式（1）完成两类蚂蚁路径的构建。

步骤6然后，根据式（8）～（10）分别对寻优蚁和侦查蚁执行局部信息素更新。

步骤7当所有蚂蚁完成迭代，两类蚂蚁进行优良解交换，若达到交换条件，则根据式（11）进行交换；否则，不进行交换。

步骤8根据式（4）进行全局信息素更新。

步骤9当NC≤NCmax时，NC=NC+1，跳转到步骤5；否则，转到步骤10。

步骤10输出最优解。

算法的整体框架如图3所示。

算法流程：

ABC-ACS Algorithm for TSP

1.Procedure ABC-ACS（）

2.Begin：

3.Initialize the pheromone and parameters

4.Calculate the distance between cities

5.#Algorithm：ACS

6.for iter=1 do

7.for i←1 to m do#m as ant'snumber

8.for j←2 to n do#n as cities'number

9.Construct ant solutions

10.Compute fitness&Classify ants

11.end-for

12.end for

13.end-for

14.Update pheromones

15.#Algorithm：ABC-ACS

16.for iter←2 to NC do

17.for i←1 to m do#m as ant'snumber

18.for j←2 to n do#n as cities'number

19.Construct ant solutions

20.Update dynamic local pheromones

21.if(‖ length ‖＜‖ length ‖)do

22.Exchange excellent solutions

23.end if

24.end for

25.end for

26.end for

27.Update pheromones

3.5 算法复杂度分析

由算法流程分析可知ABC-ACS算法的复杂度为O(1×m×(n-1)+(NC-1)×m×(n-1))，具体可分为两个部分：其中，第一代算法沿用的是ACS算法进行路径构建、求解，其复杂度为O(1×m×(n-1))；而从第二代开始，根据第一代所产生解的适应度将种群分为两个蚁态继续进行迭代，其算法复杂度为O((NC-1)×m×(n-1))。所以，改进后算法的总体复杂度为O(NC×m×n)，而ACS算法的复杂度为O(NC×m×n)，可见本文算法的复杂度并未发生改变。

3.6 算法收敛性分析

3.6.1 经典ACO算法收敛性分析定理[8]一旦找到最优解s*，则公式（12）成立：

对于经典蚁群算法而言，只存在全局信息素更新机制，其更新公式为τij(t+1)=(1-ρ)τij(t)+Δτij(t)。假设一次迭代之后任意一条边(i,j)上的信息素的最大增量为qf(s*)，则根据更新公式可知，第一次迭代中信息素最大值是(1-ρ)τ0+qf(s*)，第二次迭代中最大值是(1-ρ)2τ0+(1-ρ)qf(s*)+qf(s*)，以此类推，第θ次迭代中最大值。由于信息素具有挥发作用，信息素水平只能渐近于最大值水平，故。所以，一旦找到最优解，所有边上的信息素值都会收敛于τmax。此外，Dorigo等定义过每条边都存在相同的初始信息素τ0，其值为大于0的极小常数，因此，τmin＞0。所以，对于任意一条边而言，其信息素上下限为[τmin,τmax]。

根据式（2）蚁群算法的路径构建公式可知，任意一个可行解都有其选择概率p，且其下界pmin如公式（13）所示：

其中，Nc为成分集合C的势；τmin为信息素值的下界。

需要说明的是，可行选择概率p取到下界(p=pmin)时，即出现最优可行解增加的信息素浓度最低为τmin，而其他Nc-1个非最优可行解的信息素皆为最大值τmax的最差情况，那么求得任意的一般性解s′，包括任意最优解s*∈S*的概率，其中，n＜+∞是序列的最大长度，这足够让一只蚂蚁找到一个最优解，P*(θ)有如下下限：

3.6.2 ABC-ACS算法收敛性分析

ABC-ACS算法与经典蚁群算法的不同点主要体现在几个方面：第一，ABC-ACS沿用了伪随机比例规则，使得算法在路径选择和局部信息素加权更新时更具偏向性和准确性；第二，ABC-ACS中并不是所有边上的信息素都会蒸发，只有属于至今最优解的边才会蒸发信息素；第三，ABC-ACS中每只蚂蚁在构造解时都会使用局部信息素更新规则，在蚂蚁经过一条边(i,j)之后立即更新素；第四，对局部信息素更新规则进行动态加权改进；第五，采用了优良解交换策略。

ABC-ACS算法具有局部、全局两种更新机制，更新公式可以记为τij(t+1)=(1-ρ)τij(t)+ρb这种形式，在全局更新中，b=qf(sbs)；在局部更新中，b=τ0。当算法迭代θ次之后，信息素的最大值为，当θ→∞时，信息素的最大值渐近于。其次，τ0为信息素下限值。

根据公式（1）伪随机比例规则可知，如果边(i,j)的信息素值不是最大的，那么选中(i,j)的概率就是算法进行随机选择的概率(1-q0)与在随机选择中选择边(i,j)的概率的乘积。因为信息素取值存在上下限，所以任意一个可行解选择都有概率p＞0，且存在下界pmin，其公式如式（13）所示。因此，构造任意可行解的概率都大于0，任意一条边(i,j)选中的概率下界为(1-q0)pmin。根据公式（14）可得，ABC-ACS的下限公式为(θ)=1-(1-(1-q0))θ，则当迭代次数θ足够大时，

4 实验对比与结果分析

为了检验ABC-ACS算法的性能，本章选取了标准TSBLIP库中19个经典的TSP实例进行仿真，每个实例进行10次实验，并将其结果与传统算法，最新改进算法以及其他算法作对比。

4.1 与经典算法对比

4.1.1 与经典算法性能对比分析

对比分析了算法的性能，验证了本文算法求解质量更高，对比结果及算法搜索到的最优路径迭代图如表1和图4所示。从表1可以看出，ABC-ACS在各种规模的TSP实例中，无论是最优解、平均解还是误差率等方面都优于ACS和MMAS。其中，在Oliver30～pr107等小规模的TSP问题中，ABC-ACS都能以最快的速度找到标准最优解，算法寻优能力和收敛速度较ACS和MMAS均明显提升；而随着城市规模扩大，虽然ABC-ACS算法迭代数较大，但解的质量显著提高：中规模TSP测试集的误差均小于0.1%，其中，在ch130的测试上，算法所得解为6 113，而标准最优解为6 110，误差率仅为0.05%；在KroB150的测试中，更是达到了标准最优解。而对于pr226～rand300等大规模TSP问题的测试中，误差也都小于1%。这是因为对蚁群进行动态分级，并且执行优良解交换策略的结果，既保证了算法的多样性，提高了算法的全局搜索能力，避免了陷入全局最优，又优化了解的质量。因此，同样规模的测试集，ACS、MMAS花较少的迭代数但却陷入早熟、停滞状态，而ABC-ACS算法依然具有很好的多样性和全局搜索能力可以继续搜寻更优的解，充分说明了ABC-ACS算法的性能良好，且求解精度更高。

4.1.2 与经典算法收敛速度对比分析

为了更加充分比较ABC-ACS与经典算法的性能，本文又选取了eil51等不同规模的8个TSP实例对其收敛速度进行对比，结果如图5所示。

由图5所示，ABC-ACS在解决eil51等小规模TSP问题时，都能以最快的速度找到最优解，这是由于寻优蚁精英导向作用的影响，大大缩减了前期蚁群的搜索周期，提高了算法搜索效率；在求解KroA150等中规模的TSP问题时，虽然迭代数有所增大，但整体还是快于ACS、MMAS，且解的质量更高，标准最优解为26 524，ABC-ACS所得解为26 550，误差率仅为0.1%。而对于求解KroA200等大规模TSP测试时，前期收敛速度依然很快，且后期种群多样性依然好，这是由于ABC-ACS算法融合了人工蜂群分级的思想，对蚁群进行了动态分级，增加了算法搜索的多样性，避免陷入局部最优。由于每一代搜索完成之后，算法都会执行优良解交换策略，故与ACS、MMAS相比，ABC-ACS算法后期收敛速度稍慢，但求解精度更高。

4.1.3 算法多样性对比分析

为了进一步验证改进算法的多样性，本文以KroA100测试集为例，设置代码执行断点，统计算法执行到200、500、1 000、1 500以及2 000代时个体多样性的变化情况，并与ACS算法作对比分析，结果如图6所示，横坐标为迭代次数，纵坐标为标准差值（用以衡量算法每次迭代的多样性）。

通过图6多样性图对比可以看出：ABC-ACS算法整体多样性要优于ACS算法，且设置断点执行代码对比不同迭代数时两个算法的个体多样性情况，可以发现ABC-ACS依然更优。

其中，500～1 000代ABC-ACS多样性下降趋势明显，这是由于算法改进了局部信息素更新规则，动态加权系数的引入，使得较优路径上信息素增加的浓度要高于非较优路径，从而突出了寻优蚁的导向作用，导致选择较优路径的蚂蚁数大幅增多，加快了算法的收敛速度，因此多样性下降幅度很大；而1 000～1 500代，多样性又有所上升，这是因为侦查蚁不受寻优蚁导向作用的影响，而去搜索非较优路径以发现更多优化解，并且通过优良解交换策略将发现的更优解与寻优蚁进行交流互换，从而帮助算法跳出局部最优，故多样性得以增加；算法执行到后期1 500～2 000代，多样性虽然有所下降，但依然高于ACS算法。所以，总体而言，改进后的ABCACS算法较ACS算法保持了良好的多样性，并且通过动态加权的局部信息素更新规则，加快了算法的收敛速度。此外，两类蚂蚁各司其职、优良解交换，增强了算法全局寻优的能力，提高了解的质量（ABC-ACS找到的最优解是21 282，为标准最优解；ACS找到的最优解为21 292，存在误差）。

表1 ABC-ACS、ACS、MMAS在不同TSP测试集的性能对比

图4 最优路径

4.2 与最新蚁群改进算法对比分析

为了更好地说明ABC-ACS算法求解精度高，本文又选取了刘中强等[9]提出的D-ACS和袁汪凰等[10]提出的SA-MMAS两种最新的蚁群改进算法与eil51等不同规模的TSP问题进行性能对比，结果如表2所示。

明显可以看出：ABC-ACS在求解选取的各个规模TSP问题时几乎都能寻得最优解，其中KroA150和KroA200虽然没达到最优解，但误差都控制在很小的范围之内，且各方面表现皆优于D-ACS和SA-MMAS。

图5 收敛速度对比

表2 ABC-ACS、D-ACS、SA-MMAS性能对比

4.3 与其他优化算法对比分析

为了进一步验证ABC-ACS算法的可行性以及性能的高效，本文还将其与最新粒子群改进算法IMRGHPSO[3]、蜂群改进算法Proposed ABC[15]进行对比，其结果如表3所示。

通过结果对比可以直观地看出：ABC-ACS求解旅行商问题精度更高、性能更好，各个规模的表现皆优于最新的粒子群改进算法IMRGHPSO和蜂群改进算法Improved ABC，足以说明其可行性以及求解问题的性能高效。

综合以上所有数据对比及分析表明：ABC-ACS算法既增加了导向性，提高了搜索效率，缩短了收敛周期；又增加了多样性，提高了全局搜索能力，能够跳出局部最优，发现更多优化解；再加上优良解交换策略的影响，使得算法求解精度更高。其中，结合表1和图5可以看出，在解决中小规模TSP问题时，ABC-ACS均能以最快的速度找到最优解；而在解决少数的大规模TSP问题时，在没有找到标准最优解的情况下，由于其良好的多样性，不会很快收敛而陷入局部最优，与经典ACS、MMAS算法相比求解质量更好。结合表2可以看出，ABC-ACS不仅跟传统的蚁群算法相比有优势，对比最新的蚁群改进算法其性能优势仍然明显。而结合表3可以进一步直观地看出，ABC-ACS与其他最新的智能优化改进算法相比其表现还是更优。所以整体来看，改进后的ABC-ACS算法在解决TSP问题时既具备较快的收敛速度，又有较好的多样性。而且，无论是对比经典的蚁群算法，还是对比最新的蚁群改进算法，又或是其他最新的改进优化算法，ABC-ACS算法皆表现得更优，性能更好，实用性很强。

表3 ABC-ACS、Improved ABC、IMRGHPSO性能对比

图6 多样性对比

5 结束语

本文提出动态分级的改良蚁群算法，结合人工蜂群算法分级的思想，将蚁群划分为侦查蚁和寻优蚁两个蚁态进行分工合作解决TSP问题。其中，寻优蚁增加导向性，提高收敛速度；侦查蚁增加多样性，避免陷入局部最优。然后，通过优良解的交换，对所求解的质量进行优化。最后，应用ACS全局信息素更新策略，突出全局最优路径的精英导向作用，使算法很快找到最优解。经过多次不同规模的TSP实验，以及与经典蚁群算法、最新改进算法还有其他最新优化算法全方位对比得出：本文算法是可行有效的，在解决TSP问题时收敛速度明显提高，而大规模TSP问题质量更优。下一步将深入研究蚁群算法多种群之间的交流，进一步优化大规模TSP问题解的质量和收敛速度。