旅行商问题(traveling salesman problem,TSP)是数学领域中一个重要的组合优化问题，属于NP问题.虽然目前有一些精确算法可用于求解该问题，但精确算法求解原理复杂，并且存在随城市数增加而产生的“组合爆炸”问题，因此，国内外学者一直努力寻求一种高效稳定的算法求解这一复杂问题.

人工蜂群算法(artificial bee colony,ABC)是Karaboga^[1]于2005年提出的一种基于群体智能的启发式搜索算法.该算法以蜂群的自组织模拟模型为基础，具有设置参数少、易于实现、鲁棒性强等优点，受到国内外学者的广泛关注，并已在许多领域得到了应用^{[2,3,4,5,6,7]}.目前，ABC算法主要应用于求解连续域优化问题,而在离散域上的研究和应用相对较少.虽然文献^[6]和文献^[7]提出了求解TSP的离散人工蜂群算法，但文献^[6]并未考虑从整体上提升人工蜂群算法求解性能，而是着重对比分析了产生邻域解的方法；而文献^[7]又主要基于蚁群算法求解TSP思想，对每个城市逐一进行选择后生成解向量，导致算法求解速度较慢.为了提升TSP求解性能，本文提出了一种新的离散人工蜂群算法，该算法考虑了空间探索和局部求精间的平衡.通过对TSPLIB 标准库中多个实例进行对比测试，结果表明，本文算法求解TSP具有较好的效果.

1 人工蜂群算法及其离散化定义

ABC算法的寻优过程模拟蜜蜂寻找优质花蜜源的行为，按分工将人工蜂群分为引领蜂、跟随蜂和侦查蜂三种角色，角色之间基于一定条件进行转变.每个蜜源对应问题的一个可能解，蜜源的收益度代表问题解的质量，每个引领蜂对应一个确定的蜜源，并在迭代中对其邻域进行搜索.引领蜂完成搜索后将所搜索到的信息与跟随蜂共享，跟随蜂按照一定的概率选择蜜源，继续在其邻域进行搜索，若引领蜂在给定的搜索次数内没有获得更好的蜜源，便放弃该蜜源，并且引领蜂将转变为侦查蜂随机搜索可行的新蜜源.

ABC算法是一种群智能优化算法，而探索和开采是决定群智能优化算法性能的两个主要因素.探索能力越好，个体在全局范围内搜索未知区域的能力越强，即全局寻优能力越强；开采能力越好，个体在局部范围内搜索更优解的能力越强，即局部求精的能力越强.因此，要保证ABC算法的求解质量，需要协调和平衡探索及开采的过程，这也是智能群体算法需要解决的一个核心问题^[8].

ABC算法在解决连续变量问题时，缺乏对探索和开采能力的考虑，导致算法求解速度和求解质量有时难以得到保证，本文提出的改进离散人工蜂群算法通过对引领蜂、跟随蜂和侦查蜂的搜索策略进行重新定义，较好地协调和平衡了算法的探索及开采能力.为了便于描述,本文给出以下定义.

定义1 收益比r_i：每只蜜蜂搜索到的蜜源收益度fit_i与蜂群中最优个体蜜源收益度fit_best的比值.对于TSP，fit_i与目标函数f(X_i)的关系为

定义2 相似度s_i,j：是指任意两个解向量X_i和X_j的相似程度，定义为s_i,j=M/N，式中N为城市的数目，M为两个解向量具有相同邻接边的个数，可见s_i,j∈[0,1].

例1 有一个10城市的TSP，其两个解向量分别为X₁=[1 5 6 2 4 8 3 10 7 9]和X₂=[1 3 6 2 4 8 10 5 7 9]，则N=10,两个解向量具有5个相同邻接边：6→2，2→4，4→8，7→9，9→1，即M=5，所以s_i,j=0.5.

定义3 排斥操作：是指对解向量X_i和X_j(i≠j)的相同邻接边城市序列重新进行随机排序得到一个向量Y，再把该向量作用于X_j，从而使解向量X_j和X_i相似度下降.

例2 解向量X₁和X₂同例1，可见相同邻接边城市序列为6，2，4，8，7，9，1，若Y=[2 0 8 6 1 4 0 0 7 9]，经排斥操作后

此时，解向量X₂和X₁具有1个相同邻接边7→9，则相似度为0.1，可见，相比变换前的相似度0.5有所下降.

定义4 学习操作：是指对解向量X_i和X_j=(i≠j)的不同邻接边城市序列重新进行随机排序得到一个向量Y，再把该向量作用于X_j，从而使解向量X_j和X_i相似度上升，即学习操作为排斥操作的反向操作.

