（信号与信息处理专业论文）基于反序杂交算子的改进蚁群算法研究与实现.pdf

哈尔滨工稃大学硕士学位论文 摘要 作为群体智能的一种典型实例，蚁群算法受到越来越多的关注。它是继 模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索 算法以后的又一种应用于组合优化问题的启发式搜索算法。蚁群算法不仅能 够实现智能搜索、全局优化，而且具有稳健性( 鲁棒性) 、正反馈、分布式计 算、易与其它算法结合等特点。因此，蚁群算法已成为当前群智能领域中最 令人感兴趣的研究课题之一。 目前蚁群算法的研究尚未成熟，作为一种新兴的智能优化算法，它存在 算法自身求解速度缓慢、容易陷入局部最优等缺点。针对这些缺点，本文对 蚁群算法基本理论进行了深入分析，对蚁群算法近年来的研究进展进行了归 纳总结，并对不足之处进行了深入的分析。通过实验验证蚁群算法的各个参 数对算法性能的影响，给出了蚁群算法中各参数的理想取值。 在深入研究目前各种蚁群算法的改进模型基础上提出了一种基于反序 杂交算子的改进蚁群算法。利用反序一杂交算子在产生后代时能跳离局部最优 值，并且使算法具有自适应性的优点对蚁群算法进行了有效改进，增加了局 部解的个数，从而扩大了最优解的选择范围。实验结果表明，本文提出的改 进算法，加速了最优解的收敛速度，改善了最优解的质量，从而大大提高了 蚁群算法的性能。 关键词：蚁群算法；反序杂交算子；优化；参数分析 哈尔滨工程大学硕士学位论文 a b s t r a c t a sa t y p i c a lp a r a d i g mo fs w a r mi n t e l l i g e n c e ，a n tc o l o n ya l g o r i t h mh a db e e n p a i dm o r ea n dm o r ea t t e n t i o n i ti sa n o t h e rh e u r i s t i cs e a r c ha l g o r i t h ma p p l i e di n c o m b i n a t i o n a lo p t i m i z e dp r o b l e ma f t e rs i m u l a t e da n n e a l i n ga l g o r i t h m , g e n e t i c a l g o r i t h m , t a b o os e a r c ha l g o r i t h m , a n na n ds o o n n o to n l yc a r ta n tc o l o n y a l g o r i t h m ( a c o ) r e a l i z ei n t e l l i g e n ts e a r c h , i n t e l l i g e n to p t i m i z e ，b u ta l s oh a sm a n y c h a r a c t e r i s t i c ss u c ha sr o b u s t n e s s , p o s i t i v ef e e d b a c k , d i s t r i b u t ec o m p u t i n g , e a s i l y c o m b i n e dw i t ho t h e ra l g o r i t h m sa n ds of o r t h s oi th a sb e e n0 1 1 eo ft h em o s t a t t r a c t i v er e s e a r c h i n gs u b j e c ti nt h ef i e l do f s w a mi n t e l l i g e n c e a san e wi n t e l l i g e n ta l g o r i t h mf o ro p t i m i z a t i o np r o b l e m , i th a ss o m e d i s a d v a n t a g e s , s u c ha s , i tg e t ss o l u t i o ns l o w l y , a n dg e t si n t ol o c a lo p t i m i z a t i o n e a s i l y a c c o r d i n gt ot h e s ep r o b l e m s ，t h eb a s i ct h e o r yo f a c oi sa n a l y z e dd e e p l y i nt h et h e s i s r $ 1 1 m m a r i z c st h er e s e a r c hd e v e l o p m e n to fa c 0 a n dt h e d i s a d v a n t a g e so fa c o a r ea n a l y z e d t h ee f f e c to fp a r a m e t e r so nt h ep e r f o r m a n c e o fa c oi sv a l i d a t e db ye x p e r i m e n t s t h ep e r f e c tv a l u eo fp a r a m e t e r sa r eg i v e n 蜘t h o r o u g hr e s e a r c ho ft h ep r e s e n ti m p r o v e dm o d e lo fa c o ，i tb r i n g s f o r w a r d sa ni m p r o v e da c ob a s e d0 1 1i n v e r - o v e ro 讲粕r i tc a nj u m po u tt h e l o c a lo p t i m i z a t i o nb yt h ei n v e r - o v e ro p e r a t o ra n dm a k ei t s e l fb ea d a p t i v e s oi t c a ni n c r e a s et h en u m b e ro fl o c a ls o l u t i o n sa n de n l a r g et h er a n g eo ft h eo p t i m u m s o l u t i o n t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h ma c c e l e r a t e st h e c o n v e r g e n c es p e e do ft h eo p t i m u ms o l u t i o na n di m p r o v e st h eq u a l i t yo ft h e o p t i m u m s o l u t i o n s oi tl a r g e l ye n h a n c e st h ec a p a b i l i t yo f a c o k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；i n v e r - o v e ro p e r a t o r ；o p t i m i z a t i o n ；p a r m n e t e = r a n a l y s i s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：蔓查堕 日期：砷年3 月f d 日 哈尔滨工程大学硕士学位论文 1 1 课题的目的及意义 第1 章绪论 动物界的智能行为一直是科学家灵感的源泉。近年来，群居的昆虫表现 出来的集体智慧吸引了研究者的注意。蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n , a c o ) 就是利用群集智能解决组合优化问题的典型例子。它是由意大利学者 m d o r i g o ，v m a n i e z z o ，a c o l o m i 等人在2 0 世纪9 0 年代初首先提出来的。 它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发 式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。蚁群算法 不仅能够智能搜索、全局优化，而且具有稳健性( 鲁棒性) ，正反馈、分布式 计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分 布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利 于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合， 可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修 改，便可用于其它问题。因此，蚁群算法的问世为诸多领域解决复杂优化问 题提供了有力的工具。但是，蚁群算法的发展历史只有l o 年左右，还不像其 它的启发式算法那样己形成系统的分析方法和具有坚实的数学基础。目前参 数的选择更多的是依靠实验和经验，没有定理来确定。而且它的计算时间偏 长，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看， 这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景，更多深入 细致的工作还有待于进一步展开。 本课题属于基础理论研究，旨在对蚁群算法近年来的研究进展进行总结， 归纳算法的成功应用领域和存在的不足，并对不足之处进行深入理论分析， 目的在于提高蚁群算法的总体性能。目前对蚁群算法的研究，不仅有算法意 义上的研究，还有应用模型的研究，并且不断有学者提出对蚁群算法的改进 方案：有的将蚁群算法与遗传算法相结合，有的给蚁群系统加入变异特征， 哈尔溟工程大学硕士学位论文 还有的提出所谓最大最小蚁群算法( m m a s ) 。本课题提出了一种高效的、全 局收敛的改进蚁群算法基于反序杂交算子的改进蚁群算法。 1 2 国内外研究现状 目前蚁群算法的研究学者主要集中在比利时、意大利、德国等国家，美 国和日本在近几年也开始了对蚁群算法的研究。国内的研究始于1 9 9 8 年末， 主要在上海、北京等少数几个大学和研究所开展了此项工作，主要围绕t s p 及相关问题的实验仿真，少数涉及通信网络的路由选择、负载平衡、电力系 统的故障检测以及蚁群算法在连续系统的应用，如函数逼近等方面应用的尝 试。在国外，蚁群算法已经在集成电路布线、网络路由选择、机器人线路规 划等方面得到了应用。 蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合 优化问题提供了新思路，并很快被应用到其它组合优化问题中。如二次规划 闯j 题( q u a d r a t i ca s s i g n m e n tp r o b l e m , q a p ) 彩1 、网络路由化( n e t w o r k s r o u t i n go p t i m i z a t i o n ) 摊3 9 1 、机器人路径规划删、作业流程规划、图着色( g r a p h c o l o r i n g ) 等问题。 自从d o r i g o 等提出第一个a c o 算法，即a s ( a n ts y s t e m ) 算法( d o d g o ， m a n i e z z o & c o l o m i ，1 9 9 1 ，1 9 9 6 ) 后，许多学者对如何改进基本a c o 算法进行了 大量的研究。最早提出的是具有精英策略的a s 抛( b u l l n h e i m e re ta 1 1 9 9 9 ) ， 即蚁群在每次环游之后，除了正常的信息素更新，还在该次环游中产生的最 优路径上增加额外的信息素，使得算法的收敛速度大大加快。之后提出了引 入了q 学习机制的a n t - q ( g a m b a r d e l l a l m & m d o r i g o ，1 9 9 5 ，d o r i g o m & l m g a m b a r d e l l a , 1 9 9 6 ) ，蚁群每次环游时都让信息量最大的路径以较大 的概率被选中，以充分利用学习机制，强化最优信息的反馈。 随后又提出了几种比较成功的扩展算法：基于蚂蚁等级的彳s 。 ( b u l l n h c i m e r e t a 1 1 9 9 9 ) ，采用伪随机比例规则的a c s ( d o r i g o m & l m g a m b a r d e l l a 。1 9 9 7 a ，d o r i g om & l m g a m b a r d e l l a , 1 9 9 t 0 ) ，将信息 2 哈尔滨t 程大学硕士学位论文 限制在一定的范围内并使用了信息素平滑机制的最大最小蚁群算法m m a s 等。此外，国内的学者就提高a c o 算法韵性能也做了大量有益的工作，如： 张纪会等提出了自适应的蚁群算法，采用确定性选择和随机选择相结合的策 略，在搜索的过程中动态地调整选择的概率，实现了选择概率的自适应，提 高了算法的收敛速度和性能；覃刚力和杨家本提出了一种基于自适应调整信 息素的改进蚁群算法，该算法根据人工蚂蚁所获得解的情况，动态地调整路 径上的信息素，使算法跳离局部最小；谢剑英和王颖通过自适应地改变算法 的挥发度等系数以克服例如蚁群算法易陷局部最小的缺陷，并能够在保证收 敛速度的前提下提高算法解的全局最佳性；吴斌和史忠植首先在蚁群算法的 基础上提出了相遇算法，提高了蚁群算法蚂蚁一次周游的解的质量；陈峻、 沈洁和秦岭等提出基于分布均匀度的自适应蚁群算法，该算法根据优化过程 中解的分布均匀度，自适应地调整路径选择概率的确定策略和信息量更新策 略；朱庆保和杨志军提出基于变异和动态信息素更新的蚁群优化算法，它针 对t s p 问题提出了三种策略：最近节点选择策略、信息素动态更新策略和最 优个体变异策略，大大提高了a c o 算法求解t s p 问题的能力。 自1 9 9 8 年，第一届蚁群优化国际研讨会召开以来，已经召开了三届，大 大推动了蚁群算法的发展。蚁群算法已经引起越来越多的关注，尽管它还缺 乏完善的理论分析，其有效性也没有给出严格的数学解释，一但回顾模糊控制 的发展历史，理论的不完善并不妨碍应用，有时应用是超前于理论的，并推 动理论的研究，可以说蚁群算法必将得到广泛的应用。 1 3 课题研究内容及论文安排 本课题属于基础理论研究，旨在对蚁群算法近年来的研究发展进行总结， 归纳算法的成功应用领域和存在的不足，并对不足之处进行深入理论分析， 目的在于提高蚁群算法的总体性能。针对目前蚁群算法研究进展及其存在的 缺点，本课题提出一种高效变化算子一反序杂交算子对蚁群算法本次循环的 最优、次优解进行反序、杂交，在产生后代时可以提高解的多样性，并能跳 哈尔滨工程大学硕士学位论文 离局部最优，让算法快速达到全局收敛。本文的具体内容安排如下： 第1 章为绪论。首先介绍了蚁群算法的研究目的、意义及目前国内外发 展现状，最后给出了本文的主要工作和内容安排。 第2 章为蚁群算法的基本理论及应用。详细介绍了蚁群算法的基本内容， 包括蚁群算法的基本原理、算法模型、蚁群系统，并指出该算法的优缺点， 分析了各参数对蚁群算法性能的影响，以及目前蚁群算法在各个领域的应用 情况。 第3 章详尽描述了现阶段蚁群优化算法的改进状况，并介绍了当前蚁群 算法的改进实例，包括蚁群系统的扩展( e a s 、r a s 、m m a s ) 、具有变异特 征的蚁群算法、引入知识的改进蚁群算法、基于蚁群算法的分段求解算法， 还有改进的增强型蚁群算法、基于生物免疫遗传学的蚁群算法以及其他一些 小改进的蚁群算法。分析目前各种改进算法的性能优劣，提出本文的改进算 法。 第4 章对改进蚁群算法引入反序杂交算子的缘由进行了说明，对该算子 的基本原理、算法流程作了详细介绍，并对蚁群算法的改进方法作了分析， 给出了改进蚁群算法的原理框图，最后对改进蚁群算法的参数进行了理论分 析。 第5 章针对本文提出的改进蚁群算法进行了实验仿真，在不同参数条件 下，对该算法的性能进行了比较，确定参数最佳取值；并且跟基本蚁群算法 和带杂交算子的蚁群算法就相同条件的几个复杂度不同t s p 问题进行了比 较，来说明该算法性能。 最后全文总结归纳了作者一年来在蚁群算法研究上所作的工作，并对蚁 群算法的未来发展进行了展望。 4 哈尔滨工程大学硕士学位论文 第2 章蚁群算法基本理论及应用 自2 0 世纪8 0 年代以来，人们提出了一类模拟大自然的元启发式算法； 智能型全局优化方法。元启发式算法通过模拟或揭示某些自然现象或过程而 得到发展，其思想涉及数学、物理学、生物进化、人工智能等方面，为解决 复杂问题提供了新的思想和手段。由于元启发式算法本身是一个优化系统， 具有自适应性，所以对于有多个局部最优解的问题，不会陷入局部优化。 t a i l l a r de d 等人提出了元启发式算法的统一概念。目前研究较多的元启发式 算法有蚁群算法( a c 0 ) 、模拟退火法( s a ) 、遗传算法( g a ) 、禁忌搜索法( t s ) 等。其中蚁群算法是最近l o 年发展起来的一种新型的元启发式方法，并迅速 得到广大科技人员的研究与应用，且己取得令人鼓舞的成果。 第2 章主要蚁群算法的基本理论及应用。详细介绍了蚁群算法的基本内 容，包括蚁群算法的基本原理、算法模型、蚁群系统，并指出该算法的优缺 点，分析了各参数对蚁群算法性能的影响，以及目前蚁群算法在各个领域的 应用情况。 2 1 蚁群算法基本原理 现实生活中单个蚂蚁的能力和智力非常简单，但它们通过相互协调、分 工、合作完成不论工蚁还是蚁后都不可能有足够的能力来指挥完成筑巢、觅 食、迁徙、清扫蚁穴等复杂行为，比如在蚂蚁觅食过程中能够通过相互协作 找到食物源和巢穴间的最短路径。像蚂蚁这样的群居昆虫，虽然没有视觉， 却能找到由蚁巢到食物源的最短路径，原因是什么呢? 蚂蚁群体不仅能够完成复杂的任务，还能够适应环境的变化。如：在蚁 群运动路线上突然出现障碍物时，一开始各个蚂蚁分布是均匀的，不管路径 是否区分长短，蚂蚁总是先按同等概率选择各条路径。 但经过一段时间后蚂蚁能够很快的重新找到最优路径，蚁群是如何完成 j 哈尔滨1 = 程大学硕士学位论文 这些复杂任务的呢? 所有这些问题j 很早就激起了生物学家和仿生学家的强 烈兴趣，仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称 为外激素( p h e r o m o n e ) 的物质进行信息传递，从而能相互协作完成复杂的任 务。蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起 着重要的作用。 蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁 在运动过程中能够感知这种物质的存在及强度，并以此指导自己的运动方向， 蚂蚁倾向于朝着该物质强度高的方向移动。如果路径上出现障碍物时，相等 时间内较短的路径上信息量就遗留得比较多，选择较短路径的蚂蚁也随着增 多。 图2 1 所示的就是蚁群的搜索原理，蚂蚁选择路径的方法与上述过程基 本一致。从蚁巢出发的蚂蚁中，经过较短路径的蚂蚁将较早地到达食物源， 并较早地回到蚁巢，那么较短路径上的信息素就在较短的时间内得到了加强， 这样就会导致更多的蚂蚁选择较短的路径。 食物 4 m i l l 8 i i h n 图2 1 蚂蚁路径搜索原理 上述情况中都没有考虑信息素的构成、放置和挥发。在自然环境下的实 际信息素遗留方式是多种多样的。研究人员只是通过试验获取了一些基本的 信息素特性，如：蒸发率、吸收率、扩散常数等。研究证明，信息素能够在 6 哈尔滨工程大学硕士学位论文 路径上保持很长的时间( 从几个小时到数个月) ，它与蚂蚁的种类、种群规律 和环境条件有着密切的联系。 研究者在蚂蚁优化算法中引用了信息素挥发的特征，其目的是避免搜索 陷入局部最优。图2 2 进一步说明了蚂蚁群体的路径搜索原理和机制。 夺，夺瓷 图2 2 蚁群算法原理示意图 假设蚂蚁在食物源4 和巢穴e 之间运动，每单位时间内前进单位距离，且每 单位时间内各有3 0 只蚂蚁从彳和e 出发。图中a b d e 不是通路，只有a f e 和 a c e 两条可选择路径，距离分别为4 和3 。假设在t = 0 时刻各有3 0 只蚂蚁 在d 点和0 点，由于没有任何遗留的信息素供参考，所以他们随机选择( 概 率相等) 一条路径前进，即在b 和d 点各有1 5 只向c 和f 移动。此时b c d 上 的信息素浓度是b f d 上信息素浓度的两倍，因为在单位时间内有3 0 只蚂蚁 经过此路径( 1 5 只由曰到d ，1 5 只由d 到b ) ，而相同时间内，较长的路径 上只有1 5 只蚂蚁由b ( 或d ) 到达了，到了t = l 时，在b 和d 下一批3 0 只蚂蚁又开始选路，这时它们依据不同路径的信息素浓度进行判断，口点2 0 只蚂蚁选择b c d ，1 0 只选择b f d ( 相对的d 点2 0 只选择d c b ，1 0 只选择 d f b ) ，这样一来，较短路径上的信息素变得更浓。整个选路过程如此往复， 即实现了随机选择到自适应行为的过程。 不难看出，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈 现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂 7 哈尔滨t 程大学硕士学位论文 蚁个体之间就是通过这种信息的交流来搜索食物，并最终沿着最短路径行进。 人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的 方法提出的，即让人工蚂蚁根据路径上的相当于外激素的数字信息量的强度 选择路径，并在所经过的路径上留下相当于外激素的数字信息量，然后随着 时间的推移，最优路径上的数字信息量将积累的越来越大，从而被选择的概 率也越来越大，最终所有人工蚂蚁将趋向于选择该路径。这种模拟蚁群搜索 食物的过程与著名的旅行商问题非常相似，因而最初人工蚁群算法被提出用 于求解旅行商问题。真实蚂蚁觅食行为与优化问题求解过程的相似性的比较 如表2 1 所示。 表2 1 蚂蚁觅食行为与优化问题的对照 优化问题蚂蚁觅食问题 各个状态 解 最优解 各状态的吸引度 状态更新 目标函数 要环游的各个城市 蚂蚁的环游 最短环游 信息素的数量 信息素更新 路径长度 可见，人工蚁群算法是一种随机搜索算法，与其他模拟进化算法一样， 通过侯选解组成的群体的进化过程来寻求最优解，该过程包含两个基本阶段： 适应阶段和协作阶段。在适应阶段，各侯选解根据积累的信息不断调整自身 结构；在协作阶段，侯选解之间通过信息交流，以期望产生性能更好的解。 2 2 蚁群算法数学模型 2 2 1 旅行商问题 l 、t s p 问题描述 给定n 个城市和两城市之间的距离，要求确定一条经过每一个城市且每 8 哈尔滨下程大学硕士学位论文 个城市只经过一次的最短路线。也可以用图论表示：c r - - - - ( c ，l ) ，c 是顶点集 ( 每个城市为一个顶点) ，l 为各顶点的连线。每段弧长表示顶点i 和顶点j 间的距离，记为d e ，( f 力c 。t s p 也就是寻找一条最短的哈密顿回路，即 遍历所有顶点当且仅当一次的最短回路。这里假设吒= d 。 2 、t s p 问题重要性 t s p 问题在蚁群算法中扮演着重要角色，因为第一个蚁群算法蚂蚁 系统( a s ) ，以及后来相继出现的蚁群算法一开始大都是应用在t s p 问题上。 选择t s p 问题主要有以下几个原因： ( 1 ) t s p 问题与真实蚂蚁路径的相似性； ( 2 ) t s p 问题是一个n p h a r d 优化问题； ( 3 ) 对于一个新的算法，t s p 问题是一个标准测试问题，如果t s p 的测 试结果好，那就为此算法的使用性提供了很好的证据； ( 4 ) t s p 问题很容易理解，因此算法的编码不会有很多的技术和专业难 度。 2 2 2 蚁群算法数学模型 t s p 的目的是寻求一条连接聆个指定城市的单向最短闭合路径，每个城 市都要经过，但每个城市只可经过一次。假设城市j 和，之间的距离为巩， 可将问题定义在e u c l i d e a n 空间，则有： 吒= ( 一x j ) 2 + ( j ，。一y j ) 2 ( 2 1 ) 其中o ，一) 为空间坐标。城市分布也可表示为图的形式( ，) ，其中 为城市节点，e 为连接不同城市的边。由各个城市间距离构成的矩阵并不一 定是对称的。但是城市间距离的对称或不对称对蚁群算法的求解方式没有太 大影响。 在蚂蚁系统中，蚂蚁由一个城市运动到另一个城市，逐步完成它们的搜 索过程。在算法迭代过程中，每只蚂蚁k ( k = 1 , 2 ，f t ) 根据概率转换规则生 9 成一个有步过程的行动路线。整个算法的迭代过程以r 为刻度，1 s f f 。， 其中f 一是预先设定的算法最大迭代次数。 在第t 次迭代时，每只蚂蚁由城市i 转到城市，所需要的条件如下： l 、每只蚂蚁都只有一个记忆空间，或者称为禁忌列表( t a b ul i s t ) 。在一个 完整的行程中，该列表内容是逐渐增加的。该表是用来表示第k 只蚂蚁已经 访问的城市集，它存储了直至时刻t 的所有已访问城市，并禁忌蚂蚁在一 次迭代( 一个周期) 结束之前再访问它们，利用该表可避免第k 只蚂蚁重复访 问同一个城市。 2 、能见度( v i s i b i l i t y ) ，其定义为距离的倒数t 。= 1 屯。能见度是以本地 信息为基础的，代表了由城市i 到_ ，的启发性愿望( h e u r i s t i cd e s i r a b i l i t y ) ，被用 来引导蚂蚁的搜索。这种信息是静态的，在问题求解过程中不发生变化。 一3 、城市f 到_ ，路径上遗留的虚拟信息素( v i r t u a lp h e r o m o n et r a i l ) r “。该参 数是实时在线更新的，并且代表了由城市i 到，的获知性愿望( 1 e a r n e d d e s i r a b i l i t y ) 。与能见度相反，虚拟信息素是一种动态的全局信息，它反映了 蚂蚁在问题解决过程中的经验积累。 蚂蚁选择由城市f 到，的路径时所依据的转换规则如下式： f 鼻掣盘如果剧 p 却： 哥册燃 ( 2 2 ) “。 1 0 如果j r 式中钟是用来表示第k 只蚂蚁已经访问的城市集，口和是两个可以调整的 参数，用于控制信息素和能见度的相对权值。如果口= 0 ，则最近的城市容易 被选择，就有些类似经典的随机贪婪算法。如果= 0 ，则只有信息素放大 机制在独自工作，这将导致算法迅速获得一个可能是非最优的解。因此在信 息素浓度和能见度之间确定一种折衷关系是非常必要的。值得注意的是，尽 管在一次迭代过程中。公式( 2 - 2 ) 保持不变，但是处在同一城市的两只蚂蚁所 得到的钟( r ) 可能是不同的。因为，露( r ) 是的函数。 l o 哈尔滨工程大学硕士学位论文 一次移动结束后，每只蚂蚁k 在路径( 切上留下一定的信息素f ：o ) 。在 第t 次迭代时( 当所有的蚂蚁移动一次后，迭代次数计数器加1 ) ，f ：( f ) 的 计算方式如下： 咄，= q 。l * o ) ，黝：鬻 ， 其中，t ( f ) 是第k 只蚂蚁在第t 次迭代经过的路径，r ( f ) 是该路径的长 度，q 是一个预置参数。 这种没有信息素挥发的路径搜索方式并不能获得理想的效果。它很可能 导致初始化随机波动的进一步放大，从而得到一个非最优解。为了保证对解 空间的充分搜索，有必要引入信息素挥发机制，否则所有的蚂蚁都可能停滞 于相同的路径。在算法设计中，通过引入信息素挥发系数从0 p q o 时，a c s 与a s 的转换规则是一致的。当q q o 时，其转换规则就来源 于与问题相关的知识，也就是关于城市间距离的启发性知识和存储器中以信 息素形式存在的获得性知识。通过调整吼来影响搜索能够使系统集中于最好 的解，而不是持续的搜索下去。这种调整类似于模拟退火算法中对温度的调 整：当吼接近于l 时，只有本地的优化解被选择，但这并不能保证全局最优 解的获得；反之，当日。接近于0 时，所有的局部解都要被检测，但是其中的 局部最优解将被分配一个大的权值( 这是与模拟退火不同的，a s 中所有的状 态在较高温度下都具备同样的权值) 。按照这种方法，就可以在系统初始化阶 段在 o ，1 1 之间逐步调整吼，从而提高系统在初始化阶段的探索能力，为后续 的搜索奠定基础。 信息素更新规则：在a s 系统中，所有的蚂蚁都在经过的路径上留下信 息素，而在a c s 系统中，只有在路径搜索开始以后获得最好路径的蚂蚁才能 全局更新最好路径分支上的信息素。这样有利于诱使更多的蚂蚁搜索已发现 最好路径周围的路径，也就是增强了系统搜索的导向性。另一个与a s 系统 不同之处是，a c s 只更新属于最好路径的各条边的信息素浓度。更新规则如 下： ( f ) = ( 1 一p ) f 。( f ) + p f “( f ) ( 2 9 ) 其中( f ，- ，) 是属于t + 的边。f i ( f ) = l r 。如此，最好解得到了局部增强。 为了发现其它的解，还必须进行局部的信息素更新。 信息素的局部更新：当蚂蚁七选择由城市f 运动到j 0 时，( f ，力上的 信息素按如下公式更新： t v ( t ) = ( 1 一力f f ，( f ) + p o ( 2 一l o ) f o 和a s 中的信息素初始化值类似，其设置是通过试验方法确定的， f o = 伪。) ，其中甩是城市的数量，三。是利用最近邻启发式算法获得的最 短路径长度。 当一只蚂蚁经过一条边时，信息素的局部更新使该边上的信息素减少。 哈尔滨工程大学硕士学位论文 这样可使已经被很多蚂蚁经过的路径的吸引力逐步减弱，从而间接地促进蚂 蚁探索那些仍未被访问过的边。这样操作的一个结果就是，蚂蚁们不会集中 收敛于单一路径。通过实验也已证实，这种方法的优点是有利于发现更多的 潜在最优解，从而提高算法的搜索质量。如果没有局部更新过程，所有蚂蚁 都可能陷入一个范围非常窄小的搜索空间。 候选列表：为了解决大规模t s p 的求解问题，a c s 设计了一种数据结构。 候选列表就是距离城市f 最近的若干城市组成的列表。每次进行城市选择时， 蚂蚁首先检测候选列表中没有访问过的城市，只有当候选列表中的城市全部 访问过之后才考虑其它城市。候选列表中包含的城市数用d 表示，并按照距 离升序排列。在运算过程中，按照串行序列扫描候选列表。在a c s - t s p 中， 蚂蚁k 要选择下一个目标城市时，首先搜索当前城市的候选列表，如果其中 存在未访问城市，则按照公式( 2 - 7 ) 和( 2 8 ) 处理。否则，选择列表之外未访问 的最近城市，。 a c s t s p 算法的伪代码描述如下： 严初始化+ ， = 2 ；p - - o 1 ；历= 1 0 ；f o = ( n 工。) 。；q o = o 9 ； c l = 1 5 f o r 每条边u ，j ) d o f ( 0 ) = f o e n d f o r f o r k = lt o 埘d o 将蚂蚁k 分配到随机选择的城市 e n d f o r t + = 算法执行过程中所得到的最短路径变量： r = 算法执行过程中所得到的最短路径的长度变量； 程序主循环 f o r t = l t of d o f o r k = - lt o 珊d o 1 7 执行加1 次如下计算，构造七条途径t o ) ： i f 候选列表中存在至少一个城市jt h , n 根据如下公式从候选列表中选择下个城市_ ，jer ， ，= j g 吗知心矿忉“般 其中，0 是按照下式确定的概率随机选择的城市： 加) = 踹 选择最近的城市d 每次转换之后，蚂蚁k 进行局部信息素更新： f f ( f ) = ( 1 一力7 f ( ，) + p 如 计算蚂蚁k 在当前所经过的路径t + ( ，) 和其长度r ( ，) f f 发现一条更好的路径t h e n 更新丁+ 和r f o r 每条路径( f ，j ) e t + d o 按照如下公式更新各路径上的信息素 勺( ，) = ( 1 一力( o + p 。勺( r ) ，其中a r ，( f ) = l l * ； f o r 每条路径以力d o 勺( ，+ 1 ) = 勺( ，) 1 8 哈尔滨工程大学硕士学位论文 e n d f o r e n d f o r 输出最短路径r 和r ； 研究人员利用a c s - t s p 进行了各种规模t s p 的求解，并与其它的一些 典型算法，如e l a s t i cn e t ( e n ) 算法、s d f - o r g a n i z i n gm a p s ( s o m ) 、s a 、g a 和 e v o l u t i o n a r yp r o g r a m m i n g ( e p ) 进行了比较分析。其中采用的是随机生成的5 0 城市的对称t s p ，a c s - t s p 设计了1 0 只蚂蚁，2 5 0 0 次迭代，运行2 5 遍，取 最优行程长度的平均值。对比试验结果证明，在大多数问题中a c s - t s p 都获 得了最好解。 蚁群算法是一种有效的随机搜索算法，具有如下优点： 1 、蚁群算法本质上是一种分布式并行算法。单个蚂蚁的搜索过程是彼此 独立的，容易陷入局部最优。但通过个体之间不断的信息交流和传递有利于 发现较好解。 2 、蚁群算法是一种正反馈算法。路径上的信息素水平较高，将吸引更多 的蚂蚁沿这条路径运动，这又使得其信息素水平增加，这样就加快了算法的 进化过程。 3 、蚁群算法具有较强的鲁棒性。只要对其模型稍加修改，便可以应用于 其它问题。 4 、易于与其它方法结合。蚁群算法很容易与其它启发式算法相结合，以 改善算法的性能。 同时，经过研究发现，最初的蚁群系统在求解t s p 问题时也常常存在以 下问题： l 、容易产生局部最优解，即当搜索一段时间后，由于算法的全局搜索能 力不足，蚂蚁个体发现的解基本一致，算法出现停滞现象，在还没有找到全 局最优解时就收敛。 一 2 ，搜索时间过长，结果常常在局部最优解与全局最优解之间反复。 针对上述蚁群算法的优缺点，下面对蚁群算法的各参数进行了详细分析， 1 9 哈尔滨工程大学硕士学位论文 以便更好的利用其优点，克服其缺点，提高算法的执行效率。 2 4 蚁群算法的参数分析 蚁群算法是一种新颖的仿生进化算法，这一性质决定了蚁群算法的参数 选择对求解结果的优劣有很大地影响，因而有必要讨论一下各个参数地选择， 以便给具体问题的算法模型的设计者提供一个帮助。在人工蚂蚁系统中，影 响求解结果的参数主要包括以下几个；l 、信息激素的启发因子口和自启发量 因子；2 、常数q 。；3 ，信息激素挥发系数p ；4 、蚂蚁群体中蚂蚁的数量r a t 5 、总信息量q 。 2 4 1 启发因子a 和b 的分析 首先，根据蚁群算法的抽象过程和前文的论述可以看出，在蚂蚁构造解 的过程中既利用了信息激素f 也跟反映了问题空闻本身特征信息的自启发 量r 。相关，而信息激素启发因子口和自启发量启发因子则分别代表这两个 信息在算法执行过程中各自的相对重要性。参数口反映了人工蚂蚁在运动过 程中所积累的信息激素( 即残留信息激素“) 在指导蚁群搜索中的相对重要 程度，参数则反映了人工蚂蚁在运动过程中自启发量巩在指导蚁群搜索中 的相对重要程度。参数口的大小反映了蚁群在路径搜索中随机性因素作用的 强度，其值越大，蚂蚁在以后的循环中选择之前循环走过的路径的可能性越 大，搜索的随机性减弱，并且口值过大还会导致蚁群的搜索过早陷于局部最 优解( “停滞”现象) ；参数的大小反映了蚁群在路径搜索中先验性，确定 性因素作用的强度，其值越大，蚂蚁在某个局部点上选择局部最短路径的可 能性越大，虽然搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中 随机性减弱，易于陷入局部最优。 其次，蚁群算法的全局寻优性能，首先要求蚁群的搜索过程必须有很强 的随机性；而蚁群算法的快速收敛性能，又要求蚁群的搜索过程必须要有较 高的确定性。因此，两者对蚁群算法性能的影响和作用是相互配合、密切相 2 0 哈尔滨工程大学硕士学位论文 关的，算法要获得优化解就必须在这二者之间选取一个平衡，在蚁群算法中 具体体现为对参数口和的选择。 在本章公式( 2 - 2 ) 和( 2 7 ) 中出现的参数口和分别代表信息激素浓度权重 和自启发因子权重。 若口= 0 ，公式( 2 2 ) 和( 2 - 7 ) m 化为： 拼( f ) = 慧 t j t ( 2 - 1 1 ) 鼍j t j t f - a r gm a ) 【矿跣】p ，翻 q o ( 2 - t 2 ) 。 i，否则 从公式( 2 1 1 ) 和( 2 - 1 2 ) 可以看出，实际上，当算法中不考虑信息激素的影 响时( 即口= 0 时) ，算法就是一个完全的启发式搜索，用到的启发量是问题空 间本身的特征信息自启发量巩。特别的当不用这个自启发量时( 即 o r = o ，= 0 时) ，算法进一步退化为一个完全随机搜索算法，求解结果的不 同只是因为数值试验的随机性影响。 信息激素启发因子口对算法性能的影响，可以通过计算机仿真实验来分 析。以中国3 1 个城市问题作为例子作仿真实验，实验中有关算法参数取为： 蚂蚁数量m = 3 1 ，自启发量因子= 2 ，信息激素挥发系数p = 0 8 ，蚂蚁遍历 一次后所释放的总信息量o = 1 0 0 ，并使信息激素启发因子的取值为 岱 o a i ，有关结果如表2 3 所示。 表2 3 信息激素启发因子口对算法性能的影响 信息激素启发因子口最好路径长度循环次数 o1 5 8 5 2 1 0 1 11 5 5 0 4 5 6 2 l ，一 堕沙仉 哈尔滨工程大学硕士学位论文 巅 嚣 赡 姆 。 ，f 一 图2 3 信息激素启发因子口对算法性能的影响 对比表2 3 中第二行和第三行的数据，不难看出，用到了反馈信息( 即 口0 时) 的蚁群算法和没有用到反馈信息( 即口= 0 时) 的启发式算法相比，在 其他条件完全相同的情况下，得到的结果总是更好一些。由于二者的