第25卷第8期 计算机应用与软件
V o l .25N o .8
2008年8月 C o m p u t e r A p p l i c a t i o n s a n d S o f t w a r e A u g .2008
收稿日期:2006-12-19。国家自然科学基金(90412014)资助。倪庆剑,博士生,主研领域:群智能方法,机器学习。
蚁群算法及其应用研究进展
倪庆剑 邢汉承 张志政 王蓁蓁
(东南大学计算机科学与工程学院 江苏南京210096)
摘 要 蚁群算法作为一种仿生进化算法,是受到真实蚁群觅食机制的启发而提出的。首先介绍了蚁群算法的基本原理和工作
机制,然后分别就蚁群算法的理论和应用的研究现状进行了综述,主要包括蚁群算法的参数设置,蚁群算法的改进,蚁群算法的收敛性以及蚁群算法在组合优化问题和连续优化问题中的应用,并进一步给出了它们的研究重点和发展方向,最后是关于蚁群算法的研究展望和面临的挑战,提出了蚁群算法研究中值得探讨的一些课题。关键词 群智能方法 蚁群算法 优化问题
A N TC O L O N YA L G O R I T H M A N DI T SA P P L I C A T I O N S :R E V I E W A N DP R O G R E S S
N i Q i n g j i a n X i n g H a n c h e n g Z h a n g Z h i z h e n g W a n g Z h e n z h e n
(S c h o o l o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g ,S o u t h e a s t U n i v e r s i t y ,N a n j i n g 210096,J i a n g s u ,C h i n a )
A b s t r a c t T h e a n t c o l o n y a l g o r i t h mi s a m e t a h e u r i s t i c a l g o r i t h mf o r o p t i m i z a t i o n p r o b l e m s ,w h i c h i s i n s p i r e d b y f o r a g i n g m e c h a n i s m s o f r e -a l a n t c o l o n i e s .T h e b a s i c p r i n c i p l e a n dw o r k i n g m e c h a n i s mo f a n t c o l o n y a l g o r i t h m a r e f i r s t l y i n t r o d u c e d ,a n d c u r r e n t r e s e a r c h e s i n t h e o r i e s a n d a p p l i c a t i o n s o f a n t c o l o n y a l g o r i t h ma r e a l s o o v e r v i e w e dr e s p e c t i v e l y ,w h i c h a r e r e l a t e dt o t h e c o n f i g u r a t i o no f p a r a m e t e r s ,i m p r o v e m e n t s ,c o n v e r g e n c e a n a l y s i s a n da p p l i c a t i o n s i nd y n a m i cc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s a n dc o n t i n u o u so p t i m i z a t i o np r o b l e m s .A t t h es a m e t i m e ,f u r t h e r f o c u s i n g a r e a s a n d e x p l o i t a t i o n d i r e c t i o n s a r e p r e s e n t e d .F i n a l l y ,s o m e r e m a r k s o nt h e f u t u r e t r e n d s a n d c h a l l e n g e s f a c e d a s w e l l a s e x i s t i n g p r o b l e m s r e l a t e d t o a n t c o l o n y a l g o r i t h m a r e d i s c u s s e da n d c o n c l u d e d .K e y w o r d s S w a r mi n t e l l i g e n c e A n t c o l o n y a l g o r i t h m O p t i m i z a t i o n p r o b l e m
0 引 言
蚁群算法(A n t C o l o n yA l g o r i t h m )是由意大利学者D o r i g o
等
[1]
人在20世纪90年代受到真实蚁群的觅食机制的启发而提
出的一种新的进化计算方法。最早的蚁群算法是蚂蚁系统(A n t S y s t e m ),研究者们根据不同的改进策略对蚂蚁系统进行改进并开发了不同版本的蚁群算法,并成功地应用于优化领域。
蚁群算法具有分布式计算,无中心控制和分布式个体之间间接通信的特征,易于与其它优化算法相结合,蚁群算法通过简单个体之间的协作表现出了求解复杂问题的能力,已被广泛应用于求解优化问题。蚁群算法相对易于实现,且算法中并不涉及复杂的数学操作,其处理过程对计算机的软硬件要求也不高,因此对它的研究在理论和实践中都具有重要的意义。
目前国内外的许多研究者和研究机构都开展了对蚁群算法理论和应用的研究。比利时布鲁塞尔自由大学的I R I D I A 实验室,瑞士的I D S I A 等都是目前在蚁群算法研究领域较为活跃的机构。总的来说,蚁群算法已成为国际计算智能领域关注的热点课题。蚁群算法作为群智能方法中的一种,是每年一度的I E E ES w a r mI n t e l l i g e n c e S y m p o s i u m 中的重要内容。1998年在布鲁塞尔召开了第一届蚁群优化和群智能国际研讨会,此后该会每两年召开一次。虽然目前蚁群算法没有形成严格的理论基础,但其作为一种新兴的进化算法已在智能优化等领域表现出了强大的生命力。
本文就蚁群算法的理论和应用研究现状进行了综述,勾画
了当前蚁群算法研究领域的热点及发展趋势。
1 蚁群算法的基本原理
真实蚁群通过在觅食路径上释放信息素(P h e r o m o n e )最终可以在蚁穴和食物源之间找到一条最短路径,蚁群算法正是通过模拟真实蚁群的这一特征工作的。
1.1 真实蚁群的觅食机理
蚂蚁是一种社会性昆虫,蚂蚁之间可以相互协作完成复杂的任务。单个蚂蚁的行为较为简单,但是由简单个体所组成的蚂蚁群体却表现出了极为复杂的行为。真实蚁群在觅食时能够在蚁穴和食物之间找到一条最短路径[2],并且在环境变化时,比如出现新的障碍物时,蚁群可以相互协作找到一条新的最短路径。
蚁群在觅食路径上释放信息素,单个蚂蚁通过感知路径上的信息素强度按概率选择下一步的行进方向,而蚂蚁之间则通过感知和释放信息素完成了间接的信息传递。当觅食路径上有了新的障碍物时,信息素轨迹暂时被隔断,此时蚂蚁随机地选择下一步的行进方向,而恰好选择了障碍物附近新的最短路径的那些蚂蚁将最先重构起连续的信息素轨迹,久而久之,选择短路
第8期
倪庆剑等:蚁群算法及其应用研究进展13
径的蚂蚁越来越多,使得短路径上的信息素的强度越发大于较长路径上的信息素强度,从而使得后续的蚂蚁以较大的概率选
择短路径,这种自身催化过程形成的信息正反馈机制使得蚁群最终可以找到新的最短路径。
1.2 蚁群算法的基本原理
蚁群算法是通过模拟真实蚁群的觅食机理求解优化问题的,最早是D o r i g o [3]
等提出的蚂蚁系统,被用来解决旅行商问题,后来经过D o r i g o 和G a m b a r d e l l a 等[4-6]
人的改进后称为蚁群
算法(A n t C o l o n y A l g o r i t h m )或蚁群优化算法(A n t C o l o n y O p t i m i -z a t i o nA l g o r i t h m )。
蚁群算法模拟真实蚁群的觅食机制[5],引入了信息素概念及相关的信息素更新机制。但与真实蚁群中的蚂蚁不同,蚁群算法中的蚂蚁被赋予了部分记忆,并且可以感知某些启发信息,这种记忆并非存储于蚂蚁个体,而是分布在路径上。蚁群通过感知路径上的信息素进行通信。蚂蚁之间的这种间接通信方式称为S t i g m e r g y 机制,个体之间并不直接进行信息交互,而是通过改变它们共同存在的环境进行交互,个体又通过对环境的改变去影响其它个体的行为,从而形成了一种正反馈机制。蚁群算法最初被应用于对称旅行商问题(S y m m e t r i cT S P ),下面以文献[5]中提出的蚁群系统求解对称旅行商问题说明蚁群算法的基本原理。
经典的对称旅行商问题简单描述如下:任给n 个城市V={v 1,v 2,…,v n },n 个城市之间的边的集合A ={(r ,s )∶r ,s ∈V },城市r 和s 的E u c l i d e a n 距离为δ(r ,s ),δ(r ,s )为边(r ,s )的长度,这里δ(r ,s )=δ(s ,r )。旅行商问题就是在有向图G (V ,A )中寻找一条长度最短的H a m i l t o n 回路,也就是寻找一条遍历所有n 个城市有且仅有一次最后回到出发城市的最短路径。在应用蚁群算法解决对称旅行商问题时,每一条边(r ,s )都有一个信息素强度值τ(r ,s ),它由蚁群算法的信息素局部更新规则和全局更新规则进行更新。
蚁群算法的工作过程简单描述如下:将m 个蚂蚁按照某种初始化规则分布在n 个城市,然后每个蚂蚁根据状态转移规则选择遍历的城市,蚂蚁倾向于选择那些长度较短且信息素强度较高的路径。单个蚂蚁在遍历过程中根据信息素局部更新规则在路径上释放一定数量的信息素,同时蚂蚁经过路径上的信息素随着时间的推移而蒸发。当所有的蚂蚁都完成了它们的遍历过程之后,每个蚂蚁都建立了一条H a m i l t o n 回路,这条回路就是单个蚂蚁找得的旅行商问题的解,此时可以计算出此次迭代的最短路径,再应用信息素全局更新规则对获得最短路径的蚂蚁所经历的边上的信息素进行更新。此后算法反复迭代直至满足终止条件后结束。可见,蚁群算法的求解过程主要由三个规则控制,即状态转移规则,信息素全局更新规则,信息素局部更新规则。
(1)状态转移规则 位于城市r 的蚂蚁通过状态转移规则选择要访问的城市。
s =
a r g m a x u ∈J k (r ){[τ(r ,u )]·[η(r ,u )]β} i f q ≤q 0S o t h e r w i s e
(1)
式(1)中J k
(r )表示蚂蚁k 在当前位置r 能访问的城市的集合,蚂蚁被赋予了记忆能力,可以记录蚂蚁已经过的城市,这种记忆一般通过设置禁忌表来实现。η=
1
δ
,是城市间距离的倒数,表达了启发式信息。β(β>0)是描述状态转移时信息素和启发式信息(距离)相对重要性的参数。q 是服从均匀分布的[0,1]之间的随机数,q 0是一个参数(0≤q 0≤1)。S 是由式(2)给出的概率分布选出的一个随机变量。
p k
(r ,s )=[τ(r ,s )]·[η(r ,s )]β
∑μ∈J k
(r )[τ
(r ,u )]·[η(r ,u )]β
i f s ∈J k
(r )0 o t h e r w i s e
(2)
由式(1)和(2)决定的状态转移规则被称为伪随机比例规则(P s e u d o -R a n d o m -P r o p o r t i o n a l R u l e )。状态转移规则使得蚂蚁倾向于选择短的且信息素强度高的路径。参数q 0决定了“勘探”(探索问题未知解空间以寻找那些可能最优的区域)和“开采”(充分利用已有的有效信息寻找可能最优的区域)之间的相对重要性:当位于城市r 的蚂蚁选择下一个将要访问的城市时,它选择一个随机数0≤q ≤1,如果q ≤q 0,则根据启发信息和信息素强度取最好的边,否则按照式(2)的随机比例规则选一条边。
(2)信息素全局更新规则 蚁群算法中只有那些属于最短路径上的边的信息素才被得到增强。这种规则和伪随机比例规则的使用都是为了让算法的寻优过程更具有指导性:最短路径的寻找始终是在当前找到的最短路径的附近进行。在所有的蚂蚁遍历完n 个城市之后,按照式(3)进行全局更新。
τ(r ,s )→(1-α)·τ(r ,s )+α·Δτ(r ,s )
(3)Δτ(r ,s )=
(L g b )-1,i f (r ,s )∈g l o b a l -b e s t -t o u r 0,o t h e r w i s e
(4)
α是信息素的蒸发系数。L g b
是实验开始至今的全局最短路径长度,也有用此次迭代得到的最优路径的长度L i b 来代替L g b 的,实验表明这两种情况下算法的性能差别较小,取L g b 的性能略微占优[5]。
(3)信息素局部更新规则 单个蚂蚁在遍历的过程中应用信息素局部更新规则对它所经过的边按照式(5)进行信息素更新。
τ(r ,s )→(1-ρ)·τ(r ,s )+ρ·Δτ(r ,s )(5)式(5)中,ρ为参数,0<ρ<1。实验表明,取Δτ(r ,s )=γ·m a x z ∈J k (s )τ(s ,z )(0≤γ<1为参数)及Δτ(r ,s )=τ0(τ0为路径的初始信息素量)时算法效果较好[5]。局部更新规则使得被蚂蚁经过的路径减少了一部分信息素,使得这些边被后来的蚂蚁经过的可能性减少,增强了算法的“勘探”能力,从而有效避免算法进入停滞状态(所有的蚂蚁收敛到同一路径)。
总之,蚁群算法先通过状态转移规则选择蚂蚁下一步将访问的城市,在建立解的过程中应用信息素局部更新规则更新经过的路径上的信息素,在遍历所有城市之后,根据信息素全局更新规则对所有的路径上的信息素进行更新。
2 蚁群算法的改进及其理论研究
蚁群算法的理论研究主要集中在如下几个方面:蚁群算法的参数设置,蚁群算法的改进,蚁群算法收敛性及工作机制的研究,蚁群算法与其它算法的融合。
2.1 蚁群算法参数设置的研究
蚁群算法的参数设置对蚁群算法的性能有着重要的影响。总的来说,蚁群算法中的参数包括初始蚁群中蚂蚁的数目m ,式
(1)和(2)中的β和q 0,式(3)中的α,式(5)中的ρ和τ0等等。
14
计算机应用与软件2008年
其中β描述了状态转移时信息素和启发式信息之间的相对重要程度。q 0表达了算法在“勘探”和“开采”之间的折衷程度。ρ和α都刻画了信息素随时间的衰减程度。τ0则是初始信息素的强度。
S o l n o n [7]
分析了信息素相关参数对“勘探”和“开采”的影
响,提出了在蚁群算法运行之前加入一个预处理阶段,这个阶段
先不使用信息素找到一定数量的路径(即回路),再从中选择部分路径在算法开始前初始化信息素,获得了较好的效果。不同的参数组合影响着蚁群算法的性能,P i l a t 以及G a e r t n e r 等[8,9]人将遗传算法与蚁群算法相结合,应用遗传算法优化蚁群算法的
参数,获得了较好的效果。M e y e r [10]
研究了蚁群算法中参数对“勘探”行为,即保持解的多样性的影响,指出式(2)中的β不仅
对协调“勘探”和“开采”行为有决定作用,而且对系统的鲁棒性也有重要影响。
关于蚁群算法参数优化的研究相对较少,然而蚁群算法的参数设置关系到算法最终的性能,因此参数的设置原则值得更深入的研究。
2.2 蚁群算法的改进研究
为了提高蚁群算法的性能,获得更快的收敛速度和求解质量,很多研究工作围绕蚁群算法的改进展开。
G a m b a r d e l l a 等[11]将蚂蚁系统和增强学习中的Q 学习算法融合在一起提出了A n t -Q 算法。D o r i g o 等[3]采用“精英策略”(E l i t i s t S t r a t e g y )对蚂蚁系统信息素更新机制进行改进,即增强在每次迭代中找到最优路径的蚂蚁的重要性,对其找到的路径增加额外的信息素,这种策略改善了蚂蚁系统求解大规模问题的能力。
T a i l l a r d 等
[12]
提出了快速蚂蚁系统F A N T (F a s t A n t S y s t e m )
的概念,F A N T 为了避免算法收敛于局部最优而引入了信息素
重置机制。S t u t z l e [13]
提出了最大-最小蚂蚁系统(M A X -M I N A n t S y s t e m )的概念,它和第一节中介绍的蚁群系统[5]
类似,但最大—最小蚂蚁系统事先限定了路径上信息素的变化范围在τm i n 和τm a x 之间,τm i n 和τm a x
是预先设定的参数,这样有效避免了搜索陷入停滞。B l u m 和D o r i g o [14]提出了超立方框架下的蚁群
算法(H y p e r -C u b eF r a m e w o r kf o r A n t C o l o n yO p t i m i z a t i o n ),通过改进信息素更新规则并且限制信息素在[0,1]之间,使得在这种框架下对蚁群算法的理论分析更容易,而且增加了系统的鲁棒性。
最初的蚁群算法适用于解决组合优化问题,现在也有学者尝试改进蚁群算法求解连续优化问题。P o u r t a k d o u s t 等[15]提出了只在信息素指导下进行寻优的求解连续优化问题的蚁群算法。D r éo 等[16]提出了连续交互式蚁群算法(C o n t i n u o u s I n t e r a c -t i n gA n t C o l o n y )求解多目标连续函数优化问题。改进蚁群算法求解连续优化问题的研究相对较少,这是一个很有潜力的研究方向。
2.3 蚁群算法的收敛性及工作机制的研究
蚁群算法问世以来,对蚁群算法的实验研究较多,对算法本身收敛性的分析较少。蚁群算法的收敛性研究对深入理解蚁群
算法的工作机理具有重要的理论价值,同时在提高算法收敛速度改善算法性能方面也具有现实意义。因此蚁群算法的收敛性研究是近期蚁群算法理论研究中的一个重要内容。
G u t j a h r [17]
基于图建立了蚁群算法解决组合优化问题的一般框架,并且证明了在特定的条件下,基于图的蚁群算法
(G B A S )可以保证以任意接近于1的概率收敛于给定问题实例
的最优解;S t u t z l e 和D o r i g o [18]
证明了针对一类蚁群算法,当迭代次数趋向于无穷时,蚁群算法可以保证找到全局最优解;G u t -j a h r [19]后来针对上述两类算法的缺点,对基于图的蚁群算法进
行改进并提出了G B A S /t d e v 和G B A S /t d l b ,证明了可以选择合
适的参数组合使得蚁群算法的动态随机过程收敛到最优解。V e r b e e c k 等[20]基于互联的学习自动机(I n t e r c o n n e c t e dL e a r n i n g A u t o m a t a )对蚁群的行为建模,认为可以把互连的学习自动机作为理论工具来考察蚁群算法的工作机理。
蚁群算法的理论分析为蚁群算法的改进提供了新的思路和角度,对建立其理论基础有重要意义,目前这方面的研究相对较少,而且这些研究大都针对某一类蚁群算法,并没有在一个共同的理论框架下讨论。
2.4 蚁群算法与其它算法的融合
蚁群算法易于与其它算法融合从而互相取长补短,改善算法的性能。目前这个方面的研究成果,包括蚁群算法与遗传算法、神经网络、微粒群算法等等之间的融合研究。
蚁群算法与遗传算法的融合。丁建立等[21]利用遗传算法产生路径上的初始信息素分布,获得了较好的效果。对于蚁群算法与遗传算法的融合,研究主要是用遗传算法优化蚁群算法中的参数和信息素,以及将遗传算法中的选择、交叉变异等操作融入蚁群算法。
蚁群算法与神经网络的融合。B l u m 等[22]用蚁群算法训练前馈神经网络,并将其应用于模式分类。蚁群算法还可以与其它优化算法融合,如免疫算法、粒子群算法。H o l d e n 等[23]将蚁群算法和粒子群算法(P a r t i c l e S w a r m O p t i m i z a t i o n )集成在一起,用于处理生物数据集的层次分类(H i e r a r c h i c a l C l a s s i f i c a t i o n )。
B e l l o 等[24]
提出了一个基于蚁群算法和粗糙集方法的模型,并将其用于特征选择。
蚁群算法作为一种较新的仿生优化方法,与其它算法融合和比较的研究仍处于初级阶段,相关的研究文献和报告较少。因此,设计新的融合策略结合其它算法进一步改善蚁群算法的性能,以及探讨蚁群算法与其它算法之间的联系都是非常有意义的研究方向。
3 蚁群算法的应用研究
蚁群算法最初被应用到经典的组合优化问题,随着研究的深入,应用范围逐渐扩大到更多的组合优化问题,而且目前已有将蚁群算法应用到连续优化问题的研究。
3.1 静态组合优化问题中的应用
蚁群算法目前已经在诸多领域得到应用,如水资源规划、电力系统的优化、物流领域等等。
典型的组合优化问题。从最初用蚁群算法解决旅行商问题[1,3]开始,研究者们陆续将其应用到其它典型的组合优化问题:二次规划问题[12](Q u a d r a t i c A s s i g n m e n t P r o b l e m s )、图着色问题[25](G r a p h C o l o r i n gP r o b l e m s )。这些问题具有很强的工程代表性,蚁群算法在典型的组合优化问题上的出色表现加速了它在工程应用领域的发展。
·水利科学方面的应用 蚁群算法在水科学方面的应用集中在水资源规划设计方面。Z e c c h i n 等[26]用改进的蚁群算法对配水系统的设计进行优化。H i l t o n 等[27]人用蚁群算法对地下
第8期 倪庆剑等:蚁群算法及其应用研究进展15
水监测网络的设计进行优化。水利科学中的配水系统、灌溉系统、防洪系统的设计等工程应用问题都表现出组合优化问题的特征,因此蚁群算法在水利工程优化领域有广泛的应用前景。
·电力系统领域的应用 电力系统的许多优化问题本质上属于组合优化问题。G o m e z等[28]人将蚁群算法应用于配电网络的规划。V l a c h o g i a n n i s[29]提出了用蚁群算法解决约束潮流问题,实验结果表明蚁群算法具有较高的可靠性和优化能力。
F o o n g等[30]人将蚁群算法应用到发电厂检修计划的优化。电力系统的这些组合优化问题的有效解决将为电力企业节省大量的资金,因此在电力系统领域的应用具有很高的实际价值。
·物流领域的应用 物流领域中的一些问题也具有组合优化问题的性质。研究较多的是物流配送领域的车辆路径问题,G a m b a r d e l l a等[31]人最先将蚁群算法应用于车辆路径问题。M e r k l e等[32]人将蚁群算法应用于资源项目约束的排定问题(R e s o u r c e-C o n s t r a i n e d P r o j e c t S c h e d u l i n g P r o b l e m s),实验表明与其它启发式算法相比较优势明显。
3.2 动态组合优化问题中的应用
在动态组合优化问题中,问题的解随时间而变。蚁群算法在动态组合优化问题的中的应用研究集中在通信领域。S c h o o n d e r w o e r d等[33]人率先将蚁群算法用于通信网络的路由问题,提出了基于蚁群算法的路由算法。D i C a r o等[34]人基于蚁群算法设计了自适应路由算法A n t N e t,每个节点根据网络的状况动态更新路由表项。H u s s e i n等[35]提出了改进的蚁群算法应用于移动自组织网络的路由问题。
通信网络的一些特征,如分布式的信息存储结构、网络的动态特性等与蚁群算法的本质特性非常类似,因此蚁群算法在通信领域中有广泛的应用前景。
3.3 连续优化问题中的应用
目前蚁群算法在连续优化问题中的应用相对较少。B i l c h e v 等[36]最先尝试用蚁群算法解决连续优化问题。H o等[37]通过改进信息素更新策略提出了求解连续优化问题的蚁群算法,算法应用在电磁装置的优化设计上获得了良好的效果。
目前将蚁群算法应用于连续优化问题的研究才刚刚起步,连续优化问题与组合优化问题相比,它们的最终优化目标不同,因此需要在信息素更新策略、蚂蚁的状态转移策略上进行改进以适应连续的连续优化问题的求解。
4 总结与展望
蚁群算法问世至今已有十多年,其理论和应用都有了很大的进步,蚁群算法从最初求解旅行商问题开始,已经逐步发展为一个优化工具,并且较为成功地应用到科学和工程中的多个领域。蚁群算法具有分布式计算、无中心控制、个体之间异步间接通信的特点,而且易于与其它优化算法相结合。但是同时它也存在一些缺点:问题规模很大时,需要耗费很长时间才能找到可接受的解;算法容易出现停滞现象;蚁群算法作为一个仿生进化算法,它在数学上缺少严格的理论基础以及正确性和可靠性的证明。因此,蚁群算法在理论上还有很多问题尚待解决,它的应用领域也有待进一步的挖掘。
综合本文的分析,蚁群算法在如下几个方面可以作进一步的探讨:
(1)蚁群算法理论基础的挖掘。包括蚁群算法收敛性的分析与证明,蚁群算法适用于一般问题的普遍理论框架的建立,蚁群算法参数设置的原则的进一步研究。
(2)蚁群算法的改进。可以考虑从新的角度对蚁群算法进行改进,比如概率方法,多种群策略,蚁群之间信息共享机制的改进,以及引入其它优化算法中的思想,蚁群算法是一种基于种群的方法(P o p u l a t i o nB a s e dM e t h o d),具有并行性,可以进一步对算法的并行化进行研究。
(3)蚁群算法与其它优化算法比较和融合研究。蚁群算法与其它随机算法之间的比较研究尚处于起步阶段,研究者们已经尝试将蚁群算法与其它优化算法相融合以获得更强的优化能力,但是蚁群算法与其它算法之间融合机制和策略仍有待进一步的探讨。
(4)蚁群算法在实际的工程应用中的问题。当前的应用相当一部分仍是实验和仿真,作为概率算法,它在应用于实际问题时的稳定性也值得研究。
(5)蚁群算法应用领域的拓展。蚁群算法已经被引入很多领域发挥其优化能力。目前应用较多的是静态组合优化问题,如何改进将其应用于动态组合优化问题和连续优化问题是一个值得探索的方向。
参考文献
[1]C o l o r n i A,D o r i g o M,M a n i e z z o V.D i s t r i b u t e do p t i m i z a t i o nb y a n t c o l o-
n i e s.P r o c e e d i n g s o f t h eF i r s t E u r o p e a nC o n f e r e n c eo nA r t i f i c i a l L i f e,
P a r i s,F r a n c e,1991.
[2]G o s s S,A r o nS,D e n e u b o u r gJ L,e t a l.S e l f-o r g a n i z e ds h o r t c u t s i nt h e
A r g e n t i n e a n t.N a t u r w i s s e n s c h a f t e n,1989,76(12):579581.
[3]D o r i g o M,M a n i e z z o V,C o l o r n i A.A n t s y s t e m:o p t i m i z a t i o nb y ac o l o n y
o f c o o p e r a t i n g a g e n t s.I E E ET r a n s a c t i o n s o nS y s t e m s,M a na n dC y b e r-
n e t i c s,P a r t B,1996,26(1):2941.
[4]D o r i g oM,D i C a r oG.A n t c o l o n yo p t i m i z a t i o n:an e wm e t a-h e u r i s t i c.
T h eC o n g r e s s o nE v o l u t i o n a r y C o m p u t a t i o n,W a s h i n g t o n,D C,1999.
[5]D o r i g o M,G a m b a r d e l l a LM.A n t c o l o n y s y s t e m:a c o o p e r a t i v el e a r n i n g
a p p r o a c ht o t h e t r a v e l i n g s a l e s m a np r o
b l e m.I E E ET r a n s a
c t i o n s o n E v o-
l u t i o n a r y C o m p u t a t i o n,1997,1(1):5366.
[6]M D o r i g o,LM G a m b a r d e l l a.A n t c o l o n i e s f o r t h et r a v e l l i n gs a l e s m a n
p r o b l e m.B i o s y s t e m s,1997,43(2):7381.
[7]S o l n o nC.B o o s t i n g A C Ow i t h a P r e p r o c e s s i n g S t e p.T h e A p p l i c a t i o n s o f
E v o l u t i o n a r y C o m p u t i n g,E v o Wo r k s h o p s2002:E v o C O P,E v o I A S P,
E v o S T I M/E v o P L A N,K i n s a l e,I r e l a n d,2002.
[8]G a e r t n e r D,C l a r k K.O nO p t i m a l P a r a m e t e r s f o r A n t C o l o n y O p t i m i z a-
t i o n A l g o r i t h m s.T h e I n t e r n a t i o n a l C o n f e r e n c e o n A r t i f i c i a l I n t e l l i g e n c e,
L a s V e g a s,U S A,2005.
[9]P i l a t M L,W h i t e T.U s i n gG e n e t i cA l g o r i t h m s t oO p t i m i z e A C S-T S P.
T h eT h i r dI n t e r n a t i o n a lW o r k s h o po nA n t A l g o r i t h m s,B r u s s e l s,B e l-
g i u m,2002.
[10]M e y e r B.C o n v e r g e n c eC o n t r o l i nA C O.T h eG e n e t i ca n dE v o l u t i o n a r y
C o m p u t a t i o nC o n f e r e n c e,S e a t t l e,U S A,2004.
[11]G a m b a r d e l l a LM,D o r i g o M.A n t-Q:a r e i n f o r c e m e n t l e a r n i n ga p p r o a c h
t o t h e t r a v e l i n g s a l e s m a np r o b l e m.T h e12t hI n t e r n a t i o n a l C o n f e r e n c e o n M a c h i n e L e a r n i n g,T a h o e C i t y,C A,U S A,1995.
[12]T a i l l a r dED,G a m b a r d e l l aL.A d a p t i v e m e m o r i e s f o r t h e Q u a d r a t i cA s-
s i g n m e n t P r o b l e m s.I s t i t u t o D a l l e M o l l e D i S t u d i S u l l I n t e l l i g e n z a A r t i f i-
c i a l e,T e c h n i c a l R e p o r t:I D S I A-8797,1997.
[13]TS t u t z l e,H H o o s.I m p r o v e m e n t so nt h ea n t s y s t e m:i n t r o d u c i n gt h e
M A X-M I Na n t s y s t e m.T h eI n t e r n a t i o n a l C o n f e r e n c eo nA r t i f i c i a l N e u-
r a l N e t w o r k s a n dG e n e t i c A l g o r i t h m s,W i e n,G e r m a n y,1997.
16
计算机应用与软件2008年
[14]CB l u m,M D o r i g o.T h e h y p e r-c u b ef r a m e w o r kf o r a n t c o l o n y o p t i m i z a-
t i o n.I E E E T r a n s a c t i o n so nS y s t e m s,M a na n d C y b e r n e t i c s,P a r tB,
2004,34(2):11611172.
[15]S H P o u r t a k d o u s t,H N o b a h a r i.A nE x t e n s i o no f A n t C o l o n yS y s t e mt o
C o n t i n u o u s O p t i m i z a t i o nP r o b l e m s.T h e4t h I n t e r n a t i o n a l W o r k s h o pA n t
C o l o n y O p t i m i z a t i o na n dS w a r m I n t e l l i g e n c e,B r u s s e l s,B e l g i u m,2004.
[16]J D réo,PS i a r r y.AN e wA n t C o l o n y A l g o r i t h mU s i n g t h eH e t e r a r c h i c a l
C o n c e p t A i m e d a t O p t i m i z a t i o n o f M u l t i m i n i m aC o n t i n u o u s F u n c t i o n s.
T h e T h i r dI n t e r n a t i o n a l Wo r k s h o po nA n t A l g o r i t h m s,B r u s s e l s,B e l-
g i u m,2002.
[17]G u t j a h r W J.A G r a p h-b a s e dA n t S y s t e m a n di t s c o n v e r g e n c e.F u t u r e
G e n e r a t i o nC o m p u t e r S y s t e m s,2000,16(8):873888.
[18]S t u t z l e T,D o r i g o M.As h o r t c o n v e r g e n c e p r o o f f o r a c l a s s o f a n t c o l o n y
o p t i m i z a t i o na l g o r i t h m s.I E E E T r a n s a c t i o n so nE v o l u t i o n a r yC o m p u t a-
t i o n,2002,6(4):358365.
[19]G u t j a h r W J.A C Oa l g o r i t h m s w i t hg u a r a n t e e dc o n v e r g e n c e t o t h e o p t i-
m a l s o l u t i o n.I n f o r m a t i o nP r o c e s s i n g L e t t e r s,2002,82(3):145153.
[20]V e r b e e c k K,AN o wé.C o l o n i e s o f l e a r n i n g a u t o m a t a.I E E ET r a n s a c t i o n s
o nS y s t e m s,M a na n dC y b e r n e t i c s,P a r t B,2002,32(6):772780. [21]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合.计算机研究
与发展,2003,40(9):13511356.
[22]B l u m C,S o c h a K.T r a i n i n g f e e d-f o r w a r d n e u r a l n e t w o r k s w i t h a n t c o l o-
n y o p t i m i z a t i o n:A n a p p l i c a t i o n t o p a t t e r n c l a s s i f i c a t i o n.T h e F i f t h I n t e r-
n a t i o n a l C o n f e r e n c e o n H y b r i d I n t e l l i g e n t S y s t e m s,R i o d e J a n e i r o,B r a-
z i l,2005.
[23]H o l d e nN,F r e i t a s AA.Ah y b r i dp a r t i c l e s w a r m/a n t c o l o n y a l g o r i t h m
f o r t h ec l a s s i f i c a t i o no f h i e r a r c h i c a l b i o l o
g i c a l d a t a.T
h e2005I E E E
S w a r mI n t e l l i g e n c e S y m p o s i u m,C a l i f o r n i a,U S A,2005.
[24]B e l l o R,N o w e A,YC a b a l l e r o,e t a l.Am o d e l b a s e do na n t c o l o n y s y s-
t e ma n d r o u g h s e t t h e o r yt of e a t u r es e l e c t i o n.T h eG e n e t i ca n dE v o l u-
t i o n a r y C o m p u t a t i o n C o n f e r e n c e,Wa s h i n g t o n D C,U S A,2005.
[25]C o s t a D,H e r t z A.A n t sc a nc o l o u rg r a p h s.J o u r n a l o f t h eO p e r a t i o n a l
R e s e a r c h S o c i e t y,1997,48(3):295305.
[26]Z e c c h i nAC,S i m p s o nAR,H RM a i e r,e t a l.P a r a m e t r i cs t u d y f o r a n
a n t a l g o r i t h m a p p l i e dt ow a t e r d i s t r i
b u t i o ns y s t e m o p t i m i z a t i o n.I E E E
T r a n s a c t i o n s o nE v o l u t i o n a r y C o m p u t a t i o n,2005,9(2):175191. [27]H i l t o nA C,Y L i.O p t i m a l G r o u n d w a t e rS a m p l i n gN e t w o r kD e s i g n
t h r o u g h A n t C o l o n yO p t i m i z a t i o n.T h e G e n e t i ca n dE v o l u t i o n a r yC o m-
p u t a t i o nC o n f e r e n c e,Wa s h i n g t o n,D C,U S A,2005.
[28]G o m e z J F,K h o d r HM,PMD e O l i v e i r a,e t a l.A n t c o l o n y s y s t e ma l g o-
r i t h mf o r t h ep l a n n i n go f p r i m a r yd i s t r i b u t i o nc i r c u i t s.I E E ET r a n s a c-
t i o n s o nP o w e r S y s t e m s,2004,19(2):9961004.
[29]V l a c h o g i a n n i s JG,H a t z i a r g y r i o uM D,KY L e e.A n t C o l o n yS y s t e m-
B a s e dA l g o r i t h m f o r
C o n s t r a i n e dL o a dF l o w P r o b l e m.I E E ET r a n s a c-
t i o n s o nP o w e r S y s t e m s,2005,20(3):12411249.
[30]Wa i K u a n F,H o l g e r RM,A n g u s RS.A n t c o l o n y o p t i m i z a t i o n f o r p o w e r
p l a n t m a i n t e n a n c e s c h e d u l i n g o p t i m i z a t i o n.T h e G e n e t i c a n dE v o l u t i o n-
a r yC o m p u t a t i o nC o n f e r e n c e,Wa s h i n g t o nD C,U S A,2005.
[31]LM G a m b a r d e l l a,éT a i l l a r d,GA g a z z i.M A C S-V R P T W:am u l t i p l e a n t
c o l o n y s y s t e mf o r v e h i c l er o u t i n g p r o b l e m s w i t ht i m ew i n
d o w s.I nN
e w
i d e a s i no p t i m i z a t i o n:M c G r a w-H i l l L t d.,U K,1999:6376.
[32]M e r k l e D,M i d d e n d o r f M,S c h m e c kH.A n t c o l o n yo p t i m i z a t i o nf o r r e-
s o u r c e-c o n s t r a i n e dp r o j e c t s c h e d u l i n g.I E E ET r a n s a c t i o n s o nE v o l u t i o n-
a r yC o m p u t a t i o n,2002,6(4):333346.
[33]R u u d S,O w e nH,J a n e t B.A n t-l i k e a g e n t s f o r l o a db a l a n c i n g i nt e l e-
c o m m u n i c a t i o n s n e t w o r k s.P r o c e e
d i n g s o f t h ef i r s t i n t
e r n a t i o n a l c o n
f e r-
e n c e o nA u t o n o m o u s a g e n t s,M a r i n a d e l R e y,C a l i
f o r n i a,U n i t e dS t a t e s,
1997.
[34]C a r oGD,D o r i g o M.A n t N e t:AM o b i l e A g e n t s A p p r o a c ht oA d a p t i v e
R o u t i n g.U n i v e r s i t e L i b r e d eB r u x e l l e s,I R I D I A,T e c h n i c a lR e p o r t:
I R I D I A1997:9712.
[35]H u s s e i nOH,S a a d a w i TM,L.M y u n gJ o n g.P r o b a b i l i t y r o u t i n ga l g o-
r i t h mf o r m o b i l e a dh o c n e t w o r k s r e s o u r c e s m a n a g e m e n t.I E E EJ o u r n a l o n S e l e c t e dA r e a s i nC o m m u n i c a t i o n s,2005,23(12):22482259.
[36]BG e o r g e,CPI a n.T h e A n t C o l o n y Me t a p h o r f o r S e a r c h i n g C o n t i n u o u s
D e s i g nS p a c e s.T h e A I S BWo r k s h o po n
E v o l u t i o n a r yC o m p u t i n g,S h e f-
f i e l d,U K,1995.
[37]SLH o,YS h i y o u,HCWo n g,e t a l.A ni m p r o v e da n t c o l o n y o p t i m i z a-
t i o na l g o r i t h m a n di t sa p p l i c a t i o nt oe l e c t r o m a g n e t i cd e v i c e s d e s i g n s.
I E E ET r a n s a c t i o n s o nM a g n e t i c s,2005,41(5):17641767.
(上接第11页)
8.决策机选择出最大值的Q o S,即S e r v i c e N的值;
E n d
F o r;
9.S'=S'∪{S e r v i c e N};
R e t u r nS e r v i c e N;
在整个过程中,计算Q o S值的步骤7是最关键的。我们定义一个函数来专门处理这个问题,并希望从数学方法论的观点出发选择出最好的服务。
3 结 论
本文主要针对目前服务发现中过分依赖W e b服务的功能性属性这一方法的不足,提出了一种基于非功能性W e b服务质量Q o S本体的We b服务选择B r o k e r模型。之后,介绍了Q o S P P R来描述用户的个人偏好,量化用户模糊需求;提出了服务选择匹配算法和Q o S值计算公式。目的是想通过这样的方法,得到和用户模糊需求匹配度最好的W e b服务。
参考文献
[1]夏虹,李增智,陈彦萍.基于概念格的语义We b服务匹配研究.北
京邮电大学学报,2006,29.
[2]安杨,关佶红,赵波.基于D A M L2S的We b服务匹配方法.复旦学
报:自然科学版,2004,43(5).
[3]S o y d a nB i l g i nA,M u n i n d a r PS i n g h.A D A M L-B a s e dR e p o s i t o r yf o r
Q o S-A w a r eS e m a n t i c We bS e r v i c e S e l e c t i o n.P r o c e e d i n g s o f t h eI E E E
I n t e r n a t i o n a l C o n f e r e n c e o nWe bS e r v i c e s,2004.
[4]Z h u C h e n g,L i uZ h o n g,Z h a n gW e i m i n g,e t a l.A nE f f i c i e n t D e c e n t r a l-
i z e d G r i dS e r v i c e D i s c o v e r y A p p r o a c h b a s e d o n S e r v i c e O n t o l o g y.P r o-
c e e
d i n g s o f t h
e I E E E/WI C/A C M I n t e r n a t i o n a l C o n
f e r e n c e o n We b I n-
t e l l i g e n c e,2004.
[5]Z h o uC,C h i aL,L e eB.D A M L-Q o SO n t o l o g yf o r We bS e r v i c e s.I n t.
C o n f e r e n c eo nWe bS e r v i c e s2004,S a n
D i e g o,C a l i f o r n i a,U S A,J u l y
2004.
[6]T i a nM,G r a m mA,N a u m o w i c z T,e t a l.A C o n c e p t f o r Q o SI n t e g r a t i o n
i nWe bS e r v i c e s.1s t We bS e r v i c e s Q u a l i t y Wo r k s h o p,R o m e I t a l y,D e-
c e m b e r2003.
[7]B i a n c h i n i D,D e A n t o n e l l i s V,M e l c h i o r i M.Q o S i no n t o l o g y-b a s e d s e r v-
i c e c l a s s i f i c a t i o na n d d i s c o v e r y.3r d I n t e r n a t i o n a l Wo r k s h o p o n We b S e-
m a n t i c s,S a r a g o s s a,S p a i n,A u g u s t2004.
大连理工大学 研究生必修课 作业 课程名称：现代物流管理 研究生姓名：徐静学号：21511149 作业成绩： 任课教师(签名) 交作业日时间：2016 年6 月1日
蚁群算法在TSP问题上的应用 摘要蚁群算法是受现实蚂蚁群体行为启发而得出的一类仿生算法。本文以解决TSP问题为基础,系统地介绍了蚁群算法从诞生到成熟过程中几个代表性的算法。在阐述算法基本思想的前提下，着重论述算法的创新之处。 关键词蚁群算法，TSP问题，蚁群优化 1引言 蚁群算法也称作蚁群优化(Ant Colony Optimization，ACO)，最早是由Dorigo及其研究同伴所提出，用于求解诸如旅行商问题之类的组合优化问题。自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素)，该物质会吸引蚁群中的其它成员再次选择该段路径；食物与巢穴之前较短的路径容易积累较多的信息素，因而使得更多的蚂蚁选择走该段路径，最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。Dorigo等从此现象中抽象出路径选择和信息素积累的数学模型，作为蚁群算法的核心，并通过对蚂蚁寻找最短路径的计算机模拟，实现了对TSP问题的求解。自此，蚁群算法越来越多地被用于求解其它的组合优化问题，也被推广到工业工程上应用。 蚁群算法特点是并发性、鲁棒性、正反馈性等。在蚁群算法求解问题的过程中，利用蚁群在问题空间中同时构造问题的多个解体现了算法的并发性。蚁群不会因为单个蚂蚁寻找到较差的解或者因为问题空间发生改变而使得算法丧失作用，这体现了算法的鲁棒性。在蚂蚁构造问题解的过程中，以蚁群觅食行为为例，会在经过的解路径上释放信息素，而解空间中获得信息素越多的路径，对蚂蚁的吸引力就越大，使更多的蚂蚁经过该路径并进一步在上面释放信息素，这体现了算法的正反馈性。 TSP问题代表一类组合优化问题，在实际工程中有许多应用，如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例。求其最优解的代价是指数级的，因此对其近似解的研究一直是算法设计的一个重要课题。 TSP问题是典型的NP完全问题，许多算验证法及算法效率测试都以TSP问题为基础。在蚁群算法研究中，第一个蚁群算法，蚂蚁系统,就是在TSP问题的基础上提出来的。而后，依据TSP问题，又提出了蚁群算法系列中具有代表性的蚁群系统、最大——最小蚂蚁系统。 本文以TSP问题为基础,对蚁群算法的基本问题及典型的蚁群算法进行了综述。涉及到算法的基本问题、算法描述、算法改进及意义。通过研究总结了蚁群算法的发展历程和实现思想。
２００７年第２期空间电子技术收稿日期：２００６－０４－０３；收修改稿日期：２００６－０４－３０ 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安７１００７１） 摘要文章首次提出了一种用于求解组合优化问题的ＰＡＡＡ算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求精确解（即细搜索）。将文中提出的算法用于经典ＴＳＰ问题的求解，仿真结果表明ＰＡＡＡ算法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题ＰＡＡＡ ０引言 近年来对生物启发式计算（Ｂｉｏ－ｉｎｓｐｉｒｅｄＣｏｍｐｕｔｉｎｇ）的研究，越来越引起众多学者的关注和兴 趣，产生了神经网络、 遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。粒子群优化（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法［１，２］是由Ｅｂｅｒｈａｒｔ和Ｋｅｎｎｅｄｙ于１９９５年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（１）算法简洁，可调参数少，易于实现；（２）随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（３）利用评价函数衡量个体的优劣程度，搜索速度快；（４）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法［３，４］（ＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）是由意大利学者Ｍ．Ｄｏｒｉｇｏ，Ｖ．Ｍａｎｉｅｚｚｏ和Ａ．Ｃｏｌｏｒｎｉ 于２０世纪９０年代初提出的一种新型的智能优化算法，已经被应用到ＴＳＰ问题［５，６］、二次分配问题、工件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（１）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（２）是一种分布式的优化方法，易于并行实现；（３）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（４）适合于求解离散优化问题；（５）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了ＰＡＡＡ算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术ＳＰＡＣＥＥＬＥＣＴＲＯＮＩＣＴＥＣＨＮＯＬＯＧＹ７６
ＥｑｕｉｐｍｅｎｔＭａｎｕｆａｃｔｒｉｎｇＴｅｃｈｎｏｌｏｇｙＮｏ．２，２００８ 收稿日期：２００７－１１－１３ 基金项目：教育部新世纪优秀人才支持计划（ＮＣＥＴ－０６－０３８２）；教育部重大项目（３０６０２３）；霍英东基金项目（１０４０３０）作者简介：姜秋霞（１９８２—）女，硕士生，研究方向：混合蚁群算法；王中杰，博士，教授。 混合蚁群算法的研究及其应用 姜秋霞，王中杰 （同济大学电子与信息工程学院，上海２０１８０４） 摘要：蚁群算法较强的鲁棒性、寻径过程的并行性以及易于与其他启发式算法结合的特点，使得蚁群算法吸引了越来越多研究者的注意。分析了各种混合蚁群算法，总结了蚁群算法与其他智能算法相结合的方法，针对ＱｏＳ路由寻优问题验证混合蚁群算法，通过比较混合蚁群算法和基本蚁群算法的仿真结果，进一步说明混合蚁群算法的有效性和可行性。关键词：蚁群算法；混合蚁群算法；算法融合；ＱｏＳ路由中图分类号：ＴＰ３０１．６ 文献标识码：Ａ 文章编号：１６７２－５４５Ｘ（２００８）０２－００３６－０３ 蚁群算法是由意大利学者Ｍ．Ｄｏｒｉｇｎ［１－４］从生物进化的机理中受到启发，模拟自然界中蚁群的觅食行为而提出的用以解决复杂优化问题的一种新型模拟进化算法。虽然这种新型的智能优化方法具有并行性、正反馈等许多优点，但也存在如初期信息素匮乏、收敛速度慢等一些不足之处，针对这些缺陷，近年来众多国内外学者在蚁群算法的改进方面做了大量的研究工作。 尽管算法的改进有效地改善了算法的收敛性，但难以满足实际应用中的需求，当问题的规模和复杂度增加时，单一算法的优化能力大为削减。鉴于这种现状，算法混合的思想已成为提高算法优化性能的一个重要而有效的途径。蚁群算法优点之一是易于与其他智能算法相结合，而混合算法是利用不同优化算法的特长互相补充，为此将蚁群算法与其他智能优化算法相融合，形成优势互补。因此，混合算法是改进和完善蚁群优化算法的重要途径。 １各种混合蚁群算法基本思想 １．１蚁群算法简介［２￣３］ 为模拟蚂蚁实际行为设定：ｍ是蚁群中蚂蚁的数量，ｄｉｊ是 ｉ城市到ｊ城市之间的距离，!ｉｊ是边（ｉ，ｊ）的能见度，"ｉｊ＝１／ｄｉｊ，反 映由城市ｉ转移到城市ｊ的启发程度，#ｉｊ是边（ｉ，ｊ）上的信息素轨迹强度，Δ$ｋ ｉｊ（ｔ）是蚂蚁ｋ在边（ｉ，ｊ）上留下的单位长度轨迹信息素量， ｐｋ ｉｊ 是蚂蚁ｋ从城市ｉ转移到城市ｊ的状态转移概 率，ｊ是尚未访问的城市，则状态转移概率ｐｋ ｉｊ可由下式表示： ｐｋ ｉｊ（ｔ）＝ %ｉｊ（ ｔ!"） & ?’ｉｋ（ ｔ!" ） ( #)ｉｓ（ｔ! "）*?+ｉｓ（ｔ!"）,，若ｊ∈ａｌｌｏｗｅｄｋ ，$ & & &&&% & &&&&’ ０ 式中ａｌｌｏｗｅｄｋ＝Ｃ－ｔａｂｕｋ() 表示蚂蚁ｋ下一步允许选择的城市；-为信息素启发式因子，表示轨迹的相对重要性；.为期望启发式因子，表示能见度的相对重要性；/ｉｊ（ｔ）为启发函数，其表达式为：0ｉｊ＝１／ｄｉｊ。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有ｎ个城市的遍历后，要对残留信息进行更新处理。由此，ｔ＋ｎ时刻在路径（ｉ，ｊ）上的信息量可按如下规则进行调整： 1ｉｊ（ｔ＋ｎ）＝（１－2）?3ｉｊ（ｔ）＋Δ4ｉｊ（ｔ）Δ5ｉｊ（ｔ）＝ｍ ｋ＝１ #Δ6ｋ ｉｊ（ｔ ）式中，7表示信息素挥发系数，则１－8表示信息素残留因子，为了防止信息的无限积累，9的取值范围：:*０，!" １；Δ;ｉｊ（ｔ）表示本次循环中路径上的信息素增量，初始时刻Δ<ｉｊ（ｔ）＝０，Δ=ｋ ｉｊ（ｔ）表示第ｋ只蚂蚁在本次循环中留在路 径（ｉ，ｊ）上的信息素。 根据信息素更新策略的不同，Ｄｏｒｉｇｏ给出了三种不同的模型：蚁周系统 （ａｎｔ－ｃｙｃｌｅｓｙｓｔｅｍ）、蚁量系统（ａｎｔ－ｑｕａｎｔｉｔｙｓｙｓｔｅｍ）、蚁密系统（ａｎｔ－ｄｅｎｓｉｔｙｓｙｓｔｅｍ）。区别仅在于Δ>ｋ ｉｊ（ｔ，ｔ＋１）的表达式不同。蚁周系统使用了全局信息，而其他两种模型只使用了局部信息。 １．２蚁群算法与遗传算法相融合 蚁群算法与遗传算法（ＧＡ）相融合是蚁群算法与仿生优化算法相互融合方面研究最早且应用最广的一个尝试。Ｐｉｌａｔ ＭＬ［５］等采用ＧＡ对蚁群算法中的３个参数进行优化，首先对信 息启发式因子 ?取默认值，期望启发式因子@、 信息素挥发系数A 、信息素强度Ｑ的取值是相对于B 的一个比值。但由于不能实现蚁群算法４个组合参数的全局寻优，也就很难求得 ＴＳＰ的全局最优解。段海滨等人［６￣９］针对求解离散域优化问题 提出一种新的蚁群遗传算法（ＡＣＡＧＡ），其核心是应用ＧＡ对 Ｓ*ａｌｌｏｗｅｄｋ
第２４卷第∞期计算机仿真 文章编号：１００６—９３４８（２００７）０８０１６７—０４ 双信息素蚁群算法及其在ＴＳＰ中的应用研究 薛莉，戴居丰，魏志成 （天津大学电子信息二程学院，人津３０００７２） 摘要：提出了一种新的蚁群箅法，通过在算法中引人双信息素，很好地改进ｒ算法在解决ＴＳＰ（旅行商）问题¨的收敛眭和最优解的仝局性。一方而通过提高全局信息素对城市路释选择的影响度，很大程度上缩短了算法寻优时｜１１Ｊ，使算法收敛悱得到很大的改善；另一方面通过刘接近最优解的定范围内次优解进行局部更新，避免了舅珐容易收敛于局部最优解的欹点，极大地改进了最优解的全局特一阡。神：ＭＡＴＬＡＢ中构建了摹于蚁群算法的ＴＳＰ问题模型，仿真结果表明，独立的全局信息索使蚁群很快集中于各个次优解区域搜索，局部更新策略又使蚁群跳出局部级值寻找最优，仿真结果证明算法的改进｜１分有救。 关键词：蚁群算法；双信息素；旅行阿问题 中图分类号：ＴＰ３０１，６文献标识码：Ａ ＡｐｐｌｉｃａｔｉｏｎｏｆＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ ｗｉｔｈＴＷＯＫｉｎｄｓｏｆＰｈｅｒｏｍｏｎｅｉｎＴＳＰ ＸＵＥＬｉ．ＤＡＩＪｕ—ｆｅｎｇ．ＷＥＩＺｈｉ—ｅｈｅｎｇ （ＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇＤｅｐａｒｔｍｅｎｔ，ＴｉａｎｊｉｎＵｎｉｖｅｒｓｉｔｙ，Ｔｉｍｔｊｉｎ３０００７２，Ｃｈｉｎａ）ＡＢＳＴＲＡＣＴ：Ｔｈｉｓｐａｐｅｒｇｉｖｅｓａｎｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｗｉｔｈｔｗｏｋｉｎｄｓｏｆｐｈｅｒｏｍｏｎｅ，ｉｔｃａｎｏｖｅｒｃｏｍｃｔｈｅｄｅｆｉｃｉｅｎｃｉｅｓｏｆｔｈｅｐｒｉｍａｌａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ．ＴｏｓｏｌｖｅＴＳＰ．ｉｔｓｈｏｒｔｅｎｓｔｈｅｔｉｍｅｏｆｔｈｅｃｏｕｒｓｅｔｏｆｉｎｄｔｈｅｂｅｓｔｖａｌｕｅｂｙｅｎｈａｎｃｉｎｇｔｈｅｇｌｏｂａｌｐｈｅｒｏｍｏｎｅｗｅｉｇｈｔ．ＡｌｓｏａｌｏｃａｌｕｐｄａｔｉｎｇｉｓｉｎｔｒｏｄｕｃｅｄｗｈｅｎｔｈｅｖａｌｕｅｉｓｉｎａｒａｎｇｅｏｆｔｈｅｂｅｓｔｖａｌｕｅｇｉｖｅｎｉｎＴＳＰＬＩＢ．Ｓｏｔｈｉｓｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｃ０１１ｆｉｎｄｔｈｅｄｅｓｉｒｅｄｖａｌｕｅｆｌｅｅｔｌｙａｎｄａｃｃｕｒａｔｅｌｙ．Ａｔｌａｓｔ，ｔｈｅｍｏｄｕｌｅｏｆＴＳＰｉｓｄｅｖｅｌｏｐｅｄ，ｔｈｅｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｓｉｍｕｌａｔｃｄｉｎＭＡＴＬＡ．Ｂ，ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｉｓｉｍｐｒｏｖｅｄｏｂｖｉｏｕｓｌｙ ＫＥＹＷＯＲＤＳ：Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；’ｌ＇ｗｏｋｉｎｄｓｏｆｐｈｅｒｏｍｏｎｅ；ＴＳＰ １引言 ’ｒｓｐ“１（旅行商）问题是一个经典的组合优化问题，问题要求得到一条遍历所有给定城市的最短闭合路径，属于ＮＰ难问题。随着城市数目的不断增加，导致求懈空间成指数级增长，通过穷举法根奉元法求解，因此用优化算法解决ＴＳＰ问题就十分必要。因此对一些性能较好的优化算法就呼之欲出。 随着人们对现代生物特性的不断研究，一些进化仿生优化算法可以比较理想地解决复杂的组合优化问题。目前求解。Ｉ，＇ＳＰ问题的典型优化算法主要有遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ）和蚁群算法（ＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ）。蚁群算法是由意大利学者ＭａｃｒｏＤｏｒｉｇｏ等，通过对蚂蚁觅食过程的研究而提出的。，该算法应用了蚂蚁觅食中个体行动、整体协作的 收稿日期：２００６—０８—３０修同Ｈ期：２００６—０９—０７工作特性，通过信息素（Ｐｈｅｒｏｍｏｎｅ）这个中间纽带将多个个体（蚂蚁）的动作联系起来，最终完成ｒ谣个蚁群系统的觅食（寻优）过程。 自加世纪９０年代蚁群算法诞生以来，各位专家学者肘它进行了不断的研究和改进４’ｌ。，蚁群算法虽然可以解央ＴＳＰ问题，但是普遍存在收敛速度慢、求解结果易收敛于局部最优解等缺陷。为此本文提出了种新的蚁群算法一双信息素蚁群算法，该算法不仅可以寻找到最优ＴＳＰ路径，相对于ＭＭＡＳ，ＡＣＡ，ＧＡ算法极大地缩短了算法的寻优时间．极大地改进了算法的全局特性。本文通过在ＭＡＴＬＡＢ中构建基于蚁群算法的ＴＳＰ标准问题模璎，仿真了算法的寻优过程。最后通过分析仿真结果，发现双信息索蚁群算法相比传统优化算法在寻优特性和最优解的收敛性上都有ｒ很大改进。 ２蚁群算法 自然界中蚂蚁之所以总能够发现巢穴副食物问的最短 一１６７— 万方数据万方数据
智能控制之蚁群算法 1引言 进入21世纪以来，随着信息技术的发展，许多新方法和技术进入工程化、产品化阶段，这对自动控制技术提出新的挑战，促进了智能理论在控制技术中的应用，以解决用传统的方法难以解决的复杂系统的控制问题。随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。 智能控制技术的主要方法有模糊控制、基于知识的专家控制、神经网络控制和集成智能控制等,以及常用优化算法有:遗传算法、蚁群算法、免疫算法等。 蚁群算法是近些年来迅速发展起来的，并得到广泛应用的一种新型模拟进化优化算法。研究表明该算法具有并行性，鲁棒性等优良性质。它广泛应用于求解组合优化问题，所以本文着重介绍了这种智能计算方法，即蚁群算法，阐述了其工作原理和特点，同时对蚁群算法的前景进行了展望。 2 蚁群算法概述 1、起源 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 Deneubourg及其同事(Deneubourg et al.,1990; Goss et al.,1989)在可监控实验条件下研究了蚂蚁的觅食行为，实验结果显示这些蚂蚁可以通过使用一种称为信息素的化学物质来标记走过的路径，从而找出从蚁穴到食物源之间的最短路径。 在蚂蚁寻找食物的实验中发现，信息素的蒸发速度相对于蚁群收敛到最短路径所需的时间来说过于缓慢，因此在模型构建时，可以忽略信息素的蒸发。然而当考虑的对象是人工蚂蚁时，情况就不同了。实验结果显示，对于双桥模型和扩展双桥模型这些简单的连接图来说，同样不需要考虑信息素的蒸发。相反，在更复杂的连接图上，对于最小成本路径问题来说，信息素的蒸发可以提高算法找到好解的性能。 2、基于蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下假设： （1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的环境作出反应，也只对其周围的局部环境产生影响。 （2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的自适应表现，即蚂蚁是反应型适应性主体。 （3）在个体水平上，每只蚂蚁仅根据环境作出独立选择；在群体水平上，单
蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法; 1 前言 蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。 2 基本蚁群算法 2.1 蚁群算法基本原理 根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路
第31卷 第1期 吉首大学学报(自然科学版)Vol.31 No.1 2010年1月J ournal of J is ho u Uni ver s i t y (Nat ural Sci ence Editio n )J an.2010 文章编号:1007-2985(2010)01-0035-05 蚁群算法研究应用现状与展望 3 叶志伟,周 欣,夏 彬 (湖北工业大学计算机学院,湖北武汉 430068) 摘 要:蚁群算法是工程优化领域中新出现的一种仿生进化算法.首先介绍基本蚁群算法的原理和模型,然后评述近年来对蚁群算法的若干改进以及在许多新领域中的发展应用,最后对蚁群算法未来的发展和研究方向进行展望. 关键词:蚁群算法;优化;最优决策 中图分类号:TN911.73 文献标识码:A 实际工程问题常具有复杂性、非线性等特点,而它的解决通常也是一种寻求最优决策的过程,因此寻求一种适合大规模并行、具有智能特征的优化算法已经成为引人注目的研究方向.目前,除了业已得到公认的遗传算法、模拟退火算法、禁忌搜索算法等热门进化算法,蚁群优化算法[1-3](Ant Colony Optimization Algo rithm ,ACO ,也称蚂蚁系统)正在开始崭露头角,为复杂的系统优化问题提供了新的具有竞争力的求解算法.ACO 是由意大利学者M.D o rigo 等人于1991年首先提出来一种新兴模拟生物智能的算法,在短期内得到了迅速的发展,除了用于大批经典优化问题的求解,如二次分配问题(Qua d 2ra tic Assignme nt Problem ,QAP )、有序排列问题(Sequential Orde ring Problem ,SOP )[2-16]等,在实际工程领域也得到广泛的应用. 1 基本ACO 原理 为了说明ACO 模型,这里引入旅行商问题(TSP ),它是一类经典的组合优化问题,即在给定城市个数和各城市之间距离的条件下,要找到1条遍历所有城市当且仅当1次最短的线路. 为模拟真实蚂蚁的行为,首先引入如下标记:m 是蚁群的规模;b i (t )是t 时刻位于城市i 的蚂蚁数量,m = ∑n i =1 b i (t );d i j 是两城市i 和j 之间的距离;ηi j 是由城市i 转移到城市j 的可见度,反映城市i 转移到城市j 的启发信息,这个量在ACO 的 运行中保持不变;τi j 是边(i ,j )上的信息素轨迹强度;Δτi j 是蚂蚁k 在边(i ,j )上留下的信息素轨迹量;p k i j 是蚂蚁k 的转移概 率,j 是没有访问过的城市. 每只蚂蚁都是具有如下行为的个体:①由城市i 转移到城市j 的过程中或是在完成1次循环以后,蚂蚁在边(i ,j)上释放信息素;②蚂蚁随机的选择下一个将要访问的城市;③在完成一次循环以前,不允许选择已经访问过的城市. 基本ACO 在TSP 问题中实现的具体过程如下:假设将m 只蚂蚁放入到n 个随机选择的城市中;每只蚂蚁每步根据一定的概率,选择下一个它还没有访问过的城市,将所有城市遍历完以后回到出发的城市.蚂蚁选择目标城市的概率公式为 p k ij (t)= (τi j (t ))α(ηij )β/∑j ∈allowed (τi j (t ))α(ηi j )β j ∈allowed ,0 othe rwise.(1) 在得到每个候选城市的选择概率以后,蚂蚁运用随机选择的方式决定下一步要去的城市.(1)式中各参数意义如下:α表示信息素信息相对重要程度;β表示可见度信息相对重要程度.为了避免对同一个城市的重复访问,每只蚂蚁都保存一个列表tabu (k ),用于记录到目前为止蚂蚁已经访问过的城市集合.为了避免残留信息素过多引起残留信息淹没启发信息的现象发生,在每一只蚂蚁走完1步或者完成对所有n 个城市的访问后,对残留信息素进行更新处理.这样得到(t +n)时刻在(i , 3收稿日期:2009-04-10 基金项目:湖北省自然科学基金资助项目(2008CDZ003;2008CDB342);湖北省教育厅优秀中青年项目(Q20081409;Q20081402) 作者简介叶志伟(),男,湖北浠水人,湖北工业大学计算机学院副教授,博士,主要从图像处理领域和智能计算研究:1978-.
蚁群算法在车辆路径问题中的应用 摘要 蚁群算法（Ant Colony Optimization, ACO）是意大利学者M.Dorigo等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。通过介绍蚁群觅食过程中基于信息素（pheromone）的最短路径的搜索策略，给出了基于MATLAB 的蚁群算法在车辆路径问题（Vehicle Routing Problem, VRP）中的应用。蚁群算法采用分布式并行计算机制，易于其他方法结合，而且具有较强的鲁棒性，但搜索时间长，容易陷入局部最优解。针对蚁群算法存在的过早收敛问题，加入2—opt方法对问题求解进行了局部优化，计算机仿真结果表明，这种混合型蚁群算法对求解车辆路径问题有较好的改进效果。 关键词：蚁群算法、组合优化、车辆路径问题、2-opt方法 1.车辆路径问题 车辆路径问题（VRP）来源于交通运输，1959年由Dantzig 提出，它是组合优化问题中一个典型的NP-hard问题。最初用于研究亚特兰大炼油厂向各个加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点。
车路优化问题如下： 已知有一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干可供派送的车辆，运载能力给定，每辆车都是从起点出发，完成若干客户点的运送任务后再回到起点。现要求以最少的车辆数和最少的车辆总行程来完成货物的派送任务。 2、蚁群系统基本原理 在蚂蚁群找到食物时，它们总能找到一条从食物到蚁穴之间的最短路径。因为蚂蚁在寻找食物时会在路途上释放一种特殊的信息素。当它们碰到一个还没有走过的路口时，会随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后面的蚂蚁再次碰到这个路口时，会选择激素浓度较高的路径走。这样形成了一个正反馈，最优路径上的激素浓度越来越高，而其他的路径上激素浓度却会随时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻找过程中，整个蚁群通过相互留下的信息素作用交换着路径信息，最终找到最优路径。 3、基本蚁群算法求解车辆路径问题 求解VRP问题的蚂蚁算法中，每只蚂蚁是一个独立的用 于构造路线的过程，若干蚂蚁过程之间通过信息素值来交换信
蚁群算法及其在序列比对中的应用研究综述摘要：蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。 关键词：蚁群算法；序列比对；信息素 Abstract: Ant colony algorithm (ACA) is a novel bionic evolutionary algorithm. As a global searching approach，ACA has some characteristic，such as positive feedback, distributing，paralleling, self-organizing, etc，and from it was introduced, it has been used to solve all kinds of complex optimization problem. Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained from sequence alignment, one can infers the structure, function and evolutionary relationship of genes. In this paper, the basic principles of ACA are introduced at length, and various improvements and convergence Analysis of ACA are also presented. Then the current study of double sequence alignment and multiple sequence alignment based on ant colony algorithm are reviewed and evaluated. Finally, some future research directions about ACA are proposed. Key words: Ant Colony Algorithm; Sequence Alignment; Pheromone 1 引言 蚁群算法(Ant Algorithm)是一种源于大自然中生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于在模拟仿真中使用的是人工蚂蚁概念，因此有时亦被称为蚂蚁系统(Ant System)。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物——信息激素(Pheromone)，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息激素轨迹(Trail)也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强
蚁群算法原理及在TSP 中的应用 1 蚁群算法（ACA ）原理 1.1 基本蚁群算法的数学模型 以求解平面上一个n 阶旅行商问题(Traveling Salesman Problem ，TSP)为例来说明蚁群算法ACA （Ant Colony Algorithm ）的基本原理。对于其他问题，可以对此模型稍作修改便可应用。TSP 问题就是给定一组城市，求一条遍历所有城市的最短回路问题。 设()i b t 表示t 时刻位于元素i 的蚂蚁数目，()ij t τ为t 时刻路径(,)i j 上的信息量，n 表示TSP 规模，m 为蚁群的总数目，则1()n i i m b t ==∑；{(),}ij i i t c c C τΓ=?是t 时刻集合C 中元素(城市)两两连接ij t 上残留信息量的集合。在初始时刻各条路径上信息量相等，并设 (0)ij const τ=，基本蚁群算法的寻优是通过有向图 (,,)g C L =Γ实现的。 蚂蚁(1,2,...,)k k m =在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表(1,2,...,)k tabu k m =来记录蚂蚁k 当前所走过的城市，集合随着 k tabu 进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路 径的启发信息来计算状态转移概率。()k ij p t 表示在t 时刻蚂蚁k 由元素(城市)i 转移 到元素(城市)j 的状态转移概率。 ()*()()*()()0k ij ij k k ij ij ij s allowed t t j allowed t t p t αβ αβτητη??????????? ∈?????=????? ??? ∑若否则 (1) 式中，{}k k allowed C tabuk =-表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心规则；()ij t η为启发函数，其表达式如下： 1 ()ij ij t d η= (2)
《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年
蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理
%% 蚁群算法求函数极值 % 初始化 clear all; %清除所有变量 close all; %清图 clc; %清屏 m = 20; %蚂蚁个数 G = 200; %最大迭代次数 Rho = 0.9; %信息素蒸发系数 P0 = 0.2; %转移概率常数 XMAX = 7; %搜素变量x最大值 XMIN = 1; %搜素变量x最小值 YMAX = 7; %搜素变量y最大值 YMIN = 1; %搜素变量y最小值 %% 随机设置蚂蚁初始位置 for i = 1:m X(i,1) = (XMIN +(XMAX-XMIN)*rand); X(i,2) = (YMIN +(YMAX-YMIN)*rand); Tau(i) = func(X(i,1),X(i,2)); end step = 0.1; for NC = 1:G lamda = 1/NC; [Tau_best,BestIndex] = max(Tau); % 计算状态转移概率 for i = 1:m P(NC,i) =(Tau(BestIndex)-Tau(i))/Tau(BestIndex); end % 位置更新 for i = 1:m %局部搜素 if P(NC,i) < P0 temp1 = X(i,1)+(2*rand-1)*step*lamda; temp2 = X(i,2)+(2*rand-1)*step*lamda; else %全局搜索 temp1 = X(i,1)+(XMAX-XMIN)*(rand-0.5); temp2 = X(i,2)+(YMAX-YMIN)*(rand-0.5); end % 边界处理 if temp1 < XMIN temp1 = XMIN; end if temp1 > XMAX temp1 = XMAX;
蚁群算法综述 控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景 蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。 从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。 二、蚁群算法的研究发展现状 国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。提出一种基于蚁群算法的TSP问题分段求解算法。王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。 随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。ACO-MH为蚁群算法的理论研究和算法设计提供了技术上的保障。在蚁群优化的收敛性方面，W.J.Gutjahr做了开创性的工作，提出了基于图的蚂蚁系统元启发式(Graph-Based Ant System Metaheuristic)这一通用的蚁群优化 的模型，该模型在一定的条件下能以任意接近l的概率收敛到最优解。T.StBtzle 和M.Dorigo对一类ACO算法的收敛性进行了证明，其结论可以直接用到两类实验上，证明是最成功的蚁群算法——MMAs和ACS。N.Meuleau和M.Dorigo研究了
蚁群算法在物流系统优化中的应用 ——配送中心选址问题 LOGO https://www.doczj.com/doc/942166290.html,
框架 蚁群算法概述 蚁群算法模型 物流系统中配送中心选择问题 蚁群算法应用与物流配送中心选址 算法举例
蚁群算法简介 ?蚁群算法(Ant Algorithm简称AA)是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁群优化方法(Ant Colony Optimization简称ACO)。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统(Ant System，简称AS)。
蚁群觅食图1 ?How do I incorporate my LOGO and URL to a slide that will apply to all the other slides? –On the [View]menu, point to [Master],and then click [Slide Master]or [Notes Master].Change images to the one you like, then it will apply to all the other slides. [ Image information in product ] ?Image : www.wizdata.co.kr ?Note to customers : This image has been licensed to be used within this PowerPoint template only. You may not extract the image for any other use.