改进的增强型蚁群算法
第31卷
yo1．3l
第2期
№ 2
计 算 机 工 程
Com puter Engineering
2005年1月
lanuar3 2005
· 人工智 能及识 别技术 · ~ltm-g-：1000-_3428(2 0Il5)o2—1l76—13 文献标识码：A 中图分类号：TP37
改进 的增强型蚁群 算法
陈宏建‘，陈 峻 ，徐晓华I，屠 莉‘
(I扬 州 夫学信 息 l：程 学 院计算 机科 学 与工程 系 ，扬州 225009；2．南京大 学软 件新技 术 国家 重点 验室 ，南京 2 1 0093)
摘 要 ：针对传统增强型蚁群算法容易出现早熟和停滞现象的缺陷，提出 了一种改进的增强型蚁群算法。该方法将传统的增强型蚁群算法和
遗传锋法中交叉操作和变异操作相结合，实验结果表明，该方法比传统的增强型蚁群算法具有更好的搜索全局最优解的能力c一
关健词：蚁群算法 ；交叉；变异 ；优化
An Improved Augment Ant Colony Algorithm
CHEN Hongjian。，CHEN Ling。 ，XU Xiaohua ，TU Li。
(1 Dept．of Computer Sci．& Eng、College of‘Information Engineering Yangzhou Univ．Yangzhou 225009；
2．National Key Lab ofNovel Software Tcch．，Nanjing Univ．、Nanjing 2 l 0093)
l Abslracl l rO ov'crconlc the dclhult of prccocity and stagnation_l1 classical augment ant colony algorithm．an modilied atlglllCflt ant cokmy algol‘ithln
is presented Thc algol ithm LISt'S the operations ofcrossovcr and mutation ol、GA in augment ant colony optim ization Experimental rcsul~ h【1、V that the
algot ithm has much highcl。capacit3 ol、global optim ization than that classical augment ant colon),algorithm ．
1Kc)wordsl Ant colony algo~，ithm；Crossover；Mutation；Optitnization
蚁群算法还存在 许多缺陷，例如蚁群 巾多个蚂蚁的运动
是随机的，当群体规模较大时 ，很难在较短时间内从复杂无
章的路径中找出一条较好的路径。为II-~M．Dorigo等人在基本
蚁群算法的基础 提出了称之为Ant—Q System的蚁群算 ，
仅让每一次循环fIJ最短的路径 上的信息素作更新 。为 了克服
在Ant—Q中可能出现的停滞现象，T．Stu~le等人提出 rMAX—
M IN Ant System191
，允许各个路径上的信息素在一个限定的范
围内变化 。L_M．Gambardella等人提出 了一种混合型蚁群 算
法HAS161,在每次循环中蚂蚁建立各 自的解后，再以各 自的解
为起点用某种局部搜索算法求局部最优解，作为相应蚂蚁的
解，这样可以迅速提高解的质量 。我们也曾在文献[1 0，l】1中
提出了两种 克服蚁群算法早熟和停滞现象的蚁群 算法，另
外，G．BiIchev等人在使用遗传算法解决工程设计中连续空间
的优化问题时，使用 了蚁群算法对遗传算法所得到的初步结
果进行精确 化，取得 了较好的效 ，为 _『提高蚁群算法的
速度和精确度，吴斌、史忠植等提 出 了基于蚁群算法的分段
求解算 0，丁建立、陈增强等提 出了先利 用遗传算法再利
用蚁群算法 融合 的方 0，本文针对蚁群 算法容易出现停滞
现象这一缺陷，结合文献[1 5]提出的增强型蚁群算法(本文称
为传统增强型蚁群 算法)，提出 了一种改进的增强 蚁群 算
法，通过增强全局(或局部)最优解和全局(或局部)次优解的
路径上的信息素强度以及对它们进行交叉和变异操作的遗传
优化方法来改进增强型蚁群算法，从而有效地克服了传统增
强型蚁群算法中容易陷入局部最优解的问题 ，实验证明，改
进的蚁群算法比传统增强型蚁群算法具有更好的搜索全局最
优解的能力 ，并且其收敛性较传统增强型蚁群算法有了明显
的提高。
l基本蚊群算法
以 TSP问 题 为 例 说 明 基 本蚁 群 算 法 的 框 架 。 设 有
maxcities个城f ，maxallts只蚂蚁，采用 df，【i．J=1．2?．maxcitiesJ
表示城市i和城市i之川的距离，r J表示在时刻【城 市i和城市
j之间的路径上的残留信息素强度 ，我们 以此来模拟实际蚂
蚁的分泌物 。蚂蚁 在行进过程中，根据各条路径上的信 息
素强度来决定下一步所行进的路径 ，采用 ／ (，)表示在时刻
，蚂蚁 由城市 转移到城市，的概率，则有
．j ．]e alloweda ㈩ ‘( {∑ )，∥( (1)
{0、 otherwise
其中allowed 表示蚂蚁k下 一步允许行进的城市集合 ，它随蚂
蚁k的行进过程而动态改变。信息素强度 r I，J随时问的推移
会逐步消逝 ，用P表示它的消逝程度。蚂蚁选择转移到哪 个
城市采用伪随机概率选择规则 ，在这种规则下，每当蚂蚁要
选择转移 的城市时，就产生一一个在[O，l1~ t t-I ．I内的随机数 ，
根据该随机数按下列公式确定蚂蚁转移的斤向：
一
J arg max 【f( ，／)Jl，7(i， ／)J ： t’-‘ ． ，
一 I— l
； S lj
其中，q为一个在区问[O，1]内的随机数，q 为[0，l1内的 ·
个参数 ，s由式(1)确 定。这样 ，经 过，，7 (·ities时刻 ，蚂蚁走
完所有的城市，即完成了 一次循环。此时根据下式对各路 径
的信息素进行更新 ：
r
f， (r+I)=(I—p)一r (r)+△r，， l3)
其中 A r =∑ Ar ‘ (4)
= l
△r 表示蚂蚁七在本次循环中在城市 和城市，之间的路
基金：哽日：国家 自然科学基金资助项 目(600740】3)；国家高性能 计
算基金资助项 目(002】0)；江苏省教育厅 自然科学基金和南京 大学软
件新 技术 国家 重点 实验 室开 放基金 资助项 目
作者简介 ：’陈宏建(】968一)，男，iJ{：Oili，1-~／Jf斤向为并行算法和软
件 工程 ；陈 蛟 ，教授 ；徐 晓 华，肼 莉 ，硕 一L }
定稿 日期 ：2004．0】一O4 E—mail：yzchj@、ZCll net
维普资讯 http://www.cqvip.com
径 上留下的信息索，其计算方法可以根据计算模型而定，在
最常用的Ant Circle System模型中：
’
惭 m肝 “ ㈤
其中，Q为常数 ，Lk为蚂蚁k任本次循环中所行走路径的总长
度，在式(I)oO，a表示蚂蚁在行进过程 中所积累 的信息 素
对它选择路径所起的作用程度 ，r1“表示由城市i转移到城市
i的期 望程 度 ， 可根 据 某种 启 发算 法 而定 ，例如 可 以取
，7J，=1／d ，表示r1，肭作用。当Q=0时，算法就是传统的贪
心算法，而当p=0时，算法就成 了纯粹 的正反馈的启 发式算
法。可以用试验的方法确定参数CI，p的最优组合。在经过
若干次循环以后 ，呵以根据适当的停止条件来结束计算。
2改进的增强型蚁群算法
演化算法就是在 “探索”和 “利用”之间寻找一个平衡
点 ，也即要使得算法的搜索空问尽可能的大 ，以寻找那些可
能存在最优解的解空 间；同时又要充分利用群体内当前具有
的有效信息，使得算法的侧重点放在那些可能具有较高适应
值 的个体所在的空间内，从 而以较大概率收缩到全局最优
解。在蚁群算法【{1，信息素足蚁群之间进行信息交互和通信
的纽带和中介 ，足蚁群具有智能特点的关键 因素 ，而信息素
的强度随着路径距离的减少而增加，当系统搜索到较好的解
时 ，就更改相关路径 上的信息素强度，这有利于系统搜索 较
好的解 ，因而文献【1 5]提出了几种增强型蚁群算法 ，主要是
通过增强全局最优解或局部最优解的所有路径中信息素强度
来提高蚁群算法的搜索能力，但这种方法在实验过程中发现
很容易陷入局部最优。受遗传算法的启示，本文在增强全局
最优解或局部最优解的路径中的信息素强度的基础上，再对
全局(或局部)最优解和全局(或局部)次优解进行交叉和变异
操作 ，从而得到了一种改进 的蚁群算法。以求解TSP问题为
例，采用路径表示TSP问题的解 ，首先增强全局(或局部)最
优解和全局(或局部)次优解的所有路径中的信息，然后按下
列方法进行交叉和变异操作 ：首先在最优解和次优解的路径
中选取两个交叉点 ，然后交换两个解路径中交叉点之间的部
分路径 ，再在原来的各 自解路径中删去与现有解路径中交叉
部分相同的路径点 ，并按顺序将剩余路径点从左至右依次填
入新的解路径中。交叉完成后，再随机地在两个解路径中选
取 两个变异点 ，设为x1，x2，将该变异点x1：~llx2视为路径终
点，再随机地产生两个值yl和y2分别替换变异点x1，x2，同
时将解路径中的路径终点为Y1的值改为X1值 ，为y2的值改为
x2值。例如：设最优解的路径为 ：3—4—7一l6—5—2l一 1—
8，次优解 的路径为：6—4—8一I7—2— 1l一3—5，竖线之间
的部分为交叉段 ，则交叉后两个解路径变为3—4—6—
7—2—1—5—8和4—8—7—6—5—2— 1—3。交叉后 再
变异，首先产生一个随机数作为变异点 ，设该数为3，
再将两个解路径中 的第3个路径点xl=6~11x2=7视为变
异点，再随机地产生两个数 ，设为Y1=5，y2=1，则变异
后的两个解路径为3—4—5—7—2— 1—6—8和4—8一 I
一6—5—2—7—3。其算法框架描述如下 ：
step l 初始化E1、p、P等参数 ；
step 2 tbri=I to c“c·~lies do／／II1~1X6·~lies为城市的数量
rorj I Iomaxcities do T (iIi i) I)
step 3 ror k=1 to maxants do／／nl[ixallts为蚂蚁 的个 数
f设 为蚂 蚁k的 开始城 市 ；
AllowedL={1，2，·一．maxcitiesl—iLI；
i = I；}
step 4 lbr p=l tomaxcities do
(if p
fbr k=1 to maxants do
{按式(1)和式(2)选择 F一个城市i ；
Allowedk= AllowedL一 ；
Tou (p) (i iL)；；
else
fbr k= l to maxants do
{jk=ikI；
Tourdp)=(i k． k)；)
fbr k= 1 tom axants do
{t ( }k)=(J—p (II1_ )+△t ；
i =j ；}}
step fi for k=I to maxants do计算 Lengthk；
／／Length 为第k条 蚂蚁 所行 进的 长度
寻找最优解和次优解并巫新其路径中的信息素；
对 最优解 和 次优解 实施 交叉 和变 异操作 ；
评价 交 叉变 异后解 的优劣 求 出新 的最优 解 并更新 该最 优解
路径中信息 素；
ror每条边edge( ，)do更新每条边上的信息素；
step 6 if结 束条件 满 足 then输 出结 果 else转 lblstep 4
上述 算法 中首先增强最优解和 次优解路径中信息素 强
度，再使用交叉和变异操作，引进了遗传算法的优化方法 ，
增加了解空间的多样性 ，提高 了全局搜索能力，避免了局部
收敛和早熟现象 ，实验证明改进后的蚁群算法比单纯地改变
全局最优解或局部最优解路径中信息素强度具有更好的搜索
最优解 的能力。
3仿真实验
为了说明改进的增强型蚁群算法的搜索全局最优解的能
力 ，本 文 同 样 以TSPLIB和 文 献 【1 5]中 提 供 的TSP问 题
GR21、GR24、Swiss42、Hk48、Gr1 20及Ei176为例 。实验中
所采取的各项参数如下 ：初始化巾蚂蚁的数 I1等于TSP中城
市的个数 ，每个城 市分布 的蚂蚁个数为0～2个，CI 3，p 5，
p=0．2，系统信息素强度的初始值为1，常数为1，统计次数
为 1 5， 最 大 迭 代 次 数 Gr2l、 Gr24为 300次 ，Ei176、
Swiss42、Hk48为500次，GI．120为 l 500次 。实验中采 用的方
法有两种 ：方法 1是增强全局最优解和全局次优解路径中的
信息素强度，其实验结果如表 l所示(带 的数据参照文献
【1 5])；方法2是增强局部最优解和局部次优解路径中的信 息
素强度，其实验结果如表2所示 ；表中的最优解是统 汁中的
最小值 ，平均解表示每次最优解的平均值。
表l方法l中几种蚊群算法的最优解和平均解的进化情况
法及解 况 Gr2I Gr24 Ei】76 Swiss42 ltk48 G rI20
h 蚁 ffl' 址 优解 2 707 I 272 604 88 】28I ll 46I 7 482
钟}』二 甲均解 2 8" I 3 I 274 62I()7 I 286 3 l1 465 3 7 573 3
埔 蚁 优解 2 707 I 272 572 88 I 173 I1 46I 7 435()
l 』 均解 2 7I 3 45 I 272 575 50 I 279 lI 46l 7 546
．
7
』{=i仇解 2 407 40 I 244 55 563 88 75 7 35 9 838 28 7 423 82 小 史 避
蚁 艚弹 法 甲均娇 2 407
．
40 I 244 55 564 28 763 39 9 979 I6 7 461 04
维普资讯 http://www.cqvip.com
表2方法2中几种蚊群算法的最优解和平均解的进化情况
钾 及 的 况 Gr2l Gr24 Ei J76 Swiss42 Hk48 Gr J 20
}．J1玳蚁肼 f 2 707 J 172 604 88 l28 J l】46 J 7 482
法 F均 孵 1 8l 7 J 3 I 274 62l 07 l 286 3 l1 465 3 7 573 3
增 似 蚁 越 优解 2 707 l 272 572．88 J 300 ll 744* J4 303．0
』 钟 甲均 解 2 7l0 4 J 175 6 575．50 l308 6 lJ 897 6 I4 54 7
小 史 进 址优解 2 407 40 I 244 55 563港8 770 7l l0 283 50 7 457 lJ
蚁 肝 浊 l溉 2 407 40 l 25I 8 J 576 57 78I 63 l0 302 76 7 797 J2
改进的蚁群算法实验中上述诸问题所找到的最优解的路
径如图I至图6所示。
图i Gr21找封的
最傥路径
图4 Swiss42找强的
最傥路径
图2 Gr24找封的
最优路径
图5 Hk48所拽弼的
最优路径
图3 Ei176找封的
最优路径
图6 Grl20拽弼的
最傥路径
由上述实验可知，改进后的蚁群算法具有比传统增强型
蚁群算法更强的搜索全局最优解的能力。另外 ，笔者还采用
传统的蚁群 算法和改进 的蚁群算法对问题Hk48和G rl20的优
化过程进行了比较，其使用的参数 同上 ，其优化过程如图7
至图l0所示。由该实验结果不难发现改进后的蚁群算法较一
般的增强型蚁群算法具有更好的稳定性和收敛性。
l 1OI 201
图7传统蚊群算：法中
Hk48的最优解进化过程
“
图8改进蚊群算法中
Hk48的最优解进化过程
一 三 豆 磊 至要 享 三 一 三 三 至 要
图9传统蚊群算法中
Gri20的最优解进化过程
一 l78一
图1 O改进蚊群算：法中
Grl 20的最优解进化过程
4结 浯
本文结合文献[I 5]给出的增强型蚁群算法，提 出
了一种改进 的增强型蚁群 算法 ，通过增强全局(或局
部)最优解和全 局(或局部)次优解路径上的信息素强
度 以及使用遗传算法中的交叉和变异操作的优化手
段相结合的方法改进传统 的蚁群 算法 ，从而有效 地
克服 了传 统蚁群 算法 中容易 陷入局部最 优解 的 缺
陷 ，使得传统 的蚁群算法的性能有了显著的提高 。
这有利于蚁群算法的应 用与推广。相信随着蚁群算
法研究的不断深入，蚁群算法将会获得更广泛的应用。
参考文献
i Dorigo M ，M aniezzo V，Colorni A．Ant System ：Optimization by a
Colon}'of Coo rpe rating Agents IEEE Transactions on SMC
，
1 996，
26(1)：8-41
2 Dorigo M ，Gam bardella L M A nt Colony System ：a Cooperative
Learn ing Approach to the Traveling Salesman Problem
． 1EEE
Transactions on Evolutionary Computing 1 997， 1(1)：53．56
3 Colorni A，Dorigo M ，M aniezzo V
． Ant Colony System tbr Job．shop
Scheduling．Belgian Journal ol’O perations Research Statistics and
Computer Science，1 994，34(1)：39-53
4 M aniezzo V．Exact and Approximate Nonditerm inistic Trec Search
Procedures tbr the Quadratic Assignment Problem Informs Journa1 of
Computer，l 999，l 1(4)：358-369
5 Maniezzo V，Carbonaro A．An ANTS Heuristic for thc Fl，eauencY
Assignment Problem Future Generation Computer Systems
，
2000，1 6
(8)：927．935
6 Gambardella L M ，Dorigo M
．
HAS．SOP：A Hybrid Ant Systcm for
the Sequential Ordering Problem
． Technique Report，No IDSIA 97．
1 1，IDSIA，Lugano，Switzerland，
l 997
7 Gambardella L M ，Dorigo M
． Ant．Q：A Reinforcement Leamin
Approach to the Traveling Salesm an Problem
．
In：Pl·ieditis A．Russell
S(eds．)Proceedings of the 12th International Conference on Machine
Learning，Tahoe City
，
CA：M organ Kaufmann
，
1 995：252．260
8 Dorigo M，Luca M．A Study of Some Properties of Ant．O
．
Technica1
Report TR／IRIDIA／1996-4
， IR1DIA，University Librc de Bruxe}}es
．
1996
9 Stutzle T，Hoo s H H．Improvements on the Ant System：lntroducin￡
the M AX-M 1N Ant System
．
1n：Artilicial Neural Networks and Genet[c
Algorithms，New York：Springer．Verlag． 1 988：245．249
l0陈 蛟，沈 洁，秦 玲等．基于分布均匀度的自适应蚁群算法
．
软 件
学 报，2003，l4(8)：l 379．1 387
I】陈 蛟，秦 玲，陈宏建 具有感觉和知觉特征 的蚁群算法 系统仿
真学报，2003，l 5(1O) l4l 8．1425
12 Bilchev G，Parm ee I C
．
Adaptive Search Strategies lbr Heavil、．
Constrained Design Spaces
．
Procecdings of 22nd Internati0naI
Conference on Computer Aided Design 95 Yelta[C]Ukraine
，
l 995：
230．235
3吴 斌，史忠植．一种基于蚁群算法的TsP问题分段求解算法
． 计
算机学报，200l，24(12)：I328．1 333
4丁建立，陈增强 ，袁著祉．遗传算法与蚂蚁算法 的融合 计算机
研究与发展，2003，40(9)：l 35卜l 356
5燕 忠，袁春伟．增强型的蚁群优 化算法
． 计算机工程与应 用，
2003，39(23)：62．64
7 6 { 7
“ 州州州肼肌叭 ?川
维普资讯 http://www.cqvip.com
改进的增强型蚁群算法.pdf
