蚁群算法的原理及其应用

蚁群算法的原理及其应用

第 1 8卷

第 2期

潍坊教育学院学报J OURNAL OF W EI FANG EDUCATI NA L COLLE O GE

Vo . 8 No 2 11 .

20 0 5年第 2期

J .05 un 2 0

蚁群算法的原理及其应用王芳(北电力大学计算机科学与工程学院 .北保定 0 1 0 )华河 7 0 3

摘要：群算法是优化领域中新出现的一种仿生进化算法。该算法采用分布式并行计算机制，有较强蚁具的鲁棒性；有搜索时间较长，但易陷入局部最优解的缺点。文首先讲述蚁群算法的来源和基本原理，本然后讨论蚁群算法的几种改进策略，简单介绍近年来蚁群算法在许多新领域中的发展应用，并最后对今后进一步研究的方向作了展望。

关键词：群算法；蚁蚂蚁；息素；化信优中图分类号： P 3 T 381引言

文献标识码： A

文章编号：0 9 0 0 2 0 ) 2 O 7—O 1 0—2 8 (0 5 0 - O O 3这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行

后蚁群算法是群体智能的典型实现，一种基于种群寻优为，来数学及计算机方面的专家和工程师把这种超越生物是的启发式搜索算法。自从 M、 o io等意大利学者在 1 9年本身的模型转化成了一项有用的优化和控制算法——蚁群算 D r g 91首先提出蚁群算法 ( t o n y tm . C ) An l yS se A S以来， C o这种新型法，也称为蚁群系统。蚁群算法中对蚂蚁个体的描述大致为： 的分布式智能模拟算法已逐渐引起人们的注意并得到广泛的应用。

2 1个体 (个人工蚁 )行为极其简单 .通过个体问 .单的而

的相互协作，体行为相当复杂，完成复杂的任务；群能2 2个体不是全盲 .且有一定的记忆能力； .而 2 3个体能够适应环境的变化。 . 为了具体说明蚁群系统的原理，面举出人工蚁群路径下

蚁群算法不仅能够智能搜索、局优化，且具有鲁棒全而性、反馈、布式计算、与其它算法结合等特点。M、 o i正分易 D r— g o等人将蚁群算法先后应用于旅行商问题 ( S )资源二

次 T P .

分配问题 ( a rt sin e tPo l, Qu dai A s m n rbe QAP等经典优化搜索的例子 (图， ) c g m )如略。问题，到了较好的效果。在动态环境下，群算法也表现出得蚁

图( ) . A是蚁穴 .略中设 B是食物源， ah和 pt 2为从 pt1 ah

高度的灵活性和健壮性，在集成电路布线设计、信路由控蚁穴绕过障碍物到食物源的两条路径，如电且设 p t1的路径长度 ah制、交通建模及规划、电力系统优化及故障分析等方面都被认为 2单位 .pt 2的路径长度为 1个单位 .个 ah AC, DB的长度远

为是目前较好的算法之一。2蚊群算法的基本原理

小于一个单位，略不计 (图 1 a所示略 )假设每个时间单忽如 ()。位有3 O只蚂蚁分别从 A, B出发，蚁的行走速度都为 1每单蚂 (

M、 o io等人在观察蚂蚁的觅食习性时发现，盲的蚂位时间行走 1位长度 )且每只蚂蚁可在时刻 t下浓度为 1 D r g全单，留 蚁总能找到巢穴与食物源之间的最短路径。蚁群算法的提出的信息素。为了简单起见 .考虑在等间隔离散时间点 (一 0 只 t,

就是借鉴和吸收了现实世界中这种蚂蚁集体寻径的行为特 1 2… ) .,的蚁群系统情况；假设信息紊在时刻 (+ 0 5瞬时且 t .)征：研究发现，蚁在觅食过程中分泌一种称之为信息紊完全挥发；:0时刻无任何信息紊。经蚂 t( h r mo e的物质，种物质会随着时间而挥发蚂蚁能利 p eo n )这那么，一 0时刻从 A出发的 3 t O只蚂蚁第一次到达 C点，

用信息紊作为媒介与其它蚂蚁进行信息沟通。一条路径上留它们随机选择路径，认为沿两条路径行走的蚂蚁各为 1 可 5下的信息紊浓度的大小与这条路径上通过的蚂蚁数成正比，只。是经过 1时间单位后，ah上的信息紊浓度为 1; 但个 pt1 5而当通过的蚂蚁越多，留下的信息紊就越多，而导致后来蚂由于 p t 2短，一个时间单位里 . p t 2由 A到 B和由 B则从 ah较在沿 ah

蚁选择该条路径的概率提高。样，有视觉能力的蚂蚁在上到 A的蚂蚁分别为 1这没 5只，以 p t2上的信息紊浓度总数为所 ah述过程中展现出一种协作的自催化行为能力，蚁正是基于 3。么t 1时刻， A出发到达 C点的蚂蚁就会倾向于选择蚂 O那一从

这种原理建立最短的移动路径。得指出的是，种合作基本较短的路径 p t 2也就是说，有三分之二的蚂蚁选择值这 ah,将上是自组织的，且每个蚂蚁智能体很简单，蚁群体之所以 p t 2对于从 B点出发的蚂蚁也会有同样的情况而蚂 ah能够完成如此复杂的功能，是“就简单规则中的智能涌现”

随着时间的推移和上述过程的重复，径 pt 2上的信息路 ah

最初，究者从实际蚁群引申出“群系统”概念，立紊将以更快的速度增长，研蚁的建于是便会有越来越多的蚂蚁选择了

收稿日期： 0 S 6 1 2 0一0— S

作者简介：芳 (9 1 )女 (族 )山东青州人，北电力大学计算机科学与工程学院，士学位研究生王 18￣,汉，华硕7 0

蚁群算法的原理及其应用

20 0 5年第 2期

王

芳：群算法的原理及其应蚁

p t。致最终完全选择短路径 p t 2。 ah2以 ah

蚁群算法中设置动态变化的挥发因子。息索浓度越高。挥信则

浓挥通信通过上面的例子。以这样理解蚁群算法的基本思想：可当发因子越大；度越低。发因子越小。过限制 .息索的浓一

只蚂蚁在给定点进行路径选择。先行蚂蚁选择次数越多度不可能无限增大。不可能为零。被也 这样。于目标城市的动态选择和信息索挥发因子的动由

的路径 .选中的概率越大。该算法的主要特点可表述如下：被

动 ( )蚁群体行为表现出正反馈过程通过反馈机制的调态性，态蚁群算法有力地减少进化停滞现象。 1蚂整。对系统中的较优解起到一个自增强的作用 .而使问题 4蚁群算法的应用可从的解向着全局最优的方向演变，终能有效地获得全局相对最较优解。

蚁群算法能够将问题求解的快速性、局优化特性和有全

限

时间内答案的合理性结合起来 .此对于能够直接转化为因

( )群算法是一种本质并行的算法 .体之间不断进行路径优化问题的组合类寻优问题。取得比较理想的效果。 2蚁个能

信息交流和传递 .利于较好解的发现 .在很大程度上减有并少了陷于局部最优的可能。

4 1规模集成电路的线网布局 .大

在大规模集成电路的线网布局中，要根据电路和工艺需

然 ( )蚁之间没有直接联系。是通过路径上的信息索进的要求完成芯片上单元或功能模块的布局，后实现它们之 3蚂而行信息的传递。就是间接通讯。也 3对蚁群算法的改进间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个 Ag n根据启发策 et

虽然传统的蚁群算法具有很强的全局寻优解的能力。但略 .蚂蚁一样在开关盒网格上爬行，经之处便设置一条金像所历线也存在一些缺陷。如：算法的搜索时间过长，部分计算属线 .经一个线网的所有引脚之后 .网便布通了。应用蚁例该大

可最而时间被用于解的构造；执行过程中容易出现停滞现象，问群算法，以找到成本最低、合理的线网布局 .且由于其在当比 题规模较大时存在陷入局部最优的可能性等。此。究者对本身的并行性。较适合于解决此类问题。因研 4 2通信网络路由 . 近年来 .多学者将蚁群算法应用于通讯领域，别是通许特

传统的蚁群算法进行了很多改进研究。下面介绍两种有代表性的改进方法。 3 1最大最小蚁群系统 .

信网络中的路由问题。信网络的路由是通过路由表进行的 .通

最大 …… 此处隐藏：6832字，全部文档内容请下载后查看。喜欢就下载吧 ……