（计算机应用技术专业论文）蚁群算法与遗传算法的融合及其应用研究.pdf

南京珈 u 学院坝j 。斜究生学位论文 摘要 摘要 蚁群算法是近年来新出现的，具有良好寻优效果的一种启发式算法，也是 目前国内外人工智能算法研究的热点。蚁群算法是人们对自然界中蚂蚁群体行 为的研究而提出的一种基于种群的模拟进化算法，它模拟了真实蚂蚁群体搜寻 食物的行为，成为解决n p 完全问题的锐利武器。目前其应用已涉及到诸多领 域，如旅行商问题( t s p ) ，指派问题，工作调度问题等等，并取得了良好的寻 优效果。但目前对于蚁群算法的理论研究和实际应用远不及对遗传算法( g a ) 、 模拟退火( s a ) 等算法的研究成熟，存在诸多需要研究和探索的问题。 遗传算法是一种模拟自然选择和遗传的随机搜索算法，其本身是种通用 的优化算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，最 显著的特点则是隐含并行性和全局解空间搜索。目前，遗传算法愈来愈得到人 们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合 优化、遗传学等领域得到了成功应用。 本文首先描述了两种启发式智能优化算法的机理，论述了蚁群系统和遗传 系统的模型，分别指出了两种算法的特点及存在问题。然后针对人工蚁群系统 存在的问题，引入遗传算法，将两种算法融合，提出遗传蚁群算法( g a a c s ) ， 以安现对搜索空间高效、快速的全面寻优。在实验仿真中将遗传蚁群算法分 i j j 、i 月求解t s p 问题和q o s 组播路由问题，将实验结果与其他启发式算法进行 比较后，- r j 以看出遗传蚁群算法有很好的全局搜索性。文中还分析了遗传蚁群 算法的复杂度、收敛性。 关键词： 遗传算法，蚁群算法，t s p ，q o s 路m 南京邮 u 学院顾i ：研究生学位论文 a b s ”a c c a b s t r a c t a n ta l g o r i t h mi san e wm e t a h e u r i s t i ca l g o r i t h m ，w h i c hc a nf i n dt h eb e s tr e s u l t q u i c k l y t h e r ei sc u r r e n t l yal o to fo n g o i n ga c t i v i t yi nt h es c i e n t i f i cc o m m u n i t yt o e x t e n do ra p p l ya n t - b a s e da l g o r i t h m st od i f f e r e n td i s c r e t eo p t i m i z a t i o np r o b l e m i t m o d i f i e st h eb e h a v i o ro ft r u e a n t sw h e nt h e ys e a r c hf o rf o o d ，a n di tw i l is o l v et h en p c o m p l e t ep r o b l e me f f e c t i v e l y a n ta l g o r i t h mh a sb e e nu s e ds u c c e s s f u l l yi nm a n y f i e l d s ，s u c ha st s p , a s s i g n m e n tp r o b l e m ，j o b s h o ps c h e d u l i n ga n dg r a p hc o l o r i n g t h et h e o r ya n da p p l i c a t i o no fa n ta l g o r i t h ma r en o tm a t u r ea sg e n e t i ca l g o r i t h ma n d s i m u l a t e da n n e a l i n g s ow em u s ts t u d yi tm o r e g e n e t i ca l g o r i t h mi sah e u r i s t i cs e a r c hs c h e m e sb a s e do nt h em o t i o no ft 1 1 e s u r v i v a lo ft h ef i t t e s ta n di n h e r i t a n c e i ti sau n i v e r s a la l g o r i t h m a n dh a sm a n y v i r t u e s ，s u c ha ss i m p l eg e n e t i co p e r a t i o na n dc o d i n gt e c h n o l o g y , g o o ds e a r c h i n g a b i l i t yi nw h o l ea r e a ，a n ds oo n i th a sb e e na p p l i e dt oaw i d ev a r i e t yo fp r o b l e m s ， f o re x a m p l e ：m a c h i n e r ys t u d y , m o d ei d e n t i f i c a t i o n ，i m a g ed i s p o s a l ，n e u r a ln e t w o r k ， a n dc o m b i n a t o r i a lo p t i m i z a t i o n i nt h i sp a p e r w ei n t r o d u c et h et h e o r yo fa n ta l g o r i t h ma n dg e n e t i ca l g o r i t h m f i r s t l y , g i v et h em o d e lo ft h e m ，a n da n a l y z et h ec h a r a c t e r i s t i co ft h e i r s t h e n ，w e p r o p o s ean e wa l g o r i t h m - - g a a c s ，w h o s ec o r e sa r et h a tu s i n gt h eg e n e t i ca l g o r i t h m ( g a ) t oo p t i m i z et h ec o n t r o lp a r a m e t e r so f t h ea c s ( e g n 、p 、p 、q 0 ) a n da p p l y i n g m m a st or o u t i n g t h en e wa l g o r i t h m ( g a a c s 、i sc h a r a c t e r i z e db yg o o dg l o b a l s e a r c hc a p 曲i l i t y w ju s ei tt os o l v et s p ( t r a v e l i n gs a l e s m a np r o b l e m ) a n dq o s m u l t i c a s tr o u t i n gp r o b l e m s i m u l a t i o nr e s u l t ss h o wt h a tg a a c si ss u p e r i o rt o c o n v e n t i o n a lh e u r i s t i ca l g o r i t h m si nq u a l i t ya n de m c i e n c y k e y w o r d s ： g e n e t i ca l g o r i t h m ，a n tc o l o n ya l g o r i t h m ，t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) q u a l i t yo fs e r v i c e ( q o s ) r o u t i n g i i 南京邮电学院学位论文独创性声明 7 6 5 1 3 3 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 王燃日期：塑：垫缰 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名： 至奁篮 导师签名： 汪丝! 厶日期：砬：结盛 南京邮i u 学院坝l 研究生学位论文i 吉 引言 课题背景： 优化技术是用于求解各种工程问题优化解的应用技术，对提高生产效率， 节省资源具有重要的作用。工程领域中的优化问题一般属于n p 完全问题，简 单地说，如果一个问题无法在多项式时问内被确定性图灵机解决，我们称它为 n p 完全问题。而解决n p 完全问题有两种方法：一个是求具有指数复杂度的精 确解；另一个是应用启发式算法求次优解。求精确解需要做大量的工作，不适 合实际的应用。一个合理的目标是寻找问题的一个近似算法，使我们能在一个 低阶多项式时阳j 内找一个“接近”最优的解。所以，目前解决n p 完全问题一般采 用启发式算法找出近似解。 蚁群算法( a n tc o l o n ya l g o r i t h m ) 【l 】是新近提出的一种全新的优化算法，目前 己应用于求解旅行商问题( t s p ) 、指派问题( a s s i g n m e n t p r o b l e m ) 、j o b s h o p 调度 问题等，并取得了较好的实验结果。较强的鲁棒性、寻径过程的并行性以及易 于与其他启发式算法结合的特点，使得蚁群算法吸引了越来越多研究者的注意， 不断对其进行更深入的研究，并用其来解决实际问题。目前的研究表明，蚁群 算法在求解复杂优化问题方面，尤其是离散优化问题，比其他进化算法具有一 定的优势。但是其缺点也比较明显：参数缺乏理论指导，易于陷入局部较优解。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 【2 j 【3 f 5 1 是美国m i c h i g a n 大学的j o h n h o l l a n d 教授等人于1 9 7 5 年提出的模拟自然界中生物遗传机制的随机搜索算法。 g a 在本质上是一个群体迭代算法，它从一组随机的初始群体出发，由目标函 数( 适应度函数) 对其进行评价，根据“优胜劣汰”的竞争原则，通过选择、 交叉、变异等优化过程，产生性能更优的下一代群体，不断重复，直到获得满 意的结果。g a 的特点是：具有全局搜索能力和潜在的并行型，具有较强的鲁 棒性，汁算过程简单，能很好地解决丌发最优解和探寻搜索空问的矛盾，具有可 扩展性，易于和其它算法结合。但g a 算法对于系统中的反馈信息利用不充分， 当求解到一定范围时会做大量的无效迭代。 目前，将蚁群算法与遗传算法相融合来解决n p 完全问题，已取得了一些成 果5 儿q 。文献【6 】【7 】，采用遗传算法对蚁群算法( a c s ) 的三个参数( b 、p 、 南京邮 u 学院颁t - t 0 究生学位论文 j l 苦 q 。) 进行优化，并在t s p 问题中进行验证。出于文中对a 取默认值，b 、p 、 q o 的取值是相对于q 的一个比值，所以无法实现a c s 四个参数( a 、1 3 、p 、 q 。) 组合的全局寻优，也就无法求得n p 完全问题的全局最优解。 本文对遗传算法和蚁群算法的机理和性能进行了研究，将两种算法融合， 提出一种遗传蚁群算法g a a c s ，设计思想是采用遗传算法来优化蚁群算法中 的四个控制参数( a 、1 3 、p 、q o ) ，并运用m m a s 改进传统蚁群算法的寻径行 为，实现对搜索空间高效、快速的全面寻优。本文将遗传蚁群算法用于求解t s p 问题及q o s 路由问题，都获得了较成功的应用。 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 是组合优化领域中一个著名 的经典n p 完全难题。本文应用g a a c s 求解t s p 问题，并和采用基本蚁群算 法求解t s p 问题的仿真实验结果进行对比验证了算法的有效性和收敛性。 q o s 组播路由技术是网络多媒体信息传输的关键技术之一，其目的就是在 网络中寻找一条组播路由，满足用户对线路的带宽、延迟、时延抖动、费用的 要求，即向用户提供端到端的服务质量保证。基于多个不相关可加度量的q o s 组播路由问题是n p 完全问题”3 ，目前采用启发式智能算法求解。为了进一步扩 大遗传蚁群算法( g a a c s ) 的应用范围，本论文应用g a a c s 求解q o s 组播路 由问题。在仿真实验中通过与遗传算法的求解结果比较，可看出遗传蚁群算法 具有更强的有效性和更好的收敛性。 论文组织： 全文共分为四个章节，内容组织如下： 第章，概述智能优化算法研究的现状与存在问题，介绍了模拟退火算法、 祭忌搜索算法、遗传算法、蚁群算法等启发式智能算法的理沦原理、系统模型、 特点及目自u 的研究现状和应用领域。 第二章，详细介绍遗传算法和蚁群算法的理论原理和系统模型，并对其优 缺点进行了分析。提出了一种将两种算法融合形成的遗传蚁群算法，并详细介 绍了新算法的理论模型。 第三章，介绍遗传蚁群算法在t s p 问题中的应用。通过求解t s p 问题，分 析了新算法的有效性c 复杂性以及收敛性能。 第四章，应用遗传蚁群算法解决通信领域中的优化问题( q o s 组播路由) 。 南京邮电学院顾i ：研究生学位论文引言 文章给出了详细的算法步骤和流程。并将应用遗传蚁群算法求得的解与遗传算 法的求解结果进行比较，以分析新算法的优势。 南京f 【f i 乜学院城j 研究生学位论文第一章智能优化算法 ! j i _ 究的现状j 存 的问题 第一章智能优化算法研究的现状与存在的问题 1 1 问题的提出 目前科学技术f 处于多学科相互交叉和渗透的时代，特别是计算机科学与 技术的迅速发展与普及，从根本上改变了人类的生产与生活。同时，随着人类 生存空间的扩大以及认识与改造世界范围的拓宽，人们对科学技术提出了掰的 更高的要求。其中，对于高效的优化技术和智能计算的要求f l 益迫切。 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。 作为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得 到迅速推广和应用，比如：系统控制、人工智能、模式识别、生产调度和计算 机工程等。实现生产过程的最优化，对提高生产效率与效益、节省资源具有重 要的作用。同时，优化方法的理论研究对改进算法性能、拓宽算法应用领域、 完善算法体系同样具有重要作用。因此，优化理论与算法的研究是一个同时具 有理论意义和应用价值的重要课题。鉴于工程问题的复杂性、约束性、非线性、 建模困难等特点，寻求一种适合于大规模并行且具有智能特性的算法己成为相 关学科的重要研究目标和引人注目的研究方向。 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传 算法、进化规划、模拟退火、禁忌搜索及其混合优化策略等，通过模拟或揭示 某些自然现象( 过程) 而得到发展，其思想和内容涉及数学、物理学、生物进 化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路 耳| i 手段。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了 浚领域的研究热潮，且在诸多领域得到了成功应用。在优化领域，由于这些算 法构造的直观性与自然机理，因而通常被称作智能优化算法( i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ) ，或称现代启发式算法( m e t a h e u r i s t i ca l g o r i t h m s ) 。 虽然这些方法是由不同的人在不同的时期发展起来的，但他们都来源于自 然界。自然界始终是人类灵感的重要来源。人工神经网络、模拟退火算法、遗 传算法、蚁群算法等的研究方向都起源于对自然界或过程的模拟。所谓优化算 法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途 南京邮电学院硕士研究生学位论文第一章智能优化算法研究的现状与存在的问题 径或规则来得到满足用户需求的问题的解。而这些来自自然界的现代启发式算 法都属于改进型的优化算法，即从任一解出发，对其邻域的不断搜索和当前解 的替换来实现优化。根据搜索行为，它又可以分为局部搜索法和指导性搜索法。 局部搜索法，以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前 解的状态作为下当前解的爬山法；接受当前解邻域中的最好解作为下一当前 解的最陡下降法等。指导性搜索法，即利用一些指导规则来指导整个解空间中 对优良解的探索，比如模拟退火算法、遗传算法、禁忌搜索、神经优化算法和 混沌搜索等。 局部搜索算法是基于贪婪思想利用邻域函数进行搜索的，它通常可描述为： 从一个初始解出发，利用邻域函数持续地在当前解的邻域中搜索比它好的解， 若能够找到如此解，就将之作为新的当前解，然后重复上述过程，否则结束搜 索过程，并以当前解作为最终解。可见，局部搜索算法尽管具有通用易实现的 特点，但搜索性能完全依赖于邻域函数和初始解，邻域函数设计不当或初值选 取不合适，则算法最终的性能将会很差。同时，贪婪思想无疑将使算法丧失全 局优化的能力，也即算法在搜索过程中无法避免陷入局部极小。因此，若不在 搜索策略上进行改进，那么要实现全局优化，局部搜索算法采用的邻域函数必 须是“完全的”，即邻域函数将导致解的完全枚举。而这在大多情况下是无法实 现的，而且穷举的方法对于大规模问题在搜索时间上是不允许的。 鉴于局部搜索算法的上述缺点，智能优化算法，如模拟退火算法、遗传算 法、禁忌搜索、蚁群算法、神经网络和混沌搜索等，从不同的角度利用不同的 搜索机制和策略实现对局部搜索算法的改进，来取得较好的全局优化性能。 f 面将介绍些常用的智能启发式优化算法。 1 2 智能优化算法研究的现状与存在的问题 1 2 1 模拟退火算法 模拟退火算法( s i m u l a t e d a n n e a l i n g ，s a ) 1 3 】1 4 l 的思想最早是由m e t r o p o l i s 等( 1 9 5 3 年) 提出的，1 9 8 3 年k i r k p a t r i c k 等将其用于求解组合优化，其目的在 于：为具有n p 复杂性的问题提供有效的近似求解算法；克服优化过程陷入局 南京邮电学院颂 ：研，生学位论文 第一章智能优化算法研究的现状与存在的问题 部极小：克服初值依赖性。s a 算法是基于m e n t ec a r l o 迭代求解策略的一种随 机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题 之间的相似性。模拟退火算法由某一较高初温开始，利用具有概率突跳特性的 m e t r o p o l i s 抽样策略在解空间进行随机搜索，伴随温度参数的不断下降重复抽样 过程，最终得到问题的全局最优解。 理论上，s a 算法的参数只有满足算法的收敛条件，才能保证实现的算法依 概率1 收敛到全局最优解。然而，由s a 算法的收敛理论知，某些收敛条件无 法严格的实现，b p 使某些收敛条件可以实现，但也常常会因为实际应用的效果 不理想而不被采用。因此，至今s a 算法的参数选择依然是一个难题，通常只 能依据一定的启发式准则或大量的实验加以选取。 在确保一定要求的优化质量基础上，提高模拟退火算法的搜索效率( 时间 性能) ，是对s a 算法进行改进的主要内容。可行的方案包括：设计合适的状态 产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性； 设计高效的退火历程；避免状态的迂回搜索；采用并行搜索结构；为避免陷入 局部极小，改进对温度的控制方式；选择合适的初始状态；设计合适的算法终 止准则。此外，我们还可以通过增加某些环节来实现对模拟退火算法的改进。 改进方法主要包括：增加升温或重升温过程；增加记忆功能；增加补充搜索过 程；对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而 非标准s a 的单次比较方式等等。现己提出的改进策略主要有：并行多邻域搜 索，平滑优化曲面形状，引进重升温、商抽样等高级技术等。 由于算法的一些环节无法在实际设计算法时实现，因此s a 算法往往得不 到全局最优解，或算法结果存在波动性。许多学者试图给出选择“最佳”s a 算 法参数的理论依据，但所得结论与实际应用还有一定距离，特别是对连续变量 函数的优化问题。1 7 1 前，s a 算法参数的选择仍依赖于一些启发式准则和待求问 题的性质。算法的实验性能具有质量高、初值鲁棒性强、通用易实现的优点。 但是，为寻到最优解。算法通常要求较高的初温、较慢的降温速率、较低的终 止温度以及各温度下足够多次的抽样，因而模拟退火算法往往优化过程较长， 这也是s a 算法最大的缺点。因此，要真正取得质量和可靠性高、初值鲁棒性 好的效果，克服计算时间较长、效率低的缺点，并适用于规模较大的问题，尚 南京邮电学院预土研究生学位论文 第一章智能优化算法研究的现状与存在的问题 需进行大量的研究工作。 1 2 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，g a ) t 2 1 1 3 】 4 l 【5 】是一种模拟自然选择和遗传的 随机搜索算法，由j h o l l a n d 于1 9 7 5 年受生物进化论的启发而提出的。它是以 达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物 遗传进化主要在染色体上，子代是父代遗传基因在染色体上的有序排列”为基 础，模拟生物界进化过程的。其基本形式要求有一个“染色体”表示用来对参 数空间编码、一个适度函数用于估计所有的染色体、一组遗传操作用于产生新 的染色体和一组概率用于控制遗传操作。算法通过“染色体”群的一代代不断 进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境”的个体，从 丽求得问题的最优解或满意解。 g a 算法，其编码技术和遗传操作比较简单，优化不受限制条件的约束，而 其两个最显著特点则是隐含并行性和全局解空间搜索。目前，随着计算机技术 的发展，g a 愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、 神经网络、优化控制、组合优化、遗传学等领域得到了成功应用。 遗传算法的主要目的，是设法产生或有助于产生优良的个体成员，且这些 成员能够充分表现出解空间中的解，从而使算法效率提高并避免收敛早熟。但 在实际应用遗传算法时，往往出现早熟收敛和收敛性能差等问题。目前的改进 方法，大都针对基因操作、种群的宏观操作、基于知识的操作和并行化g a 进 行。 对于求解有约束优化问题，目前的处理方法主要有三种：第一，把问题的 约束在“染色体”的表示形式中体现出来，并涉及专门的遗传算子，使“染色 体”所表示的解在g a 运行过程中始终保持可行性。这种方法最直接，但适用 领域有限，算子的设计比较困难。第二，在编码过程中不考虑约束，而在g a 运行过程中通过检验解的可行性来决定解是否被弃。这种方法一般只适用于求 解简单约束问题。第三，采用惩罚的方法来处理约束越界问题。到目前为止， 采用g a 求解高维、多约束、多目标的优化问题仍是一个没有很好解决的课题， 它的进展将会推动g a 在许多工程领域的应用。 南京邮电学院颂【研究生学位论文 第一章智能优化算法研究的现状 j 存在的问题 1 2 3 禁忌搜索算法 禁忌搜索( t a b us e a r c h 或t a b o os e a r c h ，t s ) 【3 1 1 4 】的思想最早由g 1 0 v e r ( 1 9 8 6 ) 提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类 智力过程的一种模拟。t s 算法通过引入一个灵活的存储结构和相应的禁忌准则 来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多 样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，t s 是又一 种搜索特点不同的现代启发式( m e t a - h e u r i s t i c ) 算法。迄今为止，t s 算法在组 合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功。 近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 禁忌搜索最重要的思想是标记对应已搜索到的局部最优解的一些对象，并 在进一步的迭代搜索中尽量避_ 丌这些对象( 而不是绝对禁止循环) ，从面保证对 不同的有效搜索途径的探索。 简单t s 算法的基本思想是：给定一个当前解( 初始解) 和一种邻域，然后 在当前解的邻域中确定若干候选解：若最佳候选解对应的目标值优于“b e s ts o f a r ”状态，则忽视其禁忌特性，用其替代当前解和“b e s ts of a r ”状态，并将相 应的对象加入禁忌表同时修改禁忌表中各对象的任期；若不存在上述候选鳃， 则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的 优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期。如此重 复上述迭代搜索过程，直至满足停止准则。 与传统的优化算法卡日比，t s 算法的主要特点为： 搜索过程中可以接受劣解，冈此，具有较强的“爬山”能力； 新解不是在当前解的邻域中随机产生，或是优于“b e s ts of a r ”的 解，或是非禁忌的最佳解，因此选取优良解的概率较大。 于t s 算法具有灵活的记忆功能和藐视准则，并且在搜索过程可以接受 劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空 恻的其它区域，从而增强获得更好的全局最优解的概率，所以t s 算法是一种局 部搜索能力很强的全局迭代寻优算法。但是，t s 也有明显的不足，如： 对初始解有较强的依赖性，好的初始解可使t s 在解空间中搜索到好的 解，而较差的初始解则会降低t s 的收敛速度。 南京怫 也学院碗l ：t i j 究生学位论文第一章智能优化算法研究的现状1 j 存在的问题 迭代搜索过程是串行的，仅是单一状态的移动，而并非并行搜索。 为了进一步改善禁忌搜索的性能，一方面可以对禁忌搜索算法本身的操作 和参数选取进行改进，另一方面则可以与模拟退火、遗传算法、神经网络以及 基于问题信息的局部搜索相结合。 1 2 4 蚁群算法 蚁群算法( a n t a l g o r i t h m ，a a ) 的思想最早是由意大利学者m a r c o d o r i g o 等人提出，它是种源于生物世界的仿生类进化算法。该算法模仿自然界中蚂 蚁觅食的行为，参加寻径的蚂蚁通过留在链路上的信息素交互来选择路由，从 而达到逐步收敛于全局最优解的目的。其主要特点是：本身是一个增强型学习系 统，具有分布式的计算特性，具有很强的鲁棒性，易于与其它优化算法融合。 但是蚁群算法在解决大型优化问题时，存在搜索空间和时间性能上的矛盾，易出 现过早收敛于非全局最优解以及收敛初期信息素匮乏。求解速度慢、计算时间 过长的弱点。 m a r c od o r i g o 等人提出基本的蚁群算法【9 1 1 1 0 1 后不久又提出了更一般性的 蚁群算法，称之为a n t qs y s t e m 【l q ot h o m a s 等人提出的m m a s ( m a x m i na n t s y s t e m ) 1 2 1 ，其基本思想是仅让每一代中最好的个体所走路径上的信息素进行调 整，以加快收敛速度；通过引入 - 分支因子，对各条链路上信息素的值进行限 制和动态调整，有效防止了过早停滞现象。此外，文献 1 3 将蚁群算法与变异因 子有机结合，根据寻径情况的不同调整消逝因子的大小，结果表明这种方法可 以大大提高蚁群算法的搜索效率。文献 1 4 1 通过引入遗忘因子，可以做到对以往 知识的慢慢遗忘，因而能够强化后来学习得到的“知识”，不致过早出现停滞现 象，有利 ：发现更好的解。所有这些研究，都在定程度上提高了螭本蚁群算 法的搜索效率。 蚁群算法自产生以来表现出强大的生命力，较之以往的启发式智能优化算 法不论是在搜索效率上，还是在算法的时i 复杂度方面都取得了令人满意的 效果。目前广泛应用于组合优化、人工智能等多个领域。较强的鲁棒性、寻径 过程的并行性以及易于与其他启发算法结合的优越性，使得蚁群算法吸引了越 来越多研究者的注意，不断对其进行更深入的研究。初步的研究表明，蚁群算 6 南京邮电学院颂i ：t i j f 究生学位论文第一章智能优化算法研究的现状1 j 存a ：的问题 法在求解复杂优化问题方面，尤其是离散优化问题，比目前广泛应用的遗传算 法、模拟退火算法等进化算法具有一定的优势。 目前研究和应用蚁群算法的学者主要集中在比利时、意大利、英国、法国 等欧洲国家，同本和美国近两年也开始启动对蚁群算法的研究。国内的研究则 稍晚，1 9 9 8 年未才开始有少量的研究报道，而且也基本局限于t s p 问题。但近 两年出现了许多利用蚁群算法求解工程性问题的文章。在文献【1 5 】和【1 6 中分别 采用蚁群算法求解a t m 网的路由问题和电话网路由问题。 蚁群算法是种新型的模拟进化算法，对它的研究才刚刚开始，虽然蚁群 算法思想在启发式智能方法范畴内已经逐渐成为一个独立分支，但远未象遗传 算法、模拟退火算法等算法那样形成系统的分析方法，具备坚实的数学基础， 缺乏理论的支持，有许多问题仍有待于进一步的研究，如算法的收敛性、理论 依据等。但随着研究的深入，相信蚁群算法也将会同其他启发式算法一样，获 得越来越多的应用。 南京| l l i f 电学院倾卜研究生学位论文第二章遗传蚁群算法的优化机理 第二章遗传蚁群算法的优化机理 2 1 蚁群算法的优化机理及模型描述 2 1 1 基本蚁群算法( a a ) 的优化机理 蚁群算法是人们受自然界中真实的蚂蚁群体行为的启发而提出的一种基于 种群的模拟进化算法，它模拟了真实蚂蚁群体搜索食物的行为。在自然界中， 蚂蚁是一种群居昆虫，单个个体的行为比较简单，但由简单的单个个体所组成 的蚂蚁群体却表现出极其复杂的行为，能够完成复杂的任务。除此之外，蚂蚁 还能够适应环境的变化，比如：在蚁群运动线路上突然出现障碍物的时候，蚂 蚁能够很快地做出调整，重新找到最优路径。经过大量的实验研究表明蚁群 之所以表现出复杂有序的行为，个体之闯的信息交流与相互协作起着重要的作 用。蚂蚁在运动过程中，会在路径上释放出一种特殊的物质，我们称之为信息 素( p h e r o m o n e ) ，该物质随着时间的推移会逐渐挥发消失。运动中的蚂蚁能够 感知这种物质的存在及其强度，并以此了解蚂蚁的运动方向。蚂蚁倾向于朝着 该信息素强度高的方向移动，后面的蚂蚁可根据前面走过的蚂蚁所遗留下来的 信息素值来选择其下一步要走的路径。一条路径上的信息素值越高，蚂蚁选择 这条路径的概率就越大，这样就构成了一个学习信息的正反馈过程。最优路径 i ：的信息素浓度越来越大，而其它的路径上信息素的浓度将会随着时闻的推移 而消失，蚂蚁个体之问就是通过这种信息的交流来达到寻找最优路径的目的。 下面介绍真实蚁群寻找最优路径的原理川l 。 ，如图2 1 所示。 南京邮电学院硕士研究生学位论文第二章i 传蚁群算法的优化机理 “) 蜘精状毒( b ) 中再状i 矗 ( c 】中间状态 ( d ) 舟睇冬状i 蠡 图2 1 蚂蚁寻找最优路径的示意图 最初，如图2 1 ( a ) 所示，蚂蚁们来到一个分支路口，要决定该往哪边走， 由于初始时没有什么线索可供参考，它们就以相同的概率随机地选择路径。可 以这样认为，最终有一半的蚂蚁选择上边一条路径，而剩下的另一半走下条路 ( 如b 所示) ，并在途中留下信息素，同样的现象发生在从左向右和从右向左两 个行进方向的蚂蚁身上。假设蚂蚁具有相同的运动速度，路径上信息素 p h e r o m o n e 的更新( 包括挥发和加重) 程度与选择它的蚂蚁所走的路径总长度 相关。即蚂蚁在较短路径上( 下条路 所留下来的p h e r o m o n e 的强度较大。由 于蚂蚁选择p h e r o m o n e 强度大路径的概率大，因此后来的蚂蚁会渐渐地趋向于 选择下条路( 如c 所示) ，这就导致该路径上p h e r o m o n e 强度继续加大，而被加 大p h e r o m o n e 强度的路径会吸引更多的蚂蚁，从而形成了正反馈。经过一段时 恻后，两条路径上的p h e r o m o n e 的强度会有明显的区别，这就使新来的蚂蚁选 择较短路径( 下条路) 的概率越来越大，最终，绝大多数的蚂蚁将选择这条较 短的路径( 如d 所示) 。 蚁群算法中寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的 行为提出的，即让寻径蚁群根据路径上类似于p h e r o m o n e 的数字信息素的大小 ( 或强度) 选择路径，并在所经过的路径上留下数字信息素，随着时间的推移， 最优路径上的数字信息素值就会越来越大，从而选择这条最优路径的概率也就 越来越大，最终几乎所有的寻径蚁群都将选择这条路径。 下面以求解t s p 问题为例。为蚁群算法建立算法模型。 南京邮电学院硕士研究生学位论文 第二章遗传蚁群算法的优化帆理 2 1 2 基本蚁群算法模型 给定已知节点为n ，寻径蚂蚁的数量为m ，每个蚂蚁的行为应符合下列规律， 即蚁群算法的状态转移规则和信息素更新规则研： 根据路径上的信息素浓度，以相应的概率来选取下一个节点： 选择下一个城市的根据主要有两点： q ( t 卜一t 时刻连接节点i 和j 的路径上残留的信息浓度，即由算法本身提供 的信息； 1 1 “由节点i 转移到节点j 的启发信息，该启发信息是根据要解决的问题 给出的，由一定的算法实现。一般取t l i j = 1 d i j ( d i i 表示节点i ，j 间的距离，m 在这里可以称为能见度信息) 。 那么，蚂蚁选中某个节点的可能性是根据问题本身所提供的启发信息和从 蚂蚁目前所在节点到目标节点路径上残留的信息量的函数来决定的。也即t 时 刻位于节点i 的蚂蚁k 选择城市j 为目标的概率是： j 毒磐謦粤尝坍。z ( i ) 】 p j ) = 磊r 【顼i ，j ) r 圳p 八u 1 ( 2 1 ) b o l h e 刑汝 式中a 残留信息的相对重要程度； b 一能见度的相对重要程度； j k ( i ) c 0 ，l ，2 ，n 1 ) 表示第k 个蚂蚁下一步可以选择的节点集； 路径上信息素浓度的更新； 随着时间的推移，以前留下的信息逐渐消逝，用参数p 表示信息素消逝的 程度。当蚂蚁完成一次任务，即完成一次循环后，蚂蚁在所走过的路径上会释 放相应浓度的信息素，并更新所有路径上的信息素浓度。 为了避免残留信息过多，引起启发信息被淹没的问题在每一只蚂蚁完成 对节点的访问后，必须对残留信息进行更新处理，对旧的信息进行削弱。同时 将最新的蚂蚁访闯路径信息加入。相应边上的信息素浓度为 f ( i ，j ) 4 - - 0 一纠f ( i ，j ) + p k i ，j ) ( 2 2 ) 其中p _ 胄息素的消逝因子，为二个取值范围在0 到l 之间的常数系数； 南京邮电学院硕士研究生学位论文 第二章遗传蚁群算法的优化机理 则1 一p 被称为残留信息被保留的部分，即在时间t 到t + l 之间挥发后剩下 的信息素系数； t 。u 第k 个蚂蚁在时间t 到什l 之间，在路径链路( i ，j ) 上增加的信息 素变量。 基本蚁群算法的流程图如图2 2 ，n c m a ) ( 表示蚂蚁寻径最大循环次数。 图2 2 基本蚁群算法的流程图 2 1 3 蚁群算法( a c s ) 与m m a s 蚁群算法a c s ( a n tc o l o n ys y s t e m ，a c s ) 1 1 0 l 是1 9 9 6 年g a m b a r d e i i a 和 d o r i g o 提出来的。它与基本蚁群算法( a a ) 的区别主要在于： 1 ) 蚂蚁在寻找最佳路径的过程中采用局部信息对信息素浓度进行调 整： 南京邮电学院硕士研究生学位论文 第二章遗传蚁群算法的优化帆型 2 ) 在所有进行寻优的蚂蚁结束路径寻优后，采用全局信息来调整信息 素的浓度，而且只对过程中发现的最好路径上的信息素浓度进行加 强： 3 )蚂蚁的状态转移规则( s t a t et r a n s i t i o nr u l e ) 有了改进。在a c s 中， 每个蚂蚁根据状态转移规则来选择下一跳节点，而信息素值的更新 有全局更新和局部更新两种规则，使用两种信息素的更新规则可以 取得更快的全局优化结果。 下面分别介绍这三种规则： ( 1 ) 信息素的全局更新规则 当m 只蚂蚁成功的完成一次寻径行为时，选择出目标函数值最小的一个路 由，用来完成全局信息素的更新。以使较优解保留下来，影响后继的蚂蚁行为。 这样就达到了较快收敛于最优解的目的。i 、j 是两个相邻的节点，则有 f ( i ，j ) 卜( 1 一p ) r ( i ，j ) + p x a r ( i ，j ) ( 2 3 ) 其中，o p l ，l k 是目标函数，l b 。是最佳目标函数值， 毗j ) = 警予“：抓i j ) g f 0 蚰卜伽卜脚 u o t t l e r w l s e q 为常数系数，用以调整r 的大小。 ( 2 ) 信息素的局部更新规则 对于第k 只蚂蚁，如果节点i 、j 是它所选择路径上的两个相邻节点，则有 f ( i ，j ) 卜( 1 一p ) r ( i ，j ) + p a r ( i ，j ) ( 2 。4 ) 否则，不更新。其中，0 p o ) 是能见度的相对重要性。 j k ( i ) c 0 ，1 ，2 ，n 一1 ) 表示第k 个蚂蚁下一步可以选择的节点集 叩( i ，j ) = 去，c o s t ( i d ) 表示节点i 、j 间的费用大小。 c o s ，1 1 ，1 j 这三种规则是蚁群算法中的根本选择准则。 m m a s ( m a x - m i na n ts y s t e m ) 算法是比利时学者t h o m a ss t u z z l e 托1 提出的， 它对基本蚁群算法( a a ) 也进行了3 点改进： ( 1 ) 为了更加充分地进行路径寻优，各路径上的信息素初值设为最大值 m a x ； ( 2 ) 一次寻径结束后，只有最优路径的蚂蚁才能进行信息素的修改增加， 这与a c s 模型的调整方法相似： ( 3 ) 为了避免算法过早收敛于非全局最优解，将各路径上的信息素浓度限 制在 m ，t 。 之间，超出这个范围的值被强制设为t 或者t 。 本文中采用m m a s 算法对基本蚁群算法进行改进。 2 1 4 蚁群算法的特点及存在的问题 基本蚁群算法系统本身是一种f 反馈机制或者称为增强型学习系统，能够 充分应用原有信息，通过信息素的不断更新达到最终收敛于最优路径的目的。 基本蚁群算法具有以下特点： l 、 分布式计算：蚁群算法是一种基于种群的进化算法，具有并行性。 2 、 较强的鲁捧性：对其基本模型稍加修改，便可应用于其他问题。 3 、 易于与其他算法结合：易于与多种启发式的算法融合，以改进算 法的性能。 南京邮f 乜学院预士研究生学位论文 第二章遗传蚁群算法的优化机理 4 、是一种全局优化方法，不仅可用于求解单目标优化问题，还可用 于求解多目标优化问题。 众多研究表明蚁群算法具有很强的寻优能力，这是因为该算法不仅具有正 反馈机制，在一定程度上可以加快进化过程：而且是一种本质并行的算法，不 同个体之间不断进行信息交换和传递，从而能够相互合作，有利于加快寻优过 程。 虽然蚁群算法获得了一些成功的应用，但也存在一些问题。如：与其它算 法相比，该算法需要较长的搜索时削；而且该方法容易出现停滞现象，即搜索 过程进行到一定程度后，几乎所有的个体所发现的解完全一致，从而不能对解 空间进行全面的搜索，不利于发现更好的解。此外，蚁群算法的参数选择缺乏 理论的支持。比如蚁群算法中的四个控制参数( n 、b 、p 、q 0 ) 的选取与网络 本身有关，取较大的值可加快算法的收敛速度，但是过快的收敛又会导致得到 的是局部最优解，所以不同的网络对应着不同的参数组合。通常算法中a 、b 的取值在0 0 5 - o 2 之内，n c m a x ( 循环次数) 的取值在几到一百之内，p 应根 据分泌物初始强度t0 及q 进行取值，保证p 与q 之商和分泌物初始强度t0 相 差不多。本文的任务是在一定的网络拓扑结构下，采用遗传算法求得最佳参数 组合，并将其用于网络中路由求解过程。 2 2 遗传算法的优化机理与模型描述 2 2 1 遗传算法的优化机理 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 【2 5 l 是借鉴生物界的进化规律( 适 者生存、优胜劣汰、遗传机制) 而产生的一种随机搜索算法。它由美国的j h o l l a n d 教授19 7 5 年首次提出，其主要特点是直接对结构对象进行操作，不存在求导和 函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化 的寻优