在明确定义1~定义4的基础上，本文提出了离散人工蜂群算法.该算法的蜂群同样分引领蜂、跟随蜂和侦查蜂三种角色，但角色之间不再基于设定的搜索次数进行转换，而是基于定义的收益比，并且为了平衡算法探索及开采能力，对每种角色的搜索策略重新进行了制定.

离散人工蜂群算法中引领蜂的作用与ABC相同，同样是在每个蜜源的邻域内寻找更优蜜源，但由于求解的TSP是离散变量问题，邻域解的产生机制需要重新定义，本文寻优初期采用2-opt邻域结构^[9]对每个蜜源进行邻域搜索.2-opt邻域操作时，首先在当前解中分别移走两条不相邻的边，然后针对这两条边对应的4个城市重新进行操作：将第1条边上的第1个城市与第2条边上的第1个城市相连，第1条边上的第2个城市与第2条边上的第2个城市相连；由此得到的新解作为邻域解.

例3 有一个5节点的TSP，解为X_i=[1 2 3 4 5]，见图1a；对边(1,2)和(4,5)进行2-opt变换，则得到邻域解X_i^′=[1 4 3 2 5]，见图1b.

图 1(Figure 1)

Fig. 1

图 1 2-opt邻域操作示意图 Fig. 1 Neighborhood operation of 2-opt(a)—Xi=[1 2 3 4 5]； (b)—Xi′=[1 4 3 2 5].

对比解X_i和X_i^′可以看出，为了保证经过 2-opt变换的解为TSP的可行解，实质上 2-opt邻域操作是倒置X_i第1条边的第2个城市和第2条边第1个城市之间的城市序列.

离散人工蜂群算法中跟随蜂的作用与ABC相同，是基于轮盘赌方法按照式(2)计算出的概率选择某一蜜源，在其邻域内作局部搜索.

离散人工蜂群算法中跟随蜂搜索与ABC不同的是引入了禁忌表tabu_i(i=1,2,…,SN)，用来记录蜜蜂对于蜜源X_i的最近邻域搜索信息，如例3中蜜源X_i的最近邻域解X_i^′是通过倒置其城市2和城市4之间的序列得出的，对于蜜源X_i^′如果再对以这两个城市分别为首和尾的边(2,5)和(1,4)进行2-opt变换，得到的邻域解又将是X_t ；这样的搜索是毫无意义的，为了避免在蜜源X_j同一邻域内反复搜索，提高算法的开采能力，对于例3禁忌表tabu_i只需记录2，4两点，即记录第1条边的第2个城市和第2条边第1个城市.

ABC算法中侦查蜂是由引领蜂转变而来的，其作用是负责发现可能陷入局部最优的个体，并对其进行更新，从而降低算法出现早熟的概率.引领蜂转变为侦查蜂的条件是其在设定的搜索次数内没有获得更好的蜜源.在ABC算法中，侦查蜂转变机制及搜索行为存在以下3个问题：

1) 侦查蜂的角色转变依赖于设定的搜索次数，求解不同实际问题时该参数并不相同，难以进行设定，且如设置不当会影响算法跳出局部最优的能力.

2) 侦查蜂是在发现个体已经早熟收敛时才被转变，并探索新的蜜源，这样导致算法找到全局最优的速度较慢.

3) ABC算法中侦查蜂随机地搜索新蜜源，并未考虑当前处于主导搜索的引领蜂所处的位置，无法保证尽可能在全局范围内搜索到更多的新蜜源，从而抑制算法的探索能力.

为了解决以上不足，本文定义了收益比这一指标，引领蜂基于该指标转变为侦查蜂.其优点一方面在于解决不同实际问题时该指标更易被设定；另一方面在于蜂群角色及搜索机制依赖搜索次数的动态变化.寻优初期发现个体收益比相对较差时，引领蜂立刻转变为侦查蜂，并基于轮盘赌方法执行排斥操作以便基于当前引领蜂位置信息尽可能在全局范围内寻找更优的蜜源；在寻优后期发现个体收益比都较好时，引领蜂则不再转变为侦查蜂，且搜索机制从2-opt操作转变为基于轮盘赌方法的学习操作.即寻优初期充分考虑种群个体多样性，提高算法的探索能力；寻优后期充分考虑种群信息共享，提高算法的开采能力和寻优速度.

归纳起来，应用离散人工蜂群算法求解TSP步骤如下：

步骤1 初始化蜂群.随机初始化蜜源，即随机生成种群初始解，并按式(1)计算各蜜源的收益度.

