蚁群算法的研究与展望.pdf

2 0 0 9年第 6期 总 第 1 1 8 期 牡丹 江教 育学院学报 J OURNAL OF M UDANJ I ANG COLLE GE OF EDUCATI ON NO 6 2 0 09 Se r i a 1 NO 1 1 8 蚁群算 法 的研 究与展 望 惫 浩 扬州 职业 大学 江 苏 扬州 2 2 5 0 0 0 摘要 在介绍 了蚁群算 法的基本原理和特 点之后 指 出蚁群 算法并 不完善 重点分 析 了蚁群 算 法的改 进机制和应 用成 果 并指 出了改进算法的特点和优势 最后 总结 了蚁群算法的研 究方 向和发展趋势 关键词 蚁群 算法 组合优 化 中图分类号 TP 3 0 1 文献标识码 A 文章编号 1 0 0 9 2 3 2 3 2 0 0 9 0 6 0 1 1 4 0 2 蚂蚁是一种社会性 昆虫 蚂蚁 之间可 以相互协 作完成 复杂的任务 单个蚂蚁 的行为 较为简单 但 是 由简 单个体 所组 成的蚂蚁 群体却表 现出了极 为复杂的行 为 真实蚁群 在觅食 时能够 在蚁 穴和食物之 间找 到一条最 短路径 并且 在环境变化时 比如 出现新的障碍物时 蚁 群可以相互协作 找到一条新的最短路径 2 O世纪 9 O年 代初 意 大利 学者 M D o r i g o V Ma n i e z Z O A C o l o r n i 等通过模拟蚂 蚁搜索 路径 的行 为 提 出 了一 种新型的模拟进化算法 蚁 群算法 并将其 应用 于经 典 的旅行商问题 T s P 取得了较好的实验效果 接着又在 其 他典型问题中得到了成功应用 蚁群算法具有较好的鲁棒 性 并行分布式计算及易 于与其他启发式方法结合等优点 在短期内得到了很大发展 其应用领域也不 断得 到扩 展 显 示了其在求解复杂的组合优化问题方面的优势 同时 由于 蚁群算法收敛速度慢 容 易发生停滞 易陷入局部最优解等 不足 国内外专 家学者对 其进行 了不 断的改进 提高 了算法 的性能 一 蚁群算 法 1 蚁群算法 的原理 蚁群在觅食路径上 释放信 息素 单个 蚂蚁 通过感 知路 径上 的信息素强度按概 率选择 下一步 的行进方 向 而蚂蚁 之 间则通过感知 和释放信息素 完成 了间接 的信息传递 因 此 蚁群的集体行为便表现出一种信息正反馈现象 某一路 径 上走过 的蚂蚁越 多 则后来者选择该路径 的概率就越大 蚂蚁个体之 间就 是通 过这 种信 息的交流 达到搜 索食 物的 目 的 整个蚁群算法 的最优解 即最优路径将在 蚂蚁个体 的共 同协作 下求 出 2 蚁群算法存在的问题 蚁群算法的初始信息量 是相 同的 蚁 群创建第 一条 路 径依据的主要是城市问 的距 离信息 所 以信息 素对蚂蚁 搜 索方向的指导作用不强 因此蚂 蚁搜索 呈现 出较大 的盲 目 性 不仅如此 蚁群算 法 利用 随机 策略 使 得进 化 速度 较 慢 收敛速 度不 理想 容易 出现停滞现象 同时利用正反馈 可 以强化性能较好 的解 但导致 当前 不被选用 的路径 今后 被选用 的概率越来越小 在蚁群算 法进 行过程中 任何一次 路径选择和信息素更新 发生 的错 误都会误 导整个 算法 使 最 终 得 到 的最 优 解 是 错 误 的 二 蚁群算法的研究 1 9 9 6年 D o r i g o M 等提 出一种 修正 的蚁群 算法 论文 中对 蚁群 算法提出了一些讨 论 其 中包括 不 同的蚁群初 始 分布对求解的影响等 还提 出了所谓 的精英 策略 以强化精 英 蚂蚁 发现迄今最好路 径 的蚂 蚁 的影 响 并 在此基 础上 提出了一种称之为 An t Q S y s t e m 的更 一般 的蚁群算法 该算 法仅让每一次循环 中最短路径 上 的信息量作 更新 每 次让信息量最大的路径 以较大 的概率被 选 中 以充分 利用 学习机制 强化最优 信息 的反馈 为 了克服在 An t Q 中 可能出现的停滞现象 德 国学 者 S t u t z l e和 Ho o s 提 出另一 种改进 的蚁 群 算 法 最 大最小 蚁 群 系统 MMAS Ma x Mi n An t S y s t e m 该算 法允 许各个路径上的信息量在一个 限定的范围 内变化 MMAS是到 目前 为止 解决 T S P QAP 等问题最好 的 A C 0类 算法 它 限定 了痕迹 浓度 允许 值 的 上下限 并且采 用了平滑 机制 吴庆 洪等提 出 了具 有变异 特征的蚁群算法 该算 法为 了克服蚁 群算法 收敛较 慢的 问 题 采 用 逆 转 变 异 方 式 随 机 地 进 行 变 异 这 种 变 异 机 制 充 分利用 了 2 一o p t 方法简洁高效 的特点 因而具 有较快 的收 敛 速 度 这 是 国 内学 者 对 蚁 群 算 法 所 做 的最 早 改 进 三 蚁群算法的改进机制分析 1 基 于模 式学习的小窗 口蚁群算法 通过对蚁群算法 的研究发 现 蚁 群这 个 自适应 系统 与 其他许 多复杂 自适应 系统一样 存在 着模式 蚁 群就是通过 信息素来记 忆 更换 和组 合这 些模 式 以搜索 最优 路 径 的 在用蚁群算法求解 T S P时 可通过 限定蚂蚁 每步移动 的城 市 数 目来 降低解 空间的规模 以提 高解 空间的质 量 在此基 础 上提取模 式 模式 的获取可 以通过不 同次优 解之 间的交 集 实现 将 这些模式看 做一个个 整体 一个个 积木块 最 后 在这些模式中寻找最优解 这种基于模式学 习的小窗 口 蚁群算法在求解大规模组 合优化 问题 时 使蚁 群算法 的全 局收敛性能有 了很大 的提高 2 基 于混 合 行 为 的蚁 群 算 法 该算法采用具有不 同行为特征 的蚂蚁相互协作来 发现 所求问题 的全 局优 化解 它 的模 型 由 以下 四部 分组 成 蚂 蚁 规 则集 环境 以及状态空 间 其 中每 只蚂蚁拥有 自己的 行为特征 该行为由规则集 储存在环境 中的知识 以及状态 空 间一起决 定 状态 空 间与 待求 解 问题 具有 一一 映 射关 系 蚂蚁在状态 空 间中移 动 逐步 构造 出所求 问题 的可行 解 蚂蚁之 间不能直 接通信 而是 在移动 过程 中通 过环境 间接通信 蚂蚁利用通道读取写入信息到环境 环境储 存了 蚁群过 去行 动中所获取的历史知识 收稿 日期3 2 0 0 9 0 4 2 1 作者简介 唐浩 1 9 8 1 一 男 江苏兴化人 扬 州职业大 学信息工程 学院助教 扬州大学计算机应 用方 面在读硕士 3 带 聚 类 处理 的蚁 群 算 法 针对一类带聚类特征的 T S P 该算法首先对 T S t 中的 城市进行 聚类处理 将 F S P问题分解成许多小规模 的子问 题 子问题数 目与城市的聚类数相 等 然后 利用蚁 群算法 对每个子问题并行求解 并将 所有 子问题 的解按一 定规则 合并成待求解 问题 的解 由于该过程利用问题 本身的聚类 特征对所求问题进行分解 并行求解每一个子问题 从而极 大地加快了算 法的求解速度 4 基 于云模 型理 论 的蚁 群 算 法 云 模 型 是 一种 新 的实 现 定 性 概 念 和 定 量数 值 之 问转 换 的有 力工具 用来统一刻 画基 于语言值 的定性概念 和数值 表示之间的相互 映射关 系 该算法研究了一种利用 云模型 来有效限制蚁群算 法陷入局部最 优解的方法 它 主要是用 云模型理论来 调整信息素挥 发系数 p和信息素 强度 Q 从 而使随机过程和信 息素 强度 信息素挥 发系数 的优 化设置 有机地结合在一起 云模型多规则生成器的规则倾 向性保 证 了蚁群算法的快速搜索能力和全局收敛性能 同时 云模 型所蕴含 的随机过程保证了总体上 的最佳求解效果 5 基 于信 息 熵 的 改 进蚁 群 算 法 信息熵是 由美国学者 S h a n n o n C E于 1 9 4 8年将热力 学熵 引入信息论而提出 的 其为不确 定方法 的一个重要 概 念 常被用 于较粗略地 给出不确定 性的度量 因为基本蚁 群算法 中各路径的信息量具有不确定性 对于全局来讲 蚂 蚁选择哪条路径也表现 出一定 的不确定性 而信息熵本身 为不确定性的一种度量 故可尝试将信息熵引入蚁群算法 利用与蚁群算法运行过程相关的信息熵值表示选择过程中 的不确定性 采用控制信息熵 的值来控制路径选择和局 部 随机 变异扰动的概率 便可实现蚁群算法的 自适应调节 四 蚁群 算 法的 展 望 1 蚁 群 算 法 的 模 型 改进 蚁群算法发展至今 人们 已经针对 不同 的具体 问题提 出了许多不同类型的改进蚁群算 法模型 但这些 改进的蚁 群算法模型往往普适性 不强 同时基本 蚁群算法模 型也不 能直接应用于解决 所有 的优 化问题 基 于此 可从 以下几 个 方 面 对 模 型 进 行 改进 1 设计 一种通H j 的蚁群算 法普适性模型 现实中的问题 千差 万别 并不 是每一 个问题都能 够很 容易规划到这样一个拥 有高度社会 性的蚁群 智能模型 因 此存算法的普适性研究 方面 今后 应进 一步探索蚁群 算法 多种模型的高层次统一 机制 这方 面可结 合复杂性 系统展 开研究 提 更普适的蚁群算法模 型 2 进一步研究 自然蚁群行 为 提 出更加智能化 的蚁群 混 合 行 为模 型 从深度上 说 虽然 蚁群算法是 基于蚂蚁 觅食 行为 而发 展起 来的 但是 自然界中的真实蚂 蚁觅食机 理并不那 么简 单 至今仍有许多借豁之处 今后 应该继续挖掘蚂蚁觅食 中 一 些 未知 的行为 从而得到新的蚁群算法模型 3 摆脱传统模拟框架 开发新 的蚁群算法模型 由于蚁群算法足建 立在对 自然界 中真实蚂蚁觅食行为 进行模拟这一基础上的 模 拟把蚁群算 法 与自然 界 中可能 发 生 的过 程 紧 密 地 联 系在 一 起 模 拟 具 有 解 释 能 力 的 同 时 也有 不利 的方 面 沿 着 模 拟 的 道 路 走 下 去 会 阻 碍那 些 不 符合模拟所认 可模 式的发展 因此 在可供选择的框架下 有必要蘑新表示各种通 用方法 的原 理和过程 进 而开 发 出 更加优 良的蚁群算法模型 2 蚁群 算法的理论分析 蚁群算法是一种概率 搜索算法 从数学 上对其正 确性 与可靠性进 行证 明相对 于 确定性 算法 而言 比较 困难 自 G u t j a h r W J最先从有 向图论的角度 对一种改 进蚁群算 法 的收敛性进行理论证 明至今 人们在其 收敛性研 究方 面 已 经取得了相当丰富的理论 研究成果 但是 这些理论成 果基 本上都是针对一 些改 进蚁群算法 的理论分 析 并 没有把对 蚁群算法的理论 分析统 N一个共 同的框架之下 3 蚁 群 算 法 的 并行 实现 蚁群算 法本 身隐含着一定 的并行性 并 行机实现 中往 往需要在计 算与通信 之间寻求一 种平衡 蚁群算法 的并行 机实现主要集中在最优 的并行化 所谓最优的并 行化是指 使用适量的处理 机以最小 的代价使得并行化蚁群算 法性能 达到当前情况下的最 好 或 者说 当并行 化蚁群算法性 能不 变时 应竭力减少计算和通信的成本 4 蚁 群 算 法 的 应 用领 域 虽然蚁群算法的应用范围已经几乎涉及到各个优化领 域 但是还存在很 多不足 主要有 以下两点 第一 纵 向而言 蚁群算法 的应用深度还不够 从公开 发表 的研究成果来看 大部分应用还仅仅停留在仿 真阶段 而且所做的研究大都是在对实际问题 的实验条件或约束条 件简化的前提下进行的 第二 横 向而言 蚁群算法 的应用领域还需要进一步拓 宽 不 同 的 应 用 领 域 都 有 许 多 不 同 的 实 际 问 题 尝 试 蚁 群 算 法 在 不 同问 题 中 的 实 际 应 用 也 是 今后 的一 项 重 要 研 究 内 容 5 蚁 群 算 法 的 智 能 融 合 蚁群算法可以 与遗 传算法 人 工神 经 网络 微粒 群算 法 人 丁免疫算法等其他算法做进一步的融合 但从现有 的 成果来看 这些智能融合大部分是一螳初 步尝试 很多都是 针对具体问题来进行的 所解决 的问题不 同 其融合 策略 也就存在着很多差异 因此 应该在现有成果的基础上继续 进行深入研 究 努力探索蚁群 算法与一种 或几种仿生 优化 算法相融合的统一机制 参 考 文 献 1 C o l o r n i A Do r ig o M Ma n i e z z o V D i s t r i b u t e d o p t i mi z a t io n b y a n t c o l o n i e s e1 I n P r o c o f 1 a t Eu r o p e a n C o n f e r e n c e o n Ani fi c i a l I i e Pa n s F r a n c e El s e v i e r l 9 9 2 C o l o r n i A D o r i g o M Ma n i e z z o V An i n v e s t i g a t i o n o f s o me p r o p e r t i e s o f a n a n t a l g o r i t h m c I n P r o c Of p a r a l l e l P r o b l e m S ol v i n g r o m Na t u r e PPS N F r a n c e El s i v e r 1 9 9 2 3 吴庆红 张纪会 徐 心和 具有 变异特征 的蚁群 算法 J 计算 机研 究 与 发 展 1 9 9 9 3 6 1 0 1 2 4 0 1 2 4 5 4 萧蕴 诗 李炳宇 小窗 口蚁群算法 J 计算机工程 2 0 0 3 2 9 2 O 1 4 3 1 4 5 5 胡小 兵 黄席樾 基于混合行为蚁群算法的研究 J 控制与决 策 2 0 0 5 2 0 1 6 9 7 1 6 胡小兵 黄席樾 对一类带聚类特征 TS P问题的蚁群算法求解 J 系统仿真学报 2 0 0 t 6 2 2 6 8 3 2 6 8 6 7 段海滨 王道波 于秀芬等 基于 云模 型理论的蚁群算法 改进 研究E J 哈尔滨工业大学学报 2 0 0 5 3 7 1 1 1 5 1 1 9 8 李万庆 李彦苍 求解复杂优 化问题的基于信息熵 的 自适 应蚁 群算法 J 数学 的实践 与认识 2 0 0 5 3 5 2 1 3 4 1 3 9 An Ov e r v i e w o f Re s e a r c h a n d Pr o s p e c t o n An t Co l o ny Al g o r i t h m TANG Ha o Ya n g z ho u Po l y t e c hn i c Co l l e g e Ya n g z h o u