蚁群算法的理论及其应用

蚁群算法的理论及其应用

维普资讯

计算机时代 2 0 0 4年第 6期

蚁群算法的理论及其应用姜长元

(南京师范大学数学与计算机科学学院,江苏南京 200) 109摘要:本文介绍了一种崭新的求解复杂优化问题的启发式算法一蚁群算法.该方法通过模拟蚁群搜索食物的过程,达

到求解此类问题的目的,它具有智能搜索,全局优化,稳健性强,分布式计算,易与其它方法结合等优点.该算法用于解决组合优化问题, T P Q P JP效果较好如 S, A,S等

关键词:蚁群算法;模拟进化算法;组合优化;旅行商问题

1引言研究群居性昆虫行为的科学家发现,昆虫在群落一级上的合作基本上是自组织的,在许多场合中尽管这些合作可能很简

蚂蚁还能够适应环境的变化,例如在蚁群的运动路线上突然出现障碍物时,它们能够很快地重新找到最优路径 .人们通过大量的研究发现,蚂蚁个体之间是通过在其所经过的路上留下一

信息素"( e m n) p r o e的物质来进行信息传递的 . ho 单,但它们却可以解决许多复杂的问题蚁群算法就是利用群种可称之为"随后的蚂蚁遇到信息素时,不仅能检测出该物质的存在以及量集智能解决组合优化题的典型例子蚁群算法 ( n C ln At o y o的多少,而且可根据信息素的浓度来指导自己对前进方向的选同时,该物质随着时间的推移会逐渐挥发掉,于是路径的长 C l n等人在 2) o ri o【世纪 9年代初首先提出来的 ( )它是继模拟退择 .短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生火算法,遗传算法,禁忌搜索 ( au Sa h) T b er算法, c人工神经反过来信息素的强弱又指导着其它蚂蚁的行动方向.因络算法等元启发式搜索算法以后的又一种应用于组合优化问影响,Agrh A A )是由意大利学者 M.o g, . n zo A l i m, C ot D r o VMai z, . i e

题的启发式搜索算法.

此,某一路径上走过的蚂蚁越多,则后来者选择该路径的概率

这就构成了蚂蚁群体行为表现出的一种信息正反馈现蚁群算法不仅能够智能搜索,全局优化,而且具有稳健性就越大.蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食 (鲁棒性)正反馈,,分布式计算,易与其它算法结合等特点.利用象.能更具体地说明蚁群系统的原理. 正反馈原理,可以加快进化过程;分布式计算使该算法易于并物源的目的.图 1行实现,个体之间不断进行信息交流和传递,有利于找到较好H H H

的解,不容易陷入局部最优;该算法易与多种启发式算法结合,可改善算法的性能;由于鲁棒性强,故在基本蚁群算法模型的基础上进行修改,便

可用于其它问题因此,蚁群算法的问世为诸多领域解决复杂优化『题提供了有力的工具: u JC C c

M.o g D r o等人将蚁群算法先后应用于旅行商『题 i h J( S,源二次分配问题 ( udac A s n n Pol T P)资 Q ar i s gmet rbe t i m,

() a

() b

() c

图 1蚁群优化系统示意图

Q P) A等经典优化问题,得到了较好的效果.蚁群算法在动态环境下也表现出高度的灵活性和健壮性,如其在电信路由控制方面的应用被认为是目前较好的算法之一.此外,蚁群任务分工,

图中设 A是蚁巢, E是食物源, C为障碍物,距离为 d H, .由于障碍物的存在, A外出觅食或由 E返回巢穴的蚂蚁只能由经由 H或 C到达目的地.假设蚂蚁以"单位长度/ 1单位时间"的速度往返于 A和 E每经过一个单位时间各有 3, 0只蚂蚁离开 A和 E到达 B和 D图 l) ( a.初始时,各有 3 0只蚂蚁在 B

打扫蚁巢分类蚁卵等行为也启发了相应的协作和聚类算法.

2蚁群算法的基本原理蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自组织模式.尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为,蚂蚁也不可能从这些解释中获益,但是数学及汁算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法一蚁群算法,称蚁群系统 (n C l yS s m, C )也 A t o n yt A S o e

和 D点遇到障碍物,开始选择路径.由于此时路径上无信息素,蚂蚁便以相同的概率随机地走两条路中的任意一条,因而 l 5只选往 C 1只选往 H图 l),5 ( b.经过一个单位时间以后,路径 B D被 3 C 0只蚂蚁爬过,而路径 B D上则只被 l H 5只蚂蚁爬过

( B D距离为 1 B D距离为 2, C因 C而 H ) B D上的信息量是 B D上信息量的两倍 . H此时,又有 3只蚂蚁离开 B和 D, 0于是各 2只选择往 C方向,另外各 l只则选往 H图 l)这样, 0而 0 ( c. 更多的信息素量被留在更短的路径 B D上.随着时间的推移 C和上述过程的重复,短路径上的信息量便以更快的速度增长,

蚁群优化( n C ln pi zt n A O是该系统的核 A t ooy O t ao, C ) mi i心内容,其原理可大致描述如下:蚂蚁属于群居昆虫,个体行为

极其简单,而群体行为却相当复杂.相互协作的一群蚂蚁很容于是会有越来越多的蚂蚁选择这条短路径,以致最终完全选择易找到从蚁巢到食物源的最短路径,而单个蚂蚁则不能 .此外, 这条短路径 .

蚁群算法的理论及其应用

维普资讯

·

2 ·

Co u e a No 6 0 4 mp tr Er . 2 0

由上述可见,蚁群算法的核心有三条.第一,选择机制:信

息素越多的路径,被选中的概率

越大;第二,皂素更新机制:信,路径越短,迹增加越怏;第三,协作机制:个体之间通过信息素进行交流.

其中 -=/ C为经过路径(j q I, C i),所需的花费.【 p两 …… 此处隐藏：5131字，全部文档内容请下载后查看。喜欢就下载吧 ……