第 18卷 第 3期
Vo1.18 No.3
控 制 与 决 策
Control and Decision
2003年 5月
M ay 2003
文|I【一号 :1OO1一O92O(2OO3)O3一O317一O3
简单蚁群算法的仿真分析
周 伟 ,刘粉林 ,吴 灏 ,王 清 贤
(解放军信 息工程大学 信 息工程学 院 ,河南 郑州 45Q002)
摘 要 :蚁群算 法是 一类模 拟 生物群体突现聚 集行为 的非经典算 法。 首先描述 了一个 筒单蚂蚁 系统及
其筒单蚁群 算法 ,并对其进 行 了计 算机程序模 拟与动力 系统仿真 。结果表 明,筒单蚂 蚁系统 中存 在规模
聚集效 应 ,当蚁群 的规模超 过 某一临界值 时 ,蚂蚁 的行 为开始 向有 序 的方 向收敛 ,并最终稳定 在 一种 有
序状 态。
关t词 :蚂蚁系统 ;蚁群算 法 ;仿真 ;多主体系统
中圈分 类 号 :TP18 文献标识 码 :A
Dynam ical sim ulation of sim ple ant system s
. zHoU W 菇。LIU Fen-lin,W U H ao,W ANG Qing-xian
(Information Engineering Institute,The PLA,Information Engineering University,Zhengzhou 450002,China)
Abstract:Ant algorithm s analogize the social behaviour of ant colonies. A simple ant system wit}lⅣ
foraging ants and one shorter path and one longer path that lead to the same food source is described.A
simple ant algorithm is given.To analyze the emergent aggregation property of the simple ant system ,
a multi—agent system using the simple ant algorithm is programm ed to analogize the sim ple ant system ,
and a dynamical system is presented to simulate the com plex collective behavior of foraging ants.W hen
the number of ants exceeds a critical value,almost all of the ants are shown to select th e shorter path .
Key words:An t system s;Ant algorithm s;Sim ulation;M ulti—agent system
1 引 言
较 为简 单 的主 体 的聚 集相互 作用 ,必然 会 涌现
出复杂的大尺度行为 。遗 传算法之父 霍兰德 称这种
现象为突 现聚集特性[1]。生物群 体的复杂适 应性行
为就是从组成群体 的适应性 个体行 为 中涌现 出来 的
一
种全 局性质 。
蚂蚁 是 一 类 行 为 简 单 的 昆虫 ,只 有 十 分有 限 的
记忆能力 。在个体水平 上 ,蚂蚁 的行为带有随机性 。
但在群体水平上 ,蚁群 的集体行 为却高度 有序。蚂蚁
依靠 集体的智慧 ,可 完成相 当复杂 的任务 。蚂蚁 的觅
食行 为是动 物行为学家非 常感兴趣 的现 象 。蚂 蚁搬
运食物 回巢 的路上 ,分泌一种化学激素 ,以吸引其他
蚂蚁 到这条 路上来 。蚁群通 过这种 机制 ,可 以发 现 一
条从 蚁巢到 食物源 的最短路径 。假 设在蚁 巢和食 物
源之 间 ,存 在两 条 长度 不 同的路径 A 和 B,其 中路
径 A 和 B 的 长 度 不 同 ,且 B 的 长 度 明显 地 大 于 A
的长度 ,那么蚂蚁将会 选择较短的路径 A。一般认
为,沿 路径 A 找到食 物 ,然后 又从 路径 A 返 回的蚂
蚁 ,花 费时间较少 ,将 成为第一批 携带食 物 回到蚁巢
的蚂 蚁 。这样 ,路径 A首 先被 蚂蚁两次 分泌 的化学
激素 重复标记 。由于这 时路径 A 上化学激素 比路径
B上 的多 ,所 以随 后 出巢 和返巢 的蚂 蚁被 吸引到 A
上来 。随 着 越 来越 多 的蚂 蚁选 择 路 径 A,路 径 A 上
化学 激素的浓度 也越来 越大 。最 后,几乎 所有 蚂蚁选
收稿 日期 :2002—01—01;修 回 日期 :2002—04—22。
基金项 目 :河南 省高校杰 出科研人 才创新工程 资助项 目(2001KYCX008);中 国博士 后科学基金 资助项 目。
作者筒介 :周伟 (1966一 ),男 ,山东临沂人 ,博 士生 ,从 事 网络 安全 、人 工智 能等研究 ;王 清贤(196O一 ),男 ,河南卫 辉人 ,教
授 ,博士生 导师 ,从 事信 息安全 、算法分析 与设计等研 究 。
维普资讯 http://www.cqvip.com
评论0