（计算机应用技术专业论文）面向web+services应用集成蚁群优化算法的研究.pdf

摘要 随着w e bs e r v i c e s 技术的提出，将软件作为服务的理念也逐渐深入人心。 w e b 服务具有良好的开放性、互操作性、语言和平台的无关性等优点，使其成为 解决异构系统集成的首选。 现有的w e b 服务应用集成采取被动的交互模式，w e b 服务通过接口中定义的 操作来显示激活。如果w e b 服务是自治的且仅支持暂时合作，这种被动方式就有 很大局限性：因为暂时合作关系不采用任何先验安排。服务必须动态发现正确的 合作伙伴以便协同准备并对高层业务过程提供支持。为了便于服务间按需实时联 系的建立，就有必要建立w e b 服务间的动态和暂时交互关系，通过他们之间的这 种关系来找到一个好w e b 服务。而要找到这样一个好的动态的w e b 服务，并且用 最快最经济的方法来找到它，这就是求解最优路径问题。本文的主要工作就是用 改进的蚁群优化算法来求解面向w e bs e r v i c e s 应用集成中的路径问题。 本文首先对蚁群算法的基本原理进行了介绍，研究了蚁群算法的机理分析以 及它的特点，同时也对基本蚁群算法和改进的蚁群算法作了一些研究。然后阐述 了w e bs e r v i c e s 的核心支持技术：) ( m l ，s o a p ，w s d l ，u d d i 以及扩展的协议栈， 并给出面向w e bs e r v i c e s 的模型框架图，论述了用改进的蚁群算法来求解面向 w e bs e r v i c e s 应用集成中最优路径问题的可行性。 最后，本文结合有关概率统计方面的知识证明了：用蚁群算法求解最短路径 的收敛性，并给出了它的验证仿真图。 本文所设计的面向w e bs e r v i c e s 应用集成蚁群优化算法经系统仿真证明， 能有效地找到所需要的w e b 服务，从而提高1 i j y e b 服务的利用率。因此本文所设的 面向w e bs e r v i c e s 应用集成蚁群优化算法对提高w e b 服务的质量有很重要的影 响，能够创造明显的经济效益。由于面向w e bs e r v i c e s 应用集成的问题还是一 个新的技术问题，将蚁群算法的应用研究扩展到面向w e bs e r v i c e s 应用集成对 蚁群算法的发展也具有非常重要的意义。 关键词：w e bs e r v i c e s ，蚁群算法，最优路径，优化，应用集成 论文类型：理论研究 a b s t r a c t w i t ht h ed e v e l o p m e n to fw e bs e r v i c e s ，t h ec o n c e p to fs o f t w a r es e r v i c e p r e v a i l si ni ti n d u s t r y t h en i c eo p e n n e s s ， c o o p e r a t i o na n di n d e p e n d e n c e o ns o f t w a r e o sm a k ew e bs e r v i c e st h eo p t i m a lt e c h n i q u et os e t t l et h e i n t e g r a t i o no fh e t e r o g e n e o u ss y s t e m c u r r e n t w e bs e r v i c e s a p p li c a t i o ni n t e g r a t i o n a d o p t sp a s s i v e i n t e r a c t i y em o d e l ，w e bs e r v i c es h o w sa c t i y a t i o nb yt h e d e f i n i n go p e r a t i o n o ft h ei n t e r f a c e i fw e bs e r v i c ei sa u t o n o m i ca n do n l ys u p p o r t st e i i l p o r a r y c o o p e r a t i o n ，t h i sp a s s i v em o d em a yh a v eah u g e1 i m i t ：b e c a u s et e m p o r a r y c o o p e r a tio nd o e s n tu s ea n y p r e d e t e r m in e da r r a n g e m e n t i no r d e rt o s u p p o r tt h eh i g h1 e v e lo p e r a t i o np r o c e s s ，t h es e r v i c em u s td y n a m i c a l l y f i n dt h er i g h tc 0 1 1 a b o r a t o r i ti sn e c e s s a r yt ob u i l dad y n a m i ca n d t e m p o r a r yi n t e r a c t i v dr e l a t i o na m o n gt h ew e bs e r v i c e st oe a s et h ef i n d i n g o fr e a lt i m ed e m a n do r i e n t e dc o n n e c t i o n ag o o dw e bs e r v i c ec a nb ef o u n d t h r o u g ht h er e l a t i o n sm e n t i o n e da b o v e t h ef i n d i n go fag o o dd y n a m i cw e b s e r v i c ew i t haf a s t e s ta n dm o s te c o n o m i cw a yi st h ep r o b l e mo ff i n d i n g t h eo p t i m i z a t i o np a t h t h et a s ko ft h ep a p e ri st of i n dt h eo p t i m i z a t i o n p a t hi nt h ei n t e g r a t i o no fw e bs e r v i c e so r i e n t e da p p l i c a t i o nb a s e do n i m p r o v e da n tc 0 1 0 n y a l g o r ith i l l i nt h ep a p e r ， f i r s t l y ， w ei n t r o d u c et h ep r i n c i p l eo ft h eb a s i ca n t c o l o n ya l g o r i t h i n ， a n dm a k er e s e a r c ho ni t sm e c h a n i s ma n a l y s i sa n di t s c h a r a c t e r i s t i c s w ep r o p o s ean e wa l g o r i t h mb a s e do nt h eb a s i ca n tc o l o n v a l g o r i t h i l l t h e nt h ec o r et e c h n o l o g i e s ( x m l ，s o a p ，w s d l ，a n du d d i ) a n d e x t e n d e d p r o t o c 0 1s t a c ko fw e bs e r v i c e sa r ed is c u s s e d 。 a n da s e r v i c e o r i e n t e dm o d e lf r a m ei sp r o p o s e d w ea l s od i s c u s st h ef e a s i b i li t v o ff i n d i n gt h eo p t i m i z a t i o np a t hi nt h e i n t e g r a t i o no fw e bs e r v i c e s o r i e n t e da p p l i c a t i o n f i n a l l y ，c o m b i n i n gt h ek n o w l e d g ei nt h ep r o b a b i l i t ys t a t ，t h ep a p e r p r o v e st h ec o n v e r g e n c eo fs h o r t e s tp a t hu s i n ga n tc 0 1 0 n ya l g o r it h ma n d g i v e sav a l i de 叫1 a t i o n 伊a p h t h ea p p l i c a t i o ni n t e g r a t e d i m p r o v e da n tc o l o n ya l g o r i t h mw h i c hi s o r i e n t e dt o w a r d sw e bs e r v i c e sw a sp r o v e db ys y s t e ms i m u l a t i o nt h a ti tc a n e f f e c t i v e l yf i n dt h ew e bs e r v i c ei nn e e d a sar e s u l t ，i tc a ni m p r o v et h e u til it yr a t e s ot h ep r o p o s e da l g o r ith i i lh a sa ni m p o r t a n ti m p a c to nt h e i m p r o v e m e n to ft h eq u a l i t yo fw e bs e r v i c e sa n di tc a na l s oy i e l dg r e a t e c o n o m i cr e t u r n s s i n c et h ea p p l i c a t i o ni n t e g r a t e dp r o b l e mw h i c hi s o r i e n t e dt o w a r d sw e bs e r v i c ei san e wt e c h n i c a lo n e ，i t i so fg r e a t i m p o r t a n c et oe x p a n dt h es t u d yo fa n tc 0 1 0 n ya l g o r i t h mf r o ma p p l i c a t i o n r e s e a r c ht oa p p li c a t i o ni n t e g r a t e do n eo r i e n t e dt o w a r d sw e bs e r v i c e s k e y w o r d s = w e bs e r v i c e s ，a n tc o l o y 舢g o r i t l l n l ，t h eb e s tp a t h ，0 p t i m i z a t i o 玛 a p p l i c a t i o ni l l t e 伊a t i o n 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名撇 日期：彻夕矛乡形 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 名韶栌师签叫魄 上海师范大学硕士学位论文第一章绪论 第一章绪论 在科学实践与工程技术中，人们经常遇到大量的、各式各样的最优化问题， 并需要对它们进行求解，而传统的优化方法由于其计算时间依赖于问题的规模与 结构，很难满足人们的要求。于是，技术难题的解决呼唤先进的理论与算法，智 能优化技术的出现与发展为解决这些优化问题提供了途径。蚁群优化算法( a n t c o l o n y0 p t i m i z a t i o n ，a c o ) 是近年来发展的一种新颖的仿生型的智能优化算法， 是一种很有前途的优化算法，本文就通过求解面向w e bs e r v i c e s 应用集成蚁群 优化算法问题的研究展开课题。 1 1 研究背景与研究意义 w e b 和i n t e r n e t 的增长方式正在变革着商业组织与它们的合作伙伴及客户间 的交互方式。实际上，用户越来越要求商业组织能够为它们提供准确、最新的信 息。由于能够有效地发现和发布满足用户需求的信息，面向w e bs e r v i c e s 的应用 正在获得强劲的发展势头，其核心过程是合成相关元w e b 服务，创建定制的、满 足客户需求的高层w e b 服务。 现有的w e b 服务合成应用采取被动的交互模式，w e b 服务通过接口中定义的操 作来显示激活。如果w e b 服务是自治的且仅支持暂时合作，这种被动方式就有很 大局限性：因为暂时合作关系不采用任何先验安排。服务必须动态发现正确的合 作伙伴以便协同准备并对高层业务过程提供支持，为了便于服务间按需实时联系 的建立，就有必要建立w e b 服务间的动态和暂时交互关系，通过他们之间的这种 关系来找到一个好的w e b 服务。而要找到这样一个好的动态的w e b 服务，并且用最 快最经济的方法来找到它，这就是最短路径问题。本课题就是在这样的背景下来 选择的。 w e bs e r v i c e s 不是应用集成或者是应用集成的一部分，更甚者，w e bs e r v i c e s 是另外一个技术，w e bs e r v i c e s 能够使应用集成成为真正可能的、便捷实施的， 同时又引人注目的解决方案。w e bs e r v i c e s 能够彻底地改变传统的应用集成中点 第一章绪论 上海师范大学硕士学位论文 对点的集成处理方式。 使用w e bs e r v i c e s ，通过松散的应用集成，可以仅仅实现应用集成的一个子 集，即能取得实效。与之相反，应用集成要实现一个全盘的方案，来紧密的集成 和联系支持业务的所有的系统和应用。在政府内部、政府之间、政府与企业之间 不同的业务系统和技术单体中可能需要花费数年的持续的努力，高投资以及为之 配备的充实的资源。 w e bs e r v i c e s ，以这样一种松散的服务捆绑集合形式( 也可以说是一个特别 的解决方案) ，能够快速、低价地开发、发布、发现和动态绑定应用。就当代w e b s e r v i c e s 的技术发展水平来看，w e bs e r v i c e s 可以实现应用程序之间的函数或方 法级的集成。它们不是自然的基于事务的，同时仅提供了基本的“请求响应 功能。然而，在下一代的w e bs e r v i c e s 中，在功能上和技术上都会更先进，将会 提供用户接口封装和安全性，他们将能够包装成一个应用程序并且把他嵌入到其 他的应用程序中去。 现有的主要关注于应用集成的应用集成解决方案将不得不因此而改变。在将 来，包装好的应用程序将使用如) ( m l 、s o a p 、w s d l 和u 叻i 技术来把它们的函数或 方法作为w e bs e r v i c e s 的界面来显示。因此，应用集成解决方案将不得不提供一 个对服务集成的广泛的支持，而不仅仅是应用集成。 传统的最短路径算法以及人工智能中的状态空间搜索等许多问题的求解算 法均是基于搜索路径的耗费具有可加性的假设，并假设这些耗费是确定的。但是， 在实际的网络中，边的权值往往是随时间变化的，是有关时间的函数。因此，传 统的方法不能解决非线性路径耗费的路径问题，即耗费之间具有潜在的随机相关 性、时变性问题【1 1 。文献【2 】中首次对交通网络中边属性值为时变随机的情形进行 了研究，并指出传统的最短路径算法不能解决这类网络，必须建立严格的一致性 约束条件才能求解某一动态网络中的最短路径问题。改进的d i j k s t r a 算法【3 l 虽然 能够在一定条件下求得最优解，但由于其时间复杂度为姗m 2 q 其中n 是网络的 结点数，m 是边的数目，m 是时间段数目，c 是所有边中最大的权值) 且要求网 络是离散型的，当时间段数m 比较大时，算法所用的时间将会非常的大1 4 j 。 实际上，动态网络的最短路径问题在许多情形下都是n p 问题，在没有找到 多项式算法前，可以考虑使用人工智能领域的一些智能算法来求解满意解【5 1 。文 2 上海师范大学硕士学位论文第一章绪论 献【5 】通过将动态网络离散化，采用遗传算法来求解动态网络中的最短路径问题。 文献【3 1 提出了一种动态网络模型，并用改进的d i i l 【s t r a 算法进行求解，时间复杂 度很高。在这种模型的基础上，文献【4 6 1 分别通过随机d i j s k t r a 方法、拆边法来产 生初始群体的遗传算法来求解动态网络中的最短路径问题，这两种方法能适合连 续和离散的网络。但是，遗传算法容易过早地收敛，使搜索陷入局部最优解。因 此，这两种方法搜索到全局最优解的概率都不高。文献阴采用反馈神经网络进行 求解，但要求神经网络的权值矩阵必须对称，而且要求边的走行时间函数必须是 连续有界的。本文就是在这样的一个情况下提出用改进的蚁群算法来求解面向 w 曲s e i c e s 应用集成中最优化路径问题。 因为蚁群算法具有正反馈、分布式计算的特性。正反馈过程使它能较快地发 现问题的较好解；分布式易于并行实现，将它与启发式算法相结合，也易于发现 最优解。且蚁群算法具有良好的并行性、鲁棒性，比较适合于用来解决网络中的 最佳路径搜索问题。最重要的是：蚁群算法不仅能快速地收敛，而且可以在搜索 最佳路径的同时，搜索到次优路径，而不用额外的搜索时间。 1 2 论文的主要工作 论文的主要工作如下安排： 1 、由于蚁群算法的关键一点就是在探索与利用之间建立一个平衡点，以寻 求那些可能存在最优解的解区域，同时充分利用群体内当前具有的有效信息，使 得算法搜索的重点放在那些可能具有适应值的个体所在的区间内，从而以大概率 搜索到全局最优解。蚁群算法的信息交互及通信主要通过信息素来完成，信息素 的正反馈易于出现停滞现象。 针对蚁群算法中存在的不足，提出了信息素更新策略的优化方法。 改进蚁群算法，提高其寻优速度：引入相遇蚁群算法的思想，并且在局部更 新算法中采用具有变异特征的算法与2 0 p t 相结合的算法，提高解的搜索空间。 分析算法复杂度，从理论上证明本算法求解最优路径的可行性，用拓扑学知识 来验证。 通过把改进的蚁群算法与改进前的算法进行比较表明，这些改进可以有效提 高规则的准确率。 2 、为多个w 曲s e i c e s 应用集成建立数学模型，并用基本蚁群算法对此建 3 第一章绪论上海师范大学硕士学位论文 立的数学模型进行求解其静态路径。 3 、建立动态模型，并用改进的蚁群优化算法来求解面向w e bs e n r i c e s 应用 集成中的路径问题。 1 3 论文的研究内容与成果 本文在广泛阅读国内外关于拟生态算法蚁群算法和w e bs e r v i c e s 的文 献后，提出了应用蚁群优化算法来求解w e bs e r v i c e s 应用集成中的问题。论文的 主要内容包括以下几个方面： ( 1 ) 第一章绪论 介绍本论文的选题背景与研究意义，分析了为什么要用蚁群算法来解决面向 w e bs e r v i c e s 应用集成中的最优化路径问题，并进一步说明了用蚁群算法来解决 这一问题的可行性，最后一部分为概述了本论文的研究内容与成果。 ( 2 ) 第二章解析基本蚁群算法，找出影响蚁群算法性能的因素 在深刻理解基本蚁群算法的基础上，通过实验程序找出影响基本蚁群算法 的关键因素，并对基本蚁群算法进行简单的改进，而这些关键因素及实验性的改 进思路将为后面设计面向w e bs e r v i c e s 应用集成中求解最优路径提供参考。 ( 3 ) 第三章解析w e bs e r v i c e s 实现的关键技术研究，建构出面向w e bs e r v i c e s 应用集成模型 从w e bs e r v i c e s 的体系结构以及关键实现技术如x m l 、s o a p 、w s d l 、u d d i 等进行了详细分析与论述。应用w e bs e r v i c e s 及其相关理论，建立面向w e b s e r v i c e s 的应用集成框架并对该集成框架各个组成部分进行了详细分析。并且 对面向w e bs e r v i c e s 的应用集成进行框架设计建立了模型。 ( 4 ) 第四章是结合前二章所叙述的知识，提出面向简单的w e bs e r v i c e s 应 用集成蚁群优化算法的问题，对最短路径的知识进行了简短的回顾，并对最短路 的蚁群算法收敛性进行了分析并给出了它的仿真算例。应用所得知识来求解面向 简单的w e bs e r v i c e s 应用集成中蚁群优化问题。 ( 5 ) 第五章在前一章节的基础上提出了一种面向复杂的w e bs e r v i c e s 应用 集成蚁群优化算法的问题。并结合蚁群优化算法的实现来求解它的最优路径，并 与经典的d i j s k t r a 算法求解最短路径作了一个比较。修改模型，当w e bs e r v i c e s 应用集成中某一个w e b 服务器发生故障即：一个动态的模型，应用改进的蚁群优 4 上海师范大学硕士学位论文 第一章绪论 化算法来求解时的情况给了一个分析。 ( 6 ) 第六章对本论文作了一个总结。分析、总结本文的主要工作、创新点 及进一步的工作。 最后是参考文献、附录、致谢及读研期间发表的论文和参与的科研项目的介 绍。 本文所设计的面向w e bs e r v i c e s 应用集成蚁群优化算法经系统仿真证明， 能有效地找到所需要的w e b 服务，从而提高w e b 服务的利用率。因此本文所做的 面向w e bs e r v i c e s 应用集成蚁群优化算法对提高w e b 服务的质量有很重要的影 响，能够创造明显的经济效益。由于面向w e bs e r v i c e s 应用集成的问题还是一 个新的技术问题，将蚁群算法的应用研究扩展到面向w e bs e r v i c e s 应用集成对 蚁群算法的发展也具有非常重要的意义。 1 4 本章小结 本章提出论文研究目的和思路，并列举论文所作的研究内容和将要得出的研 究成果。 5 第二章蚁群算法原理和研究上海师范大学硕士学位论文 第二章蚁群算法原理和研究 2 1 蚁群算法原理 2 1 1 蚂蚁觅食的现象 昆虫学家在研究群居性昆虫行为特性时，发现昆虫在群落这一级的合作基本 上是自组织的，在许多场合中虽然这种合作看起来很简单，但是它们却可以解决 复杂的问题。 这种由群居生物产生出来的一种集体行为，即产生的群集智能引起了包括计 算机科学家在内的众多研究人员的兴趣。在研究蚂蚁的觅食行为时，科学家们发 现蚁群能找到蚁巢到食物间的最短路径，开始时最短路径上的蚂蚁数目较少，随 着蚂蚁搬运食物的进行，最短路径上的蚂蚁数目也在增多，直到所有的蚂蚁都汇 聚到这条最短路径上。科学家对蚂蚁走的路径进行研究时，发现蚂蚁汇聚行为的 发生是由于蚂蚁自身发出的一种物质，蚂蚁在运动的过程中能够感知这种物质的 存在及其强度，并以此指导自己的运动方向，科学家们称这种物质为信息素，信 息素越多，它浓度越大，蚂蚁倾向于朝着该物质浓度高的方向移动，即蚂蚁向信 息素多的路径( 即信息素浓度大的路径) 汇聚，而蚂蚁的增多使该路径上的信息 素浓度进一步加大，以致所有的蚂蚁都走此路径。蚂蚁个体之间就是通过这种信 息的交流达到搜索食物的目的。科学家在蚂蚁找到的最短路径上放障碍物后，蚂 蚁仍然能根据信息素的“指引”下找到此环境里的最短路径汹3 。由意大利学者 m d o r i g o 嘶1 等人提出的蚁群算法就是模拟上述蚂蚁觅食方式，为了与真实蚁群相 区别，我们将蚁群算法中的蚁群称为人工蚁群。 2 1 2 人工蚁群与真实蚁群的联系 蚁群算法中绝大多数的观点来源于真实的蚂蚁。因此它们都包括以下几项： 个体之间能相互协作的群体；进行当前信息交流的( 人工) 信息素迹；为找 到最短路径记录的当前移动队列；以及利用当前信息而没有未来信息的随机选择 策略。下面我们对上述四点进行解释。 ( 1 ) 个体之间能相互协作的群体作为真实的蚁群，蚁群算法是利用同步 的和非同步的全局协作的一个种群( 或群体) 找到所考虑问题的最优解。虽然每 6 上海师范大学硕士学位论文 第二章蚁群算法原理和研究 个人工蚂蚁都可以找到一个可行解( 即任何一个真实蚂蚁都可以找到一条从蚁巢 到食物源的路径) ，但是只有依靠整个蚁群中个体间的相互协作才能找到最优解。 2 6 ( 2 ) 进行当前信息交流的( 人工) 信息素人工蚂蚁与真实蚂蚁都改变了 它们所处环境的一些方面。真实蚂蚁在它们经过的路径上留下了一种化学物质一 信息素 2 7 ，人工蚂蚁在它们经过的路径上改变了路径上存储的数字信息。这 个信息考虑了蚂蚁当前的和历史的性能，并且还能被其他经过这里的人工蚂蚁读 和写。类似地，我们称这种数字信息为人工信息素迹。在蚁群优化算法中蚂蚁进 行交流协作的方式就是当前路径上的信息素轨迹。这种交流的方式在收集可利用 的知识上占据着重要的位置。其重要的作用在于它改变了当前蚂蚁所经过的路径 周围的环境，同时也像一个函数似的改变了整个蚁群所存储的历史信息。通常， 在蚁群优化算法中有一个挥发机制，它像真实的信息素挥发一样随着时间的推移 改变路径上的人工信息素。挥发现象使得蚁群可以逐渐的忘却历史，这样就可以 不局限于过去而选择出新的路径。 ( 3 ) 为找到最短路径记录的当前移动队列这里人工蚂蚁和真实蚂蚁都要 完成一个相同的任务：寻找一条从源节点( 蚁巢) 到目的节点( 食物源) 的最短 路径。真实蚂蚁和人工蚂蚁都不具有跳跃性，即它们都只能在相邻节点之间一步 一步地移动。 ( 4 ) 利用当前信息而没有未来信息的随机选择策略人工蚁群算法中人工 蚂蚁从一个节点移动到下一个节点的求解方法是利用概率选择策略实现的。概率 选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息。因此， 这一应用策略无论在空间还是在时间上利用的完全都是当前信息。 另外，人工蚁群还具有一些真实蚁群不具有的特点： ( 1 )人工蚁群生活在一个离散的世界中，它们的移动包括从离散 状态到离散状态的转换。 ( 2 )人工蚁群具有一个内在的状态。这种私有的状态包括该蚁群 以前行为的记忆。 ( 3 )人工蚁群放置信息的定时性，是随问题而定的，它并不反映 真实蚁群的行为。例如，在一些例子中人工蚂蚁只在产生一 7 第二章蚁群算法原理和研究 上海师范大学硕士学位论文 个解之后才改变信息素痕迹，并不是随时改变的。 ( 4 ) 为改善系统的有效性，蚁群算法中可以增加一此额外的性能， 比如说预测未来、局部优化、回退等等。这些在真实蚁群中 是没有的。在很多应用中人工蚁群可以在局部优化过程中相 互交换信息，还有一些蚁群算法实现了简单的预测。 在对人工蚁群和真实蚁群的特点进行比较之后，将具体讲述利用人工蚁群的 蚁群算法是如何模拟真实蚁群进行问题求解的。 2 1 3 蚁群算法的生物学原理 首先从真实蚁群搜索食物的一个具体过程谈起：蚂蚁是一种群居昆虫，单个 蚂蚁的行为极其简单，但由这样的单个简单的个体所组成的蚂蚁群体却表现出极 其复杂的行为，能够完成复杂的任务，不仅如此蚂蚁还能够适应环境的变化，如： 在蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。经过 大量研究发现，蚁群之所以表现出复杂有序的行为，是因为个体之间的信息交流 与相互协作起着重要的作用。蚂蚁在运动过程中，能够在它所经过的路径上留下 一种称之为信息素( p h e r o m o n e ) 的物质，而且蚂蚁在运动过程中能够感知这种 物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度 高的方向移动。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的啪1 。 下面简单介绍真实蚁群寻找最优路径的原理： 图4 1 中n 表示蚁巢，f 表示食物所在位置，叩为障碍物，设d 和a ，d 和c 之间 的距离为2 个单位，a 和b ，b 与c 之间的距离均为1 个单位，在一个时间单元内有3 0 只蚂蚁由n 到达a 点，同样有3 0 只蚂蚁由f 到d 点，蚂蚁的运动速度是2 个单位距离 单位时间，每只蚂蚁在其走过的路径上留下一个单位的信息量。假设初始时刻t = 0 时各条路径均无蚂蚁走过，位于a 和c 点的各3 0 只蚂蚁选择所走路线的概率是相同 的，按照统计规律，可知有1 5 只蚂蚁选择a d ( c d ) ，另外1 5 只蚂蚁选择a b ( c b ) 。 由于d a d = d d c = 2 d a b = 2 d b c ，所有经过1 个单位时间后，走过路径a b 和b c 的蚂蚁个数 是走过路径a d 和d c 蚂蚁个数的两倍。这些蚂蚁留在路径上的信息量前者也是后者 的两倍。在t = 1 时，新的3 0 只蚂蚁位于a 点和c 点，根据信息量的多少，它们选择 a b ( b c ) 的概率是选择a d ( c d ) 的两倍，即：有2 0 只蚂蚁选择前者，只有1 0 只蚂 蚁选择后者。这一过程一直继续下去，最终所有的蚂蚁都将选择由蚁巢到食物的 8 上海师范大学硕士学位论文第二章蚁群算法原理和研究 最短路径。 d b 图2 1 蚁群搜索食物路线示意图 f i g 2 1a ne x a m p l eo fr e a la n tc 0 1 0 n yw h i1 es e a r c h i n gf o o d 让人工蚂蚁根据路径上的相当于p h e r o m o n e 的数字信息素的大小( 即强度) 选择路径，并在所经过的路径上留下相当于p h e r o m o n e 的数字信息素，然后随着 时间的推移，最优路径上的数字信息素就会越来越大，从而选择它的概率也就越 来越大，最终所有的人工蚂蚁都选择这条路径。 大量蚂蚁组成的蚁群的集体行为实际上就构成了一种信息正反馈现象：某一 路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。该算法的本质在于： l 、选择机制，信息素越多的路径，被选择的概率越大； 2 、更新机制，路径上面的信息素会随着蚂蚁的经过而增长，而且同时也随 着时间的推移逐渐挥发消失； 3 、协调机制，蚂蚁之间实际上是通过信息素来相互通信、协同工作的。 2 2 蚁群算法机理分析 蚁群算法是模拟蚂蚁的食物搜索行为，针对n p h a r d 组合优化问题而设计的 一类构造性算法。蚁群作为一种社会性昆虫，其食物搜索行为具有非常高的协作 性。当蚂蚁在食物源和巢穴之间行走时，会在路上存储信息素。蚂蚁可以感知到 9 第二章蚁群算法原理和研究 上海师范大学硕士学位论文 环境中这种物质的存在及其强度，并在选择移动时，倾向于选择信息素浓度高的 方向。当一条路径较短时，会有较多的蚂蚁使用这条路径，这使得该路径上的被 存放了较多的信息素，从而吸引更多的蚂蚁使用这一路径。最终，信息素浓度最 高的路径标志出食物和巢穴之间的最短路径。 我们以求解平面上n 个城市( 用1 ，2 ，n 表示城市序号) 的tsp 问题来说 明基本蚁群算法的机理。设设m 表示蚁群中蚂蚁的数量；d i j ( i ，j = 1 ，2 ，n ) 表示 i 城和j 城之间的距离( 即d t j = ( 鼍一x f ) 2 + ( 咒一y f ) 2 ) ；b t ( t ) 表示t 时刻位于城市i 的蚂蚁个数，m _ 罗轨o ) ，一r ；，( t ) 表示t 时刻在i j 连线的路径上残留的信息量( 即 信息素浓度) ，我们以此来模拟实际蚂蚁的信息素浓度。 每一个简单蚂蚁有以下特性： 1 、它依据以城市距离和连接边上外激素数量为变量的概率函数选择下一个 城市( 设o ) 为t 时刻边e ( i ，j ) 上外激素的强度) ； 2 、通过禁忌表控制蚂蚁走合法路线，除非周游完成，一次周游中，不允许 转到已访问城市( 设t a b u 。表示第k 个蚂蚁的禁忌表，t a b u 。( s ) 表示禁忌表中第s 个元素) ； 3 、它完成周游后，蚂蚁在它每一条访问的边上留下信息素，并更新走过的 路径上的信息素浓度。 初始时刻，各条路径上的信息量相等，设c ；。( 0 ) = 常数。m 只蚂蚁被放置在不 同的城市上。每个蚂蚁k 的t a b u 。集合的第一个元素赋值为它所在的城市。 p ：( t ) 表示在t 时刻蚂蚁k 从城市i 转移到城市j 的概率啪1 ，则 露o ) ；蒜器座以 荟】卜 0 ，其他 ( 2 一1 ) 式中： q 蚂蚁在行进过程中所积累的信息浓度对它选择路径所起的作用大小， 当q = 0 时，算法就是传统的贪心算法； 1 0 上海师范大学硕士学位论文第二章蚁群算法原理和研究 母q ；，的重要程度，当b = o 时，算法就成了纯粹的正反馈的启发式算法； 可以用试验的方法确定参数a ，b 的最优组合。 f l 。j 由城市i 转移到城市j 的期望程度，可根据某种启发算法而定，例如， 可以取nl j - 1 d 。j ： t 。，( t ) 随着时间的推移会逐步衰减，用卜p 表示它的衰减程度； 表示蚂蚁k 下一步允许选择的城市的集合，它随蚂蚁k 的行进过程而 动态改变。 经过n 个时刻，蚂蚁完成一次循环，此时，要根据下式对各条路径上的信息 素浓度作更新： o + ，1 ) 一p o ) + ( 2 2 ) r f ，一了ri 储 u ( 2 3 ) 式中表示第k 只蚂蚁在本次循环中留在路径i j 上的信息量，表示本 峰p 嘲翟槲鲥 4 ， 厶第k 只蚂蚁在本次循环中所走的路径长度。 丐。f 罢，若第七只蚂蚁在本次循环中经过巧 c 2 5 ， l 0 其他 第二章蚁群算法原理和研究 上海师范大学硕士学位论文 噶ar 靴鹏嚣躲畅m j ( 2 6 ) 它们之间的区别是：蚁周系统在搜索过程中使用的反馈信息是全局的，而蚁 量系统和蚁密系统使用的反馈信息都是局部的，故蚁周系统模型的性能要优于蚁 量系统模型和蚁密系统模型，仿真出来的结果也证明了这个推断。 蚁群算法中的参数设定目前尚无理论上的依据，参数q ，c ，d ，b ，p 可以 用实验确定其最优组合。经验结果为：1 ) 1 q 5 ；2 ) 1 b 5 ：3 ) 0 。5 p 0 9 9 ，p 取0 7 左右为佳；4 ) 1 q 1 0 0 0 0 。 蚁群算法的主要步骤如下： 步骤ln c = 0 ( n c 为迭代步数或搜索次数) ；每条边上的t ，( 0 ) 一c ( 常数) ，并且 = o ：放置m 个蚂蚁到n 个城市上。 步骤2 将各蚂蚁的初始出发点置于当前解集细6 0 ) 中；对每个蚂蚁 k ( k = 1 ，m ) ，按概率露移至下一城市j ：将城市j 置于缸6 o ) 中。 步骤3 经过n 个时刻，蚂蚁k 可走完所有的城市，完成一次循环。计算每个蚂 蚁走过的总路径长度丘，更新找到的最短路径。 步骤4 更新每条边上的信息素浓度o + n ) 。 步骤5 对每一条边置。0 ；n c = n c + 1 。 步骤6 若n c q o ，则按第二种情况选择随机变量s ，称为搜 索，s 的概率分布以( ，s ) 与蚁周系统( 柚tc y c l es y s t e m ) 中的仇( ，s ) 的计算方法 相同。这一算法和以前算法的主要不同在于蚂蚁选择下一城市之前，多进行了一 次随机试验，将选择情况分成“利用已知信息和“探索 两类。 具有变异特征的蚁群算法是在遗传算法中变异算子的启发下产生的。意大利 学家f a b i o a b b a t t i s t a 等人也受遗传算法的启发，提出蚁群算法和遗传算法相结 合的一条思路。鉴于在蚁群处中参数q ，b 和q 的选择对算法的性能有很大影响， 可以将q ，0 和q 看成代表蚂蚁典型特征的染色g 中的三段代码。在g 中，g 。 和g 。将q ，b 编码为实数，g q 将q 编码为整数。然后将此染色体通过遗传算子 交由一个进化进程处理。简而言之，这一改进算法的变异是指对蚁群算法中q ， b 和q 这三个参数的变异，这样就把蚁群系统的协作效应与遗传算法的进化效 应相结合。 b i l c h e v 等人曾在使用遗传算法解决工程设计中连续空间的优化问题时，配 合使用了蚁群算法对遗传算法所得到的初步结果进行了精确化，取得了较好的效 果【加】。 德国学者n o m 勰s t t z l e 与h o l g e rh o o s 提出的改进的蚁群算法“最大最小蚁 群系统：( m a x m i n 狃ts y s t e m ，m m a s ) 也是一种较好的通用优化算法【4 1 4 2 1 。在 求解对称旅行商问题( t s p ) 与非对称旅行商问题( 衄s p ，a m i s o m e r o u s1 h v e l i n g s a l e s m 锄p r o b l e m ) 时，m m a s 的性能与a c s 相当，在平均路径长度上还优于 a c s 。两者的共同点是在算法的每次迭代中只允许表现最好的蚂蚁更新路径上的 信息素浓度，以加快收敛速度；其不同之处主要在于如何防止过早的停滞现象 ( s t a g n a t i o n ) 。m m a s 限定了信息素浓度允许值的上下限，并且采用了平滑机制 ( t m i is m 0 0 t h j n gm e c h a n i s m ) 。m m a s 在算法启动时将所有支路上的信息素浓度初 始化为最大值每次迭代后，按挥发系统p 降低信息素浓度，只有最佳路径上 第二章蚁群算法原理和研究上海师范大学硕士学位论文 的支路才允许增加其浓度，并保持高水平上。但是只采用最大最小信息素浓度的 限制还不足以在较长的运行时间里消除停滞现象，因此采用了平滑机制：信息素 浓度的增加正经于和当前浓度f ( r ，s ) 之差。对此算法的进一步扩展是加入局 部搜索，目的是一方面提高算法性能，能在搜索初期获得高质量的解，更直接地 引导学习机制；另一方面，使m m a s 为后续的局部搜索阶段构造好的初始解， 以便找到接近最优的解。 2 0 0 1 年，k es g 等人提出了一种新的改进的信息素更新策略：其一，局部 信息素修改时，挥发系数动态改变；其二，全局信息素更新时，则将蚂蚁所走过 的较短的那些路径上的信息加强，而较差的那些路径上的信息减弱【4 3 1 。与此同 时，吴斌、史忠植又提出了一种相遇算法，其基本思想是在求解t s p 问题中， 用两只蚂蚁共同完成一条路径的搜索，其目的都在于提高搜索速度【2 6 1 。 2 0 0 0 年，w j g u t i j a h r 首先对a c 0 的收敛性进行了探讨，取得了一些初步 的结果，目前已有少量文献涉及a c o 的收敛性，但还很不成熟。 目前，a c o 在启发式方法范畴内已逐渐成为一个独立的研究领域，在有关 国际会议上多次作为专题加以讨论，如1 9 9 8 年、2 0 0 0 年、2 0 0 2 年、2 0 0 6 年在 比利时布鲁塞尔大学召开了四届a c o 国际研讨会( a n t s 9 8 ，a 卫t s 2 0 0 0 ，a n t s 2 0 0 2 ， a m t s 2 0 0 6 ) 。就s i 算法，a c o 算法和群集机器人技术( s r ，s w a mr o b o t i c s ) 进行讨论。 2 4 2 国内研究 国内的研究始于1 9 9 8 年末，国内首先研究该算法的研究者应该是张纪会、徐 心和。该算法主要在上海、北京、东北少数几个学校和研究所开展了研究工作， 主要围绕t s p 及相关问题的试验仿真，少数设计网络通讯的路由选择、负载平衡、 电力系统的故障检测以及蚁群算法在连续系统中的应用，如函数逼近等方面应用 的尝试。 蚁群算法在国内的研究虽然也取得了一些成果，但是在研究力度和广度上还 与国外相差甚远。并且把蚁群算法用于面向w 曲s e r v i c e s 应用集成最优路径的求 解上还没有正式的研究。 1 6 上海师范大学硕士学位论文 第二章蚁群算法原理和研究 2 。5 蚁群算法中一些参数的选择 蚁群算法中的人工蚂蚁之所以能从大量杂乱无章的候选路径中找到一条从 蚁巢到食物源的最优路径，是因为路径上信息素的存在。人工蚂蚁通过信息素相 互影响，形成信息正反馈，最终达到寻优的目的。因此，蚁群算法中与信息素有 关的一些参数的选择好坏对算法的性能影响很大。本节通过蚁群算法实验室对基 本蚁群算法中的参数a 、b 、p 的选择进行分析。 2 5 1q 和b 的选择 启发因子a 、b 分别为残留信息的相对重要程度和能见度的相对重要程度。 q 的大小反映了蚂蚁在路径搜索过程中随机性因素作用的强弱