（控制理论与控制工程专业论文）基于连续空间优化问题的蚁群算法及其应用研究.pdf

华北电力大学硕士学位论文摘要 摘要 蚁群算法是一种随机搜索算法，与其它模拟进化优化算法样，通过由候选解 组成的群体的进化过程来寻求最优解，它具有许多优良性质和实际应用价值。本文 介绍了蚁群算法基本模型的原理、特点、构成和实现方法。通过仿真试验分析了关 键参数对算法性能的影响，并对基本蚁群算法参数的合理选取进行了实验分析。文 章在分析总结用于连续函数优化的蚁群算法的基础上，对用于一般连续函数优化的 蚁群算法模型中的全局转移因子和信息素挥发系数提出了改进措旌。通过仿真实验 证明该改进模型用于处理一般函数的优化和控制系统的p i d 参数优化效果良好，值 得进一步研究。 关键词：蚁群算法，连续空间优化，全局转移因子，信息素挥发系数，p i d 参 数优化 a b s t r a c t t h ea n te o l o n ya l g o r i t h mi sak i n do fs t o c h a s t i e ce x p l o r a t i v ea l g o r i t h m s ，a s t h es a m eo fo t h e rk i n do fs t i m u l a t e de v o l u t i o n a r ya l g o r i t h m s ，i tf i n d st h eb e s t s o l u t i o no fo p t i m i z a t i o np r o b l e mb ym a k i n gu s e so ft h ee v o l u t i o n a r yp r o c e d u r eo fa s e to fc o o p e r a t i n ga g e n t so fc a n d i d a t es o l u t i o n s i th a ss h o w nag r e a td e a lo fs a l i e n t c h a r a e t e ra n dp e r f o r m e dg r e a tv a l u ei ni t sa p p l i c a t i o n t h ep r i n c i p l e ，t h em o d e l ，t h e c h a r a c t e r i s t i c sa n dt h em a n a g e m e n ta b o u tt h eb a s i ca l g o r i t h m so fa n tc o l o n ya r e p r e s e n t e d i nt h i sp a p e r t h ei n f l u n c eo ft h ep a r a m e t e r so na l g o r i t h ma n dt h e r e a s i o n a b l es e l e c t i o na b o u tt h ep a r a m e t e r sa r ed i s c u s s e di ns i m u l a t i o nr e s e a r c h t h e a u t h o ri m p r o v e st h ef a c t o ro fg l o b a lj u m pa n dt h ep h e r o m o n ep o l a t i l i t yo fa n te o l o n y a l g o r i t h mo nt h eg e n e r a lf u n c t i o no p t i m i z a t i o np r o b l e mb a s i n g0 nt h ea n a l y s i so f i m p r o v e do n e s t h er e s u l ta b o u tt h es i m u l a t i o nr e s e a r c hi sd e m o n s t r a t e dt h a tt h e c h a r a c t e r i s t i c so fa n tc o l o n ya l g o r i t h mf o rg e n e r a lf u n c t i o no p t i m i z a t i o np r o b l e m a n dp i dp a r a m e t e r so p t i m i z a t i o np r o b l e ma r es a l i e n t ，a n di ti sw e a r t h yt om a k e f u r t h e rr e s e a r e h e s j i ay a n c h e n ( c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g ) d i r e c t e db yp r o f l i uc h a n g l i a n g k e yw o r d s ：a n te o l o n ya l g o r i t h m ，c o n t i n u o u ss p a c eo p t i m i z a t i o n ，f a c t o ro f g l o b a lj u m p ，p h e r o m o n ep o l a t i l i t y ，p i dp a r a m e t e r so p t i m i z a t i o np r o b l e m 华北电力大学硕士学位论文摘要 摘要 蚁群算法是一种随机搜索算法，与其它模拟进化优化算法样，通过由候选解 组成的群体的进化过程来寻求最优解，它具有许多优良性质和实际应用价值。本文 介绍了蚁群算法基本模型的原理、特点、构成和实现方法。通过仿真试验分析了关 键参数对算法性能的影响，并对基本蚁群算法参数的合理选取进行了实验分析。文 章在分析总结用于连续函数优化的蚁群算法的基础上，对用于一般连续函数优化的 蚁群算法模型中的全局转移因子和信息素挥发系数提出了改进措旌。通过仿真实验 证明该改进模型用于处理一般函数的优化和控制系统的p i d 参数优化效果良好，值 得进一步研究。 关键词：蚁群算法，连续空间优化，全局转移因子，信息素挥发系数，p i d 参 数优化 a b s t r a c t t h ea n te o l o n ya l g o r i t h mi sak i n do fs t o c h a s t i e ce x p l o r a t i v ea l g o r i t h m s ，a s t h es a m eo fo t h e rk i n do fs t i m u l a t e de v o l u t i o n a r ya l g o r i t h m s ，i tf i n d st h eb e s t s o l u t i o no fo p t i m i z a t i o np r o b l e mb ym a k i n gu s e so ft h ee v o l u t i o n a r yp r o c e d u r eo fa s e to fc o o p e r a t i n ga g e n t so fc a n d i d a t es o l u t i o n s i th a ss h o w nag r e a td e a lo fs a l i e n t c h a r a e t e ra n dp e r f o r m e dg r e a tv a l u ei ni t sa p p l i c a t i o n t h ep r i n c i p l e ，t h em o d e l ，t h e c h a r a c t e r i s t i c sa n dt h em a n a g e m e n ta b o u tt h eb a s i ca l g o r i t h m so fa n tc o l o n ya r e p r e s e n t e d i nt h i sp a p e r t h ei n f l u n c eo ft h ep a r a m e t e r so na l g o r i t h ma n dt h e r e a s i o n a b l es e l e c t i o na b o u tt h ep a r a m e t e r sa r ed i s c u s s e di ns i m u l a t i o nr e s e a r c h t h e a u t h o ri m p r o v e st h ef a c t o ro fg l o b a lj u m pa n dt h ep h e r o m o n ep o l a t i l i t yo fa n te o l o n y a l g o r i t h mo nt h eg e n e r a lf u n c t i o no p t i m i z a t i o np r o b l e mb a s i n g0 nt h ea n a l y s i so f i m p r o v e do n e s t h er e s u l ta b o u tt h es i m u l a t i o nr e s e a r c hi sd e m o n s t r a t e dt h a tt h e c h a r a c t e r i s t i c so fa n tc o l o n ya l g o r i t h mf o rg e n e r a lf u n c t i o no p t i m i z a t i o np r o b l e m a n dp i dp a r a m e t e r so p t i m i z a t i o np r o b l e ma r es a l i e n t ，a n di ti sw e a r t h yt om a k e f u r t h e rr e s e a r e h e s j i ay a n c h e n ( c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g ) d i r e c t e db yp r o f l i uc h a n g l i a n g k e yw o r d s ：a n te o l o n ya l g o r i t h m ，c o n t i n u o u ss p a c eo p t i m i z a t i o n ，f a c t o ro f g l o b a lj u m p ，p h e r o m o n ep o l a t i l i t y ，p i dp a r a m e t e r so p t i m i z a t i o np r o b l e m 声明尸明 本人郑重声明：此处所提交的硕士学位论文基于连续空间优化问题的蚁群 算法及其应用研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进 行的研究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之 处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华北 电力大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：亟逛臣 e t 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有 权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩 印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅； 学校可以学术交流为目的，复制赠送和交换学位论文；同意学校可以用不同方 式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：秀近臣 e l 期：2 壁立3 ：f ：压 导师签名： 日 期： 华北电力大学硕士学位论文 1 1 选题背景及意义 第一章引言弟一旱jl 苗 仿生优化算法是人工智能领域中一个重要的分支，其中包括模拟生物界中自然 选择和遗传机制的遗传算法、模拟蚂蚁群体觅食行为的蚁群算法以及模拟鸟类群体 捕食行为的微粒群算法等。 上世纪9 0 年代初期，意大利学者d o f i g om a c r o 啦川等人从生物进化论中受到 启发，通过模拟自然界中蚂蚁集体寻优的行为而提出了蚁群优化算法( a n tc o l o n y o p t i m i z a t i o n ，a c o ) ，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网 络算法等启发式搜索算法之后的一种新型的基于种群的启发式仿生类进化算法。 由于该算法不依赖于具体问题的数学描述，具有全局优化能力和本质上的并行性， 同时比遗传算法模拟退火法等早期的进化算法具备更高的可靠性，求解时间短，易 于计算机实现等优点，因而受到系统优化领域研究人员的广泛重视。如今这一新兴 的仿生优化算法已经成为人工智能领域的一个研究热点。目前对其研究已经渗透到 多个应用领域，并由解决一维静态优化问题发展到解决多维动态组合优化问题。如 今在国内外许多学术期刊和重要国际会议上，蚁群算法已经成为交叉学科中一个非 常活跃的前沿性研究问题。 最初人们充分利用蚁群搜索食物的过程与旅行商问题( t s p ) 之间的相似性， 解决了t s p 问题，取得了很好的结果。随后，蚁群算法被用来求解二次分配问题 ( q a p ) 、车辆路径规划问题( v r p ) 、车间作业调度问题( j s p ) 等n p 完全问题，显 示出蚁群算法在求解复杂优化问题方面的优越性。 近1 0 年来的研究结果已经表明：蚁群算法用于组合优化具有很强的发现较好 解的能力，是一个增强型学习系统，具有分布式的计算特性，具有很强的鲁棒性， 易于与其它优化算法融合。然而，蚁群算法存在搜索时间过长、易于停滞的问题。 为了克服这些缺点，不少学者提出了改进算法。例如，d o r i g o 和g a m b a r d e l l a 提出 蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 算法【4 l ，使用伪随机比例状态转移规则选择下一 个城市，仅让每一代中最好的个体所走过的路径上的信息素进行更新，以加快收 敛速度。s t u t z l e 和h o o s 提出最大一最小蚂蚁系统( m a x - m i na n ts y s t e m 。 m m a s ) 【5 6 j ，对路径上的信息素进行限制，以期克服停滞的问题。胡晓兵等人根据 节点分支数动态地调整转移概率以避免算法出现停滞现象【7 1 。朱庆保，杨志军以最近 节点选择和动态信息更新策略来加速全局收敛，以一种独特的变异策略来加快局部 华北电力大学硕士学位论文 寻优，使收敛速度大幅度地提高【8 】。陈岐，秦玲等人提出了一种具有感觉和知觉特 征的蚁群算法【9 】，根据路径上信息量的情况动态地、自适应地决定路径选择策略， 有效地缓解基本蚁群算法容易早熟、停滞和收敛速度之间的矛盾。 从以上分析，蚁群算法的性能好坏就在于节点选择方法和信息素变化趋势。所 以，从这两个方面对蚁群算法进行改进，采用基于分散度的自适应节点选择方式 和基于自适应信息素挥发因子的信息素更新方式，提高蚁群算法的性能。蚁群算法 的另一个缺点就是难以处理连续空间的优化问题。由于每个蚂蚁在每个阶段所作的 选择总是有限的，它要求离散的解空间，因而它对组合优化等离散优化问题很适 用，而对连续空间的优化问题的求解不能直接应用。 在实际控制工程的优化问题中大量遇到的是连续性问题，因此，在将优化性能 良好的蚁群算法用于连续性空间优化问题时，只能利用蚁群算法的原理和人对优化 函数取得的有关先验知识来构造相应的算法模型，并对算法中许多实施细节加以修 正，从而确定在优化过程中蚁群协同决策所选择的移动方向，由此来求得最优解。 本文提出了一种运用人工蚊群搜索的规律来求解一般函数( 连续性变量空间) 优化 的蚁群算法模型i 该模型在全局上表现为人工蚂蚁在某种先验知识和启发信息引导 下的优化搜索，在局部上则采用了随机性的搜索策略。该策略能提高搜索过程的效 率以及搜索状态的多样性和随机性，而且不受目标函数是否连续、可微等因素的限 制，为蚁群算法应用于实际优化问题提供了一条可行途径。 1 2 蚁群算法的研究进展 自1 9 9 1 年意大利学者d o f i g om a c r o 等提出蚁群算法后的5 年时间里，并没有在 国际学术界引起广泛关注，自然这段时期在蚁群算法理论及应用上也没有取得突破 性进展。到了1 9 9 6 年d o r i g om a c r o 等在( i e e et r a n s a c t i o n so ns y s t e m s ，m a n ，a n d c y b e r n e t i c s - p a r tb 上发表了“a n ts y s t e m ：o p t i m i z a t i o nb yac o l o n yo fc o o p e r a t i n g a g e n t s 一文，在这篇文章中，d o r i g om a c r o 等不仅更加系统地阐述了蚁群算法的基 本原理和数学模型，还将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山法等 进行了仿真实验比较，并把单纯地解决对称t s p 问题拓展到解决非对称t s p 、指派问 题( q u a d r a t i c a s s i g n m e n tp r o b l e m ，q a p ) 以及车间作业调度问题( j o b s h o ps c h e d u l i n g p r o b l e m ，j s p ) ，且对蚁群算法中初始化参数对其性能的影响做了初步探讨。自1 9 9 6 年之后的5 年里，蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域也 得到了迅速拓宽，这期间也有大量有价值的研究成果陆续发表。 随着对蚁群算法关注度的不断提高，1 9 9 8 年1 0 月1 5 日至1 0 月1 6 日在比利时 的布鲁塞尔召开了第一届蚁群算法国际研讨会( a n t s 9 8 )。第一届就吸引了来 华北电力大学硕士学位论文 自世界各地的5 0 多为蚁群算法研究者，随后每隔两年都要在布鲁塞尔召开一次蚁 群算法国际研讨会，历届会议的论文集均有著名的( l e c t u r en o t e si nc o m p u t e r s c i e n c e ) ) ( s c ii n d e x ) 结集出版。2 0 0 0 年d o r i g om 和b o n a b e a ue 等在国际顶级学 术刊物n a t u r e ) ) 上发表了蚁群算法综述【l0 1 ，从而把这一领域的研究推向了国际学 术的最前沿。 进入2 l 世纪后的最近几年，国际著名的顶级学术刊物n a t u r e ) ) 曾多次对蚁群 算法的研究成果进行报道，( f u t u r eg e n e r a t i o nc o m p u t e rs y s t e m s ) ) ( v 0 1 1 6 ，n o 8 ) 和i e e et 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 ( v 0 1 6 ，n o 4 ) 分别于2 0 0 0 年和 2 0 0 2 年出版了蚁群算法特刊。如今，在国内外许多学术期刊和会议上，蚁群算法已 经成为一个备受关注的研究热点和前沿性课题。 我国在蚁群算法领域的研究起步较晚，从公开发表的论文看，国内最先研究蚁 群算法的是东北大学控制仿真研究中心的张纪会博士与徐心和教授】( 1 9 9 7 年1 0 月) 。在国内众多的蚁群算法研究者中，当时年仅1 7 岁的高中生陈烨于2 0 0 1 年在计 算机工程( v 0 1 2 7 ，n o 1 2 ) 上发表了“带杂交算子的蚁群算法 一文【1 2 】，并给予 v i s u a lb a s i c 开发了一个功能齐全、界面友好的“蚁群算法实验室一并引起了国内 广大蚁群算法研究者的极大关注。 回顾蚁群算法自创立以来的十多年的发展历程，目前人们对蚁群算法的研究已 由当初单一的t s p 领域渗透到了多个应用领域。由解决一维静态优化问题发展到解 决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内的研 究，而且在蚁群算法的硬件实现上取得了突破性进展，同时在蚁群算法模型改进及 其与其他仿生优化算法的融合方面也取得了相当丰富的研究成果。从而使这种新兴 的仿生优化算法展现出前所未有的勃勃生机，并已经成为一种完全可与遗传算法相 媲美的仿生优化算法。 下面列举部分有代表性的蚁群算法及其应用情况： 表1 - 1 蚁群算法及其应用 问题名称 研究者算法名称年代 旅行商问题 d o r i g o ，m a n i e z z oa n dc o l o m i a s1 9 9 1 ( t r a v e l i n g g a m b a r d e l l aa n dd o r i g o a n t q 1 9 9 5 s a l e s m a n d o r i g oa n dg a m b a r d e l l a t t 3 , 1 qa c s ，a c s - 3 0 p t 1 9 9 6 p r o b l e m ，t s p ) s t u t z l ea n d h o o sm m a s 1 9 9 7 指派问题m a n i e z z o ，c o l o r n ia n dd o r i g oa s q a p 1 9 9 4 ( q u a d r a t i c s t u t z l ea n dh o o s m m a s q a p 1 9 9 7 a s s i g n m e n t m a n i e z z oa n t s q a p1 9 9 8 p r o b l e m ，q a p ) m a n i e z z oa n dc o l o r n i a s - q a p 1 9 9 8 华北电力大学硕士学位论文 问题名称研究者 算法名称年代 车辆路径问 b u l l n h e i m e r , h a r t la n ds t r a u s s a s v r p1 9 9 7 题( v e h i cr o u t i n g p r o b l e m ，v r p ) g a m b a r d e l l a ，t a i l l a r da n da g a z z i h a s v i 心1 9 9 9 故障识别( f a u l t c h a n g ，e t a l 1 5 1a s f i1 9 9 9 i d e n t i f i c a t i o n ) 孙京诰，李秋艳等【1 6 】 a c a f i 2 0 0 4 连续函数优化 m a t h u rm ，e ta la c o c f o 2 0 0 0 ( c o n s t r a i n t f u n c t i o np r o b l e m魏平，熊伟清【1 7 】 a c a c f c o2 0 0 1 系统辨识w a n ga n dw u a s a s i2 0 0 1 ( s y s t e ma b b a s p o u r ，e t a la c o s i2 0 0 1 i d e n t i f i c a t i o n ) 汪镭，吴启迪【1 3 1 a s a s i2 0 0 3 d u a n ，e ta l a c a s i2 0 0 4 数据挖掘p a r e p i n e l l i ， e ta la n t m i n e r - d m2 0 0 2 ( d a t am i m n g ) 图像处理 m e s h o u la n db a t o u c h ea c s i p 2 0 0 2 ( i m a g i n e p r o c e s s i n g ) z h e n g ，e ta l h a c a i p 2 0 0 3 1 3 论文主要的工作内容 该课题的主要研究内容有： 1 蚁群算法用于连续空间优化问题的方法研究 怎样将用于组合优化问题的蚁群算法的模型用于连续优化问题是蚁群算法用 于连续优化问题需要解决的首要问题。归纳起来，目前用于连续优化问题的蚁群算 法主要有两种： ( 1 ) 基于网格划分策略的连续域蚁群算法【”】 网格法就是在变量区域内打网格，在格点上求约束函数与目标函数的值，对于 满足约束条件的点，再比较其目标函数的大小，从中选择小者，并把该网格点作为 一次迭代的结果。然后在求出的点附近将分点加密，再打网格，并重复前述计算与 比较，直到网格的间距小于预先给定的精度，终止迭代 ( 2 ) 基于信息量分布函数的连续域蚁群算法f 2 0 】 在连续域优化问题的求解中，各单蚁智能体通过散布与其所在解空间位置优劣程度 4 华北电力大学硕士学位论文 相关的信息量分布函数，对蚁群的总体运动方向做出影响，而蚁群的总体运动方向是在 特定区域内，对整个蚁群的信息量分布状态进行考察之后决定的。蚁群运动的总体效果 反映在连续空间内，并逐步收敛到最优解所在的邻近区域，各单蚁的信息量分布函数对 整个解空间所处区域均有影响，其影响程度随各单蚁所在解空间位置距离的增加而递 减。 本课题分析了各种用蚁群算法求解连续空间优化问题的方法【2 卜3 们，提出了改进 措施，建立了一种新的用于连续空间一般函数优化的蚁群算法模型。 2 改进蚁群算法的仿真应用 m a t l a b 是一种用于算法开发、数据可视化、数据分析以及数值计算的高级技 术计算语言和交互式环境。它广泛应用于信号和图像处理、通讯、控制系统设计、 测试和测量、财务建模和分析以及计算生物学等众多应用领域。附加的工具箱( 单 独提供的专用m a t l a b 函数集) 扩展了m a t l a b 环境，以解决这些应用领域内 特定类型的问题。 本文而首先在m a t l a b 环境下实现了基本蚁群算法在求解t s p 问题上的应用， 以全国3 l 城市为例讨论了基本蚁群算法的参数选择对其性能的影响，以均匀设计 法设定蚁群算法参数。 在工程优化中，所遇到的大都是连续优化闯题，即函数优化问题。传统的优化 方法对于目标函数的要求条件较多：例如可微、可导、凸函数等。在实际的工程优 化问题中这些条件的要求就很苛刻了，而蚁群算法没有对于函数的上述要求，因此 蚁群算法在连续优化问题中的应用具有重要的研究价值。但是由于最初的蚁群算法 起源于离散型的网络路径问题，使得基本蚁群算法的一个缺点就是难以处理连续空 间的优化问题。由于每个蚂蚁在每个阶段所作的选择总是有限的，它要求离散的解 空间，因而它对组合优化等离散优化问题很适用，而对线性和非线性规划等连续空 间的优化问题的求解不能直接应用。若将优化性能良好的蚁群算法用于连续性空间 优化问题时，只能利用蚁群算法的原理和人对优化函数取得的有关先验知识来构造 相应的算法模型，并对算法中许多实施细节加以修正，从而确定在优化过程中蚁群 协同决策所选择的移动方向，由此来求得最优解。 本课题将在前人研究的基础上，对基于连续空间优化问题的蚁群算法提出改进 措施，建立一种用于一般函数优化的蚁群算法模型，并将此算法应用到一般连续函 数的优化中，并针对具体的热工控制系统的p i d 参数进行了优化，优化结果表明了 该改进算法在连续空间优化方面的可行性，而且表明优化效率和求解质量上都有所 提高。 华北电力大学硕士学位论文 第二章蚁群算法的基本原理及其特点 2 1 基本蚁群算法的原理 2 1 1 真实蚁群的行为描述【3 l 】 仿生学家长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放出 一种特殊的分泌物信息素来寻找路径。当它们碰到一个还没有走过的路口时， 就随机的选择一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径 越长，则释放的信息量越小，当后来的蚂蚁再次碰到这个路口的时候，选择信息量 较大路径的概率就比较大，这样便形成了一个正反馈机制。最优路径上的信息量越 来越大，而其它路径上的信息量却会随着时间的流逝而渐渐消减，最终整个蚁群会 找出最优路径。同时蚁群能够适应环境的变化，当蚁群的运动路径上突然出现障碍 物时，蚂蚁也能很快的重新找到最优路径。可见在整个寻优过程中，虽然单只蚂蚁 的选择能力有限，但是通过信息素的作用使整个蚁群行为具有非常高的自组织性， 蚂蚁之间交换着路径信息，最终通过蚁群的集体自催化行为找出最优路径。下面用 图例2 - 1 来形象的说明蚁群的搜索原理。 eee f fp ( a )( b ) ( c ) 图2 - 1 自然界中的蚂蚁觅食模拟 如图2 - 1 所示，设a 点是蚁巢，d 点是食物源，e f 为一障碍物。由于障碍物的 存在，蚂蚁只能由a 经e 或f 到达d ，或者由d 到达a ，各点之间的距离如图2 一l ( a ) 所示，假设每个时间单位由3 0 只蚂蚁由a 点到达d 点，有3 0 只蚂蚁由d 点 到达a 点，蚂蚁过后留下的信息量为l ，设信息素存留时间为1 。在初始时刻，由 于路径b f 、f c 、b e 、e c 上均无信息素存在，位于a 点和d 点的蚂蚁可以随机选择 路径，从统计学的角度可以认为蚂蚁以相同的概率选择路径b f 、f c 、b e 、e c ，如图 2 一l ( b ) 所示。经过一个时间单位以后在路径b f c 上的信息量是路径b e c 上信息量 6 华北电力大学硕士学位论文 的2 倍。又经过一段时间，将有2 0 只蚂蚁沿b 、f 和c 点到达d 点，如图2 - i ( c ) 所示。随着时间的推移，蚂蚁将会以越来越大的概率选择路径b f c ，最终将会完全 选择路径b f c ，从而找到由蚁巢到食物源的最短路径。 2 1 2 基本蚁群算法的机制原理【3 2 】 基本蚁群算法通过人工模拟蚂蚁搜索食物的过程中个体之间的信息交流与相 互协作，最终找到从蚁巢群到食物源的最短路径的原理从而解决了t s p 问题，取得 了很好的结果。这种优化过程的本质在于： ( 1 ) 选择机制，分泌物越多的路径，被选择的概率越大。 ( 2 ) 更新机制，路径上面的分泌物会随蚂蚁的经过而增长，而且同时也随时间 的推移逐渐挥发消失。 ( 3 ) 协调机制，蚂蚁之间实际上是通过分泌物来互相通信、协同工作的。 由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某 一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体之 间通过这种信息的交流寻求通向食物的最短路径。蚁群算法正是充分利用了这样的 优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强 的发现较优解的能力。 2 2 基本蚁群算法的数学模型及其实现 2 2 1 模型描述 为了便于理解，以求解平面上万个城市的t s p 问题为例来说明基本蚁群算法模型。 设b l ( t ) 表示t 时刻位于元素f 的蚂蚁数目，吒( f ) 为t 时刻路径( f ，j ) 上的信息量，n 表示城 市的数量，m 为蚁群中蚂蚁的总数目，nm = 包( f ) ；i = s c t ) lq ，勺cc ) 是f 时刻集合 c 中元素( 城市) 两两连接t ，上残留信息量的集合。在初始时刻各条路径上的信息量相 等，并设t ，( 0 ) = c o n s t 蚂蚁k ( k = l ，2 ，m ) 在运动过程中，根据各条路径上的信息量决定其转移方向。 这里用禁忌表t a b u 。( 七= 1 ，2 ，m ) 来记录蚂蚁k 当前所走过的城市，集合随着t a b u 。进 化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信 息来计算状态转移概率。露( f ) 表示在t 时刻蚂蚁k 由城市f 转移到城市的状态转移 概率 华北电力大学硕士学位论文 露( f ) =专篙融口一 。， 0 ， 否则 式中a l l o w e d , = c - t a b u 。) 表示蚂蚁k 下一步允许选择的城市；口为信息启发式因子， 表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起 的作用；为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程 中启发信息在蚂蚁选择路径中的受重视程度。，v ( t ) 为启发函数表示由城市礴专移到 城市，的期望程度，其表达式如下： 1 o ) = - 3 - ( 2 - 2 ) “， 式中以表示从城市f 到城市j 的距离。 毛= 厄i 再而 为了避免残留信息过多引起残留信息淹没启发信息，在每只蚂蚁走完一部或者 完成对所有刀个城市的遍历( 即一个循环结束) 后，要对残留信息进行更新处理。t + n 时刻在路径( f 歹) 的信息量可按如下规则进行调整 勺o + 以) = ( 1 一力宰勺( f ) + 乃( f ) ( 2 3 ) 勺( f ) = c ( f ) ( 2 4 ) 式中，p 表示信息素挥发系数，则l p 表示信息素残留因子为了防止信息的无限积 累，p 的取值范围为：p c 0 , 1 ) ；勺( f ) 表示本次循环中路径( f ，力上的信息素增量， 初始时刻a r o ( o ) = 0 ，苟( f ) 表示第k 只蚂蚁在本次循环中留在路径( f ，歹) _ l ：f f 3 信, g 且 里。 根据信息素更新策略的不同，d o r i g om a c r o 提出了三种不同的基本蚁群算法模 型，分别成为a n t c y c l e 模型、a n t q u a n t i t y 模型和a n t d e n s i t y 模型。其差别就在 芍( f ) 的求法不同。 在a n t - c y c l e 模型中 f ：( 力： 罢，若第七只蚂蚁在本次循环中经过( i j ) i o ，否则 式中q 表示信息素强度，它在一定程度上影响算法的收敛速度； ( 2 - 5 ) 厶表示第k 只蚂蚁 华北电力大学硕士学位论文 在a n t q u a n t i t y 模型中 f ： 昙，若第七只蚂蚁在痢f + 1 之间经过q j ， 。2 6 ， io ，否则 在a n t q u a n t i t y 模型中 = 侄嚣职蚂蚁租秕“之间经过q 。 ( 2 _ 7 ) 由于这三个模型中式( 2 - 6 ) 和( 2 - 7 ) 中利用的是局部信息，即蚂蚁完成一步 后更新路径上的信息素，而式( 2 - 5 ) 中利用的是整体信息，即蚂蚁完成一个循环 后更新所有路径上的信息素，在求解t s p 问题时性能较好，因此通常采用式( 2 - 5 ) 作为蚁群算法的基本模型。 2 2 2 基本蚁群算法的实现 从以上的蚁群算法基本模型可以看出，其寻找最优解的过程实际上是一个有限 的递推过程，因而适合也便于在计算机上实现，其实现步骤如下： ( 1 ) 初始化 设定算法迭代次数n c = o ，设置最大迭代次数c 觚，设置路径a ，力上的初始 信息量( 0 ) = c ( c y g 常数) ，露( 0 ) = o ，将魂只蚂蚁随机的放在万个城市，同时为每 只蚂蚁建立禁忌表纽帆，将初始节点置入禁忌表为参数口，厉p , q 设定初始值。 ( 2 ) 迭代过程 w h i l e 结束条件 f o ri = l ：1 1 1 ( 遍历所有城市) f o rk = l ：m( 对m 只蚂蚁循环) f o r j = l ：n ( 对刀个城市循环) 根据公式( 2 一1 ) 蚂蚁k 选择下一个城市j ，将蚂蚁k 移动到下 一个城市，将城市_ ，置入禁忌表t a b u k e n d e n d e n d 计算所有蚂蚁求得的回路距离，根据公式( 2 - 3 ) 、( 2 - 4 ) 和( 2 - 5 ) 更新路 径( f ，- ，) 上的信息素； n c = c + l e n d ( 3 ) 输出结果，结束计算 9 华北电力大学硕士学位论文 2 2 3 基本蚁群算法的程序结构流程图 以t s p 为例，基本蚁群算法的程序结构流程图如下： 图2 - 2 基本蚁群算法的程序结构流程 2 3 基本蚁群算法中参数对其陛能的影响及实验分析 从蚁群搜索最短路径的机理不难看到，算法中有关参数的不同选择对蚁群算法 的性能有至关重要的影响，因此很多学者对基本蚁群算法的参数进行了讨论。但其 选取的方法和原则，至今尚无严格的理论依据，通常都是根据经验而定。目前已经公 布的蚁群算法参数设置成果都是针对利用不同蚁群算法模型所解决的特定问题而 l o 华北电力大学硕士学位论文 言的，以应用最多的a n t c y c l e 模型为例，其最好的实验结果口幻为： o 口5 ；o 5 ；0 1 p o 9 9 ；1 0 q 1 0 0 0 。 这里我们将引进一种新的蚁群算法参数设置方法并稍作改进，通过一系列的对 比仿真实验研究，来探讨蚁群算法中参数的最佳设定原则，以利于蚁群算法在实际 中的应用和推广。 2 3 1 信息素挥发度对蚁群算法性能的影响 蚁群算法中的人工蚂蚁具有人类记忆功能，随着时间的推移，旧的信息将逐步 削弱，以前留下的信息将要逐渐消逝。在算法模型中用参数p 表示信息消逝程度( 或 称信息素挥发度) ，而1 一p 就是信息素残留系数。 信息素挥发度p 的大小直接关系到蚁群算法的全局搜索能力及其收敛速度；而 信息残留因子1 一p 反映了蚂蚁之间个体相互影响的强弱。由于信息素挥发度p 的存 在，当要处理的问题规模比较大时，会使那些从来未被搜索到的路径上的信息量减 小到接近于o ，因而降低了算法的全局搜索能力，而且当p 过大时，以前搜索过的 路径被再次选择的可能性过大，也会影响到算法的随机性和全局搜索能力；反之， 通过减小p 虽然可以提高算法的随机性和全局搜索能力，但又会使算法的收敛速度 降低。 蚁群算法中信息素挥发度p 对算法性能的影响，可以通过计算机仿真实验进行 分析。这里采用全国3 1 城市的t s p 问题作对比实验，3 l 城市坐标如下： 1 3 0 42 3 1 2 3 6 3 91 3 1 5 4 1 7 7 2 2 4 4 3 7 1 21 3 9 9 3 4 8 8 1 5 3 5 3 3 2 6 1 5 5 6 3 2 3 8 1 2 2 9 4 1 9 61 0 0 4 4 3 1 27 9 0 4 3 8 65 7 0 3 0 0 71 9 7 0 2 5 6 21 7 5 6 2 7 8 81 4 9 l 华北电力大学硕士学位论文 2 3 8 1 1 6 7 6 1 3 3 26 9 5 3 7 1 5 1 6 7 8 3 9 1 82 1 7 9 4 0 6 12 3 7 0 3 7 8 02 2 1 2 3 6 7 62 5 7 8 4 0 2 92 8 3 8 4 2 6 3 2 9 3 1 3 4 2 9 1 9 0 8 3 5 0 72 3 6 7 3 3 9 42 6 4 3 3 4 3 9 3 2 0 1 2 9 3 53 2 4 0 3 1 4 03 5 5 0 2 5 4 52 3 5 7 2 7 7 82 8 2 6 2 3 7 02 9 7 5 本仿真实验采用了蚁群算法中的全局搜索机制，即采用了a n t - c y c l e 模型。实 验时，设置蚂蚁数目m = 3 1 ，蚂蚁循环一周所释放的信息总量q = 1 0 0 ，启发式因子 a = l ，期望启发式因子p = 5 ，运算停止条件为最大循环次数为2 0 0 次，并使信息素 挥发度的变化为p e o 1 ，o 3 ，o 5 ，o 7 ，o 9 ，0 9 5 信息素挥发度对算法性能影响的有 关仿真结果如表2 - 1 所示： 表2 1 信息素挥发度p 对算法性能的影响 信息素挥发度p 最优路径长度搜索到最优值时循环次数 0 11 5 6 0 2 e + 0 0 48 7 0 3 1 5 6 0 2 e + 0 0 46 3 0 51 5 6 0 2 e + 0 0 4 3 8 0 71 5 7 1 7 e + 0 0 4 2 l 0 91 5 7 7 2 e + 0 0 41 4 0 9 5 1 5 8 0 0 e + 0 0 48 使用m a t l a b 对基本蚁群算法进行编程，当p 分别为0 1 ，0 3 ，0 5 ，0 7 ，0 9 ， o 9 5 时仿真实验的搜索路线图如图2 - 3 所示： 1 2 华北电力大学硕士学位论文 ( a ) p = o 1 ( b ) p = o 3 ( c ) p = o 5 1 3 华北电力大学硕士学位论文 ( e ) p - o 7 ( f ) p = o 9 鬻勰照甥熙黝弱臻蘸戮舅警参溺燃漂瓣嘲麓獭缓黼绷 鏊l 蘧 鬟 圈 成l 蔷t 铡 确 (a l 斑t 钰， 落 黪，6 盏 ；锈 谚 g 蠡 均 ，鞠 兹 6。 tc 正 ( g ) p = o 9 5 图2 3 信息素挥发度p 对算法性能的影响 1 4 华北电力大学硕士学位论文 由上述仿真结果可知，在其它初始化参数相同的情况下，信息素挥发度p 的大 小对蚁群算法的收敛性影响极大。p 越小，迭代次数n c 越大，这是由于，当l p 很 大时，由于路径上的残留信息占主导地位，信息正反馈的作用相对较弱，搜索的随 机性增强，而且存在于环境中的信息素保持时间较长，解空间对问题空间的反馈信 息较弱，因而蚁群算法收