（计算机应用技术专业论文）改进的蚁群算法在移动agent路径选择中的应用研究.pdf

摘要 摘要 移动a g e n t 迁移过程中路径选择的一个经典的、代表问题旅行a g e n t 问题 ( t a p ) ，是一个复杂的组合优化问题。蚁群算法( a n tc o l o n ya l g o r i t h m ) 作为一种新的生物 进化算法，具有并行、正反馈和启发式搜索等特点，在求解该问题上具有一定的优势， 但搜索时间长，易陷入局部最优是其突出缺点。 本文结合现有的蚁群算法和移动a g e n t 本身的特点，提出了基于任务权重和算法迭 代次数来修改路径上信息素更新规则和信息素挥发系数p 这两种新方法，来更好的提高 蚁群算法的求解性能。 本文主要的工作包括： 1 首先，介绍了基本蚁群算法的基本原理及其在t s p 问题上的应用，给出了该算 法的研究现状及应用领域。然后介绍了移动a g e n t 的系统结构及其关键技术，并对其优 点及应用进行了简单的介绍。 2 针对蚁群算法在求解移动a g e n t 迁移过程中路径选择存在的不足，并结合移动 a g e n t 本身的特点，对蚁群算法提出了两种改进的方法。第一种改进蚁群算法一基于 任务权重来自适应的修改经过路径上的信息素更新规则及挥发系数p 。携带任务以的移 动a g e n t 在算法运行的不同阶段，根据自身的任务权重值丌圪，自适应的增大或缩小经 过的路径上的信息素增量和信息素挥发系数p ，实验证明，这样可以自适应的克服该算 法的缺陷，更好提高求解该问题的能力。 第二种方法是利用算法的迭代次数来动态的、自适应的修改经过路径上的信息素更 新规则及挥发系数p 。因为算法在不同的运行过程中，会表现出不同的缺陷，所以根据 算法的迭代次数运用相应的策略，来提高该算法的全局搜索能力和防止出现早滞现象。 实验证明，本文的算法在求解该问题上具有更强的优势。 3 最后，将上述两种改进的算法应用到旅行a g e n t 问题( t a p ) 上，进行了大量仿真 实验，对实验的结果进行了深入分析和比较。实验结果表明，这两种改进的蚁群算法比 基本蚁群算法在寻优的能力上有了进一步的提高。 关键词：移动a g e n t ，蚁群算法，任务权重，自适应 a b s t r a c t a b s t r a c t t h et r a v e l i n ga g e n tp r o b l e mi sac l a s s i c ，r e p r e s e n t a t i v ea n dc o m p l e xc 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 ，w h i c hi np a t hs e l e c t i o no fm o b i l ea g e n tm i g r a t i o n a n tc o l o n y a l g o r i t h mi san e we v o l u t i o n a r ya l g o r i t h ma n de x t r e m e l ys u i tt os o l v et h et r a v e l l i n ga g e n t p r o b l e m ，w h i c hh a st h ec h a r a c t e r i s t i co fp a r a l l e l i s m ，p o s i t i v ef e e d b a c ka n dh e u r i s t i cs e a r c h , b u ti th a st h el i m i t a t i o no fs t a g n a t i o n ，a n di se a s yt of a l l i n t ol o c a lo p t i m u m s 。 b a s e do nd u t yw e i g h ta n db yu s i n gt h en u m b e ro fi t e r a t i v ea l g o r i t h m st ou p d a t et h er u l e s a n di n f o r m a t i o n v o l a t i l ef a c t o rt oe n h a n c et h ea b i l i t yo fc h o o s i n gt h ep a t h ，t h e r ew e r et w o n e wm e t h o d sw e r ep r o p o s e d ，w h i c hw e r ef o rt h ec o m b i n a t i o no ft h ee x i s t i n ga n tc o l o n y a l g o r i t h ma n dm o b i l ea g e n tc h a r a c t e r i s t i c si nt h i sp a p e r t h em a i nw o r ko ft h i sp a p e rc a l lb ec o n c l u d e da sf o l l o w s ： 1 f i r s to fa l l ，i n t r o d u c e dt h eb a s i cp r i n c i p l e so fa n tc o l o n ya l g o r i t h ma n di t sa p p l i c a t i o n o nt h et s p g a v et h es t a t u so fr e s e a r c ha n da p p l i c a t i o i l s a n dt h e ni n t r o d u c e dt h ea r c h i t e c t u r e o fm o b i l ea g e n ts y s t e ma n di t sk e yt e c h n o l o g i e s 、a p p l i c a t i o n sa n da d v a n t a g e s 2 i nv i e wo ft h ep r o b l e mo fa n tc o l o n ya l g o r i t h ma p p l i e di nm o b i l ea g e n tm i g r a t i o n a n dc o m b i n ew i t ht h ec h a r a c t e ro fm o b i l ea g e n t ，t h e r ew e r et w oi m p r o v e da n tc o l o n y a l g o r i t h m sw e r ep r o p o s e di nt h i sp a p e r 1 1 1 ef i r s tm e t h o di st ou s et h ei d e ao fw e i g h tt a s kt o u p d a t ea n tp a t hi n f o r m a t i o na n di n f o r m a t i o n v o l a t i l ef a c t o r a c c o r d i n gt o i t so w l lw e i g h t s ， am o b i l ea g e n tc a r r y i n gt h ec o r r e s p o n d i n gt a s k ，c a na d a p t i v e l yi n c r e a s eo rr e d u c et h e i n c r e m e n t a lp h e r o m o n ea n dp h e r o m o n ee v a p o r a t i o nc o e f f i c i e n ti n d i f f e r e n ts t a g e s t h e e x p e r i m e n tr e s u l ts h o w st h a tt h es h o r t c o m i n g so fa n tc o l o n ya l g o r i t h mc a nb ea d a p t i v e l y o v e r c o m ea n db e a e rt oi m p r o v et h ea b i l i t yt os o l v et h ep r o b l e m t h eo t h e rn e wm e t h o di st ou s et h en u m b e ro fi t e r a t i v ea l g o r i t h m st ou p d a t et h er u l e sa n d i n f o r m a t i o n v o l a t i l ef a c t o r ，t h ea l g o r i t h mw i l ls h o wd i f f e r e n td e f e c t si nd i f f e r e n tp r o c e s s ，s o a c c o r d i n gt ot h en u m b e ro fi t e r a t i v ea l g o r i t h m ，t h ei m p r o v e d a n tc o l o n ya l g o r i t h mc a l lu s et h e c o r r e s p o n d i n gs t r a t e g i e st oi m p r o v et h ea l g o r i t h mo fg l o b a ls e a r c ha b i l i t ya n dp r e v e n tt h e e m e r g e n c eo f ”e a r l yl a g ”p h e n o m e n o n 1 1 1 ee x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mi nt h i s p a p e rc a ns o l v et h ep r o b l e mw i t hm o r ea d v a n t a g e s 3 a tl a s t ，t h et r a v e la g e n tp r o b l e m ( t a p ) w a ss o l v e db yt h et w oi m p r o v e da n tc o l o n y a l g o r i t h m s ，c a r r i e do u tal a r g en u m b e ro fs i m u l a t i o ne x p e r i m e n t sa n dc a r r i e do u ti n - d e p t h a n a l y s i sa n dc o m p a r i s o no n t h er e s u l t so fe x p e r i m e n t s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e t w oi m p r o v e da n tc o l o n ya l g o r i t h m sh a di m p r o v e dt h ea b i l i t yo fo p t i m i z a t i o nt h a nt h eb a s i c a n tc o l o n ya l g o r i t h m k e y w o r d s ：m o b i l ea g e n t , a n tc o l o n ya l g o r i t h m ，d u t yw e i g h t , a d a p t i v e i i 独创性声明 本人声明所呈交的学位论文是誉人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名：绎婶日期：趔姆 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：一言师签蠹：一 第一章绪论 第一章绪论 1 1 移动a g e n t 路径选择问题的概述 近年来，随着人工智能和网络技术的飞速发展，国内外众多的研究学者对移动a g c m 技术的研究和发展也更加关注。移动a g e m 技术的迁移策略是该技术的基础技术核心， 而移动a g c m 路径选择问题，正是移动a g e m 迁移策略的主要研究对象，所以求解移动 a g e m 路径选择问题具有重要的意义。移动a g c m 的迁移策略，受到了学术界和工业界 广泛的关注，并进行了大量探索和研究，取得了一定的成绩。 旅行a g e m 问题( t a p ) 是移动a g e m 路径选择问题中的一个经典例子。该问题是根 据移动a g e m 的任务、网络的软硬件环境和其他约束条件为移动a g e m 规划出最佳的迁 移路径。很多研究学者对该问题都进行了大量的研究和实验，提出了很多有效的方法和 思想，如遗传算法，模拟退化算法等等，在该问题上取得的一定的效果。旅行a g e m 问 题( t a p ) 是一个n p 完全问题，其时间度、空间复杂度都高，这就要求求解该问题的方法 一般需要具备自适应、自学习、分布式、并行化等特点。蚁群算法是意大利学者d o f i g o 等人在2 0 世纪9 0 年代，首先提出的一种基于种群的启发式仿生算法。该算法不仅仅具 有以上特征，而且还具有正反馈、引入与问题相关领域的知识等特点，所以蚁群算法求 解该问题是非常合适。 蚁群算法在求解该问题上具有很强的优势，但是随着问题规模的增大和一些不确定 性因素的存在，它会表现出全局搜索能力不强，易于陷入局部最优等缺陷，因此，本文 在基本蚁群算法的基础上，理解和掌握现有的其他改进思想和方法，提出了基于任务权 重和算法迭代次数的自适应蚁群算法来求解该问题，对仿真实验结果进行了分析和比 较。实验结果表明，本文两种改进方法使该算法的性能有了一定的提高。 1 2 蚁群算法 1 2 1 蚁群算法的研究背景 在当今社会中，随着人工智能【1 - 2 1 ( 灿) 和网络技术的飞速发展，科学技术与其他的多 种学科相互交叉，相互渗透和融合，不仅给人们的生活、学习和工作等方面带了便利， 而且也从根本上改变了人类的生活和生产。与此同时，随着人类生活空间的不断扩大和 对世界认识水平的不断提高，人们又对科学技术的发展提出了更高、更多的要求，期待 着更多的研究学者对它进行不断的研究和提高，其中高效的优化技术和智能计算的要求 也进一步的迫切需求。 为了提高优化技术水平和智能计算的发展，近些年来有很多的研究学者，特别是在 生物方面的研究专家和学者，通过对大自然中很多生物的生活现象和规律进行了大量的 研究和探讨，提出了很多的群体智能算法【3 训。它们是一种基于生物信息系统的智能仿 生算法，学者们是对社会性昆虫相互合作进行工作的研究，从生物进化和仿生学角度受 到启发而提出的。众所周知，社会性昆虫如蜜蜂，蚂蚁等，虽然其单个个体的力量很小， 江南大学硕士学位论文 行为方式很简单、随机，但是它们却可以凭借集体的力量进行一些复杂的社会性活动， 来更好的完成单个个体很难甚至不能完成的行为或活动，如它们可以通过社会分工等方 式来更快的找到食物，共同的建造巢穴和防止外敌入侵等等。这种群体所表现出来的“智 能”，就可以称之为群体智能【5 ) ( s w a r mi n t e l l i g e n c es i ) 。群体智能中的群体( s w a r m ) 是指“一 组相互之间可以进行间接通信( s t i g m e r g y ) 的主体，这组主体能够合作进行分布式问题求 解”。而所谓群体智能是指“无智能的主体通过合作表现出智能行为的特性”。群体智能 在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提 供了基础。 在很多专家和研究学者的共同努力下，有很多的群体智能算法得以提出并有了很好 的发展和应用。虽然有些智能算法有了成熟的理论基础，但是把它们能够很好的应用到 现实生活中还有一定的差距，需要我们共同的参与，进行不断的探索、尝试和研究。蚁 群算法正是群体智能算法中的一个重要分支。在对一些生物昆虫，如蜜蜂、蚂蚁等进行 大量的观察和研究后，生物学家发现了像蚂蚁这样弱小的昆虫，在觅食的时候，通过群 体的力量，经过多次的探索和寻找，最终能够找得到一条从巢穴到食物源的最短路径。 为了进一步的研究，生物学家就在蚂蚁寻找食物的路径上，设置一些障碍物来影响蚂蚁 寻找路径，经过一段时间的搜寻，最终蚂蚁还是找到了从巢穴到食物源的最短路径。经 过各种实验，生物学家进一步的研究表明，蚂蚁在寻找食物的探索过程中，会在所经过 的路径上释放一种挥发的化学物质，这种特殊的物质被称之为信息素【6 ) ( p h e r o m o n e ) 。信 息素可以沉积在路径上，并随着时间逐步的挥发。当蚂蚁选择路径的时候，它们倾向于 沿着信息素气味较浓的路径上前进。因此信息素可以引导蚂蚁来更快的，更有可能的找 到离巢穴最近的食物。实验结果表明，正是这种特殊的物质，能够使蚂蚁找到从巢穴通 向食物的最短路径。也可以说，当蚂蚁的巢穴和食物之间存在较多路径时，整个蚁群可 以通过搜索各个个体蚂蚁留下的信息素的痕迹来找到往返于蚁穴和食物之间的最短的 路径。 1 2 2 蚁群算法的历史和科学意义 蚁群算法( a n tc o l o n ya l g o r i t h m ) 是由意大利学者m d o r i g o 等在2 0 世纪9 0 年代初 期研究蚂蚁寻找从巢穴到食物源的路径时，从生物进化的机制中受到启发，提出了一种 新型的模拟进化算法。该算法具有稳健性( 鲁棒性) 、正反馈性和分布式计算等优点， 在求解复杂的组合优化问题上有更强的优势，在分配问题、j o b s h o p 调度等问题上，都 有了较好的实验结果。在求解计算机算法中经典的“旅行商问题口1 u ( t r a v e l i n gs a l e s m a n p r o b l e m t s p ) 时，众多的研究学者根据算法基本原理，在算法中设计出了虚拟的“蚂 蚁 来搜索不同的路线，还有虚拟的“信息素”，它会随着时间逐渐的消失。当每只蚂 蚁每次随机选择要走的路径，它们会尽可能的倾向于选择路径较短、信心素浓度较高的 路径，根据“信息量较浓的路线更近”的原则，即可选择出最佳的路径。由于该算法利 用了正反馈的机制，使得较短的路径能够有较大的机会得到选择，并且采用了概率算法， 来选择下一步要走的路径，所以它能够不局限于局部最优解。 虽然对蚁群算法的研究时间并不长，远不如像遗传算法，模拟退火等算法那样形成 2 第一章绪论 系统的分析方法和坚实的数学基础和理论基础，但是它的提出，能够为解决一些复杂的 系统优化问题提供了一种新的，更好的求解算法，特别是在求解离散型组合优化的问题 上，蚁群算法表现出了其他进化算法无法比拟的优越性。蚁群算法不仅具有鲁棒性、分 布式计算、正反馈性、易于和其他的智能算法相结合的特点，而且还能够智能搜索、全 局优化等优势。该算法已经引起了众多专家和学者的注意，现在正被越来越多的研究者 关注和探讨，算法的理论得到不断的完善，应用范围也普及到许多的科学技术及工程领 域，是一种有良好发展前景的模拟进化算法。 1 3 移动a g e n t 技术 1 3 1 移动a g e n t 的简介 2 0 世纪9 0 年代初，由g e n e r a lm a g i c 公司在推出系统t e l e s c r i p t 时提出了移动a g e n t 的概念。移动a g e n t 是一个能在异构的网络中，自主的从一台主机迁移到另一台主机， 并可与其他a g e n t 或主机上的资源交互的实体，实际上它是分布式计算机技术与a g e n t 技术的相互结合的产物。传统的服务器和r p c 客户之间的交互需要连续的通信，但是 移动的a g e n t 可以迁移到目标服务器上，与之本地进行高速通信，这种本地通信节省了 网络资源。移动a g e n t 迁移的内容包括其代码和运行的状态。运行的状态可分为数据和 执行这两种状态：数据状态是指与移动a g e n t 运行情况相关的数据堆内容：执行的状态 是指移动a g e n t 当前运行时的状态和情况。如运行栈内容、程序计数器等。移动a g e n t 与远程执行不同，移动a g e n t 可以能够不断的从一个网络主机迁移到另一个主机，能够 根据自己的需要自主的进行移动。移动a g e n t 也不同进程迁移，一般来说，进程迁移的 系统不允许进程迁移到哪里和选择什么时候，而移动a g e m 可以带有状态，所以，移动 a g e m 可以根据应用的需要随时可以移动到它想去的地方。移动a g e n t 与a p p l e t 存在差 异，a p p l e t 只能从服务器向客户端单方向的移动，然而移动a g e m 却可以在服务器和客 户之间进行自由双向的移动。 移动a g e n t 还有很多的优点，移动a g e n t 技术通过将服务请求a g e n t 状态迁移到目 标服务器端执行，所以a g e m 可以较少通过网络传输这一中间环节，而直接面对要访问 的服务器资源，从而有效的避免了大量数据的网络传输，大幅度的降低了系统对网络带 宽的依赖。移动a g e n t 可以不需要统一调度，经过用户创建的a g e m 可以异步的在不同 的结点上工作，等到任务完成后再将相应的结果传送给用户。为了完成某项复杂的任务， 用户可以创建多个a g e m ，同时在一个或若干个主机或服务器上运行，形成并行的求解 能力。此外，它还有很好的自治性和智能路由等特性【1 2 】。 1 3 。2 a g e n t 的历史意义及应用 a g e n t 是人工智能领域中的一部分。简单的说，a g e m 是指模拟人类行为与关系、 具有一定智能，并能够自主运行和提供相应服务的实体。a g e n t 与现在流行的软件实体 ( 如对象、构件) 相比，粒度较大，自主性强，智能化较高。随着现代网络技术的发展， 我们可以让a g e m 在网络中移动并执行，完成某些功能，把任务的结果带回来。这就是 移动a g e n t ( m o b i l ea g e n 0 的思想。 3 江南大学硕士学位论文 a g e n t 技术的诞生和发展是人工智能技术( a 0 和网络技术发展的必然结果。随着人 工智能和计算机技术的发展以及万维网( w w w ，w b r l d 晰d ew e b ) 和互联网( i n t e m e t ) 的出 现及发展，集中式的系统已经不能很好的适应科学技术的发展需要。针对这样的情况， 分布式处理等技术( 包括分布式人工智能) 和并行计算应运而生，并在过去的2 0 多年中飞 速的发展。近1 0 年来，a g e n t 技术和多a g e n t 系统与人工智能领域有着密切的关系【1 3 】， 它们的研究成为分布式人工智能研究的一个热点。网络化和智能化的发展促进了a g e n t 技术和多a g e n t 系统的发展。a g e n t 技术在不断的发展，同时可以应用到电子商务、智 能决策、空袭目标模型系统和远程教育等方面，显示出a g e n t 技术的优越性，能够更好 的为我们提供便利，具有很好的研究和发展前景。 1 4 本文的主要工作 移动a g e n t 在迁移过程中，由于网络情况和其他不确定性因素的存在，对最优路径 的选择变得更加复杂和困难。旅行a g e n t 问题( t a p ) 是该研究领域的一个代表性性问题。 本课题重点研究了蚁群算法对该问题的求解性能，针对该算法在求解过程中存在的搜索 时间过长，易于陷入局部最优等缺点，对其提出了两种改进方法。主要工作和结论如下： 在查阅大量文献的基础上，分析了蚁群算法的优点和不足。针对蚁群算法的缺点， 提出了两种改进的方法，即基于任务权重的蚁群算法和根据算法迭代次数的自适应的蚁 群算法。第一种改进方法是把算法的整个运行过程分成三个阶段。第一个阶段，在算法 开始搜索全局最优路径的时候，由于各条路径上信息素浓度很低，此时设置较小的任务 权重阈值为彤，这样，就有较多的移动a g e n t 携带任务的权重值都大于该阈值形，使 移动a g e n t 可以自适应的增大路径上信息素增量和挥发系数p ，相反，有较少的移动 a g e n t 可以自适应的缩小路径上信息素的增量和挥发系数p ，这样可以提高收敛速度。 第二个阶段，改进的蚁群算法经过一定迭代次数后，各条路径上信息素浓度的差异变大， 此时可以增大任务权重阈值为畈，这样就减少了增大路径上信息素增量和挥发系数p 的移动a g e n t 的数目，可以有效避免收敛速度过快，来自适应的扩大搜索范围，提高全 局搜索能力。第三个阶段，随着算法的运行，路径上信息素浓度的差异较大，此时把任 务权重的阈值进一步增大为呢，这样有较少的移动a g e n t 来增大路径上的信息素的增 量和挥发系数p ，最终可以在几个好的最优解中进行筛选，得到一个较好的全局最优解。 第二种改进方法是根据算法迭代次数自适应改进蚁群算法，其主要的思想是根据蚁 群算法的迭代次数动态的，自适应的修改所经过的路径上的信息素更新规则和信息素挥 发系数p 的方法。该方法把算法总的迭代次数分成了三个阶段。第一个阶段，迭代的开 始阶段，各条路径上的信息素浓度很低，所以相应的增大各条路径上的信息素增量和挥 发系数p ，这样可以在提高全局搜索能力的基础上，还可以有效的提高收敛速度。第二 个阶段，经过一定迭代次数后，各条路径上的信息素浓度差异变大，此时自适应的缩小 各条路径上信息素增量和挥发系数p ，这样可以防止该算法陷入局部最优。最后，在前 两个阶段的基础上，全局最优解和近似全局最优解已经被锁定了，此时，自适应的增大 4 第一章绪论 路径上的信息素增量和挥发系数p ，这样可以较大概率的筛选出一个全局最优解或近似 全局最优解，提高该算法的求解能力。为了验证这两种改进算法的性能，均将它们应用 于求解t a p 问题中。经实验证明，本文所提出的改进方法是有效的，改进后的算法其 性能较之原来的蚁群算法有了较大的提高。 1 5 本文的内容安排 第一章，简要的介绍了移动a g e n t 路径选择的问题和蚁群算法和的研究背景和意义， 然后给出了本文的主要工作。 第二章，详细的介绍了基本蚁群算法的原理，给出了该算法的系统模型及实现。接 着介绍了该算法的研究现状和应用。 第三章，阐述了移动a g e n t 的起源、系统结构和关键技术，然后介绍了移动a g e n t 的优点和应用领域。 第四章，针对蚁群算法在求解移动a g e n t 路径选择中的旅行a g e n t 问题( t a p ) 上， 存在的缺陷，结合移动a g e n t 本身和携带任务的特点，提出了基于任务权重的改进蚁群 算法，使移动a g e n t 在求解全局最优解过程中，根据携带任务的权重值，自适应的利用 相应的策略修改路径上信息素更新规则和挥发系数p ，这样可以动态的克服该算法的缺 陷，最后以旅行a g e n t 问题为实验对象，做了大量的仿真实验，对实验结果进行详细的 比较和分析，实验结果证明，本文改进的蚁群算法在求解该问题上具有更强的优势。 第五章，针对蚁群算法在求解该问题在不同过程中存在的缺陷，提出了基于迭代次 数的自适应改进蚁群算法。在算法的不同阶段中，根据算法迭代次数来动态的、自适应 的修改路径上的信息的更新规则和信息素的挥发系数p ，实验结果证明，这样可以有效 的提高全局搜索能力和克服“早滞”现象。 第六章，对全文的内容做出总结和展望，并为以后的工作提出一个新的研究方向。 江南大学硕士学位论文 第二章基本蚁群算法及其应用 蚁群算法( a n tc o l o n ya l g o r i t h m ) 又称为人工蚁群算法，是受到真实蚂蚁行为研究的启 发而提出来的，是一种模拟进化算法。该算法具有稳健性( 鲁棒性) 、正反馈性和分布式 计算等优点，在求解复杂的组合优化问题上有其优势，该方法求解二次分配问题【l 7 】、 t s p 问题和作业调度等问题【1 8 。19 】，取得了较好的成果。该算法已经显示出它在求解复杂 优化问题，特别是离散优化问题方面的优势，是一种很有发展前景的智能计算方法。 2 1 蚁群算法的基本原理 2 0 世纪9 0 年代初期，意大利学者m d o r i g o 等人从生物进化和仿生学角度出发，研 究蚂蚁寻找路径的自然行为，通过大量的观察和研究，提出了蚁群算法【2 呲2 1 。为了更好 的说明蚁群算法的基本原理，针对蚁群搜索食物的过程进行分析。像蜜蜂、飞蛾、蚂蚁 等群居昆虫，尽管单个昆虫的行为很简单，但正是由这些简单的个体所组成的群体，却 能表现出复杂的行为。蚂蚁这类群居的昆虫，尽管没有视觉，经过一段时间后，却能找 到由蚁穴到食物源的最优路径，原因是什么呢? 国内外的仿生学家经过大量细致的观察 研究后发现，蚂蚁个体之间是通过一种称之为信息素( p h e r o m o n e ) 的特殊物质进行信息传 递和交流。在搜索较好路径的过程中，蚂蚁能够在它所经过的路径上留下该物质，而且 其他蚂蚁在运动过程中能够感知这种物质，并以此确定自己的运动方向。所以，这些大 量的蚂蚁组成的蚁群集体的行为便表现出一种信息正反馈的现象：某一条路径上走过的 蚂蚁越多，后来蚂蚁选择该路径的概率就越大。蚂蚁个体之间就是通过这种特殊物质进 行信息的交流，达到搜索食物的目的。 本文用比较形象化的图示，来说明蚂蚁群体的路径搜索原理和机制。下面用 m d o r i g o 所举的例子来说明蚁群系统的原理。 图2 - 1 蚁群系统的初始状态 f i g 2 - 1t h ei n i t i a ls t a t eo fa n tc o l o n y s y s t e m 6 第二章基本蚁群算法及其应用 如图2 1 所示，蚁群系统的初始状态。设彳是蚂蚁的巢穴，e 是食物源，日、c 是 两个绕过障碍物的节点。由于障碍物的存在，蚂蚁只能绕过c 或日由e 到达彳，或由彳 到达e 。各节点之间的距离如图所示。设每个时间单位，有3 0 只蚂蚁由e 到达d 点和 有3 0 只蚂蚁由a 到达b ，蚂蚁在经过的路径上留下的外激素为1 。设外激素的停留时间 为1 。 图2 - 2 蚁群系统的f = 0 时刻的状态 f i g 2 - 2 t h os t a t eo f a n tc o l o n ys y s t e ma tf = 0 如图2 2 所示，蚁群系统在开始时刻的状态。由于路径d h ，d c ，b h ，b c 信息 存在，位于d 和b 的蚂蚁可以随机选择路径。从统计学的角度考虑，可以认为它们以相 同的概率选择d h ，d c ，明，b c 。经过一段时间后，路径b c d 和b i i d 上蚂蚁数目的 差距越来越大，直至大多数蚂蚁选择较短的路径b c d 。 图2 - 3 蚁群系统，= 1 时刻的状态 f i g 2 - 3t h es t a t eo fa n tc o l o n ys y s t e ma tt = 1 7 江南大学硕士学位论文 如图2 3 所示，蚁群系统在t = l 时刻的状态。此时将有2 0 只蚂蚁由d 和b 到达c ， 有1 0 只蚂蚁由d 和b 到达h 。经过一段时间，大量的蚂蚁将会以越来越大的概率选择 路径b c d ，最终完全选择路径b c d ，从而找到由蚁巢到食物源的最短的路径。由此可 见，蚂蚁个体之间的信息交换是一个正反馈机制的过程。在相同的时间和区域内，较短 的路径就会有更大的机率被选择。 蚁群算法是一种随机搜索，智能的仿生算法，与其他的进化算法一样，通过群体的 候选解进行进化，来筛选出全局最优解，此过程包括两个阶段：适应阶段与协调阶段。 在适应阶段中，各候选解就会根据积累的信息不断的调整自身的结构；在第二阶段，候 选解之间通过信息素的交流，希望产生性能更好的解。 蚁群算法作为一种通用型优化方法，与遗传算法一样，不需要任何先验知识，开始 只是随机的选择搜索路径，经过一段时间对算法解的空间的“了解”，搜索变得的有规律， 并发挥其正反馈的性能，直至最终取得全局最优解。蚁群算法对搜索空间的“了解”机制 主要包括以下几方面： ( 1 ) 蚂蚁的记忆。一只蚂蚁搜索过的路径，当下次搜索时就不会再被选择，由此可 以在蚁群算法中建立t a b u ( 禁忌) 列表来存储已经访问的节点，进行模拟。 ( 2 ) 蚂蚁利用信息素( p h e r o m o n e ) 进行相互通信。蚂蚁在选择的路径上会释放一种叫 做信息素的物质，当它们的同伙在进行路径选择的时候，会根据留在路径上的信息素进 行选择，这时信息素就成为蚂蚁之间进行通信的媒介。 ( 3 ) 蚂蚁的集群活动。一只蚂蚁的运动很难到达食物源，但是通过整个蚁群进行搜 索就完全不同。当某些路径上经过的蚂蚁越来越多的时候，在这些路径上留下的信息素 也就越来越多，导致信息素强度增大，所以，该路径被选择的概率随之增大，从而进一 步增大该路径的信息素强度，而当其他某些路径上通过的蚂蚁较少时，路径上的信息素 就会随时间推移而蒸发。因此，模拟这种现象可利用群体的智能来建立路径选择机制， 使蚁群算法的搜索朝向最优解进化。蚁群算法所利用的搜索机制呈现出一种正反馈或自 催化特征，可将蚁群算法模型理解成增强型学习系统。 2 2 蚁群算法系统模型及实现 现在用t s p 问题的分析，来说明基本蚁群算法模型a c a ( a n tc o l o n ya l g o r i t h m ) 以 及是如何实现的。 2 2 i t s p 问题的描述 给定有刀个城市的集合 l ，- ，2 ，” ，以及城市与城市之间环游的花费 c u ( 1 i ”，1 j f ，l ，f j f ) 。t s p 问题是要找到一条经过每个城市一次，并且回到起点的 最小花费的环路。假如将每个顶点看成是图上的节点，花费c 盯为连接顶点形，k 边上 的权值，则t s p 问题就是在具有刀个节点的完全图上找到一条花费最小的h a m i l t o n 回 路。 8 第二章基本蚁群算法及其应用 2 2 2 蚁群算法的描述 设6 ( f ) ( f = 1 , 2 ，m ) 是在f 时刻访问城市f 的蚂蚁个数，设m = b ，( f ) 为全部的蚂蚁 百 个数。在这里，每个简单的蚂蚁有以下几个特征： ( 1 ) 它会根据以城市之间距离和连接边上外激素数量为变量的概率函数，选择下 一个城市( 设乃【d 为r 时刻边p ( f ，) 上的外激素的强度) 。 ( 2 ) 规定蚂蚁只走合法的路径，除非周游完毕，不允许到已访问的城市，有禁忌 表控制( 设表示第k 个蚂蚁的禁忌表，t a b u 。( 5 ) 表示禁忌表中第s 个元素) 。 ( 3 ) 它完成一次周游后，蚂蚁在它每条经过的边上留下外激素 开始搜索时，各条路径上的信息素都相等，设t ，( 0 ) = c ( c 为常熟) 。蚂蚁 k ( k = 1 , 2 ，m ) 在运动过程中，会根据各条路径上的信息量指导转移方向，彤( f ) 表示 在f 时刻蚂蚁k 由位置礴章移到位置，的概率函数。 毒盟j 耐l 嗍妇l f 孑( ，) 刁善( f ) s e a l l o w e d t 0 j 匹a l l o w e d k ( 2 - 1 ) 其中，a l l o w e d k ： o ，l ，m - i 一t a b u ；表示蚂蚁k 下一步可以选择的城市，与现实的 蚁群不同，人工蚁群系统具有特殊的记忆功能，t a b u 。( 七= 1 , 2 ，朋) 用以记录蚂蚁k 当前所 走过的所有城市，集合t a b u 。会随着进化的过程做出动态的调整。气表示主机f 和主机_ ，间 的信息量表达式；是启发式因子，表示蚂蚁从主机f 迁移到主机_ 的期望程度；一般 取主机f 到主机的距离倒数。即协2 石i ，办表示城市f 与城市j 之间的距离。口和卢用 于反映信息素和启发因子在概率计算中的相对重要性。户表示轨迹的持久性，l - p 理解为 随时间推移轨迹衰减性，以前留下的信息素逐渐消失，用参数l - p 表示信息素的消失程 度，经过刀个时刻，蚂蚁完成一次循环，各条路径上的信息量要根据以下公式进行调整： 气= ( ，+ 力) = p 勺( f ) + a r ( 2 2 ) 勺=巧k(2-3) t 表示第k 只蚂蚁在本次循环中留在路径( f ，j ) 上的信息量，乃表示本次循环中 路径( f ，) 上的信息量增量，厶表示第k 只蚂蚁环游一周的路径长度。 t ：詈若第七只蚂蚁在本次循环经过扩 ( 2 4 ) 1 0 否则 a r ，( f ) ，a r ；c t ) ，p 乎c t ) 的表达形式可以不同，要根据具体的问题而定。m d o r i g o 曾给 出了三种不同的模型，分别称为a n t - c y c l es y s t e m 、a n t q u a n t i t ys y s t e m 、a n t - d e n s i t ys y s t e m 模型。 9 江南大学硕士学位论文 在a n t - q u a n t i t ys y s t e m 模型中： 苟： 善若第职蚂蚁在时刻痢f + 1 之间经勘 ( 2 _ 5 ) 1 0 否则 在a n t - d e n s i t ys y s t e m 模型中： f ： 呈若第职蚂蚁在嘤些? 7 “之间经过i ( 2 6 ) 9 10否则 容易看出以上基本算法有几个非常重要的参数j 口、风肛q 以及各路径信息素浓 f i n e r y ( o ) = c ( c 为常数) 。这些数值对于该算法的性能有很重要的影响，目前，一般是 通过反复试验获得该值。它们的区别在于：后两种模型利用的是局部的信息素更新规则， 蚂蚁在完成一个选择( 从一个城市到达另一个城市) 后更新所走过的路径上的信息素，而 前一种模型利用的是整体的信息，蚂蚁在一个循环( 对所有的城市的访问) 后，更新所有 的路径上的信息素。因此，在求解t s p 时，a n t c y c l es y s t e m 模型性能比后面两种模型好， 通常采用它为基本的模型。 算法的终止条件一般有两个：在相邻若干轮循环的最优路径之差小于某个预定值， 或者大于设置的最大迭代次数时停止。基本算法的时间复杂度为o ( n c 幸甩3 ) ，其中r l c 表 示迭代的次数，刀3 表示问题的规模。 2 2 3 蚁群算法步骤 步骤1 ：刀c 卜0 ；( t i c 为迭代步数) 对各，和a r ，进行初始化；将m 只蚂蚁随机的置 于刀个顶点上； 步骤2 ：将各个蚂蚁的初始节点置于当前解集中；对每只蚂蚁k ( k = 1 , 2 ，所) ，按 概率露转移至下一个顶点_ ，；将顶点置于当前解集； 步骤3 ：计算各蚂蚁的目标函数z 。( 七= 1 , 2 ，m ) ；记录当前的最好的全局最优解； 步骤4t 按相应的更新方程修改轨迹上的信息素强度； 步骤5 ：对各边( f ，) ，置f 打卜0 ，刀c ，f = 1 , 2 ，聆，为任务t ，其他重要信息集合，q 1 为，。的 任务工作量；啊2 为完成r ，需要的方法。 移动a g e n t a ，的能力特征表达了口，完成任务的能力。通过定义a ，的完成任务类型和 其他重要信息为约束条件，对a ，进行能力特征建模，构成口，的能力特征。定义以及数 学模型可以用如下公式表示。 定义5t a f = t a ；i = l ，2 ，3 ) ，j = 1 , 2 ，翩，为移动a g e n t a ，的任务类型特征集合。 其中尉：为的移动a g e n t a ，的标识号：黝；为a ，的完成任务类型集合；t a ；为a ，的核心 能力集合。 定义6c a ，= c a ；i = 1 , 2 ，3 ，歹；1 , 2 ，捌，其中c a ；为移动a g e n t a ，的标识号；c 4 ； 为移动a g e n t a f 所能携带任务的总量：c a ；为移动a g e n t a f 完成相应任务所有方法。 1 9 江南大学硕士学位论文 4 2 2 搜索算法流程图 根据任务特征对移动a g e n t 进行匹配搜索的流程图如图4 - 1 表示。 图4 - 1 搜索算法流程图 f i g 4 - 1s e a r c ha 1 9 0 t it h mf l o wc h a r t 第四章基于任务权重的改进蚁群算法 4 2 3 搜索算法的原理及任务权重的数学模型 搜索算法的基本原理就是：以完成子任务f ，的任务类型啊1 为约束条件，通过q 1 与 移动a g e n t 口，所要完成的任务类型黝；进行匹配搜索，构成一个与t t , 1 相匹配的移动 a g e n t 集合a t l l 。然后以子任务的其他重要信息码7 为约束条件，从集合彳互1 中，选 出符合该约束条件的移动a g e n t 集合a t , 2 。在集合彳z 2 中，计算各个移动a g e n t 与该子 任务的匹配程度，最终筛选出完成该子任务匹配程度最大的移动a g e n t ，使之携带