步骤2 引领蜂搜索阶段.计算收益比，若收益比不都大于或等于设定值r，则引领蜂执行2-opt 操作，搜索新蜜源，得到候选邻域解X_i^′；否则采用轮盘赌方法按照式(2)计算的概率选择蜜源X_j，执行学习操作，搜索新蜜源，得到候选邻域解X_i^′，若候选解收益度fit_Xi^′大于fit_Xi，则用X_i^′代替X_i，反之保留X_i不变.

步骤3 跟随蜂搜索阶段.跟随蜂采用轮盘赌方法按照式(2)计算的概率选择蜜源X_i，并在可允许操作范围内(除tabu_i外的邻域)执行2-opt操作，搜索新蜜源，得到候选邻域解X_i^′，若候选解收益度fit_Xi^′大于fit_Xi，则用X_i^′代替X_i，反之保留X_i不变.

步骤4 侦查蜂搜索阶段.计算收益比，若收益比不都大于或等于设定值r，则放弃收益比小于设定值r的蜜源X_i，并采用轮盘赌方法按照式(2)计算的概率选择蜜源X_j，执行排斥操作搜索新蜜源X_i^′，否则转步骤5.

步骤5 记录迄今为止搜索到的最好解.

步骤6 检查是否达到算法终止条件，若是，则结束；否则转步骤2.

收益比设定值r是离散人工蜂群算法主要参数，下面通过仿真实验分析该参数对算法求解性能的影响.实验环境为CPU AMD Athlon 64 X2 Dual Core Processor 4 400+ 2.29 GHz，内存2.00 GB，操作系统为Windows XP，编程软件为MATLAB 7.1，在给定其他参数的条件下，针对Att 48 TSP，采用不同r值进行实验.实验中其他参数设置：最大迭代次数Tmax=2 000，蜜蜂数目m=48，算法独立运行20次，表1记录了不同r值的运行结果.

表 1

Table 1

表 1(Table 1)

表 1 r对离散人工蜂群算法性能的影响 Table 1 Effect of r on the performance of discrete artificial bee colony algorithm r 最好值 ×10-4 最差值 ×10-4 平均值 ×10-4 标准差 ×10-2 平均运行时间 /s 1 3.41 3.61 3.52 5.90 9.922 4 0.9 3.37 3.59 3.49 4.96 9.037 0 0.8 3.36 3.51 3.45 3.60 9.034 3 0.7 3.40 3.54 3.46 3.52 9.046 4 0.6 3.46 3.62 3.56 4.82 9.688 1 0.5 3.49 3.68 3.57 4.87 9.643 7 0.4 3.46 3.67 3.58 5.45 9.623 7 0.3 3.50 3.67 3.59 4.49 9.588 0 0.2 3.47 3.64 3.58 4.35 9.621 3 0.1 3.47 3.66 3.58 5.86 9.602 1 0 3.45 3.68 3.58 6.30 9.622 0

表 1 r对离散人工蜂群算法性能的影响 Table 1 Effect of r on the performance of discrete artificial bee colony algorithm

从表1可以看出，在求解时间方面，当r逐渐减小时，算法平均运行时间并没有明显的变化规律，在r为0.9，0.8和0.7时，算法平均运行时间相对较短，其中r为0.8时的平均运行时间9.034 3最短；但从整体看，算法平均运行时间变化较小，这主要是由于无论r取何值，算法迭代过程中引领蜂、跟随蜂和侦查蜂的数量之和始终不变，即本次迭代转变为侦查蜂的引领蜂下次迭代时不再执行引领蜂操作，并且基于收益比的蜂群在不同阶段的搜索策略复杂度相差无几.在求解质量方面，当r逐渐减小时，求解性能逐渐变好后又逐渐变差，在r为1，0.6，0.5，0.4，0.3，0.2，0.1和0时，离散人工蜂群算法所得到的平均值都在3.50E+04以上，最差值都在3.60E+04以上，而在r为0.9，0.8和0.7时算法得到的平均值都在3.50E+04以下，最差值都在3.60E+04以下，其中r为0.8时，算法所得到的平均值3.45E+04、最差值3.51E+04、最好值3.36E+04均为最小，并且此时得到的标准差3.60E+02仅大于r为0.7的标准差3.52E+02，也相对较小；因此可以认为：对此问题，r为0.8时离散人工蜂群算法具有较好的求解性能.

为了进一步验证本文算法的可行性和有效性，选用国际上通用的TSPLIB测试库中多个实例进行测试，并将测试结果与相关文献中的RRS ABC^[6]，ABC^[7]和求解TSP性能较好的蚁群优化(ant colony optimization，ACO)算法进行对比分析.文献^[6]对多种邻域结构的ABC算法进行了仿真实验，RRS邻域结构与本文最相似，因此选用该邻域结构的ABC算法进行对比.

