（计算数学专业论文）具有感知觉特征的蚁群算法在连续函数优化中的应用.pdf

具有感知觉特征的蚁群算法在连续函数 优化中的应用 计算数学专业 研究生杨琼指导教师庞朝阳 摘要：蚁群算法是一种新型的模拟进化算法，它通过模拟蚁群在觅食过程 中寻找最短路径的方法来求解优化问题。该算法的出现引起了学者们的极大关 注，在过去十多年的时间里，已经充分显示了它在解决复杂离散优化问题方面 的优越性。求解连续函数优化问题也是蚁群算法的研究课题之一，目前对该问 题的研究遇见两个主要困难，一是，所求解很大可能是局部最优解，丽不是全 局最优解；二是，求解结果精确度不够高。针对以上两个困难，本文采用具有 感知觉特征的蚁群算法求解连续函数优化问题。实验表明，该算法与其它算法 相比，更能找到全局最优解，且解的精确度较高，基本克服了以上两个主要困 难。本文的主要研究内容及成果如下： ( 】) 本文围绕蚁群算法的基本理论，概述了蚁群算法的生物学机理、算法 特点及应用现状；详细介绍了基本蚁群算法模型及它的具体实现步骤，以及具 有感觉和知觉特征的蚁群算法思想和算法设计过程。 ( 2 ) 本文采用具有感知觉特征的蚁群算法，将其应用到求解连续函数优化 问题中。实验表明，具有感知觉特征的蚁群算法应用于求解连续函数优化问题， 能使得求解的性能更好。 ( 3 ) 本文详细介绍了具有感知觉特征的蚁群算法求解连续函数优化问题 的模型和具体实现步骤；为了便于对算法的理解，给出了该算法的具体代码描 述和详细的数据结构说明。 关键词：蚁群算法；离散优化；连续函数优化 t h e a p p l i c a t i o no f a n tc o l o n ya l g o r i t h m w i t h c h a r a c t e r i s t i c so fs e n s a t i o na n dc o n s c i o u s n e s so n co n t i n u o u sf u n c t io no p t i mi z a t i o n m a j o r 2c o m p u t a t i o n a lm a t h e m a t i c s p o s t g r a d u a t e ：y a n gq i o n gs u p e r v i s o r ：p a n gc h a o y a n g a b s t r a c t ：a n tc o l o n ya l g o r i t h m ( a c a ) i san e w - s t y l es i m u l a t i n ge v o l u t i o n a l g o r i t h m t h eb e h a v i o ro fr e a la n tc o l o n i e sf o r a g i n gf o rf o o di ss i m u l a t e da n du s e d f o rs o l v i n go p t i m i z a f i o np r o b l e m s m a n ) , s c h o l a r sp a y e dm u c ha t t e n t i o nt ot h e a l g o r i t h ma ss o o ba si tc a n q ef o r t h ，i nt h ep a s tt e ny e a r s ，t h ea l g o r i t h mh a sg r e a t s u p e r i o r i t yi ns o l v i n gc o m p l i c a t e dd i s c r e t eo p t i m i z a t i o np r o b l e m s s o l v i n gt h e c o m i n i o u sf u n c t i o no p t i m i z a t i o np r o b l e m si so n eo ft h ea c a ss t u d yp o i n t s t w o m a i nd i f f i c u l t i e sl i ei nt h ep r o b l e m ，o n ei st h a tt h es o l u t i o ni sal o c a lo p t i m a lv a l u e p o s s i b l y n o tg l o b a l t h eo t h e rd i f f i c u l t yi ss o l u t i o nh a sal o wa c c u r a c y f o rt h et w o d i 筋c u l t i e s ，t h i sp a p e re m p l o y a n tc o l o n y a l g o r i t h mw i t hc h a r a c t e r i s t i c so f s e n s a t i o na n dc o n s c i o u s n e s s ，a n da p p l yi tt os o l v ec o n t i n u o u sf u n c t i o no p t i m i z a t i o n p r o b l e m s e x p e r i m e n ts h o w st h a tt h ea l g o r i t h mi se a s i e rt of i n dt h eg l o b a lo p t i m a l v a l u ea n dt h es o l u t i o nh a sah i g h e ra c c u r a c yt h a no t h e ra l g o r i t h m s ，a n de v a d e st h e t w om a i nd i f f i c u l t i e si ns o m ed e g r e e n l em a i nr e s e a r c hc o n t e n t sa n dt h e i rr e s u l t s a r ed e s r i b e da sf o l l o w ： ( 1 ) b a s e do nt h e b a s i ca c at h e o r y ，t h eb i o l o g i c a lm e c h a n i s ma n dt h e c h a r a c t e ro fa c aa r es u m m a r i z e d n l ec u r r e n ta p p l i c a t i o no ft h ea n tc o l o n y a l g o r i t h mi si n t r o d u c e d t h em o d e l i n gc o u r s ea n dr e a l i z i n gs t e p sa r ei n t r o d u c e di n d e t a i l t h ea l g o r i t h mi d e aa n di t sd e s i g np r o c e d u r eo fa n tc o l o n yo p t i m i z a t i o nw i t h s e n s a t i o na n dc o n s c i o u s n e s sa r ei n t r o d u c e di nd e t a i la l s o ( 2 ) t 1 1 i sp a p e re m p l o ya n tc o l o n ya l g o r i t h m 、) i ，i 也c h a r a c t e r i s t i c so fs e n s a t i o n n a n dc o n s c i o u s n e s s a n da p p l yi tt os o l v ec o n t i n u o u sf u n c t i o no p t i m i z a t i o np r o b l e m s e x p e r i m e n ts h o w st h a tt h ea l g o r i t h ma p p l i e di nt h i sp a p e rc a t lp e r f o r mw e l li n f i n d i n gt h eo p t i m a lv a l u e ( 3 ) t h i sp a p e ri n t r o d u c e st h em o d e la n di t ss p e c i f i cr e a l i z i n gs t e p so fa p p l y i n g t h ea n tc o l o n ya l g o r i t h mw i t hc h a r a c t e r i s t i c so fs e n s a t i o na n dc o n s c i o u s n e s st o s o l v et h ec o n t i n u o u sf u n c t i o n o p t i m i z a t i o ni nd e t a i l t ou n d e r s t a n dt h ea l g o r i t h m e a s i l y , t h ed e s c r i p t i o no fs p e c i f i cc o d ea n di t se x p l a n a t i o no fd a t as t r u c t u r ec a nb e g o ti nt h i sp a p e rt o o k e y w o r d s ：a n tc o l o n ya l g o r i t h m ；d i s c r e t eo p t i m i z a t i o n ；c o m i n u o u sf u n c t i o n o p t i m i z a t i o n i i i 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师庭麴圈熬援指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何 其他个人或集体己经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 本人承诺：己提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印 刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库进 行检索；2 ) 为教学和科研目的，学校可以将公开的学位论文或解密后的学位 论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中国学位论文全 文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后使用本授权书) 学位论文作者签名：杨琼导师签名：庞朝阳 签字日期：2 0 0 9 年4 月签字日期：2 0 0 9 年4 月 第一童绪诊 1 1 蚁群算法的思想起源 蚁群算法是由意大利学者d o r i g om 等n 。1 人在2 0 世纪9 0 年代初受自然 界中真实蚁群集体行为的启发而提出的一种基于种群的模拟进化算法，属于带 有构造性特征的随机搜索算法。它是继模拟退火算法、遗传算法、禁忌搜索算 法、人工神经网络算法等启发式搜索算法后的又一种应用于组合优化问题的启 发式搜索算法。d o r i g om 等人在观察蚂蚁觅食行为时发现，蚂蚁总能找到巢 穴与食物源之间的最短路径，这种现象引起了他们极大的兴趣。经过长期观察 研究发现，尽管蚂蚁个体的智能并不高，但整个蚂蚁群体却表现为高度机构化 的社会组织，在许多情况下能完成远远超过蚂蚁个体能力的复杂任务旧1 。这种 能力来源于蚂蚁群体中的个体协作行为，其群体行为主要包括寻找食物、任务 分配和构造墓地等三种，依靠群体能力发挥出超出个体的智能。d o r i g om 等 人做了系列实验，在蚂蚁已形成的最短路径上设置障碍，而当蚂蚁在发现原 来路径有障碍物后，它们会绕开这个障碍物分散的走开，但是经过段时间， 分散的蚁群会渐渐的重新走到同一条路径上来，而这条路径也恰恰是添加障碍 物后从巢穴到食物源之间的最短路径。之后，d o r i g om 等人又不断的在蚁群 经过的新路径上设置障碍，而惊奇的发现蚂蚁总能根据障碍物的位置，分散开 来然后又聚集到当时条件下的从巢穴到食物源之间的最短路径。经研究发现， 蚂蚁的群体协作是通过一种叫做信息素( p h e r o m o n e ) 的化学物质来进行通信 和协调的，蚂蚁将信息素作为中介的化学通信作为基本信息交流方式之一。可 见，信息素在蚂蚁群体生活工作习性中有着至关重要的作用。d o r i g om 等人 受蚂蚁觅食行为中基于信息素的间接通信机制的启发，最早提出并设计了一种 蚁群算法一蚂蚁系统( a n ts y s t e m , a s ) ，该算法被首先应用于解决旅行商问题 ( t s p ) 3 ，并得到了很好的结果。自d o f i g om 等人首次将蚁群算法应用于t s p 以来，该算法就逐渐引起了国内外专家学者的关注，他们对其做了大量的研究 工作，将其推广到了诸多优化领域，并已经取得了相当丰富的研究成果。后来 d o r i g om 、和g a m b a r d e l l al 等研究者进一步发展a s 算法，把先前各种蚁群 算法归结为a c o 元启发式( a n tc o l o n yo p t i m i z a t i o nm e t a h e u r i s t i c ) 如寸。算法 的概念，把此前各种基于a s 演化而得的算法归结到一个统一的框架中，并提 供了抽象而规范的算法描述。a c o 算法作为一种新型的启发式算法已被成功 地应用于解决大量组合优化问题如：t s p 问题蛳、二次分配问题( q u a d r a t i c a s s i g n m e n tp r o b l e m ，q a p ) 嘲、车辆路径问题( v e h i c l er o u t i n gp r o b l e m ， v r p 尸、排程问题( s c h e d u l i n gp r o b l e m s ) n 引、数据挖掘( d a t am i n i n g ) 3 等。 1 2 蚁群算法的国内外研究现状 自1 9 9 1 年意大利学者d o r i g om 等【1 2 j 人在法国巴黎召开的第一届欧洲 人工生命会议( e u ro p e a nc o n f e r e n c eo na r t i f i c i a ll i f e e c a l ) 上最早提出蚁群 算法一蚂蚁系统( a n ts y s t e m ，a s ) 后的近五年时间里，这种新兴的算法并没有 在国际学术界引起广泛关注，自然这段时期在蚁群算法理论及其应用上也没有 取得突破性进展。到了1 9 9 6 年，d o r i g om 等在( ( i e e et r a n s a c t i o n so ns y s t e m s ， m a n a n dc y b e r n e t i c s p a r tb 上发表了“a n ts y s t e m ：o p t i m i z a t i o nb ya c o l o n yo f c o o p e r a t i n ga g e n t s ”一文h 3 ，在这篇文章中d o f i g om 等不仅更加系统地阐述 了蚁群算法的基本原理和数学模型，还将其与遗传算法( g e n e t i ca l g o r i t h m o a ) h 到、禁忌搜索算法( t a b us e a r c h ，t s ) n3 1 、模拟退火算；法( s i m u l a t e da n n e a l i n g ， s a ) n 钉、爬山算法( h i l lc l i m b i n g a l g o r i t h m h c a ) 新等进行了仿真实验比较，并 把算法由单纯地解决对称t s p 拓展到解决非对称t s p 、二次分配问题 ( 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 ) 瞪。、车间作业调度问题( j o b s h o p s c h e d u l i n gp r o b l e m ，j s p ) n 6 1 以及车辆路径问题( v e h i c l er o u t i n gp r o b l e m ， v r p ) 拇3 ，且对蚁群算法中初始化参数对其性能的影响做了初步探讨，这是蚁群 算法发展史上的一篇奠基性文章。自1 9 9 6 年之后的五年时间里，蚁群算法逐 渐引起了许多国家研究者的关注，其应用领域得到了迅速拓宽，这期间也有大 量有价值的研究成果陆续发表。 1 9 9 5 年g a m b a r d e l l a 和d o r i g om 提出了a n t q 算法i l 。该算法用伪随 机比例状态转移规则替换a s 算法中的随机比例选择规则，从而使算法在构造 解的过程中能够更好的保持知识探索和知识利用之间的平衡，实验表明a n t q 是一个非常有效的算法。此后，d o r i g om 和g a m b a r d e l l a 又在a n t q 的基础上 提出了蚁群系统( a n tc o l o n ys y s t e m ，a c s ) n8 1 ，该算法实现起来更为简单，但在 求解t s p 问题时具有相同的性能；s t u t z l e 和h o o s 提出了最大最小蚂蚁系统 ( m a x m i na n ts y s t e m m m a s ) n 州1 j ，该算法的主要特点是为信息素设置上下限 来避免算法出现停滞和早收敛现象；b i l c h e vga 等1 最早提出一种连续蚁群 算法，求解问题时先使用遗传算法对解空间进行全局搜索，然后利用蚁群算法 对所得结果进行局部优化，实验表明该算法有搜索较好解的能力。 对蚁群算法不断高涨的研究热情导致了1 9 9 8 年1 0 月1 5 日至1 0 月 1 6 日在比利时布鲁塞尔召开的第一届蚁群算法国际研讨会( a n t s 9 8 ) ，会 议由创始入d o r i g om 负责组织。第一届就吸引了来自世界各地5 0 多位蚁群 算法研究者，随后每隔两年都要在布鲁塞尔召开一次蚁群算法国际研讨会，历 届会议的论文集均由著名的 l e c t u r en o t e si nc o m p u t e rs c i e n c e ) ) ( s c ii n d e x ) 结集出版。2 0 0 0 年，d o f i g om 和b o n a b e a ue 等人在国际著名的项级学术刊 物 n a t u r e ) ) 上发表了蚁群算法研究综述，从而把这一领域的研究推向了国 际学术的最前沿。鉴于d o r i g om 在蚁群算法研究领域的杰出贡献，2 0 0 3 年 1 1 月欧盟委员会特别授予他“居里夫人杰出成就奖( m a r i ec u r i ee x c e l l e n c e a w a r d ) ”。进入2 1 世纪后的最近几年，国际著名的顶级刊物 n a t u r e ) ) 曾多次 对蚁群算法的研究成果进行了报道比3 。2 引，( ( f u t u r eg e n e r a t i o nc o m p u t e rs y s t e m s ) ) ( v 0 1 16 n o 8 ) 和 i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) ( v 0 1 6 n o 4 ) 分别于2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊。如今，在国内外许多学术期刊 和会议上，蚁群算法已经成为备受关注的研究热点和前沿性课题。 我国在蚁群算法领域的研究起步比较晚，从公开发表的论文( 以投稿日期 为标准) 看，国内最先研究蚁群算法的是东北大学控制仿真研究中心的张纪会 博士与徐心和教授，他们发表的“一种新的进化算法一蚁群算法 【矧；吴庆洪 等阱3 从遗传算法中变异算子的作用得到启发，在蚁群算法中采用了逆转变异机 制，进而提出了一种具有变异特征的蚁群算法，这是国内学者对蚁群算法所做 的最早改进。在国内蚁群算法的众多研究者中，值得一提的是当时年仅1 7 岁 的高二学生陈烨于2 0 0 1 年在计算机工程上发表了“带杂交算子的蚁群算 法”一文啪3 ，并基于v i s u a lb a s i c 开发了一个功能齐全、界面友好的“蚁群算 法实验室”，引起了国内广大蚁群算法研究者的关注。正如计算机工程的 “编者按”所言“一个高中生能写出如此论文实属不易”。在随后的几年里， 国内涌现出了很多改进的蚁群算法，近些年公开发表的研究成果已显示出蚁群 算法在求解离散空间优化问题方面的强大优越性。比如吴斌、史忠植提出了基 于蚁群算法的分段求解算法坦虬，提高了蚂蚁的搜索速度，为蚁群算法的并行化 奠定了基础。由于在蚁群算法构造解的过程中，选择策略一般是随机的，进化 速度较慢，陈峻等人提出了自适应的蚁群算法秘仇引：，采用确定性选择和随机选 择相结合的策略，在搜索的过程中动态地调整选择的概率，实现了选择概率的 自适应，提高了算法的收敛速度和性能；陈峻等旧2 。针对蚁群算法中的早熟、停 滞且收敛速度慢等缺陷，还提出了具有感觉和知觉特征的蚁群算法，该算法可 在加快收敛和防止早熟、停滞现象之间取得较好的平衡；段海滨等n 3 ：对基本蚁 群算法做了改进，提高了其全局优化寻优速度；胡小兵等姐钆和庞朝阳等阳瓦结合 不同的聚类算法思想对蚁群算法做了改进，将问题空间分解为若干小问题，进 而减小所求问题规模，再将每个小问题应用改进蚁群算法求解，在一定程度上 提高了蚁群算法的收敛速度与解的精度。随着蚁群算法应用领域的拓展，有些 学者提出了将蚁群算法用于求解连续空间优化问题。比如汪镭等啪门7 3 将离散域 一群算法中的“信息量留存”过程拓展为连续域中的“信息量分布函数”，并 定义了应用于连续函数寻优问题的改进蚁群算法；李艳君等协& 在借鉴遗传算法 求解连续域优化问题编码方法、精英策略以及混合算法中的区域搜索思想的基 础上，提出了一种用于连续域优化问题求解的自适应蚁群算法：段海滨等1 3 9 4 0 】 提出了一种基于网格划分策略的自适应连续域蚁群算法；杨勇等1 4 i l 提出了一 种用于求解连续域优化问题的嵌入式确定性搜索蚁群算法，该算法在全局搜索 过程中，利用信息素强度和启发式函数确定蚂蚁移动方向，而在局部搜索过程 中嵌入确定性搜索，以改善寻优性能，加快收敛速度。 回顾蚁群算法自创立以来十多年的发展历程，目前人们对蚁群算法的研究 已由当初单一的旅行商问题( t s p ) 领域渗透到了多个应用领域，由解决一维 静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓 展到了连续域范围内的研究，而且往蚁群算法的硬件实现上取得了突破性进 展，同时在蚁群算法的模型改进及与其它仿生优化算法的融合方面也取得了相 当丰富的研究成果，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的 发展前景。 4 1 3 本文的选题背景及研究意义 无论什么时候，人们无论做任何事情，总想从所有可行的方案中，通过分 析、判断、比较，从中找出一种最佳方案来，这就是人们常说的最优化问题。 随着科学技术和现代化生产的飞速发展，客观世界中的问题不断地复杂化，而 人们所要求的优化程度却越来越高，使得最优化问题在各行各业中的地位也就 越来越重要了，优化问题几乎无处不在。目前，虽然传统的数学规划理论成功 地解决了一些优化问题，但当实际工程问题的复杂度增加、约束条件增多、非 线性严重、建模困难时，传统的优化方法就显得无能为力了，因此寻找种适 合于大规模并行计算且具有智能特征的优化算法已经成为有关学科的一个主 要研究目标和引入注目的研究方向。虽然蚁群优化算法研究才刚刚起步，但是 这些初步研究已显示出了蚁群优化算法在求解复杂优化问题( 特别是离散优化 问题) 方面的优越性，证明了它是一种很有发展前景的优化方法。这种由欧洲 学者提出并加以改进的新颖系统优化思想，正吸引着越来越多的学者的关注和 研究，应用范围也开始遍及到许多科学技术及工程领域。 虽然蚁群算法在离散空间的寻优能力十分突出，但是对于连续空间的优化 也是蚁群算法应用的领域之一，也是评价蚁群算法性能的主要方面。由于最初 的蚁群算法思想起源于离散型的网络路由问题，如t s p 一旅行商问题。而一般 函数的优化问题与旅行商问题有着本质性的区别。在旅行商问题模型中，蚂蚁 选择的路线有确定的方向，而在一般函数的优化问题中，却不能直接提供蚂蚁 确定的，可供选择的路线及方向，需要人的先验知识作指导。因此，将蚁群算 法用于一般函数的优化问题中时，必须对原蚁群算法模型的许多细节进行修 正。目前国内外很多学者做了这方面的研究，研究结果表明，蚁群算法在连续 域上的寻优结果确实比不上在离散域上的寻优结果那样有明显的优越性，说明 蚁群算法用于求解一般函数的优化问题，仍存在一些缺陷。本文的目的就是进 行蚁群算法求解函数优化问题的研究，采用具有感知觉特征的蚁群算法求解连 续函数优化问题。 算法过程中通过蚂蚁对区域信息量的感知状况来确定蚂蚁的转移方式，根 据实际问题，事先确定一个感觉下限和一个感觉上限，在小于感觉下限和大于 感觉上限蚂蚁按不同的转移方式进行移动，而在感觉下限和感觉上限之间，根 据蚂蚁感知区域信息量变化的多少蚂蚁也按不同的转移方式进行移动，这样有 效地避免了早熟、停滞现象的产生。另外，在搜索过程中将全局搜索和邻域搜 索相结合，在加快收敛的同时保持解的多样性。以前许多学者运用蚁群算法求 解函数优化问题时首先将连续空间离散化，根据类似基本蚁群算法中的概率转 移方式进行移动，而本文算法并未这样，而是根据真实蚂蚁行为特征，采用具 有感知觉特征的蚁群算法，确定了新的转移规则和新的信息素更新规则，经过 常用的测试函数仿真实验证明采用具有感知觉特征的蚁群算法求解函数优化 问题性能大大优于其它一些蚁群算法求解函数优化问题。 1 4 本文的工作 本文以基本蚁群算法性能的分析为背景，探讨了蚁群算法的原理、性能、 特点及其改进措施，提出了求解函数优化问题的改进蚁群算法模型，并通过实 例分析了求解函数优化问题的改进蚁群算法的性能、特点以及进一步的研究方 向。主要内容如下： 第一章主要阐述了蚁群算法的思想起源及其国内外的研究现状和本文的 选题背景及研究意义。 第二章概述了蚁群算法的生物学基础、原理、特点及其应用。 第三章详细分析了基本蚁群算法的模型、实现以及具有感觉和知觉特征的 蚁群算法的思想和算法过程，本章内容是蚁群算法的机理分析部分，也是深入 理解蚁群算法、利用蚁群算法开展研究工作的基础。 第四章采用具有感知觉特征的蚁群算法，将其应用于求解连续函数优化问 题，首先介绍了相关概念及产生感觉的过程，接着给出了具有感知觉特征的蚁 群算法求解连续函数优化问题的思想和模型，最后把该算法与其它改进蚁群算 法做了实验对比，通过实验对比证明了本文算法的有效性。 第五章对具有感知觉特征的蚁群算法求解连续函数优化问题实现做了详 细的介绍，先给出了算法过程的伪代码描述，然后对伪代码中的重要部分分别 做了具体的代码描述和数据结构介绍。 最后，对论文工作进行了总结，并提出今后有待深入研究的有关课题。 6 第二章蚁群算法概述 蚁群算法是受到人们对自然界中真实蚁群集体行为的启发而提出的种 基于种群的模拟进化算法，属于带有构造性特征的随机搜索算法。意大利学者 d o r i g om 等n 卫1 人充分利用了蚁群搜索食物的过程与著名的旅行商问题( t s p ) 之间的相似性，吸取了昆虫王国中蚂蚁的行为特性，通过人工模拟蚂蚁搜索食 物的过程( 即通过蚂蚁个体之间的信息交流与相互协作最终找到从蚁穴到食物 源的最短路径) 来求解t s p 问题。为了区别于真实蚂蚁群体系统，称这种算法 为蚁群算法。在自然界真实的蚁群觅食过程中，蚁群在没有视觉的情况下通过 个体之间交换信息素，能够在较短的时间内找到蚁穴和食物源之间的最短路 径。生物学家通过对蚂蚁的长期观察研究发现，尽管蚂蚁个体比较简单，但整 个蚂蚁群体却表现为高度机构化的社会组织，在许多情况下能完成远远超过蚂 蚁个体能力的复杂任务口3 。这种能力来源于蚂蚁之间可以通过信息素进行协同 作用，实现蚂蚁之间的信息交流和传递，共同做出令人吃惊的行为。 2 1 蚁群算法的生物学基础 自然界中，蚂蚁的食物源总是随机散布于蚁穴周围。我们只要仔细观察就 可以发现，经过段时间后，蚂蚁总能找到一条从蚁穴到食物源的最短路径。 在现实生活中，我们总可以观察到大量蚂蚁在巢穴与食物源之间形成近乎直线 的路径，而不是曲线或者圆等其他形状，如图l 所示。 图1 无障碍的蚁群觅食m 蚂蚁群体不仅能完成复杂的任务，而且还能适应环境的变化。如在蚁群运 动路线上突然出现障碍物时，开始阶段各条路径上的蚂蚁分布是均匀的，不论 路径长短，蚂蚁总是先按同等概率选择路径，如图2 所示。 图2 突然加入障碍的蚁群觅食 蚂蚁在运动过程中，能够在其经过的路径上留下信息素( p h e r o m o n e ) ，而 且能够感知这种物质的存在及其强度，并以此指导自己运动的方向，蚂蚁倾向 于信息素浓度高的方向移动。相等时间内较短路径上的信息素遗留得比较多， 则选择较短路径的蚂蚁也随之增多，如图3 所示。 图3 有障碍的蚁群觅食过程h 3 从如图4 中不难看出，由于大量蚂蚁组成的蚁群集体行为表现出了一种信 息正反馈现象，即某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就 越大，蚂蚁个体之间就通过这种信患交流( 自催化) 机制来搜索食物，并最终 沿着最短路径进行觅食。 图4 有障碍的蚁群最终觅食路径 套辚 曲_ 明 蝉如 在以上蚂蚁搜索食物的过程中，每只蚂蚁通过感知路径上信息素的存在和 强度，倾向于向信息素浓度大的方向移动，使得整个蚁群的集体行为构成了信 息素的正反馈过程，从而找到较好路径。同时蚁群还能适应环境的改变找到当 前的最佳路径。 2 2 蚁群算法的原理 蚂蚁属于群居昆虫，每只蚂蚁的智能并不高，看起来没有集中的指挥，但 它们却能相互协调、分工、合作并完成筑巢、觅食、迁徙、清扫蚁穴等复杂行 为。比如蚂蚁在觅食过程中能够通过相互协作找到食物源和巢穴之间的最短路 径，而单个蚂蚁则不能。仿生学家通过长期的研究发现，蚂蚁虽然没有视觉， 但运动时会通过在路径上释放出一种特殊的分泌物一信息素( p h e r o m o n e ) 1 2 3 , 4 2 】，蚂蚁个体之间就是通过信息素来进行信息传递的。当它们碰到一个还没 有走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长度有关的 信息素。蚂蚁走过的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到 这个路口时，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈 机制，最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的 流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的 变化，当蚁群的路径上突然出现障碍物时，蚂蚁也能很快的重新找到最优路径。 可见，在整个寻优过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的 作用使整个蚁群行为具有非常高的自组织性，蚂蚁之间交换着路径信息，最终 9 通过蚁群的集体自催化行为找出最优路径。这里用如图5 所示的形象图例来进 一步说明蚁群的搜索原理。 l t 痢始j 至离 e hch b ) 闻蚂蚁以相霞溉串选择路晷 c ) 产1 更多蚂蚁将选择瞌短路柽 图5 自然界中的蚂蚁觅食模拟叫 图5 中，设a 点是巢穴，e 点是食物源，h c 为一障碍物。由于障碍物存在， 蚂蚁要想由a 到达e ，或者由e 返回a ，只能经由h 或c 绕过障碍物，各点之间 的距离如图5 ( a ) 所示。假设每个时间单位有3 0 只蚂蚁由a 到达b 点，有3 0 只蚂蚁 由e 到达d 点，蚂蚁过后留下的信息量为1 。为了方便起见，设该物质停留时间 为1 。在初始时刻，由于路径b h 、b c 、d h 、d c 上均无信息存在，位于b 和d 的蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择 b h 、b c 、d h 、d c ，如图5 ( b ) 所示。经过一个时间单位后，在路径b c d 上的 信息量是路径b h d 上信息量的2 倍。又经过一段时间，将有2 0 只蚂蚁由b 和d 到达c ，有1 0 只蚂蚁由b 和d 到达h ，如图5 ( c ) 所示。随着时间的推移，蚂蚁将 会以越来越大的概率选择路径b c d ，最终将会完全选择路径b c d ，从而找到 由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换式一个正反 馈过程。 通过上述真实蚂蚁行为的描述和模拟，我们可以看出信息素交流是蚂蚁寻 找最短路径最重要的媒介和手段。蚂蚁可以说是盲的，它们的活动是凭借信息 素进行的，它们有朝着信息素多的方向运动的趋势，并且留下新的信息素，这 是一种正反馈机理。并不是通过面对面的直接交流，而是通过信息素( 外激素) 进行间接交流，个体信息的收集与整个群体信息的共享，信息在系统内部进行 交流与学习，不断的优化系统，即自适应系统。蚂蚁的这种寻优机理很简单， 每个个体的行为也很简单，但整个群体通过信息素的作用，就使得蚁群可以解 1 0 决复杂的问题。 蚁群算法用于优化问题( t s p ) 的求解，正是基于真实蚂蚁觅食行为与优 化问题求解过程的相似性，见表l 。 表1 蚂蚁觅食行为与优化问题的对照n 3 j 优化问题蚂蚁觅食 各个状态要环游的各个城市 解蚂蚁的环游路径 最优解最短环游路径 各状态的吸引麦信息素的量 状态更新信息素更新 目标函数路径长度 2 3 蚁群算法的特点及其应用 从蚁群算法的原理不难看出，蚁群的觅食行为是实际上是一种分布式的协 同优化机制。单只蚂蚁虽然可以找到从蚁穴到食物源的一条路径，但是找到最 短路径的可能性极小，只有当多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁 的智能( 发现最短路径的能力) 。在寻找最短路径的过程中，蚁群使用了一种间 接的通信方式，即通过向所经过的路径上释放一定量的信息素，其它蚂蚁通过 感知路径上这种物质的强弱来选择下一步要走的路，路径上通过的蚂蚁越多， 则信息系素也逐渐增多，导致后面蚂蚁选择该路径的概率就越大，这样就使得 整个蚁群的集体行为构成了信息素的正反馈过程。众多的研究结果已经证明， 蚁群算法具有很强的发现较好解的能力，这正是因为该算法不仅利用了正反馈 机制，在一定的程度上可以加快进化过程，而且是一种本质并行的算法，不同 个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发现较好的 解。当然在使用正反馈机制时，要尽量避免早熟现象。在蚁群算法中，使用信 息素挥发和随机状态转移来弥补正反馈机制的缺陷。蚁群算法的主要特点概括 如下： ( ! ) 采用分布式控制，蚁群算法是一种基于种群的进化算法，不存在中心 控制： ( 2 ) 每个个体只能感知局部的信息，不能直接使用全局信息； ( 3 ) 个体可以改变环境，并通过环境来进行间接通信； ( 4 ) 具有很强的自组织性，郎群体的复杂行为是通过个体的交互过程中突 现m 来的； ( 5 ) 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机 会求得全局最优解； ( 6 ) 其优化过程不依赖于优化问题本身的严格数学性质，如连续性、可导 性，及目标函数和约束函数的精确数学描述； ( 7 ) 具有潜存的并行性，其搜索过程不是从一点出发，而是同时从多个点 同时进行。这种分布式多智能体的协作过程是异步并发进行的，分布并行模式 将大大提高整个算法的运行效率和快速反应能力。 基于蚁群算法以上特点，因此对该算法的应用研究一直非常活跃。由于蚁 群算法不依赖于问题的具体领域，所以目前已陆续渗透到其它许多新的领域。 ( 1 ) 组合优化 继d o r i g om 首先将蚁群算法应用于t s p 问题之后，m a n i e z z ov 旧等人将 蚁群算法应用于二次分配问题( q a p ) 。最近几年，g a m b a r d e l l ah e ，t a i l l a r d 和s t u t z l e 3 也发表了一些用蚁群算法求解q a p 问题的文章。目前，a c o 已 是求解q a pj - j 题最有效的算法之一。c o l o m ia1 9 j 等人首先将蚁群算法应用于 车间作业调度问题( j s p ) ，并取得了一系列较好的实验效果。d c o s t ah 铂等人 在d o r i g om 等人研究成果的基础上，提出了一种求解指派问题的一般模型。 该算法用来求解图着色问题时，得到了可以和其他启发式算法相媲美的结果。 ( 2 ) 网络路由通讯问题 蚁群算法在动态组合优化问题研究中的应用主要集中在通讯网络方面 h 土们：。随着i n t e m e t 上广泛的分布式多媒体应用对服务质量( q u a l i t yo f s e r v i c e ， q o s ) 需求的增长，各种服务应用对网络所能提供的q o s 提出了不同的要求。 因为路由直接关系到网络性能，所以q o s 路由成为解决q o s 问题的核心技 术之一，也是当今网络技术领域内的一个研究热点。将蚁群算法用于解决受限 路由问题，目前可以解决包括带宽、时延和最小花费等约束条件在内的q o s 1 2 路由问题h 铲弛j ，比现有的链路状态路由算法具有明显的优越性。 ( 3 ) 电力系统优化问题 电力系统优化是j 个复杂的系统工程，它包括无功优化、经济负荷分配、 电网优化及机组最优投入等一系列问题，其中很多是高维、非凸、非线性的优 化问题。h o u 等晦甜将蚁群算法成功地用于解决经济负荷分配问题；文献嫡旬则解 决了该算法在配电网优化规划中的初步设计问题。电力系统优化中的机组最优 投入问题( u n i tc o m m i t m e n t ，u c ) 是寻求一个周期内各个负荷水平下机组的最优 组合方式及开停机计划，使运行费用最小利用动态、决策及路径概念，将机 组最优投入问题设计成类似t s p 问题的模式腩朝，从而可方便地利用蚁群算法 来求解。还有人将蚁群算法编入水利发电规划能源管理软件，可很好地节约能 源。此外，对电力系统中的故障检测，蚁群算法也表现出较好的应用前景。 ( 4 ) 函数优化问题 虽然蚁群算法在离散空间的寻优能力十分突出，但在实际工程的优化中遇 到的大都是连续性问题，所以将蚁群算法应用于连续空间的优化显得尤为重 要。将优化性能良好的蚁群算法用于连续空间优化时，由于此算法的起源模型 和机理来源于离散域，所以须利用人们对优化函数的先验知识和一定方法来协 同构造相应的算法模型，并对蚁群算法中需索实施细节加以修正，从而确定优 化过程中蚁群协同决策所选择的移动方向，由此来求得最优解。已有一些学者 对蚁群算法在函数优化问题方面进行了研究卜虬3 ，但算法参数的选择缺乏严格 的理论证明，算法的优化性能也有待一步提高。 此外，蚁群算法还在数据挖掘、图像处理、系统辨识、机器人设计与控制 领域、化工和军事领域等h 2 方面也有着广泛的应用。 2 4 本章小结 本章主要对蚁群算法做了一个概述，主要介绍了蚁群算法的生物学基 础、原理和蚁群算法的特点及其应用。本章内容为以后章节奠定了理论基 础。 第三章基本蚁群算法 蚁群算法最早成功应用于解决著名的t s p 问题，该算法采用了分布式并行计算机制， 易于与其他方法结合，而且具有较强的鲁棒性。本章以平面上，? 个城市规模的t s p 问题 为例，对基本蚁群算法的数学模型进行了深入分析，并给出了该算法的具体实现步骤及 程序结构框架。 3 1 基本蚁群算法的原理 3 1 1t s p 问题描述 著名的旅行商问题( 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 c 组合优化问 题的典型代表，在蚁群算法中扮演着重要角色，最早的蚁群算法一蚂蚁系统 ( a s ) ，以及后来相继出现的改进蚁群算法开始大都是应用在t s p 问题上，用 来测试其算法的有效性。 t s p 问题的简单形象描述是；给定f 个城市，有个旅行商从某个城市出发， 访问各个城市一次且仅有一次后回到原出发城市，要求找出一条最短的巡回路 径。也可以用图论来表示：设有向图g = ( c l ) ，c = c 1 ，c “? c ，) 是顶点集( 每 个城市为一个顶点) ，l = 也旧，c ，cc 为集合c 中元素( 城市) 两两连接的集 合。4 ，( f ，j = 1 , 2 ，刀) 表示顶点c ，和顶点c ，间的e u c l i d e a n 距离。t s p 的目的 就是从有向图g 中寻找一条长度最短的h a m i l t o n 回路，即遍历所有顶点当且 仅当一次的最短回路。t s p 可分为对称t s p ( s y m m e t r i ct 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 ( a s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ) 两大类。对称 t s p 问题中各节点组成一无向图，各边上的距离有z ，= d ；非对