- 1 -
蜂群算法在 TSP问题上的参数改进
李峰磊，丁海军，方兴
河海大学计算机及信息工程学院，江苏常州 （213022）
摘 要：在分析蜜蜂采蜜原理和蜂群算法模型的基础上，本文对蜂群算法中的关键参数进行
了理论分析，并改进了算法对局部最优解的控制机制。在TSPLIB上的实验结果表明，改进
算法全局搜索能力增强，具有较好的发现最优解的能力。
关键词：蜂群算法；参数分析；TSP
中图分类号：TP30 文献标识码：A
0 引言
蜂群算法（Artificial Bee Colony Algorithm，ABC）是建立在蜜蜂自组织模型和群体智
能基础上的一种非数值优化计算方法。Seely（1995）最先提出了蜂群的自组织模拟模型。
在模型中，虽然各社会阶层的蜜蜂只完成单一的任务；但蜜蜂通过摇摆舞、气味等多种信息
交流方式，使得整个蜂群可以协同完成如构建蜂巢、收获花粉等多种工作。
组合优化问题是指寻找一组离散变量的值，使得指定目标函数的解达到最优。许多重要
实际应用和有理论研究价值的优化问题本身就具有组合性质。旅行商问题（traveling salesman
problem，TSP）是经典的组合优化问题，其目的是寻找周游一次所有城市并回到起点城市
的最短路径。国际上一般使用 TSP标准库来检验组合优化算法的求解质量。
本文在对改进蜂群算法分析研究的基础上，分析了其参数的效能，并对有突出影响的限
制性参数进行了改进尝试。在 TSPLIB上的仿真实验结果表明，本文改进算法具有较好的寻
找最优解的能力。
1 蜂群算法概述
[4]一个蜜蜂种群通常包括女王、雄蜂和工蜂。工蜂中有多种角色（role）：引领蜂（leader）、
侦察蜂（scouter）和跟随蜂（follower）。蜜蜂采蜜的群体智能通过不同角色蜜蜂间的交流、
转换和协作来实现。在 ABC 模型中，除了上述几种蜜蜂角色外，还引入食物源（source）
来代表各种可能的解；蜜蜂采蜜（食物源）的过程也就是搜寻最优解的过程。蜜蜂的基本的
行为有：搜索（search）食物源、为食物源招募（recruit）和放弃（abandon）食物源。
在算法中，食物源的价值由收益度函数体现。收益度是算法的判决函数，直接决定优化
的方向。整个系统的目标是求解收益度函数的最优解。引领蜂和其正在采集的食物源相对应，
食物源是引领蜂的引导目标。引领蜂通过与其它蜜蜂分享信息招募更多的蜜蜂采集相应的食
物源。信息的分享程度与食物源的收益度成正比。侦察蜂随机搜索蜂巢附近的新食物源，增
强了算法跳出局部最优点的能力。跟随蜂由引领蜂处获得食物源的收益度信息，依据轮盘赌
的方式选择食物源采集，在算法的收敛过程中有重要作用。
蜂群算法中的各种蜜蜂在舞蹈区交流信息。引领蜂通过摇摆舞完成为食物源的招募工
作。舞蹈的剧烈程度与相应食物源的收益度成正比。所有跟随蜂都等候在舞蹈区，根据观察
到的舞蹈选择相应的食物源采集。在食物源收益度相对较低时，引领蜂会放弃相应的食物源
转而搜索新的食物源，其角色也转变为侦察蜂。
算法中蜜蜂的采蜜流程如下：
- 2 -
初始时刻，所有蜜蜂没有任何先验知识，其角色都是侦察蜂。随机搜索到食物源后，侦
察蜂返回蜂巢的舞蹈区，根据食物源收益度的相对大小，侦察蜂可以转变为上述任何一种蜜
蜂。转变的原则如下：
I） 所采集食物源的收益度相对很低时，它可以再次成为侦察蜂搜寻附近的食物源。
其转变结果是放弃上次采集的食物源。
II） 所采集食物源的收益度排名小于临界值（如排名在后 50％）时，它可以在观察
完舞蹈后成为跟随蜂，并前往相应的食物源采蜜。
III） 所采集食物源的收益度排名高于临界值时，它成为引领蜂，继续在同一食物源
采蜜，并在舞蹈区招募更多的蜜蜂采集相应食物源。
蜂群算法中，求解最优解的过程即是寻找高收益度食物源的过程。引领蜂有保持优良食
物源的作用，具有精英特性。跟随蜂增加较好食物源对应蜜蜂数目，加速算法的收敛。侦察
蜂随意搜索新的食物源，帮助算法跳出局部最优。
2 有关 TSP问题的改进蜂群算法
TSP 是求解最短路径的问题，故定义食物源收益度为蜜蜂周游 TSP 城市一圈所走路径
长度的倒数。建立角色矩阵 role，记录下次迭代各个蜜蜂的角色。角色依据此次迭代中各蜜
蜂对应食物源的收益度选择，按照排名先后定义。其中侦察蜂的比例定义 PScout（如 10％），
引领蜂比例为 PLeader。首先选择 PLeader的引领蜂、PSout的侦察蜂，剩余蜜蜂为跟随蜂。
[3]定义 ( )mktabuk ,,2,1 "= 为纪录第 k个蜜蜂所走过的城市。在从节点 i转移到节点 j
的过程中：引领蜂完全重走上一次的路径， ktabu 不改变；跟随蜂和侦察蜂都依据下式计
算在 t时刻第 k个蜜蜂节点转移的概率：
⎪⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
∉
⎟⎟⎠
⎞
⎜⎜⎝
⎛
⎟⎟⎠
⎞
⎜⎜⎝
⎛
= ∑
∈
otherwise
tabujs
d
d
p k
alloweds is
is
ij
ij
ij
0
,
1
1
4
4
ρ
ρ
( )1
其中 ijd 、 isd 分别表示节点 i与 j、i与 s之间的距离，两种蜜蜂转移概率上的区别在于：
侦察蜂，
tij
1=ρ ，其中 t为蜜蜂未走过的节点个数； ( )2
跟随蜂：
⎪⎪⎩
⎪⎪⎨
⎧
⎪⎩
⎪⎨
⎧
−
−
=
过道路可选择径不含引领蜂走
道路可选路径含引领蜂走过不选择引领蜂的道路
选择引领蜂的道路
t
tij
1
1
1 γ
γ
ρ ( )3
其中γ 表示引领蜂的引导性强弱。
- 3 -
开 始
变 量 初 始 化
所 有 蜜 蜂 都 为
侦 察 蜂 ， 计 算
矩 阵 T a b u和
R o l e
是 否 满 足 终 止 条
件 ？
局 部 变 量 初 始
化
对 侦 察 蜂 随 机
选 择 路 径 并 记
录 T a b u表
对 跟 随 蜂 选 择
引 领 蜂 跟 随 并
复 制 引 领 蜂 路
径
路 径 变 异
计 算 适 应 度 和
角 色 矩 阵 R o l e
存 储 每 次 迭 代
的 结 果
输 出 结 果
结 束
是
路 径 交 叉
否
图 1 蜂群算法流程图
Fig1 Flow chart of Artificial Bee Colony Algorithm
[1]为了克服算法收敛性过强，容易陷入局部最优的问题，改进蜂群算法融合了遗传算法
的特性，提高其全局搜索的能力。同时引入矩阵记录每一个蜜蜂担任引领蜂的次数，定义
LeaderMaxCount 为蜜蜂连续担任引领蜂最大次数。当蜜蜂长时间担任引领蜂时，其招募的
跟随蜂越来越多，整个蜂群会趋于一个或几个食物源，蜂群极易陷入局部最优。参数
LeaderMaxCount可以控制蜜蜂连续担任引领蜂的次数。算法的改进如下：
I） 当蜜蜂连续 LeaderMaxCount次走过路径长度变化小于 1％时，强制使其放弃该
解，在下一轮循环中成为侦察蜂。
II） 每次循环结束后，对所有蜜蜂的路径进行交叉、变异，对最差解进行替换
i) 用每次循环中最短路径替代最长路径。
- 4 -
ii) 对所有路径进行交叉操作，交叉点 position采用随机选择策略。
iii) 对所有路径进行变异操作，变异策略采用交换变异点附近的两个城市的访
问顺序。
算法流程如图 1所示：
路径记录矩阵 Tabu根据各蜜蜂在角色矩阵 Role中的取值计算，Role（bee）为 Scout
时，随机搜索路径；为 Follow时，轮盘赌选择 Leader跟随，直接复制 Leader的路径；为
Leader时，路径则不改变。Role矩阵则根据前一轮迭代的适应度计算，由参数 PScout，PLeader
和 LeaderMaxCount共同控制。
3 蜂群算法的参数分析与改进
蜂群算法中，PScout 表示侦察蜂在蜜蜂中的比例。侦察蜂有随机搜索新食物源（解）
的作用。PScout取值太大，虽然能够引入较多新的个体，但也有可能破坏掉很多好的路径，
使得蜂群算法的性能近似于随机搜索算法；若 PScout 取值太小，则蜂群获取新食物源和抑
制早熟的能力就会变差。因而，PScout 的取值应兼顾加快收敛速度和跳出局部最优两个方
面。
PLeader代表了引领蜂比例大小。引领蜂具有保持路径的能力；跟随蜂能在引领蜂路径
的邻域内寻找更优解。两种蜜蜂是蜂群算法收敛的主要原因。PLeader取值较大时，由于引
领蜂在开始阶段就有较强存储路径的能力，算法收敛比较慢，随机性强。Pleader 取值较小
时，算法主要体现在跟随蜂的邻域搜索能力上，系统收敛快，但收敛以后的系统稳定性强，
抑制早熟的能力差。
[2]蜂群算法通过引入参数 LeaderMaxCount，限制引领蜂路径长度（解）连续小范围变
化的次数。这在一定程度上增强了算法跳出局部最优解的能力，但 LeaderMaxCount仅仅通
过调整引领蜂的角色转变为侦察蜂来简单控制局部最优解，对蜂群的控制能力较弱，并且调
整也只限制在下一次迭代过程内。本文引入矩阵 TourForbid来记录蜂群需要限制的局部最优
路径，仍使用参数 LeaderMaxCount作为控制参量。
在计算蜜蜂角色矩阵 Role 的函数 CaculateRole 中引入 TourForbid，算法流程如图 2 所
示。
TourForbid 矩阵直接从 Tabu 中取值，存储需要限制的路径。限制路径采用队列的方式
存储，新路径替代最早放入 TourForbid的路径。
当路径超过 LeaderMaxCount 次不发生变化时，则将其放入 TourForbid。在该路径被移
出 TourForbid前，如果出现同一路径，遵循该路径的所有蜜蜂都转变为侦察蜂。
- 5 -
图 2 引入 TourForbid的蜜蜂角色计算流程
Fig2 Flow chart of role calculating syncretized with TourForbid
4 仿真实验分析
TSPLIB是标准的组合优化问题测试库，以其中 eil101问题进行仿真实验。每次实验均
设定其它待研究参数，而只讨论某一个参数的合理取值。最大迭代次数 500。结果如表 1所
示。
表 1 参数取值测试
Parameter test
定参设置 变参设置 结果 主要收敛完成的区间
Pscout= 697 50～100
Pscout= 677 150～200
Pscout= 689 200～250
Pscout= 731 250～300
LeaderMaxCount ＝ 500 ，
Pleader＝m/2
Pscout=1 完全随机，无解 无
Pleader＝m/4 671 250～300
Pleader＝m/3 682 100～150
Pleader＝m/2 677 100～150
Pleader＝m3/4 724 100～150
LeaderMaxCount ＝ 500 ，
Pscout=
Pleader＝m 完全随机，无解 无
LeaderMaxCount＝10 718 50～100
LeaderMaxCount＝20 700 50～100
LeaderMaxCount＝50 695 150～200
LeaderMaxCount＝100 680 150～200
LeaderMaxCount＝250 685 250～300
Pscout=,Pleader＝m/2
LeaderMaxCount＝500 697 150～200
从表 1 可以看出，本文改进算法 PScout 参数在 处效果较好。相对 处 250～300
- 6 -
次的收敛区间，在 处，算法有快一倍的收敛速度，同时取得的平均解也是最优的。参数
PScout在 附近能达到兼顾收敛性和抑制早熟的效果，并取得相对优解。同样的，Pleader
在 m/2附近，LeaderMaxCount在 50附近，单独测试取得的效果较优。仿真结果证明了第三
小节的分析。
本文对参数 LeaderMaxCount采用了禁忌表控制的思想，其仿真对比效果如表 2：
表 2 改进前后实验结果对比
Contrast improved experiment results with original ones
实验次数 改进前算法 改进后算法
1
2
3
4
5
均值
最优解
禁忌表使得任一较优路径（解）都有了一定的生存期，生存期的长度为 LeaderMaxCount。
超过生存期的路径将被强制放弃。实验结果表明，禁忌表的引入能有效的控制引领蜂和跟随
蜂相互作用而引起的加速收敛，增强了算法的全局搜索能力，使算法获得更好的解。
5 结束语
蜂群算法是一种新型的进化算法，其研究模拟刚刚起步，有很多问题有待改进。本文在
研究蜂群中不同角色间的协作特性的基础上，改进蜂群算法的角色转换机制，对算法的主要
参数性能进行了分析验证，并引入禁忌表来增强算法的搜索能力。以 TSPLIB的 eil101问题
进行实验仿真表明，本文改进算法全局优化能力强，具有较好的发现最优解的能力。
参考文献
[1] 高尚，杨静．群智能算法及其应用[M]，北京：中国水利水电出版社，。
[2] 周明，孙树栋．遗传算法原理及应用[M]，北京：国防工业出版社，。
[3] D,Karaboga, The On the performance of Artificial Bee Colony (ABC) algorithm[J].Applied Soft
Computing Journal,2007,(5)：3-7。
[4] Chin Soon Chong, Malcolm Yoke Hean Low. A bee colony optimization algorithms to job shop
scheduling[J].IEEE Trans on Proceedings of the 2006 Winter Simulation Conference,2006：1-3。
- 7 -
The parameter improvement of Bee Colony Algorithm in
TSP problem
Li Fenglei，Ding Haijun，Fang Xing
Department of Computer Science and Information Engineering，Hohai University，Changzhou，
Jiangsu (213022)
Abstract
Based on the analysis of nectar searching and honeybee algorithm model,this paper studys the
important parameter of Bee Colony algorithm in theory and improves the control mechanism of local
optimal experiment result on the TSPLIB indicates that this algorithm has better ability of
global search and discovering the best solution.
Keywords：Bee Colony Optimization；parameter analysis；TSP
