基于混合行为蚁群算法的研究
第 20卷 第 1期
Vo1．2O No．1
控 制
Control
与
and
决 策
D ecision
2005年 1月
Jan．2005
文章 编号 ：1001—0920(2005)01—0069—04
基于混合行 为蚁群算 法的研 究
胡 小兵 ，黄 席樾
(1．重 庆 大学 数理学 院 ，重 庆 400044；2．重庆 大学 自动化 学 院 ，重 庆 400044)
摘 要 ：为在 加 快算 法 收敛 速度 的同 时又 能避 免停 滞现 象 ，提 出一种基 于 混合 行 为 的蚁 群 算 法．首 先 就 蚂蚁 行 为对
算法 性 能 的影响进 行 了分 析 ，在 此基 础上提 出 了该 算法 的模 型 ；然 后定 义 了蚂 蚁行 为 ，并 为该 算法 设计 了 4种 具体 的
蚂蚁 行为 ，根据 模 型实 现 了该算 法．实验 结果 表 明，该 算 法在性 能 上远优 于蚂 蚁 系统．
关 键 词 ：蚁 群 算法 ；混合 行为 ；旅行 商 问题
中图 分类 号 ：TH18 文 献标识 码 ：A
O n hybrid behavior based ant colony algorithm
H Xiao—bing 。H UAN G Xi—yue。
(1．School of Science， Chongqing U niversity， Chongqing 400044， China； 2． School of Autom ation， Chongqing
University，Chongqing 400044，China．Correspondent：HU Xiao—bing，E-mail：iamhxb@ sina．com)
Abstract：In order to accelerate the convergence rate of the algorithm while avoiding the stagnation behavior，a
hybrid behavior based ant colony algorithm (HBACA)is proposed．The influence of ant behavior on performance of
algorithm is analyzed and a model of ant colony algorithm is proposed．The ants behavior and four kinds of concrete
ants behaviors are defined for HBACA algorithm and the algorithm is im plemented based on the mode1． The
experimental results show that HBACA algorithm is better than ant system s．
Key words：ant colony algorithm ；hybrid behavior；traveling salesm an problem
1 引 言
针对蚂蚁 系统 (AS)[1 中存在 的缺点 ，人们提出
了许 多改进的蚁群算法 。 ]．文献[3]通过只增加最
优路 径上信 息素 的浓 度 ，更 好地利 用 了过去积 累的
知识 ，从 而加快 了算法 的收敛 速度 ；文献 [4]将信息
素的值 限制在 [rmi ，rm ]内 ，极大程度地避免 了算法
陷入局 部最 优 ；文献 [5]根 据算 法搜 索 的情 况 动态
修 改需要增加 的信息素量 ，即采 用时变 函数 Q(r)来
代 替 AS算 法 中的常数 Q，使 得算法 跳离局 部最优
解 ；文献 [6]提 出一 种 自适应 改变蒸 发 系数 的策 略
来避 免算 法 陷入停 滞状 态 ；文献 [7]则通 过 引入 变
异算子 来避 免算法 出现停滞现象 ．
经分 析不难看 出 ，以上算法 主要从 3个方 面对
AS作 了改进 ：
1)将信息素 限制在一定 区间 内，避免某些边 上
的信息素为零 ；
2)加 强对 过去历史知识 的利用 ；
3)通 过算法 的内部状 态 ，或根据 定性 的分析 来
判断蚁群 当前 的搜索能力 ，从而通过对 信息素更新 、
蒸发 系数 的改 变以及 释放的信息素量 Q等 的改变来
避免停滞现象．
本文则从完 全不 同的角 度 ，提 出一 种基 于混合
行为的蚁群 算 法 (HBACA)．实验结 果表 明 ，该 算法
具 有较 好 的性 能 ．
2 HBACA算法的原理 、模 型及实现
2．1 蚂蚁行为对蚁群算 法的影响
蚁群 算 法实 际 上是 一 种正 反 馈 原 理和 某 种启
发式相结合的产物．在算 法早期迭代过程 中 ，因各 路
收稿 日期 ：2004—03一l1；修 回 日期 ：2004—05—27．
基 金项 目 ：重 庆 大学 基础 及应 用基 础研 究项 目(717411061)．
作 者简 介 ：胡小 兵 (1975一 )，男 ，湖北 京 山人 ，讲 师 ，博士 ，从 事计 算智 能 、机 器人 控制 技术 的研 究 ；黄 席樾 (1943一 )，
男 (回族 )，重 庆奉 节人 ，教授 ，博 士生 导师 ，从 事机 器人 控制 技术 、人 工智 能 及机 器视 觉 的研究 ．
维普资讯 http://www.cqvip.com
70 控 制 与 决 策 第 2O卷
径上 信息 素量差 别不 大 ，蚂蚁 主要 根据城市 之 间的
距离信息 (启 发式信息 )来寻找较 好解 ，这时 的蚁 群
算法等价 于贪 婪算 法．当算 法迭代到一定代数后 ，较
好路径上 的信 息素 明显高 于其 他边上 的信息 素 ，此
时 ，蚁群 主要通 过信 息素 的交互及 通信 来寻找较 好
解 ，即信 息素越 强 的路径成 为最优 路径 的可能性 越
大．算法 在此 阶段 的搜 索 过程 主要 利用 了正反馈 原
理．然而该过程在 强化性能较好解 的同时 ，却容易导
致停滞 现象．
AS算法在 寻优过程 中，很大程度上受早期发现
的较好 解 的影响 ，这 些较 好解 以极大 的概率 引导蚁
群走 向局 部最 优解 ，这 正是 AS算 法容 易 出现 停滞
现象 的 主要原 因．解 决 AS算 法 中的停滞 现象 和保
证其具 有较 强 的探 索 能力 的方 法 就是在 “探 索”和
“利用 ”之 间建立 一个 平衡 点．也 就是说 ，既要使算
法的搜索 空 间尽 可能 的大 ，以寻找 那些 可能存在 最
优解的解空 间 ，同时也要充分利用有效 的历史知识 ，
使算法搜索 的侧重点放在那些 可能具 有最优解 的空
间 ，从 而 以更大 的概率收敛到全局最优解．
2．2 HBACA 算 法 的模 型 及 实 现
HBACA 算法采 用具有不 同行 为特征 的蚂 蚁相
互协作来 发现 问题的解．如 图 1所 示 ，HBACA 模型
由 4部分 组成 ．图 中的 ① 为蚂 蚁 ，每 只蚂蚁 可以拥
有 自己的行 为 特征 ，该行 为 由规则 集 (rule set)④ ，
储 存在环 境 (environment)③ 中的知识 以及状 态空
间 (state space)② 一起决 定．状 态空 间与待求 解 问
题 具有一一 映射关 系 ，蚂蚁 在其 中移动 ，逐 步构造 问
题 的可行解 ．图 中蚂蚁 间 的虚箭头 表示 蚂蚁之 间不
能进行直 接通讯 ，而是 在移 动过程 中通 过环境 间接
通讯．蚂 蚁利用通道 (channe1)读取 ／写入信息到环
境 ．环境 储存 了蚁 群过去行动 中获取 的历史知识．下
面 首 先 给 出 蚂 蚁 行 为 的定 义 ．
定义 1 蚂蚁行 为 ：蚂蚁在前进过程 中 ，用 以决
定 其 下一 步移动 到哪一个 状态 的规则集合 ．通 常情
图 1 HBACA算 法 的模型
况 下 ，蚂 蚁 行 为 可 表 示 为 action一 {皿 li一 1，2，? ，
)，其 中 为影 响蚂蚁行 为的第 i个 因素．
由于 HBACA算法 中影 响蚂蚁行 为的因素有 规
则集 、环 境 、状 态空 间等 ，针 对待 求 解 的 TSP问题 ，
由定义 1定义如下 4种类 型的蚂蚁行 为．
行为 1(action1) 蚂蚁 以随机方式选择 下一 座
要 到 达 的城 市 ．
行为 2(action2) 蚂蚁 以贪婪方式选择 下一 座
要 到 达 的城 市 ，即
／∑ ．∈ ( )；
户0一 6"J^“ (1)
1 0,0therwise．
其 中 ： 。』一 1／d d 为城 市 i与城市 j=之 间的距离 ；
J ( )为位 于城 市 i的蚂 蚁 壶下一 步 可行城 市 的 集
合．
行 为 3(action3) 蚂蚁按下式选 择下一座要 到
达 的城 市 ：
f rift∑ ris J E ( )；
户0一 ^“ (2) I
O rotherwise．
其 中 r。 为边 i与 之间信息的强度．
行为 4(action4) 蚂蚁 按下式选择下 一个要到
达 的状 态 ：
J— arg max(r“ 。 )，s E J^( )， (3)
其 中 r ，J ( )与式 (1)和式 (2)中的相 同．
当所有 蚂蚁完成解 的构造过程 后 ，计 算本 次 迭
代 的最 优解 (IBS)；然后将 IBS与 当前最 优解 (GBS)
进行 比较 ，如果 IBS的值 小于 GBS，则 用 IBS替 换
GBS；之后将所有边上 的信息素按下式进行 更新 ：
ri (f+ 1)一 (1一 [9)rij(f)+ Q／Lgb， (4)
其 中：L 为当前最 优解 ，p(o< P< 1)为信息 素蒸
发系数．
HBACA算法 可描述如下 ：
Step1：初 始 化 HBACA 算 法 的 参数 r ：r：：r。：
r4，P，Q ，ⅣCm丑 ，r (O)．
Step2：生成 只蚂蚁 ，其中： 干了
只蚂 蚁 按 action1行 动 ，另 外 _二F 只、
只和 _二F 只蚂 蚁 分
别 以 action2，action3，action4行 动 ．
Step3：将 4群蚂蚁 随机地 放到 座城 市 ，并将
该城市 的索 引添加 到该 蚂蚁的禁忌表 中．
Step4：for每 只蚂 蚁
repeat
维普资讯 http://www.cqvip.com
第 1期 胡小兵等 ：基于混合行为蚁群算 法的研 究 71
按 自己的行 为规则选 择下 一座城市 ；
移动 到下一座城 市 ；
将该城市 的索 引加入 自己的禁忌表 ．
until不能再 向前 移动
end for
Step5：计 算每 只蚂蚁 的路 径长度 并找 出 IBS，
如果 IBS比 GBS优 ，则 用 IBS替代 GBS．
Step6：由式 (4)更新边上 的信息素．
Step7：置 ⅣC：一 ⅣC + 1；
ifⅣC > Ⅳ C— then
输 出最优解 ；
退 出算法．
else
清空所有蚂蚁 的禁忌表 ；
转 Step 4．
end if
3 实验结果
实 验 数据 来 自 TSP库 (http：／／www．iwr．uni
-- heidelberg．de／iwr／comopt／soft／TSPLIB95／
TSPLIB．htm1)中的 benchmark实例 ，采用 编 程语
言 VC+ + 6．0在奔 腾 Ⅲ处 理器 (733 MHz)上进
行 ．
3．1 HBACA算 法的参数研究
由于参 数 Q对 大多数 蚁群算法的影响不大 ，在
实验 中Q取 100．实验分别针 对蒸发系数 』D和不同行
为群 体的 比例 r ：，． ： ；r4进行．首先在 固定蒸发
系数 』D的情况 下 ，采用 不同群体 比例 ，． ：，． ：，．。：r4
求 解 eil51问 题 ，实 验 结 果 如 表 1所 示．其 中 的
“Best”，“Avg”，“Worst”，“Std Dev”分别表示 15次
运 行的最好解 、平均值 、最差解和标准方差．
从 表 1可 以看 出 ，蚁群 中 ，． (随机搜索)所 占比
例不能太 大 ，否则对算 法 的搜索 不利 ；另外 ，启发式
因子在算法后期 所起 的作用减弱 ，，． 也不应该太大．
从 表 中 的 4 个 统 计 量 来 看 ，，． ：，． ：，．。：r4取
0．05：0．1；0．4：0．45时 ，算法 具有较好 的性能．
表 2是参 数 』D对 HBACA算法 的影 响．
对参 数 』D的实验结果显示 ，当 』D= 0．02和 0．05
表 1 参 数 ，l：，2 ：r．对 HBACA算 法 的影 响
表 2 参 数 P对 HBACA算 法 的影 响
时 ，算法 的性能较好．
3．2 对 比 实验 研 究
下 面利用 HBACA 的最 优参数 ，通过不 同规模
的 TSP问题 ，比较 HBACA算法 与 AS算 法的性能．
其 中：AS算 法 的参 数设 置 为 口一 1．5， 一 4，』D一
0．5，Q 一 100；HBACA 算 法 的 参 数 为 』D一 0．05，
，．1：，．2：，．3：r4— 0．05：0．1：0．4：0．45，Q = 1OO．
两种算法 的蚂蚁 数均为 35．表 3为运行结果 ，其 中对
每个 TSP实 例 ，两种 算法 都运 行 15次后 取其 平均
值 ，每次迭代次数 为 3 000．
从表 3中最优解和平均结果可 以看 出，HBACA
算法明显优于 AS算法 ，标 准方 差也显示 HBACA算
法 比 AS算法更加稳定．
表 3 HBACA算 法与 AS算法 的 比较 (*代 表 HBACA，# 代表 AS)
维普资讯 http://www.cqvip.com
72 控 制 与 决 策 第 2O卷
4 结 论
本 文提 出一种基 于混 合行 为 的蚁 群算法．该算
法通过 定义具 有 不 同行为 特征 的蚂蚁 ，并通 过调整
不 同行 为蚁 群 的 比例 ，保证 了蚁群 算法 在避免停滞
现 象 的 同 时 具 有 较 高 的 搜 索 较 好 解 的 能 力．仿
真 实验表 明 了该算 法 的有 效性 ，其性 能远优于蚂 蚁
系统．
参 考文献 (References)
Eli]Dorigo M ，Maniezzo V，Colorni A．The ant system：
Optimization by a colony of cooperating agents [J]．
1EEE Trans on Systems，M an。and Cybernetics—— Part
B ，1996，26(1)：29—41．
[2]Bullnheimer B，Hartl R F，Strauss C．A new rank—
based version of the ant system ：A computational study
[J]．Central European J for Operations Research and
Econom ics，1999，7(1)：25—38．
[3]Dorigo M ，Gambardella L M．Ant colony system：A
cooperative learning approach tO the traveling salesman
problem [J]． 1EEE Trans on Evolutionary
Computations，1997，1(1)：53—66．
[4]Stfitzle T，Hoos H H．Max—min ant system [J]．Fur“re
Generation Com puter Systems，2000，16(8)：889—914．
[5]覃刚 力 ，杨 家本． 自适 应调 整信 息 素 的蚁 群 算法 [J]．
怎 号 ，2002，31(3)：198—201．
(Qin G L，Yang J B．An improved ant colony algorithm
based on adaptively adjusting pheromone [J]．
Information and Control，2002，31(3)：198—201．)
[6]王颖 ，谢 剑英 ．一 种 自适应 蚁群 算 法 及 其 仿 真 研究 [J]．
莠纺 劳 真学援 ，2002，14(1)：32—33．
(W ang Y，Xie J Y．An adaptive ant colony optimization
algorithm and Simulation[J]．J of System Simulation，
2002，14(1)：32—33．)
[7]吴庆洪 ，张纪 会 ，徐心 和．具 有 变异 特征 的蚁 群 算法 [J]．
第 与发展 ，1999，36(1O)：1240—1245．
(W u Q H ， Zhang J H ， Xu X H． An ant colony
algorithm with mutation features[J]．J of Computer
Research and Development，1999，36(1O)：1240—1245．)
(上接第 64页)
参 考文献 (References)
[1]廖 成 林 ，靳 军．信 用 缺 失 现象 的博 弈 分 析 [J]． 苏通
经 ，2003，(1)：59—62．
(Liao C L，Jin J．A games analysis on discredit[J]．
China Currency Economic，2003，(1)：59-62) ．
[2]杨 万 铭 ．市场 秩 序 与信 用机 制 的构 建基 础 [J-I．经 劳
， 2002， (6)：151—153．
(Yang W M ． The base of establishing m arket system
and credit mechanism[J]]．Reform of Economic System，
2002，(6)：151—153)．
[3]李 必 强．市 场 经 济 中的信 用 、信 用 资 源 和信 用 机 制 [J]．
中 国地羲 大 学学 报 (社 会科 学皈 )，2002。2 t24—30．
(Li B Q．Credit，credit resources and credit mechanism
in market economy[J]． of China University of
Geosciences(Social Sciences Edition)， 2003，2(2)：24-
30)．
[4]范 晓屏 ，陆 韶 文．信 息 不 对 称 下 销 售 者 信 号 传 递 的 策 略
选择 [J]．企 经 劳 ．2002，(7)：83—85．
(Fan X P，Lu S W ． Seller strategic choice for signaling
in asymmetric information[J]．Firm Economic，2002，
(7)：83—85．)
[5]张 维迎 ． 硷 与 怎 经 劳 [M ]．上 海 ：上 海 人 民 出 版
社 ，1996：397—413，544—554．
[6]Yun Jungyol1． On the efficiency of the rank order
contract under moral hazard and adverse selection[J]]．J
of Labor Economics，1997，15(3)：466—494．
[7]Yun Jungyol1．Simple rank order contracts under moral
hazard and adverse selection[R]．Alifornia：Standford
University，1990：17-38．
下 期 要 目
粗集神经 网络及其在智 能信 息处理领 域的应用 ????????????? ??????? 张 东波 ，等
基 于混合微 粒群优化 的多 目标 柔性 Job—shop调度 ????? ???? ???????? 夏蔚 军 ，吴智铭
Web信 息查询优化 的遗传 算法 ??????????? ????? ????????? 王 自强 ，冯博 琴
基 于遗传 算法 的混合 H ／H 状态反馈控制器 ????????????????????? 潘 伟 ，等
基 于 Tent映射的混沌优化算法 ????????????????????????? ?? 单 梁 ，等
基 于欧 氏距离 和精 英交叉 的免疫算法研究 ?????????????????? ???? 郑 日荣 ，等
交 通信号 自适应 模糊控制器 的设计及稳定性分析 ???????????? ?? ??? 樊晓平 ，李 艳
切换系统 的不 变性原理与不变集 的状态反馈镇定 ???????????? ????? 林相 泽 ，田玉平
农 业剩余劳动 力转移 的适度规模及优化控制 ?????????????? ??? ?? 聂 荣 ，潘德 惠
不对称竞 争条件下 的集 团转移定价决 策 ??????????????????????? 慕银平 ，等
维普资讯 http://www.cqvip.com
基于混合行为蚁群算法的研究.pdf