算例中的数字表示城市数目,括号内的数是已知最优解，计算结果“—”表示对比文献未给出该项指标计算结果.实验环境与前面相同，离散人工蜂群算法参数设置为：最大迭代次数Tmax =2 000，r=0.8，蜜蜂的数目m=n，其中n是城市数目；ACO算法参数设置为：最大迭代次数Tmax =2 000，蚂蚁的数目m=n，α=1，β=5，ρ=0.9，本文算法和ACO算法对于每个算例独立运行20次，计算结果见表2.

表 2

Table 2

表 2(Table 2)

表 2 标准测试问题的计算结果 Table 2 Results for benchmark test problems 实例 计算指标 本文算法 RRS ABC[6] ABC [7] ACO Bays29 (2 020) 最好值 2 020 — 2 020 2 040 平均值 2 027.8 — 2 031.4 2 061.7 迭代次数 2 000 — 50 2 000 运行时间 5.11 — — 285.98 Oliver30 (423.74) 最好值 423.74 423.74 423.5 425.82 平均值 425.00 423.74 432.5 428.76 迭代次数 2 000 105 50 2 000 运行时间 5.36 — — 317.7 Dantzig42 (699) 最好值 679.20 — 699 696.12 平均值 692.05 — 710.2 716.46 迭代次数 2 000 — 100 2 000 运行时间 8.95 — — 672.48 Eil51 (429.98) 最好值 431.24 428.87 426 457.79 平均值 444.09 431.11 427.6 468.51 迭代次数 2 000 105 50 2 000 运行时间 10.36 — — 1001.04 Berlin52 (7 544.37) 最好值 7 680.78 7 544.37 7 542 8 048.07 平均值 7 941.27 7 562.80 7 573.4 8 131.51 迭代次数 2 000 105 150 2 000 运行时间 10.76 — — 1 055.01

表 2 标准测试问题的计算结果 Table 2 Results for benchmark test problems

从表2可以看出，本文算法与文献^[6]中的RRS ABC算法相比，在实例Oliver30，Eil51和Berlin52中，RRS ABC算法均得到了不差于已知最优解的结果，本文算法虽然仅在Oliver30中得到了与已知最优解相同的结果，但对于所有对比实例，本文算法比RRS ABC算法迭代次数都减少了98%，且本文算法求解步骤也并不复杂，而计算结果平均值却仅增加了不大于0.5%，计算结果最好值增加不大于1.8%.

本文算法与ACO算法相比，对5个实例，本文算法计算所得的最好值、平均值都相对更小，且对于Bays29，Oliver30和Dantzig42，其标准差也更小；更重要的是，对5个实例，本文算法计算时间分别节省了98.21%，98.31%，98.67%，98.97%和98.98%.

本文算法与文献^[7]中的ABC算法相比，ABC算法对于所有实例均得到了不差于已知最优解的结果；本文算法对于实例Bays29，Oliver30得到了与已知最优解相同的结果；对于实例Dantzig42，本文算法计算结果比已知最优解及ABC算法计算所得的最优解均少了19.8.图2为Dantzig42实例的实验仿真图，对应的最优路径为[33,34,35,36,37,38,39,40,41,42,1,2,3,4,5,6,7,8,9,10,25,26,27,24,11,12,23,22,17,16,13,14,15,18,19,20,21,28,29,30,
31,32].另外，对于这3个实例，本文算法的平均值都相对更小.对于实例Eil51和Berlin52，本文算法未得到已知最优解，比文献^[7]中的ABC算法计算结果略差；但ABC算法求解步骤主要以ACO算法思想为基础并融合了其他操作，在种群数相等时，其求解时间至少应与ACO算法相当.从本文ACO算法仿真结果及文献^[10] 中的ACO算法仿真结果看，ACO算法运行的确需要较长时间，因此，文献^[7]中的ABC算法计算时间相对较长.

图 2(Figure 2)

Fig. 2

图 2 实例Dantzig42的实验仿真图 Fig. 2 Simulation diagram of Dantzig42.tsp(a)—最优路径； (b)—最好值进化曲线.

综上可见，本文算法与文献^[6]中的RRS ABC、文献^[7]中的 ABC和ACO相比，综合权衡了求解时间和求解质量两项指标，具有较好的求解性能.

以求解TSP为例,本文提出了一种离散人工蜂群算法，将连续型人工蜂群优化算法推广到离散域.算法基于定义的收益比指标进行蜂群角色及搜索机制的转变，定义排斥算子以保持种群的多样性，引入禁忌表并定义了学习算子以提高算法的局部求精能力和寻优速度，从而在较好地协调算法空间探索和局部求精能力的同时，加快了算法的收敛速度.实验结果表明，本文算法能够在较短时间内找到相对满意解，提高了TSP的求解效率.