（检测技术与自动化装置专业论文）蚁群优化算法的改进及其应用.pdf

摘要 题目：蚁群优化算法的改进及其应用 学科：控制科学与工程 硕士研究生姓名：李向丽 摘要 专业：检测技术与自动化装置 导师姓名：杨慧中 人们从仿生学的机理中受到启发，提出许多解决复杂优化问题的新方法，称为元启发 式( m e t a h u e r i s t i c ) 算法，如进化策略、神经网络、模拟退火、禁忌搜索算法等。蚁群 算法( a n tc o l o n ya l g o r i t h m ，简称a c ) 是2 0 世纪9 0 年代初由意大利学者d o r i g o 和m a n i e z z o 等首先提出，在一系列系统优化问题求解中取得了成效。虽然对此方法的研究刚刚起步， 但是这些初步研究己显示出蚁群算法的优越性，证明它是一种很有发展前景的方法。 但是，蚁群算法仍然存在一些缺陷。算法的收敛速度和所得解的多样性、稳定性等性 能间存在矛盾。本文分析了蚁群算法中蚂蚁搜索过程的本质，针对蚁群算法中存在的上述 问题，引入了小生境( n i c h e ) 技术，提出了一种嵌入小生境技术的自适应并行蚁群算法。 该算法充分利用并行算法的特点，强化最优信息的反馈，当算法处于停滞状态时引入小生 境技术。小生境技术在保留部分蚂蚁继续进行局部精确搜索的同时，重新初始化其它蚂蚁， 并通过共享函数来阻止这部分蚂蚁向局部最优移动。这样既保留了原有的较优解，又达到 了跳出局部最优的目的。该算法解决了蚁群算法收敛速度和解的性能之间的矛盾。 在应用范围方面，蚁群算法的应用尚且局限在较小的范围内，难以处理连续空间的优 化问题。为此本文提出种用蚁群算法求解连续空间优化问题的方法，通过修改蚂蚁信息 素的留存方式和行走规则，定义了一个连续空间的蚁群算法。模拟蚂蚁用触角交流信息的 过程提出了直接通信的学习机制，增强了蚂蚁的搜索能力。为了防止出现“早熟”现象， 在局部搜索过程中嵌入了模拟退火的思想。同时为避免过大的残留信息，选择了新的信息 增量计算函数。实例运算证明了该算法可以推广应用到其他连续空间的优化问题中，突破 了基本蚁群算法的应用局限。 另外，我们还将蚁群算法应用到数据聚类问题中，提出了以m a x m i na n ts y s t e m ( m m a s ) 模型为基础的图形聚类方法。在这个算法中只要调整参数占就能得到有效的结果，既不需 要提前给出聚类个数也不需要给出聚类中心。通过大量仿真实例给出了占的参考设定范 围，这就使本算法可以得到广泛的应用。在蚂蚁转移方法中提出了一种基于“聚度”的锦 标赛转移法。实验结果表明了本算法处理不同类型数据的潜力。 关键词：蚁群算法；小生境；并行蚁群算法；连续空间优化；学习机制；模拟退火；图 形聚类 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 ) h a se m e r g e dr e c e n t l ya san e wm e t a - h e u r i s t i cf o rn p - h a r d p r o b l e m s i nc o m b i n a t o r i a l o p t i m i z a t i o n t h i sm e t a - h e u r i s t i c a l s oi n c l u d e s e v o l u t i o n a r y a l g o r i t h m s ，n e u r a ln e t w o r k s ，s i m u l a t e da n n e a l i n ga n dt a b us e a r c hw h i c h a r ea l lb e l o n gt ot h e c l a s so fp r o b l e m - s o l v i n gs t r a t e g i e sd e r i v e df r o mn a t u r e d o r i g o ，m a n i e z z o ，a n dc o l o m iu s i n g t h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) 嬲e x a m p l e ，i n 仃o d u c e dt h ef i r s ta ca l g o r i t h m w i t ht h e f u r t h e rs t u d yi nt h i sa r e a , a n tc o l o n ya l g o r i t h m sa r ew i d e l ya p p l i e dt os o m en pc o m p l e t e p r o b l e m s i td e m o n s t r a t e si t ss u p e r i o r i t yo fs o l v i n gc o m p l i c a t e dc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m s b u t ，t h e r ea r es t i l ls o m ef a u l t si na n tc o l o n ya l g o r i t h m f i r s t l y , t h ed i v e r s i t ya n ds t a b i l i t yo f t h es o l u t i o n ss e a r c h e db ya n tc o l o n ya r ei nc o n f l i c tw i t hc o n v e r g e n c es p e e do f t h ea l g o r i t h m i n c h a p t e rt h r e e ，w ea n a l y z et h ee s s e n c eo fi t ss e a r c hp r o c e s s ，p r o d u c eas e l f - a d a p t i v ep a r a l l e la n t c o l o n ya l g o r i t h mb a s e do nn i c h em e t h o d t h i sa l g o r i t h mu s e sp a r a l l e la n tc o l o n ys y s t e mt o i n t e n s i f yt h ef e e d b a c ko ft h eo p t i m a li n f o r m a t i o n w h e nt h ea n ti ss t a g n a t e d , t h en i c h em e t h o d w i l lb ea p p l i e dt od e t e r m i n et h en u m b e r so fs u b s e t sp o p u l a t i o ns p o n t a n e o u s l y s o m ea n t sk e e p e x p l o r i n gl o c a l l ya n do t h e r sa r er e i n i t i a l i z e dt oj u m po u tf r o mt h el o c a lo p t i m u m t h e r e i n i t i a l i z e da n t sw i l ln o tp l u n g ei n t ot h es a m el o c a lo p t i m u ma g a i nb yt h ee f f e c to fs h a r i n g f u n c t i o n s e c o n d l y , c l a s s i c a la n tc o l o n ya l g o r i t h mi sn o ts u i t a b l ef o rs o l v i n go p t i m i z a t i o np r o b l e m s w i t hc o n t i n u o u ss p a c e s o ，i nc h a p t e rf o u r , w eb r i n gf o r w a r dan e wn o v e la l g o r i t h mt ow h i c hi s d e f i n e db ym o d i l y i n gb o t ht h e t r a i lr e m a i n i n g a n dt h et r a n s f e rr u l e s b a s e do nt h ep r o c e s s e s t h a ta n t s e x c h a n g e i n f o r m a t i o n t h r o u g ha n t e n n a s ，a n o v e l s t u d ys t r a t e g y d i r e c t c o m m u n i c a t i o n i sp r e s e n t e d ，w h i c he n h a n c et h ea n t s a b i l i t yt os e a r c ht h ec o n t i n u o u ss p a c e i n t h em e a n t i m e ，as t r a t e g yo fs i m u l a t e da n n e a l i n gi se m b e d d e di nt h ea l g o r i t h mt oi m p r o v et h e o p t i m i z a t i o np e r f o r m a n c ea n dp r e v e n t p r e m a t u r e l y p h e n o m e n ad u r i n gt h el o c a ls e a r c h i n g i n o r d e rt oa v o i dt h el a r g er e s i d u a li n f o r m a t i o n ，t h en e wi n f o r m a t i o ni n c r e m e n tf u n c t i o ni sa p p l i e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi se f f e c t i v e a na d a p t i v e g r a p h i cc l u s t e r i n ga l g o r i t h m ( a g c m ) b a s e do nm a x m i na n ts y s t e m ( m m a s ) i sp r o p o s e di nc h a p t e rf i v e i nt h i sa l g o r i t h mag o o dr e s u l tc a nb eg o to n l yt h r o u g h a d j u s t i n gt h ep a r a m e t e r 占，n e i t h e rt h en u m b e ro fd a t ac l u s t e r s n o rt h ei n i t i a lg u e s s i n go f c l u s t e rc e n t e r si sr e q u i r e d t h es c o p eo ft h ep a r a m e t e r 占w a sd e t e r m i n e db yv a s tt e s t s ，t h i s m a k e st h ea l g o r i t h ma p p l i e de x t e n s i v e l y an o v e ls e l e c t i o nm e c h a n i s mn a m e dt o u r n a m e n t s e l e c t i o nb a s e do nt h em a s sd e g r e e ( t s b m d ) w a sa d o p t e d ，i ti sm o r ep o w e r f u lt h a n t r a d i t i o n a lr o u l e t t ew h e e ls e l e c t i o n e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h i sa l g o r i t h mi s s u p e r i o rt ot h ee x i s t i n ga n tc o l o n yc l u s t e r i n ga l g o r i t h m s m 扛南大学硕士学位论文 k e y w o r d s ：a n tc o l o n ya l g o r i t h m ；n i c h e ；p a r a l l e la n tc o l o n ys y s t e m ；c o n t i n u o u ss p a c e o p t i m i z a t i o n ；s t u d ys t r a t e g y ；s i m u l a t e da n n e a l i n g ；a n tg r a p h i cc l u s t e r i n ga l g o r i t h m v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 奎自盛日期：凋年弓月日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：查煎面导师签名： 日期：力曰年弓月“e l 第一章绪论 1 1 引言 第一章绪论 生命在长期进化过程中，积累了很多奇特的功能。自然界中的许多自适应优化现象不 断给人以启示：生物体和自然生态系统可通过自身的演化使许多在人类看来高度复杂的优 化问题得到完美的解决。在这种背景下，社会性动物( 如蚁群、蜂群、鸟群等) 的自组织 ( s e l f o r g a n i z a t i o n ) 行为引起了人们的广泛关注，许多学者对这种行为进行数学建模 并用计算机对其进行仿真，这些与经典数学规划原理截然不同的、试图通过模拟自然生态 系统机制以求解复杂优化问题的仿生优化算法相继出现( 如遗传算法“1 、蚁群算法、粒 子群算法0 1 、人工免疫算法、混合蛙跳算法0 1 等) ，大大丰富了现代优化技术，也为传统 优化技术难以处理的组合优化问题提供了切实可行的解决方案。 社会性动物的妙处在于：个体的行为都很简单，但当它们一起协同工作时，却能够“突 现”出非常复杂( 智能) 的行为特征。例如，单只蚂蚁的能力极其有限，但当这些简单的 蚂蚁组成蚁群时，却能完成像筑巢、觅食、迁徙、清扫蚁巢等复杂行为；鸟群在没有集中 控制的情况下能够同步飞行；群行为显得盲目的蜂群能造出精美的蜂窝等。在这些自组 织行为中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注 目。受其启发，意大利学者m d o r i g o ，y m a n i e z z o 和a c o l o r n i 于2 0 世纪9 0 年 代初提出了一种新型的智能优化算法一蚂蚁系统( a n ts y s t e m ，简称a s ) ”1 ，该算法具 有较强的鲁棒性、优良的分布式计算机制、易于与其它方法相结合等优点。3 。尽管蚁群算 法的严格理论基础尚未奠定，国内外的相关研究还处于实验探索和初步应用阶段，但是目 前人们对蚁群算法的研究已经由当初单一的旅行商问题( 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 ) 领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组 合优化问题，由离散域范围内的研究逐渐拓展到了连续域范围内的研究，而且在蚁群 算法的硬件实现上也取得了很多突破性的研究进展，从而使这种新兴的仿生优化算法展现 出勃勃的生机和广阔的前景。 本论文针对蚁群算法的原理、理论和相关应用进行了研究，特别是针对该算法收敛速 度慢且容易出现停滞现象的缺点，提出了一种改进的蚁群算法。同时将改进的蚁群算法应 用于连续空间优化问题和数据的聚类问题，都表现出了良好的效果。 1 2 蚁群算法的思想起源 根据蚂蚁“寻找食物”的群体行为，意大利学者m d o r i g o ，v m a n i e z z o 和a c o l o r n i 于1 9 9 1 年最早提出了蚁群算法的基本模型；1 9 9 2 年m d o r i g o 又在其博士论文中进一 步阐述了蚁群算法的核心思想。 1 2 1 蚂蚁行为描述 根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放出 h 望塑查兰堡主堂垡堡奎 一种特殊的分泌物一信息素来寻找路径。当它们碰到一个还没有走过的路口时，就随机地 挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的 信息素量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量大的路径的概率相对 较大，这样就形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信 息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适 应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能够很快地重新找到最优 路径。这里用图1 1 来进一步说明蚂蚁的搜索原理”1 。假设a 、e 两点是蚁群的巢穴和食 物源，从其间有两条路径a b h d e 和a b c d e ，其中b h 和h d 间距离为l m ，b c 和c d 间距离为0 5 m 。 最初( 即t = 0 时刻) ，当3 0 只蚂蚁走到分支路口b 或者d 点时，要决定往哪个方向走。 因为初始时没有什么线索可供它们选择，所以它们就以相同的概率选择路径，结果是有 1 5 只蚂蚁走左边的路径d h 、b h ；另外1 5 只蚂蚁走右边的路径d c 、b c ，这些蚂蚁 在行进过程中分别留下信息素。若假设蚂蚁都具有相同的速度0 m s ) 和信息素释放能力， 则经过1 s 后从d 点出发的3 0 只蚂蚁有1 5 只到达了h 点，有1 5 只经过c 到达了b 点， 同样的从b 点出发的3 0 只蚂蚁有1 5 只到达了h 点，有1 5 只经过c 到达了d 点。很显 然，在相等的时间间隔内路径d h b 上共有1 5 只蚂蚁经过并遗留了信息素，d c b 上却 有3 0 只蚂蚁经过并遗留了信息素，其信息量强度是d h b 路径上的2 倍。因此，当3 0 只蚂蚁分别回到a 、e 点重新选择路径时就会以2 倍于d h b 的概率选择路径d c b ， 从而d - h b 上的蚂蚁数目变成了1 0 只，是d c b 上蚂蚁数目的一半，距离较短的路径上 信息素很快得到了强化，其优势也很快被蚁群所发现。 不难看出，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈现象：某一路 径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信 息的交流搜索食物，并最终沿着最短路径行进。 e i d d = 0 5 ，c 彳= 0 5 e i j 3 0 a n t s纠n 缸 i13 0 t , a 图1 - 1 蚂蚁选路过程示例 2 2 0 a n 乜 ，s o 。n t s i f 3 0 舳 i a b i a 墨二童堕笙 人工蚂蚁寻找最优路径的方法就是根据上面的真实蚂蚁寻找最优路径的方法提出的， 即让人工蚂蚁根据路径上的相当于信息素( p h e r o m o n e ) 的数字信息量的强度选择路径， 并在所经过的路径上留下相当于信息素的数字信息量，然后随着时间的推移，最优路径上 的数字信息量将积累的越来越大，从而被选择的概率也越来越大，最终所有人工蚂蚁将趋 向于选择该路径。这种模拟蚁群搜索食物的过程与著名的旅行商问题非常相似，因而最初 人工蚁群算法被提出用于求解旅行商问题。 1 2 2 人工蚁群与真实蚁群 蚁群算法是受真实蚂蚁的群体合作行为启发而提出的，它的很多观点都来源于真实蚁 群，人工蚁群和真实蚁群的相似点包括下列几项“： ( 1 ) 在群体中存在个体相互交流通信的机制，这里通常表现为信息量。 真实蚂蚁和人工蚂蚁都存在一种机制改变当前所处的环境：真实蚂蚁在经过的路径上 留下化学刺激物一信息素( p h e r o m o n e ) ，人工蚂蚁在它们经过的路径上改变了路径上存储 的数字信息，这个信息记录了蚂蚁当前解和历史解的性能状态，而且可被其他后继人工蚂 蚁读写。这种数字信息就是算法中所定义的人工信息量，在蚁群优化算法中蚂蚁通过改变 当前路径上的信息量来进行交流协作。这种交流方式改变了当前蚂蚁所经过的路径周围的 环境，同时也以函数的形式改变了整个蚁群所存储的历史信息。通常，在蚂蚁优化算法中 有一个挥发机制，它像真实的信息量挥发一样随着时间的推移改变路径上的人工信息量。 挥发现象使得蚁群可以逐渐忘却历史遗留信息，这样就可以使蚂蚁在选择路径时不局限于 以前蚂蚁所存留的“经验”。 ( 2 ) 群体中每个个体所记录的当前遍历序列。 人工蚂蚁和真实蚂蚁都要完成一个相同的任务：寻找一个从源节点( 巢穴) 到目的节点 ( 食物源) 的最短路径，它们都不具有跳跃性，都只能在相邻节点之间一步一步移动，直至 选择完所有城市得到一个遍历序列。为了能在多次寻路过程中找到最短路径，则应该记录 当前移动序列。 ( 3 ) 利用当前信息进行路径选择的随机选择策略。 人工蚂蚁和真实蚂蚁从一个节点移动到下一个节点的移动方法都是利用概率选择策 略实现的，概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息。 因此，人工蚂蚁和真实蚂蚁所使用的选择策略在时间和空间上都是局部的。 在从真实蚂蚁的行为中获得启发构造蚁群算法的过程中，人工蚂蚁还具备了真实蚂蚁 不具有的一些特性： ( 1 ) 人工蚂蚁存在于一个离散的空间中，它们的移动是一个状态到另一个状态的转换； ( 2 ) 人工蚂蚁具有一个记忆了它本身过去行为的内在状态； ( 3 ) 人工蚂蚁更新信息量的时机是随不同问题而变化的，不反映真实蚁群的行为。如： 有的问题中人工蚂蚁在产生一个解后改变信息量，有的问题中蚂蚁每作出一步选择就更改 信息量，但无论哪种方法，信息量的更新并不是随时可以进行的； ( 4 ) 为了改善系统的性能，人工蚁群算法中可以增加一些性能，如预测未来、局部优 坚堕查堂堡圭堂垡篓苎 化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工蚂蚁可以在局 部优化过程中相互交换信息，还有一些蚁群算法实现了简单预测。 l - 3 蚁群优化的特点 蚁群的觅食行为实际上是一种分布式的协同优化机制。当多只蚂蚁组成蚁群时，其集 体行为才突现出蚂蚁的智能一发现最短路径的能力。在寻找最短路径的过程中，蚂蚁个体 间通过改变环境、感知环境的变化来彼此间接通讯的方式被称为协同机制。在蚁群的觅食 行为中，另一个重要的方面是自催化机制和解的隐式评估。自催化机制实际上是一种正反 馈机制，解的隐式评估是指蚁群将先走完较短的路径。自催化机制和解的隐式评估相结合， 极大地提高了问题的求解效率。自催化机制对基于群体的算法非常有效，如在遗传算法 ( g e n e t i ca l g o r i t h m ，简称g a ) 中，通过选择和复制机制来实现。因为它奖励好的个体， 可以指导搜索方向。当然在使用自催化机制时，要努力避免早熟现象。在蚁群算法中，使 用信息素蒸发和随机状态转移来弥补自催化机制的缺陷。 蚁群算法的主要特点概括如下1 ： 采用分布式控制，不存在中心控制； 每个个体只能感知局部的信息，不能直接使用全局信息； 个体可改变环境，并通过环境来进行间接通讯； 具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的智能； 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会求得全局 最优解； 其优化过程不依赖于优化问题本身的严格数学性质，诸如连续性、可导性，及目 标函数和约束函数的精确数学描述； 是一类基于多主体的智能算法，各主体间通过相互协作来更好地适应环境； 具有潜在的并行性，其搜索过程不是从一点出发，而是同时从多个点同时进行。 这种分布式多智能体的协作过程是异步并发进行的，分布并行模式将大大提高整 个算法的运行效率和快速反应能力。 1 4 蚁群算法的研究现状 1 9 9 1 年，m d o r i g o 等“”提出了第一个蚂蚁系统( a s ) 并成功用于求解t s p 问题。实 验结果表明a s 算法具有较强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如 收敛速度慢、易出现停滞现象等。该算法的出现引起了学者们的广泛关注，并提出了一些 改进的算法。l m g a m b a r d e l l a ，m d o r i g o “”提出了a n t q 算法，该算法用伪随机比 例状态转移规则( p s e u d or a n d o mp r o p o r t i o n a ls t a t et r a n s i t i o nr u l e ) 替换a s 算法 中的随机比例选择规则( s t o c h a s t i cp 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 ) 之间的平衡。除此之外，该算法中还引入了局部信息素更新机制和全局信息素更新中的精 4 兰二兰笪堡 英策略。m d o r i g o 等“1 在a n t - q 算法的基础上提出了蚁群系统( a n tc o l o n ys y s t e m ， 简称h c s ) ，该算法作为a n t q 算法的特例实现起来更为简单，但在求解t s p 问题时具 有相同的性能。s t u t z l e 和h o o s “”提出了最大一最小蚂蚁系统( i a x - m i na n ts y s t e m ， 简称m m a s ) ，该算法的主要特点是为信息素设置上下限来避免算法出现停滞形象。 b u l l n h e i m e r 等“”提出了基于排序的蚂蚁系统( r a n k - b a s e dv e r s i o no fa n ts y s t e m ， a s 。) ，该算法在完成一次迭代后，将蚂蚁所经路径的长度按从小到大的顺序排列，并根 据路径长度赋予不同的权重，路径较短的权重较大，如全局最优解的权重为w ，第r 个 最优解的权重为m a x 0 ，w - r ) 。 国内直到上个世纪末才有学者开始关注蚁群算法，目前对该算法的研究主要停留在算 法的改进和应用方面。吴庆洪和张纪会等啪1 通过向基本蚁群算法中引入变异机制，提出了 具有变异特征的蚁群算法。吴斌和史忠植。1 1 首先在蚁群算法的基础上提出了相遇算法，提 高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合，提出一种 基于蚁群算法的t s p 问题分段求解算法。王颖和谢剑英”1 通过自适应地改变算法的挥发度 等系数，提出一种自适应的蚁群算法以克服限于局部最小的缺点。覃刚力和杨家本”根据 人工蚂蚁所获得解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群 算法。 随着人们对蚁群算法的深入研究，近年来m d o r i g o 等人“2 ”提出了蚁群优化元启 发式( a n tc o l o n yo p t i m i z a t i o nm e t ah e u r i s t i c ，简称a c o - m h ) 这一求解复杂问题的 通用框架。a c o - m h 为蚁群算法的理论研究和算法设计提供了技术上的保障。 在蚁群算法的收敛性方面，w j g u t j a h r 。”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 ) 这一蚁群算法的通用模型， 该模型在一定的条件下能以任意接近1 的概率收敛到最优解。文献 2 7 证明了与模拟退 火( s i m u l a t e da n n e a l i n g ，简称s a ) 相似的结果，即算法能以概率1 收敛到最优解。t s t u t z l e 和m d o r i g o 汹】对一类蚁群算法的收敛性进行了证明，其结论可以直接用到两类 实验上证明是最成功的蚁群算法一m m a s 和a c s 。a b a d r 等油1 将蚁群算法模型转化为分支 随机过程，从分支随机路径和分支w i e n e r 过程的角度推导了蚂蚁路径存亡的比率，并证明 了该过程为稳态分布；孙焘等啪1 对一类简单蚁群算法的收敛性及有关参数问题做了初步研 究；丁建立等。“对一种遗传一蚁群算法的收敛性进行了m a r k o v 理论分析，并证明其优化 解满意值序列单调不增且收敛。 自m d o r i g o 首先将蚁群算法应用于t s p 问题之后，国内外许多学者对其进行了大 量的研究工作，将其推广到了诸多优化邻域，并取得了丰富的成果。v m a n i e z z o ”“等人 将蚁群算法应用于指派问题( 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 ) 。目前，蚁群 算法已是求解q a p 问题最有效的算法之一。a c o l o r n i 等人首先将a s 算法应用于车 间作业调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，简称j s p ) 。实验结果表明，该算法虽 然能解决j s p 问题，但同s t a t e - o f - t h e - a r t 相比较，并没有任何优势。但在用唧a s 算 法求解流动车间调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m , 简称f s s p ) 时，实验结果 显示删a s 算法优于模拟退火和禁忌搜索算法。b u l l n h e i m e r ，h a r t l 和s t r a u s s 1 用算 坚塑盔兰婴主兰垡笙塞 法a s r a n k 来求解车辆路径问题( v e h i c l er o u t i n gp r o b l e m s ，简称v r p ) ，取得了和最优 解非常相近的结果。近几年，g a m b a r d e l l a ，t a i l l a r d 和a g a z z i 嘲对v r p 问题的研究， 对一些基准问题( b e n c h m a r kp r o b l e m ) 的最优解有所提高。蚁群算法在通讯网络领域( 特 别是解决网络路由问题) 的应用受到越来越多学者的关注m “。 除了各种组合优化问题之外，蚁群算法还在控制参数优化啪1 、系统辨识、机器人路 径规划“”、数据挖掘、布局优化设计等领域取得了引入注目的成果。 1 5 本文的主要研究工作 本文围绕蚁群算法的原理、理论及其应用展开研究，全文共分六章，各章内容安排如 下： 第1 章：绪论 本章阐述了蚁群算法产生的背景、原理、特点及其研究现状。首先分析了人工蚂蚁与 真实蚂蚁的异同点，在此基础上对蚁群算法的特点进行了分析。最后，对国内外蚁群算法 的研究现状作了详细的介绍。 第2 章：基本蚁群算法原理及其参数特征 从深层意义上进一步分析了蚁群算法的原理。讨论了基本蚁群算法的系统学特征，给 出了基本蚁群算法的数学模型。对蚁群算法组合参数的选择做了总结。 第3 章：嵌入小生境技术的自适应并行蚁群算法 考虑到算法的收敛速度和所得解的多样性、稳定性等性能间存在矛盾。本章提出了一 种嵌入小生境技术的自适应并行蚁群算法，该算法通过加入小生境技术达到了跳出局部最 优的目的，并通过多个标准t s p 问题来验证该方法的可行性。 第4 章：蚁群算法在连续空间优化中的应用 针对蚁群算法难以处理连续空间的优化问题，本章提出了用蚁群算法求解连续空间优 化问题的方法。为了防止出现“早熟”现象，算法在局部搜索过程中嵌入了模拟退火的思 想。同时模拟蚂蚁用触角交流信息的过程提出了直接通信的学习机制，增强了蚂蚁的搜索 能力。实例运算证明了算法可以推广应用到其它连续空间的优化问题。 第5 章：蚁群算法在聚类中的应用 在第五章提出基于蚁群算法的图形聚类方法。这种方法既不需要预先知道聚类个数也 不需要预先设定聚类中心。通过对模拟数据和实际应用例子的分析，表明这是种性能十分 优越的聚类算法。 第6 章：总结与展望 本章进一步总结了蚁群算法的研究成果。集中讨论了目前蚁群算法研究领域中所存在 的问题，并着重从算法的模型改进、理论分析、应用领域等角度对算法在今后的研究方向 进行了阐述。 6 第二章基本蚁群算法原理及其参数特征 2 1 引言 第二章基本蚁群算法原理及其参数特征 蚁群算法最早成功应用于解决著名的t s p 问题。本章首先以对称t s p 问题为背景， 对基本蚁群算法的数学模型进行了深入分析，并给出了该算法的具体实现步骤、程序结构 框架。 在蚁群算法中，信息素残留因子1 一p 、信息启发式因子o 、期望启发因子b 、信息 素强度q 、蚂蚁数目n l 等都是非常重要的参数，其选取方法和选取原则直接影响到蚁群 算法的全局收敛性和求解效率。但是由于蚁群算法参数空间的庞大性和参数之间的关联 性，如何确定最优组合参数一直是一个极其复杂的优化问题，目前仍没有完善的理论依据， 大多数情况下都是根据经验而定。一般而言，蚁群算法的参数可通过反复试凑得到，这显 然会对蚁群算法的计算效率和收敛性产生不利影响。 基于此，d o r i g om m 等最早对q 、0 、p 、m 等参数的选择进行了初步研究；b o t e eh m 等用遗传算法求得a 、b 、p 、m 等参数的最优组合，但是这种用遗传算法求解组合 参数的方法比较麻烦；随后段海滨等“、郝晋等、叶志伟等“7 1 在蚁群算法的参数分析和 优化组合方面进行了大量的研究工作。本章在对现有蚁群算法参数选择方法综述的基础 上，对每个参数在算法中的特征和作用作了深入分析。 2 2 基本蚁群算法的原理 蚁群算法是一种随机搜索算法，与其它模拟进化算法一样，通过候选解组成的群体的 进化过程来寻求最优解，该过程包含两个基本阶段：适应阶段和协作阶段。在适应阶段， 各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该 路径越容易被选择；时间越长，信息量会越小“”3 。在协作阶段，候选解之间通过信 息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。 蚁群算法实际上是一类智能多主体系统，其自组织本质上是蚁群算法机制在没有外界 作用的情况下使系统信息量增加的动态过程，体现了从无序到有序的动态演化。利用蚁群 算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点，同时按照相应的信 息素更新规则对每只蚂蚁个体的信息素进行增量构建，随后从整体角度规划出蚁群活动的 行为方向，周而复始，即可求出组合优化问题的最优解。 2 2 1 基本蚁群算法模型 由于蚁群模型的定义要受到问题结构的影响，故而选择一种标准的问题是衡量算法好 坏，并与其它算法进行比较的前提。通常选择的问题是旅行商问题( t s p ) ，下面以求解n 个城市的t s p 旅行商问题为例说明a s ( , 6 m ts y s t e m ) 模型”1 。对于其他问题，对此模型稍 作修改就可以应用。 设蚁群中蚂蚁的数量为m ，d o ( i j = l 2 。力表示城市i 和城市j 之间的距离，包( f ) 7 江南大学硕士学位论文 ( i = 1 2 脚表示t 时刻位于城市i 的蚂蚁个数，巧( t ) 表示t 时刻在城市i j 连线上残留的信 , g l 。初始时刻，设气( o ) = c ( c 为常数) 。蚂蚁k ( k = l 2 ，m ) 在运动过程中，根据各条路径 上的信息量决定转移方向。露( ，) 表示在t 时刻蚂蚁k 由城市i 转移到城市j 的概率： 咖) - 熊i f 肛脚 2 p ：( f ) = 。f ：o ) 彬 ( 2 1 ) 【0 o t h e r w i s e 其e e ：巩为先验知识或称为能见度，在t s p 问题中为城市i 转移到城市j 的启发信息， 一般取= 1 矾；a 为在路径i j 上残留信息的重要程度；b 为启发信息的重要程度；与实 际蚁群不同，人工蚁群系统具有记忆功能，t a b u k 舻1 2 。，m ) 用以记录蚂蚁k 当前所走过 的城市，称为禁忌表( 下一步不允许选择的城市) 。集合t a b u k 随着进化过程作动态调整。 经过n 个时刻，所有蚂蚁都完成了一次周游。它们本次周游的禁忌表将满，此时应清空， 将当前蚂蚁所在城市置入t a b u k ，准备下一次周游。 随着时间的推移，以前留下的信息逐渐消逝，用参数户( o p 1 ) 表示信息的挥发因 子，蚂蚁完成一次循环以后( m 只蚂蚁都对n 个城市进行了一次搜索) ，各路径上的信息量 要根据式( 2 2 2 ) 作调整： 勺o + 疗) = ( 1 一p ) 勺( r ) + 勺 ( 2 2 2 ) 毛= “1 ( 2 2 3 ) 其中，毛表示本次循环中路径i j 上的信息量的增量，表示第k 只蚂蚁在本次循环中 留在路径q 上的信息量，它由式( 2 2 4 ) 表示： = 孚当蚂蚁k 走过城市i j 时 飞 0 否则 ( 2 2 4 ) q 为常数，l k 表示第k 只蚂蚁在本次循环中所走过的路径的长度。 根据信息素更新策略的不同，m d o r i g o 提出了三种不同的基本蚁群算法模型，分别 称之为a n t - c y c l e 模型、a n t - q u a n t i t y 模型及a n t - d e n s i t y 模型，其差别在于口苟( r ) 求法的 不同。三种模型如下： 在a n t - c y c l e 模型中 茎三兰苎查墼登兰鲨堕里墨基至鍪壁堡 ，i 孚，若第职蚂蚁在本次循环中经过( i ，j ) 哆( f ) = k ( 2 2 5 2 ) 。 【0 ，翻。 式中q 表示信息素强度，它在一定程度上影响算法的收敛速度：l k 表示第k 只蚂蚁在本 次循环中所走路径的总长度。 在a n t - q u a n t i t y 模型中 i 竽，若第t 只蚂蚁在t 和t + 1 之间经过( i ，j ) 丐( f ) 2 臀硼i(226)0 。 ，否则 二。u 在a n t d e n s i t y 模型中 噶( f ) = 蓊职蚂蚁瓠秕+ 1 之间经过“j ( 2 2 7 ) 蚁群算法实际上是正反馈原理和启发式算法相结合的种算法。在选择路径时，蚂蚁 不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。 三种模型的区别在于：a n t q u a n t i t y 模型和a n t - d e n s i t y 模型中利用的是局部信息， 即蚂蚁完成一步后更新路径上的信息素；而a n t c y c l e 模型中利用的是全局信息更新路径 上的信息素量，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解t s p 时性能较 好，因此通常采用a n t - c y c l e 模型作为蚁群算法的基本模型。 2 2 2 基本蚁群算法的实现步骤 以t s p 问题为例，基本蚁群算法的具体实现步骤如下： ( 1 ) 参数初始化。令时间t = 0 和循环次数n c = 0 ，设置最大循环次数n c 。，将m 蚂蚁 置于1 1 个元素( 城市) 上，令有向图上每条边( i ，j ) 的初始化信息量7i j ( t ) = c o n s t , 其中c o n s t 表示常数，且初始时刻f 。( o ) 印。 ( 2 ) 循环次数n c n c + 1 。 ( 3 ) 蚂蚁的禁忌表索引号k = 1 。 ( 4 ) 蚂蚁数目k k + 1 。 ( 5 ) 蚂蚁个体根据状态转移概率公式( 2 2 1 ) 计算的概率选择元素( 城市) j 并前进， j c t a b u k a ( 6 ) 修改禁忌表指针，即选好之后将蚂蚁移动到新的元素( 城市) ，并把该元素( 城市) 移动到该蚂蚁个体的禁忌表中。 ( 7 ) 若集合c 中元素( 城市) 未遍历完，即k n c n m ，则循环结束并输出程序计算结果， 否则清空禁忌表并跳转到第( 2 ) 步。 9 江南大学硕士学位论文 2