（计算机应用技术专业论文）连续优化的蚁群算法改进及应用.pdf

济南大擘硕士学位论文 摘要 蚁群优化( a n tc o l o n yo p t i m i z a t i o n , 简称a c o ) 是一种新兴的启发式模拟进化 算法。人们对蚁群算法做了很多改进和扩展，在很多领域获得了广泛应用。 但是蚁群算法仍然存在一些问题，如算法收敛速度慢、搜索时闯长、易陷入 局部最优等缺点。由于蚁群算法在形式上不大适于解决连续优化问题，在总结和 分析已有研究成果的基础上，对蚁群算法求解连续空间的优化问题进行了一些改 进。主要包括： ( 1 ) 提出了种用蚁群算法解决连续函数的算法框架，并在此基础上给出 了蚁群算法在优化连续和离散问题的统一描述形式。蚁群算法比较适合于解决离 散问题如静态和动态组合优化问题，但是不方便解决连续优化问题。根据蚁群算 法在解决连续优化问题时存在的问题，提出了一种描述方案：将连续问题离散化 处理，借鉴蚁群算法解决t s p 问题的思路来优化连续函数问题；同时加入变异 操作，以获得种群的多样性，在一定程度上体现连续性的要求。该方案不仅从功 能上实现了蚁群算法的优化连续空间问题，而且从描述形式上使蚁群算法应用于 离散问题和连续问题时获得了基本统一方式。 ( 2 ) 为了提高蚁群算法解决连续问题的性能，提出了一种新的杂合优化算 法即将蚁群算法与分布估计算法相融合，主要是针对种群的多样性。该算法不仅 避免了交叉和变异操作带来的参数估计问题，而且通过计算种群个体的分布密度 函数从而自适应地改变信息素浓度，从而提高了算法的优化性能。 ( 3 ) 介绍了问题复杂性描述的涵义、基本思想、并将其引入现代优化算法 中，进一步提高算法解决复杂问题的能力。极值个数、极值大小分御和极值区域 半径分稚是反映问题复杂程度的几个基本标志，也是问题复杂性描述的基本因 子。它们的获得在解决某些问题尤其是复杂问题如高维连续函数的优化上起到了 一定引导和启发作用，为减少盲目搜索，提高搜索效率起到一定的作用。提出了 一种基于问题复杂性的优化思路，通过引入问题复杂性分析的若干因子，以提高 算法的搜索效率，降低重复搜索的概率，从而提高算法优化复杂问题的性能。 关建可：蚁群算法：连续函数；分布估计算法；概率密度函数：问题复杂性 a b s t r a c t a c 0 ( a n tc o l o n yo p t i m i z a t i o n ) i san 删e n l i g h t e n i n ga n ds i m u l a t e de v o l u t i o n a l g o r i t h m ，w h i c hh a sg a i n e dm a n yi m p r o v e m e n t s ，d e v e l o p m e n t sa n da p p l i c a t i o n si n v a i l o o sf i e l d s w h e r e a s ，t h e r ea r es t i l ls o 撼尊p r o b l e m se x i s t e di na c 0 ，s u c ha sl o wc o n v e r g e n t s p e e d ，l o n gs e a r c h i n gt i m e ，e a s i l yt r a p p i n gt ol o c a lb e s te t c m o r e o v e ra c o i sn o tf i t f o rs o l v i n gc o n t i n u o u sp r o b l e m si nf o r m o nt h eb a s i so fs u m m a r i z i n ga n da n a l y z i n g t h ee x i s t e dr e s e a r c h ，觚i m p r o v e dd e s i g ns c h e m ei sp u tf o r w a r d ，w h i c hi n c l u d e s ： f i r s t l y ，a na l g o r i t h mf r a l n eo fi m p r o v e da c 0i s 誊y e nt os o l v et h ec o n t i n u o u s p r o b l e m s ，a n dau n i f o r md e s c r i b ef o rb o t hc o n t i n u o u sa n d d i s c r e t ep r o b l e m si sg i v e n o nt h eb a s eo ft h ef r a m e f o rs o l v i n gd i s c r e t ep r o b l e ms u c ha ss t a t i ca n dd y n a m i c c o m b i n e do p t i m i z a t i o nc o m b i n a t i o n , a c oi sf i tf o r , b u ti ti sh a r dt oe f f e c t i v e l ys o l v e c o n t i n u o u sp r o b l e m s a c c o r d i n gt ot h ea b o v e - m e n t i o n e dd e f e c t s ，an e wm e t h o d e m b o d yc o n t i n u o u sr e q u i r e m e n t a c c o r d i n gt ot h er e l e v a n td e f e c t s ，an e wm e t h o d w h i c hu s e st h ei d e ar e s o l v i n gt s pi na c of o rr e f e r e n c ei se m p l o y e d m u t a t i o ni s a d d e dt og e tt h ed i v e r s i t yo ft h ep o p u l a t i o n 。t h et e s tr e s u l ts h o w e dt h a tt h em e t h o di s f e a s i b l e s ot h es c h e m en o to n l ys o l v e sc o n t i n u o u sp r o b l e m s ，b u ta l s og i v e sau n i f i e d d e s c r i p t i o nf o ra c o 雒p l y i n g i nb o t hc o n t i n u o u sa n dd i s c r e t ep r o b l e m s s e c o n d l y , i no r d e rt oi m p r o v et h ec a p a c i t yo fa c of o rs o l v i n gc o n t i n u o u s p r o b l e m s , af l e wh y b r i da l g o r i t h mw h i c hp u tt h ee s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m i n t oa c oi sp u tf o r w a r d t h ea l g o r i t h mn o to n l ya v o i d s t h ep r o b l e mo fp a r a m e t e r e s t i m a t i n g 斑c r o s s o v e ro p e r a t i o na n dm u t a t i o no p e r a t i o n , b u ta l s oi m p r o v e st h e p e r f o m m n c eo fa l g o r i t h mb yc o m p u t i n gt h ed e n s i t yf u n c t i o no fi n d i v i d u a l i n p o p u l a t i o nt os e l f - a d a p tt h ed e n s i t yo f p h e r o m o n e f i n a l l y , t h es i g n i f i c a t i o na n dt h et h o u g h to fo b j e c t sc o m p l e x i t ya r ei n t r o d u c e d a n de m b e d d e di n t ot h em o d e mo p t i m i z a t i o na l g o r i t h m s ，w h i c hi m p r o v e st h e c a p a b i l i t yo fo p t i m i z i n gc o m p l e xp r o b l e m t h ef a c t o r ss u c ha se x t r e m en u m b e r s e x t r e m ed i s t r i b u t i o na n de x t r e m eb r e ad i s t r i b u t i o n 皴eb a s i cs i g n sw h i e he a br e f l e c t t h ec o m p l e x i t yo ft h ep r o b l e m i tc a l lb es e e na sa 妪醛o f i n s p i r ee s p e c i a l l yf o r o p t i m i z i n gc o m p l e xh i g hd i m e n s i o n a lp r o b l e m s s oan e wm e t h o df o ro p t i m i z i n g c o m p l e xp r o b l e m si sp u tf o r w a r d t h r o u g hi n t r o d u c i n g t h ec o m p l e xf a c t o r s ，t h e e f f i c i e n c yo fa l g o r i t h m si si m p r o v e d t h ep r o b a b i l i t yo fr e p e a t i n gs e a r c h i n gi s 玎 r e d u c e d s ot h ep e r f o r m a n c eo f a l g o r i t h m so p t i m i z i n gc o m p l e xp r o b l e m si si m p r o v e d k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ；c o n t i n u o u sf u n c t i o n ；c o m p l e x i t yo fo b j e c t ； e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m s ；p r o b a b i l i s t i cd i s t r i b u t i o n 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的 研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律责任由本人承担。 论文作者签名：芝丕到 日期： 垒竺2 ：墨 关于学位论文使用授权的声明 本人完全了解济南大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借鉴；本人授权济南大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：近垂到导师签名： 连续优化的蚁群算法酸迸及应甩 第一章引言 受社会性昆虫( 蚂蚁，鸟群，蜂群) 行为的启发，智能自动化、智能计算等 相关领域的研究工作者通过对其行为的模拟，产生了一系列寻优问题求解的新思 路群体智能( s w a r mi n t e l l i g e n c e ，简称s d 1 2 1 。社会性昆虫的显著特点在 于：每个个体的行为都很简单。但当它们一起协同工作时，却能够“突现”或“自 组织”出非常复杂( 智能) 的行为特征。例如，单只蚂蚁的能力极其有限，但当 这些简单的蚂蚁组成蚁群时，却能完成像筑巢、觅食、迁徙、清扫蚁巢等复杂行 为：一群行为显得盲目的蜂群能造出精美的蜂窝；鸟群在没有集中控制的情况下 能够同步飞行等。 受蚁群在觅食过程中总能找到条从蚁巢到食物源的最短路径的启发，意大 利学者m d o f i g o ，v m a n i e z z o 和a c o l o m i t 3 4 】于2 0 世纪9 0 年代初提出了一 种新型的智能优化算法蚂蚁系统( a n ts y s t e m ，简称a s ) ，该算法首先用于 求解著名的旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ，简称t s p ) 并获得了较好 的效果。目前该算法已取得了很多改进和改善，并己在很多领域获得了广泛的应 用。 i i 蚁群优化概述 1 1 1 基本蚁群算法的起源 蚂蚁是地球上最常见，数量最多的昆虫种类之一，常常成群结队地出现于人 类的日常生 舌环境中。这些昆虫的群体生物智能特征、引起了一些学者的注意。 意大利学者m d o f i g o ，v m a n i e z z o 等人在观察蚂蚁的觅食习性时发现，蚂蚁总 能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是 通过种遗留在其来往路径上的叫做信息素( p h e r o m o n e ) 的挥发性化学物质来进 行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活 习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是 通过这种信息素进行相互协作，形成正反馈，使多个路径上的蚂蚁逐渐聚集到最 短的那条路径上来的。 这样，m d o n g o 等人于1 9 9 1 年首先提出了蚁群算法。其主要特点就是： 通过币反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索 济南大学硕士掌位论文 算法：它充分利用了生物蚊群能通过个体问简单的信息传递，搜索从蚁巢至食物 源最短路径的集体寻优持征。以及该过程与旅行商问题求解之间的相似性，用于 求解具有n p 难度( n o n - d e t e r m i n i s t i cp o l y n o m i c a lc o m p l e t e n e s s ) 的著名旅行商 问题。 1 1 2 蚁群优化算法的意义 当今，科学技术正处于多学科相互交叉和融合的时代。特别是，计算机科学 与技术的迅速发展，从根本上改变了人类的生产与生活。同时，随着人类生存空 闯的扩大以及认识与改造世界范围的拓展，人们对科学技术提出了新的和更高的 要求，其中对高效的优化技术和智能计算的要求日益迫切。 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。 作为一个重要的科学分支、它一直受到人们的广泛重视，并在诸多工程领域得到 迅速推广和应用，如系统控制、人工智能、模式识别、生产调度和计算机工程等。 目前，除了业已得到公认的遗传算法、模拟退火法、禁忌搜索法、粒子群算法、 人工神经网络等热门迸化类方法，蚁群算法也加入了这个行列中，为复杂困难的 系统优化问题提供了新的具有竞争力的求解算法。 尽管一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自 然，解决问题的灵感似乎也应该来自于大自然。这种由欧洲学者提出并加以改进 的新颖系统优化思想，正在吸引着越来越多学者的关注和研究，应用范围也丌始 遍及到许多科学技术及工程领域，通过多年来世界各地研究工作者对蚁群算法的 精心研究和应用开发，该算法现已被大量应用予电力、通信，水利、采矿、化工、 建筑、交通等各个领域。 1 1 3 蚁群优化的特点 从a c o 的原理不难看出，蚁群的觅食行为实际上是一种分布式的协同优化 机制。单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径，但找到最短路径的可 能性极小，只有当多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁的智能发 现最短路径的能力。在寻找最短路径的过程中，蚁群使用了一种间接的通信方式， 即通过向所经过的路径上释放一定量的信息素，其它蚂蚁通过感知这种物质的强 弱柬选择下一步要走的路。这种个体间通过改变环境、感知环境的变化柬彼此间 接通讯的方式机制被称为协同机制s t i g m e r g y 【”。 在蚁群的觅食行为中，另一个重要的方面是正反馈机制和解的隐式评估。某 条路径上经过的蚂蚁数越多，其上留下的信息素也就越多( 当然，随时间的推移 会逐渐减少) ，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上外激 素的强度。把蚁群采用的这种选择路径的机制称之为正反馈机制。解的隐式评估 指蚁群将先走完较短的路径。正反馈机制和解的隐式评估相结合，极大地提高了 问题的求解效率。即对于越短的路径，蚂蚁将越早走完，从而使使更多的蚂蚁将 会选择该路径。正反馈机制对基于群体的算法非常有效，如在遗传算法 ( o e n e t i c a l g o r i t h n l 简称g a ) 中，通过选择和复制机制来实现。因为它奖励好 的个体，可以指导搜索方向。当然在使用正反馈机制时，要努力避免早熟现象。 在a c o 中j 使用信息素挥发和随机状态转移来弥补正反馈机制的缺陷。 蚁群算法的主要特点概括如下： 采用分布式控制，不存在中心控制： 每个个体只能感知局部的信息，不能直接使用全局信息： 个体可改变环境，并通过环境来进行间接通讯( s t i g m e r g y 机制) ； 具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的智能 ( e m e r g e n ti n t e l l i g e n c e ) 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得 全局最优解； 其优化过程不依赖于优化问题本身的严格数学性质，诸如连续性、可导性， 及目标函数和约束函数的精确数学描述； 是一类基于多主体( m u l t ia g e n t ) 的智能算法，各主体间通过相互协作柬更 好的适应环境： 1 1 4 蚁群算法与其它算法的比较 l 蚁群优化与蒙特卡罗模拟 7 1 可以将a c o 解释为并行的重复蒙特卡罗( m e n t ec a r l o ，简称m c ) 系统。 蒙特卡罗系统是通用的随机模拟系统，即通过利用随机状态采样和转移准则，对 问题进行重复的采样实验【8 】。实验所得的结果对问题的统计知识和感兴趣变量的 估计值进行更新。反过来，可以重复地使用知识以减少感兴趣变量的不一致性， 从而指导模拟过程向感兴趣的状态空间转移。与此相似，在a c o 中蚂蚁利用 济南大学硕士学位论文 随机决策机制在问题的解空间中逐步发现问题的可行解。每只蚂蚁自适应地修改 问题的局部信息( 即蚁群留下的信息素) ，通过正反馈机制指导蚂蚁沿着有希望 的解空间向最优解靠近，从而节约了算法的搜索时剧。 2 蚁群优化与神经网络 由许多并发、局部交互的单元( 蚂蚁) 组成的蚁群，可以看成是一种“连接” 系统。“连接”系统最具代表性的例子是神经网络( n e u r a ln e t w o r k ，简称n n ) 0 j 0 。从结构上看，a c o 与通常的神经网络具有类似的并行机制。蚂蚁访问的 每一个状态i 对应于神经网络中的神经元i ，与问题相关的状态i 的邻域结构 与神经元i 中的突触连接相对应。蚂蚁本身可看成通过神经网络的并发输入信 号，以修改突触与神经元之间的连接强度。信号经过随机转换函数的局部反传， 使用的突触越多，两个神经元之间的连接越强。a c o 中的学习规则可解释为一 种后天性的规则，即质量较好的解包含连接信号的强度高于质量较差的解。 3 蚁群优化与进化计算 a c o 与进化计算( e v o l u t i o n a r yc o m p u t a t i o n ，简称e c ) 1 1 1 1 之间有许多相似 之处。首先，两种算法都采用群体表示问题的解；其次，新群体通过包含在群体 中与问题相关的知识来生成。两者的主要差异在于进化计算中所有问题的知识都 包含在当前群体中，而a c o 中代表过去所学的知识保存在信息素中 4 蚁群优化与分布估计算法 a c o 与分布估计算法( d i s t r i b u t i o no f e s t i m a t i o na l g o r i t h m s 简称e d a ) 之 阈相似点有很多。首先，二者均不采用交叉和变异操作，从一定程度上避免了参 数配置问题；其次，代表过去所学的知识均不显式包含在当前群体中。在a c o 中过去所学知识保存在信息素中，e d a 则体现在密度分布函数中。 1 1 5 蚁群优化的研究现状 1 9 9 1 年，m d o r i g o 等人提出了第一个a c o 算法蚂蚁系统( a s ) 并 成功用于求解t s p 问题p 羽。实验结果表明a s 算法具有较强的鲁棒性和发现 较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等。该 算法的出现引起了学者们的广泛关注，并提出了一些改进的a c o 算法。l m g a m b a r d e l l a ，m d o r i g o 【1 2 】提出了a n t q 算法，该算法用伪随机比例状态转移规 则( p s e u d or a n d o m p r o p o r t i o n a ls t a t et r a n s i t i o n r u l e ) 替换a s 算法中的随机比例 4 连续提纯靛蚊群莫法教瀵及痤嗣 选择规则( s t o c h a s t i c p r o p o r t i o n a lc h o i c er u l e ) ，从而使a n t - q 算法在构造解的过 程中能够更好地保持知识探索( e x p l o r a t i o n ) 与知识利用( e x p l o i t a t i o n ) 之间的 平鬻。除蓝之舞，该舞法中还零l 入了届帮落惑豢更耨梳截鞠全局信息素燹耨中酶 精英策略。m d o f i g o 【l3 】等在a n t - q 算法的基础上提出了蚁群系统( a n tc o l o n y s y s t e m , 麓称a c s ) ，该算法作为a n t q 算法的特例实现起来更为麓肇，但在 求解t s p 蠲题时爨有褶霹兹毪熊。s t f i t z l e 稳h o o s t 降卫强遗了最大，最，j 、蚂蚁系 统( m a x m i na n ts y s t e m ，简称m m a s ) ，该簿法的主要特点是为信息素设置上 下限来避免算法出现停滞形象。b u l l r d a e i m e r 等f 博壤! 出了蒸子排序的蝎蚊系统 ( r a n k - b a s e dv e r s i o no f a n ts y s t e m , a s r a r 盘) ，该算法在完成一次迭代嚣，将鹅藏螽 经路径的长度按从小到大的顺序排列，并根据路径长度赋予不同的权熏，路径较 短的投踅较大，如全髑最优解的投踅为w ，第r 个最优解的投重为m a x o ，w - r 。 黧& 童到上个擞纪末才有掌者开始关注a c o 算法，霞魏对该算法豹研究主 要停尉在算法的改谶和应用方面。吴庆洪和张纪会等 1 9 】通道向基本蚁群舞法中引 入交雾枫制，充分利用2 交换法麓洁赢效的特点，提出了矮有变异特缎的蚁群 算法。壬颓和游剑荚搿8 随过蠢适鹰施改交算法静挥发度等系数，提出一牵牵鱼适应 的蚁群算法以克服限于局部最小的缺点。覃刚力和杨家本( 2 l 】根据人工蚂蚁所获得 解的镄猊，动态媳调整路径土豹信息素，提感了喜适应调羧信息素豹蚁群箕法。 随著人们对a c o 研究的不断深入，近年来m d o r i g o 等入 7 , 3 0 1 褥蹴了蚊群 优化元启发式( a n tc o l o n yo p t i m i z a t i o nm e r eh e u r i s t i c , 简称a c o m h ) 这一求 解复杂翘题的透舄攥架。a c o - m h 为a c o 嬲理论研究和冀法设谤提供了技术 上的僚障。在a c o 的收敛性方瑟，w 王g u t j a h r l 3 1 1 作 了歼创侄的工作，提出了 基于圈的蚂蚁系统诧启发式( g r a p h - b a s e da n ts y s t e mm e t a h e u r i s t i c ) 遮a c o 豹逶题貘型，该摸懋程一定豹条 孛下毙以任意接近l 的檄率收敛到最蜣解。强 前已商少量文献涉及a c o 的收效性 , 2 2 - 2 3 ，3 2 - 3 3 ，但还很不成熟。 对a c o 的应用研究一直非常活跃。继m d o r i g o 酋姥将a s 算法应用于 t s p 麓题之后， v tm a n i e z z o f 2 4 , 2 5 l 等久将a s 算法应瘸予籀派阕题( q u a d r a t i c a s s i g n m e n t p r o b l e m ，简称q a p ) 。瞽前，a c o 已是求解q a p 问题最肖效的算 法之。a c o l o m i 等人【2 6 l 箭先将a s 算法应用予车间作业调度问题 ( j o b - s h o p s e h e d u l i n gp r o b l e m , 麓称j s p ) 。c o s t a 彝h e r z t 2 7 】提出增强静a s 算 法。弗将其应用于瓣色图问题。 a c o 在通讯网络领域( 特别是解决网络路由问题) 的应用受到越来越多学 者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与a c o 非常 相似，如利用局部信息发现解，间接的通讯方式和随机状态的转换。d ic a r o 和 d o f i g o 2 8 2 9 l 已在相关的文献中将a c o 应用于网络路由f - 题，并称这种算法为 a n t n e t 。 除了各种组合优化问题之外，a c o 算法还在函数优化、系统辨识、机器人 路径规划、数据挖掘、大规模集成电路中的综合布线设计等领域取得了引人注目 的成果。 尽管蚁群算法获得了广泛的应用，并对其做出了很大的改进，但仍存在一些 问题，如收敛速度慢、搜索时间长、易陷入局部最优等缺点。当然这些缺陷也是 其它基于概率意义下的现代优化算法的通病。基本蚁群算法暴露出的一个突出问 题不大适合或者不很方便将其应用于连续空间问题中。尽管a c o 已在最初 模型的基础上做了很多的改进和扩展，以适应于连续空间的优化，但至今仍没有 很权威的定论。这也使得蚁群算法在应用于连续空间的优化问题上成为当前国际 和国内的研究热点之一。 1 2 论文主要工作 针对蚁群算法应用于连续空间的优化问题存在的问题，本文在总结和分析已 有的研究成果的基础上对蚁群算法求解连续空间的优化问题进行了一些改进研 究，主要包括如下几部分内容： 1 根据文献 3 4 】， 3 5 提出的解决思路将连续空问离散化，借鉴蚊群算法 解决t s p 问题的思想和模型，加入交叉和变异操作，使之适合于连续优化 进行了仿真试验。试验结果表明了该思路的有效性和可行性，在此基础上提出了 用蚁群算法解决离散优化和连续优化的统一描述方法，使其不仅从功能上实现了 蚁群算法的连续优化，而且从描述形式上统一了蚁群算法对连续空间和离散空间 的优化。 2 为了提高蚁群算法解决连续问题的性能，在本文所给出的蚁群算法统一优 化模型的基础上，提出了一种新的杂合优化算法即蚁群算法与分布估计算法融合 的优化算法。该算法主要针对蚁群算法优化连续问题时存在的一个典型问题 种群多样性的获得和实现而提出和实施的。通过估算各个变量的概率密度并从中 6 连续优化的蚁群算洼改进及应用 采样来生成新个体，以获取种群的多样性，同时利用每个个体的概率密度，自适 应地改变信息素浓度，从而引导蚂蚁更有效地进行搜索。 3 为了提高现代优化算法解决复杂问题的能力，本文提出了基于问题复杂性 描述的概念，并将基于平均收敛半径的指数变异分别加入遗传算法和蚂蚁算法 中，以达到减少盲目搜索，提高搜索效率的效果。 1 3 论文的基本结构 第一章介绍了蚁群优化算法的研究背景、意义，。现状等。第二章介绍了蚁群 算法的基本原理和模型。第三章提出了一种用蚁群算法解决连续函数的算法框 架，在此基础上给出了蚁群算法在优化连续和离散问题的统一的描述形式。第四 章在该算法框架的基础上，提出了一种新的杂合优化算法即蚁群算法与分布估计 算法结合的优化算法，即针对解决蚁群算法优化连续问题时存在的一个典型问题 1 中群多样性的获得和实现问题而提出和实施的。第五章将问题复杂性描述方 法融入现代优化算法中，以进一步提高算法解决复杂问题的能力。最后对全文的 研究工作进行了总结，并展望了蚊群优化未来的研究方向。 第二章蚁群系统基本原理 2 1 引言 现实生活中单个蚂蚁的能力和智力非常简单，但它们通过相互协调、分工、 合作却能完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为。比如在蚂蚁觅食过程中 能够通过相互协作找到食物源和巢穴间的最短路径。像蚂蚁这样的群居昆虫，虽 然没有视觉，却能找到由蚁巢到食物源的最短路径，原因是什么? 蚁群能够完成 复杂的任务不仅如此，蚂蚁还能够适应环境的变化，如：在蚁群运动路线上突然 出现障碍物时，一开始各个蚂蚁分布是均匀的，不管路径是否区分长短，蚂蚁总 是先按同等概率选择各条路径。但经过一段时间后蚂蚁能够很快的重新找到最优 路径，蚁群是如何完成这些复杂任务的? 2 。2 基本蚁群算法原理 生物学家和仿生学家对此产生了的强烈兴趣，仿生学家经过大量细致观察研 究发现，蚂蚁个体之间是通过一种称为外激素( p h e r o m o n e ) 的物质进行信息传递， 从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之 问的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中，能够在它所经过 的路径上留下该种物质，同时蚂蚁在运动过程中能够感知这种物质的存在及强 度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动，如 路径上出现障碍物时相等时间内较短的路径上信息量就遗留得比较多，选择较短 路径的蚂蚁也随着增多。 下面用下图( 图2 1 ) 说明蚂蚁群选路过程。 如图2 1c a ) 所示，在蚁巢和食物源之间有两条道路n e s t a b d f o o d 和。 n e s t acd f o o d ，其长度分别为4 和6 。单位时间内蚂蚁可移动一个单位长度 的距离。开始时所有路径上都没有外激素。 如图2 1 ( b ) ，在t = o 时刻。2 0 只蚂蚁从蚁巢出发移动到a 。由于路径上没 有信息量，它们以相同概率选择左侧或右侧道路，因此平均有1 0 只蚂蚁走左侧， 另外l o 只走右侧。这些蚂蚁在行进过程中分别留下信息量。假设蚂蚁都具有相 同的速度和信息量释放能力。 8 连续优化的蚁群舅一王改进及声用 如图2 k c ) ，在t - - 4 时刻，第一组先到达食物源的蚂蚁将折回。 如图2 1 ( d ) ，在t = 5 时刻，两组蚂蚁将在d 点相遇。此时b d 上的信息 量与c d 上的相同，因此返回的l o 只蚂蚁中有5 只选择b d 而另5 只选择 c d 。 如图2 1 ( e ) ，在t = 8 时刻，前5 个蚂蚁将返回巢穴，而在a c 、c d 和a b 上各有5 个蚂蚁。 如图2 1 ( 0 ，在脚时刻，前5 个蚂蚁又回到a 并且再次面对往左还是 往右的选择。这时，a b 上的信息量是2 0 而a c 上是1 5 ，因此将有较为多数 的蚂蚁选择往右，从而增强了a b 上信息量的数量。随着该过程的继续，两条 道路上信息量的差距将越来越大，直至绝大多数蚂蚁都选择了最短的路径。正是 由于一条道路要比另一条道路短，因此，在相同的时间间隔内，短的路线会有更 多的机会被选择。 “n ( b ) k 图2 1 蚂蚁群的选路过程 - 9 曰 ( 。) f a o d 5 锄h v n e s t ( n 。弘。默y久咩- b 吖冷热y 2 3 基本蚁群算法模型 2 3 1 旅行商问题 一般地，旅行商问题( 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 ) 可描述如 下：设c = c l ，c 2 ，e 1 1 ) 为n 个城市的集合，l = l 】l i | c i ，c j c ) 是c 中元素两 两连接的集合，o = ( c ，l ) 是一个图，t s p 问题的目的是从g 中找出长度最短 的h a m i l t o n i a n 圈，即找出对c = e l ，e 2 ，c n 中n 个城市访问且只访问一次 的最短的一条封闭曲线。t s p 问题分为对称型和非对称型。在对称型t s p 问题 中，有d i j = d j i ，v c i ，e j c ( i , j = l ，2 ，n ) ，d i j 是l 的长度：而在非对称型t s p 问题中，至少存在一对c i ，c j c ，使d i j d j i 。 2 3 2 基本蚁群算法描述 设b i ( c ) ( i = l ，2 ，n ) 为t 时刻城市i 的蚂蚁数，则芝b 。( t ) 为全部蚂蚁 数。每只蚂蚁有以下特性： 蚂蚁根据某一概率函数选择下一座城市，其中概率函数是城市间距离及 连接边上信息素量的函数( 设f i j ( t ) 为t 时刻连接边e ( i ，j ) 上的信息素量) ； 每只蚂蚁只能走合法路线，除非一次周游( 蚂蚁走完所有的城市称为一 次周游) 结束，不允许转到已访问的城市。该过程由蚂蚁的禁忌表来控制。设 t a b uk 为蚂蚁k 的禁忌表，则蚂蚁k 在经过城市i 以后，就将城市i 加入到 自己的禁忌表t a b uk 中，表示下一次不能再选择城市i 。用t a b u k 表示第k 只 蚂蚁已经访问的城市；完成一次周游后，蚂蚁在其访问过的每一条边上留下相 应的信息素。 蚁群算法表述如下：在算法的初始时刻，将m 只蚂蚁随机地放到n 座城 市，同时，将每只蚂蚁的禁忌表的第一个元素设置为它当前所在的城市。此时 各路径上的信息素量相等，设fi j ( o ) = c ( c 为一较小的常数) 。接下来，每只 蚂蚁根据路径上残留的信息素量和启发式信息( 两城市间的距离) 独立地选择 下一座城市。在时刻t ，蚂蚁k 从城市i 转移到城市j 的概率p ：。( t ) 为： p u 电) ： 黔小州( 2 1 )p ，( t ) ：濡。h “”卜“( 2 1 ) 10；否则 0 连续优化的蚁群算法改进及应用 j 。( i ) = 1 , 2 ，n 卜t a b u k 表示蚂蚁k 下一步允许选择的城市集合。列表 t a b u k 记录了蚂蚁k 当前走过的城市。当所有n 座城市都加入到t a b uk 中时，蚂蚁k 便完成了一次周游，此时蚂蚁k 所走过的路径便是t s p 问题 的个可行解。( 2 1 ) 式中的m 是一个启发式因子，表示蚂蚁从城市i 转到城 市j 的期望程度。在蚁群算法中，m 通常取城市i 与城市j 之间距离的倒数。 a 和b 分别表示信息素和启发式因子的相对重要程度。当所有蚂蚁完成一次周 游后，各路径上的信息素根据( 2 2 ) 式更新。 ( t + n ) = ( 1 一p ) ( t ) + 6 吒 ( 2 2 ) 其中p ( 0 f ( x o ) ，则将x 作为新的巢穴位置，否则，随机选择 一个点作为新的巢穴，并更新信息素。重复上述过程，直到满足终止条件。 。第二种思路：基于网格法的蚁群算法m i 。 根据问题的性质估计最优解的范围，以及各个变量的取值范围；在变量区 域内打网格，每个空间的网格点各对应种状态，人工蚂蚁在各个空间网格点 之间移动，根据各网格点的目标函数值，留下不同的信息量，以此影响下一批 人工蚂蚁的移动方向；循环一段时间后，目标函数值小的网格点信息量会比较 大，根据信息量，找出信息量大的空间网格点，缩小变量范围，在此点附近进 研南大学硕士学位论文 行人工蚁群移动；重复上述过程，直到网格的间距小于预先给定的精度，算法 终止。 第三种思路：模仿蚁群算法解决t s p 问题的思路 3 4 , 3 5 , 4 1 1 。 根据问题的性质估计最优解的范围，以及各个变量的取值范围。把变量x l 看作t s p 问题中的城市i ( i = l 2 一n ) ，在变量x 。的取值范围内分布若干蚂蚁，让每 只蚂