基本蚁群算法及其改进
第 5卷 第 6期
2004年 12月
北华 大学 学 报(自然科 学 版 )
JOURNAL OF BEIHUA UNIVERSITY(Natural Science)
VOI．5 NO．6
Dee．2004
文 章编 号 ：1009—4822(2004)06—0572—03
基本 蚁群算法及其 改进
孔令 军 ，张兴 华 ，陈建 国。
(1．北华大 学 教育技术 中心 ，吉林 吉林 132021；2．北华大学 电气信 息工程 学院，吉林 吉林 132021；
3．北华大学 后勤服 务总公司，吉林 吉林 132021)
摘要 ：给 出了群体智能的一个分支—— 蚁群算法的一个改进算法 ，充分利用 了算法的并行特点 ，提 高 了算法的效率
关键 词 ：蚁群 算 法 ；信 息矩 阵 ；组 合优 化
中 图分类 号 ：TP301．6 文献标 识码 ：A
近年来 ，计算 机 网络得到了飞速的发展 ，网络已成为社会 生活不可缺少 的部分 ．同时 ，人们对 网络信息
传输的质量 和效率 的要求也越来越高 ．为 了进一步提高 网络的效率 ，更多新算 法被 引入这个 领域 。蚁群算
法就是其 中之一 ．
1 初 期 的 蚁群 算 法
基本 的蚁 群算法 AS可 以简单 表述 如下 ：在 0时刻进行初始化过程 ，蚂蚁放置在不 同的城市 ，每一条边
都有一个初始外激素强度值 (0)．每一 只蚂蚁禁忌 表 的第一 个元 素置为它 的开始 城市 ．然后 ，每 一只蚂
蚁从城市 i移动到城 市 ，依据两个 变量的概率函数选择移动城市 (包括参数 a和p，见公式 (1．4))．在 次
循环后 ，所 有蚂蚁都 完成 了一 次周游 ，同时他们 的禁 忌表将满 ，这时 ，计算 每一 只蚂蚁 k的路径 长度 L ，
△ 依据公 式(1．3)更新 ．而且 ，保存 由蚂蚁找到 的最短路径 (即 minL ，k= 1，?，77'／)，置空所 有禁 忌表 ．
重复这一过程直 到周游计 数器达到最 大(用 户定 义)周游数 maxNc，或者所 有蚂蚁都走 同一路线 ．后一种
情况被称 为停滞状态 ．如果算法在 Nc次循 环后 结束 ，蚂蚁算法 的复杂度为 0(Nc· ·T?1)．
信息素更新公式 ：
(f+ )= ID· (f)+ Ar0， (1．1)
其 中，lD是一个参数 ，1一lD表示在 时刻 f和 f+ 之间外激素 的蒸发 ，
Ar = △r ， (1．2)
LXr,~是单位长度上在时刻f和f+ 之间第k只蚂蚁在边 (i， )留下的外激素的数量，其中
． 。 J 如果在时刻 f和f+ 之间第k只蚂蚁使用边 (i， )， ， 、 △r = L 。 (1．3)
【0， 其他 ．
Q 是一个常数 ，L 是第 k只蚂蚁 周游的路程长度 ．
第 k只蚂蚁从城市 i到城市 的跃迁概率为
聃 ：
一 3 聃 )： ’ (1．3)
【 0， ．
基 史 三 { 二堕 垒}，N 为一组城市，tabuk表示第k只蚂蚁的禁忌表，a和p都是控制外激素与可见度
维普资讯 http://www.cqvip.com
第 6期 孔 令军 ，等 ：基本 蚁群 算 法及其 改进
的相对重 要性的参数 ．跃迁 概率是可见度 和 t时刻外激素强度 的权衡 ．
综合 以上所述 ．图 1给出用基本蚁 群算法原理解决路 由选择优化 问题 的流程 图
573
图 1 基本 蚁群 算法解 决 问题流 程
Fig．1 Flow of basic ant colony
2 基本 蚁 群 算 法的 不足 之 处
从 上面针对路 由选择优化问题 的分析可 以看 出 ，虽然蚁群算 法 已经被 证 明是一种 有效的解决 组合优
化问题 的方法 ，但 是 由于 问世 的时间比较 短 ，还存在 如下不 足 ：
(1)限于局部最 优解 ．从算 法解的性质而言 ，蚁群算法也是在寻找一个 比较好 的局部最优解 ，而不 是强
求是全局最优解 ．
(2)工作 过程的 中间停滞 问题 ．和算法开始 时收敛速度快一样 ，在算法工作过程 当中 ，迭代 到一定 次数
后 ，蚂 蚁也 可能在某个或某 些局部最 优解 的邻域附近发生停滞 ．
(3)较 长的搜索时间 ．尽管和其他算 法相 比，蚁群算法在迭代次数 和解 的质量 上都有一定 的优势 ，但对
于 目前计算机 网络 的实 际情况 ，还是需 要较长 的搜索 时间．虽然计算机计 算速度的提高和蚁群算法的并行
性在一定程度 上可 以缓解这一 问题 ，但是对于 大规模复杂 的计算机 网络 ，这还是一个很大 的障碍 ．
3 加 强信 息 利用 率 的蚁 群算 法
下面从 实际应 用的角度提 出一个 改进的算法—— 加强信息 利用率 的蚁群 算法 ，其 主要 改进思 想是蚂
蚁 在网络图 中转移的同时在信息矩 阵 中转移 ，让寻找不同路径的蚂蚁 可 以协 同工作 ．根 据这个思想建立 了
新 的信 息矩阵(略 )，使蚂蚁遗 留下 的信息可 以对多次工作 产生影响 ．这 充分 利用 了算 法 的并 行特点 ，减少
了算法 的循环次数和计 算时间 ，提高 了算 法在解决这一问题时的效 率 ．下面通过仿真结 果进行分析 ．
节点工作：I观察连接情
I K 嘉嚣辜
否
是否有新 的、
新 信 息 矩 阵 ：j
新 的连 接 信息 ，
更 新已 有 的信 J
算 转 移 概 率
定 下 一 个 目
图 2 建立信 息矩 阵流 程
Fig．2 Flow of modeling of inform ation matrix
7．0 7～ ———————————————— ————————————— ————
6 5
60． l ， ? I 6 i I
．
I I f I jjj‘I 1
5．0 f l? f{ I l J
『 } l j l I 4．5}f l I ．
4．0lLL』—— ．— —— — — — — — — — — ． — — — — ． 一
0 5 10 I5 20 25 30 35 40
图 3 路 径优 化情 况
Fig．3 Chart of optimizing route
维普资讯 http://www.cqvip.com
574 北 华大学 学 报(自然科学版 ) 第 5卷
图 4 网络 模型拓 扑连接
Fig．4 Topological link of network mode
f ? ～
i I ．
i
{ I
一
L ? ．．．一
20 30 40 50 60 70
图 5 基本 蚁群算 法仿真结 果
Fig．5 Simulation result of basic ant colony
图 2是系统的仿真结果 即路径优化结果 ，横坐标代表循环次数 ，纵坐标代表蚂蚁 经过节点的数 目．仿
真过程 中，初始信息量定为0．75，衰减 系数定为0．95，循环次数为 40次．和 图 5基本 蚁群算法基于 图 4的
仿真结果相 比，可 以看出，引入 了改进思想后 ，算法 的性 能有 了比较 明显 的改善 ，一般 在 15～20次循环后
就可以稳定在最优路径上 ．在用基本算法进行仿 真时 ，干扰路径较多的路径很容易停滞在不是最优的结果
上 ，在改进算法 中，一样很快达到 了最优 ．
4 结 论
蚁群算法是近年新 出现的一种从群体智能思想演变而来的新算法 ，在解 决大规模组合优化 问题上显
示 了强大的实力 ．本文将蚁群算法引入路 由选择优化 问题 ，并做 了如下的研究探索 ：蚁群算法作为一种新
兴 的群体智能算法 ，在应用方面有 比较 突出的成绩 ，但研究者仅局 限于仿真试 验和思想 的引入 ；从理论 的
角度详细的论证 了蚁群算法解决此 问题的可行性 ，并结合算法工作的过程 ，分 析 了基本蚁群算法 的特点 ，
提 出了改进 的方 向；为 了改善基本 蚁群算法 的不足 ，提出了一种针对解决路由选择优化问题的改进蚁群算
法—— 加强 信息利用率的蚁群 算法 ．
参考 文 献 ：
[1]谭跃进 ，陈英 武 ，易进先 ．系统 工程原 理[M]．长沙 ：国防科 技大学 出版社 ，1999．
Tan Yuejin，Chen Yingwu，Yi Jinxian．The Theory of System Engineering[M]．Changsha：National Defence Technology
Publication，1999．
[2]Thomas A．Mauler．IP技术基 础—— 编址 和路由 [M]．北 京 ：机械 工业 出版社 ，2000．
Thomas A．Maufer．Basic Theory of IP Technology Address and Access[M]．Beijing：Mechanical Industry Pubhcation，
2000．
[3]胡适耕 ，施 保 昌．最优 化原理 [M]．武 汉 ：华 中理 工大学 出版社 ，2000．
Hu Shigeng，Shi Baochang．The Theory of Optimization[M ]．Wuhan：Publication of Middle China University of
Tec hnology，2000．
Basic Ant Group of Algorithm and Its Improvement
KONG Ling-j un ，ZHANG Xing．hua2，CHEN Jian．guo3
(1．Education Skill Center ofBeihua University，Jilin 132021，China；
2．Electric Information Engineering College of Beihua University，Jilin 132021，China；
3．Service Company ofBeihua University，Jilin 132021，China)
Abstract：A branch of colony intelligence improvem ent m ethod of ant group of algorithm ，basic ant group
of algorithm is introduced and algorithms effect is improved obviously．
Key words：Ant colony algorithm；Information matrix；Combinatorial optimization 【责任编辑 ：吕洪斌 】
．
．
n —__¨ ～∞
● ?㈨_- ● 三= ，赫
●
．
m
11／
～ ～ ～
维普资讯 http://www.cqvip.com
基本蚁群算法及其改进.pdf
