（计算机应用技术专业论文）蚁群算法在组合优化中的应用.pdf

摘要 组合优化中的许多问题是n p 一完全问题，也是科学和工程计算中重要和基本的 问题，这类问题的求解一直是算法研究领域的热点问题。对于n p 完全的组合优化 问题，至今尚无很好的解析算法，一般采用启发式算法来解决。蚁群算法作为一 种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点， 使其能够成功地解决许多n p 完全的组合优化问题。本文在详细介绍蚁群算法原理 的基础上，对蚁群算法在组合优化问题中的应用进行分析和研究，主要将蚁群算 法应用于求解最大团和最大割两个经典的n p 完全组合优化问题，本文主要做了以 下工作； 1 、在研究已有的最大团问题的蚁群算法以及对蚁群算法深入分析的基础上， 根据最大团问题的特点，提出了最大团问题的新型蚁群算法，通过大量的仿真试 验证明，算法的性能明显提高了。 2 、以最大团问题为例，对蚁群算法的参数进行了深入研究，并提出了使用动 态局部启发信息的改进策略。仿真试验证明，该方案使算法的性能得到一定的提 高。 3 、在研究了组合优化问题基础上，提出了最大割问题的蚁群算法方案。大量 的仿真试验证明，该方案能较成功地解决最大割问题。 关键词：蚁群算法组合优化最大团最大割 a b s t r a c t m a i l yc o m b i n a t o “a lo p t i m i z a t i o np r o b l e m s ，w h i c ha r ef u n d 锄e n t a la n di m p o n a n t i ns c i e n c ea n de n g i n e e r i n gc a l c u l a t i o n ，a r en p - c o m p l e t ep r o b l e m s t h es o l u t i o no f t h e s ep r o b l e m sh a sb e e nm ek e yp r d b l e m si nt h es t u d yo fa l g o r i m mt h e o r y f 0 r n p - c o m p l e t ec o m b i n a t i o no p t i m i z a t i o np r o b l e m s ，t h e r ei sn oe f f i c i e n ta l g o r i t h mt ot h e s o l u t i o no ft h ep r o b l e m s c o n s e q u e n t l y ，h e u r i s t i ca l g o r i t h m sm a yb eu s e dt os o l v es u c h t y p e o fp r o b l e m s a san e wh e u r i s t i ca i g o r i t l l m ，a n tc 0 1 0 n yo p t i m i z a t i o n ( a c o ) a l g o r i t h mw h o s em a i nc h a r a c t e r i s t i c sa r ep o s i t i v ef e e d b a c k ，d i s t f i b u t e dc o m p u t a t i o n a n dc o n s t n l c t i v e g r e e d y h e u r i s t i cc a ns o l v e m a l l yn p - c o m p l e t e c o m b i n a i i o n o p t i m i z a t i o np r o b l e m ss u c c e s s f u l l y t h i st h e s j si n t r o d u c e st 王l ep r i n c i p l e so fa c 0 i n d e t a i la n dd e s c r i b e so u rd e e pr e s e a r c hw o r ki nt h ea p p l i c a t i o no fc o m b i n a t i o n o p t i m i z a t j o np m b l e m s w ba p p l ya c o t 0m a 】( 油u mc l i q u ep r o b l e m sa n dm a 】【c u t p r o b l e m s ，w h i c ha r et y p i c a ln p - c o m p l e t ec o m b i n a t i o no p t i m i z a t i o np r o b l e m s t 1 l e m a i n n t r i b u t j o no ft h i st h e s i si sa sf o l l o w s ： 1 、b a s e do nt h ec h a r a c t e r i s t i c so fm a x i m u md i q u cp r o b l e m s ( m a ) an e w v e r s i o no fa c oi sp r o p o s c dt 0s o l v em c p _ t 1 l es i m u l a t i o nr e s u l t ss h o wt h a tm e p r o p o s e dh c u r i s t i ca i l tc o l o n yo p t 蛔i z a t i o ni se 侬圮t i v ea n d e f f i c i e n tf b rm c p 2 、b a s e do nt h ed e t a i ld i s c u s s i o no fa c o sc h a r a c t e r i s t i c s ，s u c h 鹤p a r 锄e t e r s s e t t i n g ，t i m ec o m p l c x i t ya n ds oo n ，w ed e s i g l l e dal o c a ld y n a m i ch c u r i s t i ca 1 9 0 r i t h mt o i i n p m v et h ep e 咖姗a i l c eo ft h ea l g 耐m m s i m u l a t i o r e s u l t sd e m o n s t r a t et h a t t h e i n l p m v e da 1 9 0 r i t l l i i lc a l la c h i e v eb e t t e rp e r f b 瑚a n c et h a i lb e f o r c 3 、h e u r i s t i ca n tc 0 1 0 n yo p t i m i z a t i o ni sc x t e n d e df o rs o l v 啦m 强c u tp r o b l e m s n ee 脓t i v e n e s so ft h ea l g o r i t h mi sd e m 衄s t r a t e d b ys i m u l a t i o n s k e y w o r d s ：a n tc o l o n yo p u m i z a t i o na i g o r i t h m c o m b i n a t o r i a io p t i m i z a t i 蛐 m 懿i m u mc l i q u ep m b i e mm a x c u tp m b i e m y8 5 9 0 6 6 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：鬯艳 日期彬j 冲 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： 导师签名： 嗜抱 福绯 日期d 占立2 争 日期口o ? 、够 f 第一章绪论 第一章绪论 1 1 研究背景 随着计算机科学的飞速发展，针对离散变量的优化问题被逐渐重视，从而形 成了有别于数学规划的另一类重要模型，即组合优化( c o m b i n a t o r i a l 0 d t i m i z a t i o n ) 。越来越多的人开始研究组合优化问题，提出许多新的方法和思路， 使得组合优化问题内容更加丰富。组合优化问题的求解一直是近年来研究的热点 领域之一 组合优化就是离散优化，它是通过数学方法寻找离散事件的最优编排、分组、 次序或筛选等。组合优化问题【2 3 l 通常可描述为：令q - “，岛o 为所有状态构 成殴解空间，c ( s 。) 为状态s i 对应的目标函数值，要求寻求最优解s ，使得 v 岛q ，c 0 + ) 一n l i n c “) 。对组合优化问题的研究，特别是求解复杂组合优化 问题方法的探索已成为众多学科关注的焦点，这不仅在于其内在的复杂性有着重 要的理论价值，也在于它们在现实生活中的很多方面有着广泛的应用。 典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ) 、加工调度 问题( s c h e d u l i n gp r o b l e m ) 、o 1 背包问题( o 1 虹a p s a c kp r0 _ b l 锄) 、装箱f 习题( b i p a c k m gp r o b l e m ) 、图着色问题( g m p hc o l o r i n gp r o b l e m ) 、聚类问题( d u s t e f i f 嘻 p d 0 b l e m ) 以及最大团问题( m 驭i m 哪c l i q u ep r o b l e m ) 和最大割问题( m a x c i l t p d 0 b l e m ) 等。这些问题数学描述非常简单，理论上说每一个组合优化问题都可以 通过枚举的方法求得最优解，但枚举是以时闻为代价的，有的枚举时间还可以接 受，有豹则不可能接受，即所谓的“组合爆炸”。对于这些n p 完全【2 均刎的缀合 优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。 近些年来，随着计算机技术的发展，一些新的启发式智能化方法愈来愈引起 了众多学者的关注和兴趣。诸如神经网络( n c u m ln e t w o r k ) 、模拟退火( s i m l l l a t e d a n n e a l i n g ) 、禁忌搜索( t a b us e a r c h ) 、进化算法( e v o l u t i o n a r ya l g o r i t t 哪s ) 、蚁群算 法( 观t l yo p t i m i 髓t i o n 越窖吲t h m ) 、d n a 计算( d n ac o m p u t a 6 ) 等，它们 毫无争议地成为解决组合爆炸及栅类问题的锐利工具。然而，面对各种问题的 特殊性和复杂性，每一种算法都表现出其自身的优势和缺陷，都会面临时间性能 和优化性能的双重挑战。 蚁群算法( a n to o l o n yo p t i i i l j z a t i o na l g o r i t h m ，a c 0 ) 是由意大利学者 2 蚁群算法在组合优化中的应用 m d 硎g o 等1 1 】人在2 0 世纪9 0 年代初通过模拟自然界中蚂蚁集体觅食的彳亍为而提 出的一种基于种群的启发式仿生类算法。它是继模拟退火算法、遗传算法、禁忌 搜索算法、神经网络算法等启发式搜索算法以后的又一种应用于组合优化问题的 启发式搜索算法。虽然与已经发展完备的一些启发式算法比较起来，蚁群算法的 计算量比较大、搜索时间长、有时候效果并不理想，但是它的成功运用还是激起 了人们对蚁群算法的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。众 多的研究结果已经证明，蚁群算法具有很强的发现较好解的能力，该算法不仅利 用了正反馈原理加快进化过程，而且是一种本质并行的算法，不同个体之间不断 进行信息的交流和传递，从而能够相互协作，有利于发现较好解。由于鲁棒性强， 使得蚁群算法易于解决各种不同的优化问题。但该算法的研究毕竟刚网0 开始，还 未形成系统的分析方法和坚实的数学基础，许多问题还有待于进一步研究。 1 2 蚁群算法的研究历史和现状 最先提出的蚁群算法被称为a s 【4 川( a n ts y s t 啪) ，它是m d 嘶g o 、a c o l o m i 、 v ：m 趾i c z z o 在意大利的米兰理工学院合作研究组合优化问题的计算机智能解决方 法时的研究成果。a s 算法首先应用于解决旅行商问题( t s p ) ，随后v ：m a i l i e z z o 、 a c o l o m i 把a s 算法用于解决二次分配问题( q a p ) 。最初的a s 算法的效果并不 理想，但是后续的研究将蚁群算法和局部搜索以及其它的一些优化方法相结合获 得的许多令人振奋的成果。 1 9 9 5 年l m g a n l b a r d e l l a 和m d o i i g o 提出了a n t q 算法 8 - 9 】。该算法建立了 a s 与q 学习机制( q 1 e a r n i n g ) 【1 0 】的联系。它在a s 算法的随机比例规则基础上， 在解构造过程中提出了伪随机比例状态迁移规则( p s e u d 0 糟n d o m p r o p o f t i o n a l s t a t et r 姐s i t i o nf i l l e ) 从而能够实现解构造过程中知识探索( c x 口l o 豫t i 嘶) 和知识利 用( e x p l o i t a t i o n ) 的平衡，并引入信息素局部更新过程，信息素局部更新规则使 用了q 学习机制。此外，在信息素的全局更新中采用了精英策略。a n t q 是一个 非常有效的算法。 此后，m d 嘶g o 和l m g a m b a r d e l l a 在a n t q 算法基础上提出了a c s 【1 1 - 1 2 】( a n t c o l o n y s y s t e m ) ；t - s t 讹z l e 和h h 0 0 s 提出了m m a s 【”j ( m a x m 玳a n ts y s t e i ：n ) 。 这两种扩展的蚂蚁算法都被用于解决对称旅行商问题( 髑p ) 以及非对称旅行商 问题( 盯s p ) ，并取得了比较满意的结果。m m a s 算法采用了用当前找到的最好 解来更新信息素指引蚂蚁向更高质量的解空间搜索的贪婪策略，并对信息素设立 上下限来避免算法的早熟。 第一章绪论 3 1 9 9 9 年，m d o r i g o 、q d i c a m 和l m g 锄b a r d e l l a 把此前各种基于a s 演化 而得的算法归结到一个统一的框架中，并提供了抽象而规范的算法描述，称为 a c o 元启发式算法【1 4 】( 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 c o 算 法。 a c o 算法的优点在于：利用了正反馈原理加快进化过程；是一种本质并行的 算法：不同个体之间不断进行信息的交流和传递，从而能够相互协作，有利于发 现较好的解；由于鲁棒性强，故易于解决各种不同的优化问题。但是，蚁群算法 的计算量比较大、搜索时间长、有时候效果并不理想，国内外的研究人员针对蚁 群算法的这些问题，做了许多研究工作，有的将蚁群算法与其它算法相结合，有 的给蚁群系统加入变异特征，取得了许多研究和应用成果。 b b u l l n h e i m e f 等【2 8 】提出了一种基于蚂蚁等级的a s r c n k 算法。w j g u t a h r l 2 9 。3 0 】 提出了基于图的蚂蚁算法g b a s ( g r a p h - b a s e d a n ts y s t e m ) ，并证明了算法将以概 率1 一收敛于最优解。其中，可以通过选择足够大的蚂蚁数量或足够小的信息 素挥发系数p 来获得任意小的值。c b l u m 【3 1 l 针对可转换为o 1 整数规划问题的组 合优化问题，提出了一种h c a c o 算法。该算法利用一些策略来避免算法陷入局 部最优解。 吴庆洪【15 】等人提出了具有变异特征的蚁群算法，有机地结合了2 一o p t 方法，提 高了算法的搜索速度。吴斌、史忠植【1 6 l 在蚁群算法的基础上提出了相遇算法，其 基本思想是在求解t s p 问题中，用两只蚂蚁共同完成对一条路径的搜索，并将相遇 算法与采用并行策略的分段算法相结合提出一种基于蚁群算法的t s p 问题分段求 解算法，提高搜索速度。陈蛟、沈洁、秦玲【”l 等针对蚁群算法加速收敛和早熟停 滞现象的矛盾，提出了一种基于分布均匀度的自适应蚁群算法。该算法根据优化 过程中解的分布均匀度，自适应地调整路径选择概率策略和信息素更新策略，以 求在加速收敛和防止早熟、停滞现象之间取得很好的平衡。朱庆保、杨志军【1 8 】针 对蚁群算法在进行大规模优化时收敛时间过长，提出了基于变异和动态信息素更 新的蚁群优化算法。该算法以最近的邻居节点选择和动态信息素更新策略来加速 全局收敛，以一种独特的变异策略来加快局部寻优，使收敛速度大幅度地提高。 i w j t a n a b e 和s m a t s u i 【3 2 l 通过自适应的控制候选集合，改善a c 0 算法性能； p ：k o r o e s 和j i l c p 3 】用多级的a c o 算法解决了网络划分问题( m e s hp a f t i t i o n i l l g p r o b l e m ) ；c s o l n o n 【3 4 j 研究了蚁群算法搜索的多样性和快速收敛性之间的矛盾， 通过对算法参数的研究提出了在算法初期增加预处理步骤，希望在不影响搜索多 样性的前提下，提高收敛速度，通过对约束满足问题( c o n s t r a i ns a t i s f a c t i p r o b l 锄) 的仿真试验表明了算法确实能提高速度。 4 蚁群算法在组合优化中的应用 目前大量的研究工作注重于a c o 的实际应用唧瑚i ，然而，近几年的研究发现： a c o 用于解决组合优化问题时，也会遇到类似进化算法中的d e c e p f i o n 和b i a s 现象。例如：c b l u m 和m s 锄p e l s 【鲫j 研究a c o 用于作业调度问题( s h o ps c h e d u l i n g p r o b l e m s ) 时发现：一段时间之后a c o 的性能会由于信息索模式和处理的问题实 例而下降，这种现象称为：s e c o n d o r d c rd e c e p t i o n 【4 l 】或者s e a r c hb i a s ，它意味着随 着时间的推移找到更好解的可能性越来越小。j m o m g o m e r y l 4 2 】等试图找出导致算 法s e a r c hb i a s 的原因；c b l u m 和m d 耐g o f 3 5 l 针对蚁群算法求解组合优化是遇到 的s e c o n do r d e rd e c e p t i o n 问题，做了大量的研究工作。然而算法性能的下降原因 仍然是未知的，这些情况表明我们需要对a c o 算法行为做更多更深入的了解。 应当指出，现阶段对蚁群算法的研究大多还只是停留在仿真阶段，尚未能提 出一个完善的理论分析，对它的有效性也没有给出严格的数学解释。但是，理论 上的不完善并不妨碍应用，有时应用还会超前于理论，并推动理论研究，蚁群算 法的研究正是如此。 目前，蚁群算法已成为国际智能计算领域关注的热点和前沿课题。1 9 9 8 年在 布鲁塞尔专门召开了第一届蚂蚁优化国际研讨会，以后每两年召开一次。尽管蚁 群算法的严格理论基础尚未奠定，但这种新兴的智能进化仿生算法已展现出勃勃 生机。 1 3 论文研究目的及主要内容 蚁群算法从其机理来说是一种天然的组合优化方法，在解决组合优化问题的 应用中相对其它的各类启发式搜索算法，具有明显的优越性。本文在详细介绍 蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行研究。 本文以下各章节的基本内容组织如下： 第二章；在介绍了蚁群算法的基本原理的基础上，以经典组合优化问题t s p 问题为例，详细介绍了其解决组合优化问题的基本框架。 第三章：用蚁群算法思想解决经典组合优化问题最大团问题。首先介绍了 传统蚁群算法解决最大团问题的策略，接着介绍了一种针对子集类问题的新型蚁 群算法。最后将最大团闯题看作子集类问题，提出了最大团问题的新型蚁群算法， 并分析了算法的时间复杂度。大量的仿真实验研究表明，该算法较最大团闯题的 传统蚁群算法有着更短的运行时间，更强的求解能力。 第四章：研究了蚁群算法的中各种参数对算法性能的影响，提出了针对参数 第一章绪论5 的改进策略，获得了比较好的实验结果。 第五章：提出了最大割问题的蚁群算法解决方案，并且指出了该算法下一步 的研究方向。 第六章：总结了本文的主要内容，以及自己在蚁群算法方面所作的研究工作， 并且明确了以后的研究方向。 本文的研究得到国家自然科学基金项目( n o 3 0 4 7 0 4 1 4 ) 的资助。 蚁群算法在组合优化中的应用 第二章蚁群算法 2 1 概述 蚁群算法( a n tc 0 l o n y0 p t i m i z a t i o na l g o r i t i l m ，a c 0 ) 是由意大利学者 m d o r i g o 等人在2 0 世纪9 0 年代初提出的一种源于生物世界的新的启发式仿生 类算法。它模拟自然界中蚂蚁集体觅食的行为。 生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢穴之间的最短路 径，而单只蚂蚁却不能。大量细致观察研究发现，蚂蚁个体之间通过一种被称为 信息素( p h e r o m o n e ) 的物质进行信息传递，以达到协同工作的目的。蚂蚁在运动 过程中，能够在它所经过的路径上留下信息素，而且蚂蚁在运动过程中能够感知 这种物质，一条路上的信息素踪迹越浓，其它蚂蚁跟随此路径的概率越高，从而 该路径上的信息素踪迹会被加强，这样就会有更多的蚂蚁选择这条路；而某些路 径上通过的蚂蚁较少时路径上的信息素就会随时间的推移而蒸发。蚂蚁个体之间 就是通过这种间接的通信机制达到协同搜索食物最短路径的目的，它们作为一个 群体所表现出来的行为是一种自催化( a u t o c a l a l y l i c ) 行为，整个过程具有正反馈 的特征。 蚁群算法就是根据蚁群觅食活动的规律，建立的一个利用群体智能进行优化 搜索的模型，相对其它的各类启发式搜索算法，蚁群算法具有明显的优越性。它 在一系列m 完全组合优化问题的求解中取得了卓有成效的结果，其典型代表有 旅行商问题1 2 5 粕】( t r a v e l i l l gs a l e 锄a np d d b l e m ，t s p ) 、指派问题田j ( q u a d m l i c 舔s i g 啪e n tp r o b l e m ，q a p ) ，作业调度( j o b s h o p ) 等经典组合优化问题。为n p 完全组合优化问题提供了新颖且有竞争力的求解方法。 2 2 蚁群算法基本原理 蚁群算法最初随机的选择搜索路径，随着对解空间的“了解”，搜索变得有 规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间的“了解”是 通过观察蚁群觅食活动中建立的机制而得到的，由蚂蚁觅食的过程可以看出，其 协作方式的本质是：信息素踪迹越浓的路径，被选中的概率越大，即路径概率 选择机制：路径越短，它上面的信息素踪迹增长得越快，即信息素更新机制； f 第二章蚁群算法 7 蚂蚁之间通过信息素进行通信，即协同工作机制。 为了进一步说明蚂蚁群体的路径搜索原理和机制，下面我们引用m d o r i g o 、 v m a i l i e z z o 和a c o l o m i 所举的例子来具体说明蚁群系统的原理【6 j ： ( a ) 各存3 0 只准备离开b 和d ( b ) 各有1 5 只选择c 和f( c ) 2 0 只选择c ，1 0 只选择f 图2 1 蚁群觅食行为不意图 如图2 1 所示，假设蚂蚁在食物源a 和巢穴e 之间运动，每单位时间内爬行 单位距离，图中d 为距离，且每单位时闻内各有3 0 只蚂蚁从巢穴和食物源出发， ( 图2 1 ( a ) ) 。 假设t = o 时，有3 0 只蚂蚁在点b 和点d ( 图2 1 ( b ) ) 。由于此时路上无信息 素，蚂蚁就以相同的概率走两条路中的一条，因而在点b 和点d 各有1 5 只蚂蚁 选择往c ，其余1 5 只选择往f 。t = 1 时，经过c 的路径被3 0 只蚂蚁爬过，而路 径b f 和d f 只被1 5 只蚂蚁爬过，从而b c d 上的信息素踪迹的浓度是b f d 的2 倍。此时，又有3 0 只蚂蚁离开b ( 和d ) ，于是有2 0 只蚂蚁选择往c ，另外1 0 只蚂蚁选择往f ，这样更多的信息素被留在更短的路径b c d 上。这样一来，较短 路径b c d 上的信息素踪迹变的更浓，越来越多的蚂蚁选择这条短路径。整个选 路过程如此往复，即实现了随机选择到自适应行为的过程。 “蚁群中的蚂蚁以信息素为媒介的间接的联系方式是蚁群算法的最大的 特点”。蚁群优化算法吸收了蚂蚁的行为特性( 内在搜索机制) ，它设计虚拟的“人 工蚂蚁( a n i f i c i a la _ n t s ) ”，让它们摸索不同路线，并留下会随时间逐渐消失的虚 拟“信息素”，根据“信息素较浓的路线更近”的原则，即可选出最佳路线。蚁群 算法中使用的人工蚂蚁决不是对实际蚂蚁的一种简单模拟，而是经过改进的蚂蚁， 在某些行为上与真实蚂蚁路有不同，它融进了入类的智能：人工蚂蚁有一定的记 忆，它能够记忆已经访问过的节点；人工蚁群在选择下一条路径时并不是完全盲 目的，而是按照一定的算法有意识地寻找最短路径，比如在碣p 问题中，蚂蚁可 以预先知道下一个节点的距离；人工蚂蚁生活的时空是离散的。 蚁群算法在优化过程中有两个重要的规则： 蕃 多萋 引j订l一 多 暾差i| 丑可 乡沁 李 8 蚁群算法在组合优化中的应用 ( 1 ) 蚂蚁在众多的路径中转移路线的选择规则：蚂蚁总是倾向于选择含有 较多信息素的路径。 这里信息素( p h e r o m o n e ) 类似于一种分布式的长期记忆，这种记忆不是局 部地存在于单个的人工蚁，而是全局地分布在整个问题空间，这就导致了一种间 接联络方式。 ( 2 ) 全局化信息素更新规蜘：在路径上的信息素，有一部分会被蒸发散失， 这样没有被选择过的路径信息素越来越少，交得越来越不受欢迎。每只蚂蚁按路 径的长短( 或找到食物的质量) 成比例地在属于其经过的路径上留下一定数量的 信息素。 信息素更新的实质就是人工蚂蚁根据真实蚂蚁在访问过的边上留下的信息 素和蒸发的信息素来模拟真实信息素数量的变化，它使得越好的解答得到越多的 增强。 这就形成了一种自催化强化学习( a m t o c a t a l y t i cr e i n f o i c e m e mk a m 协g ) 机制。 2 3 蚁群算法框架 各种基于蚁群或其它社会性昆虫搜索特性的方法都是以正反馈( p o s i t i v e f e e d b a c k ) 为基础的。蚁群算法最初随机的选择搜索路径，通过对较好解的增强， 使搜索变得有规律，并逐渐逼近直至最终达到全局最优解。在蚁群算法中是通过 虚拟信息素( n u a lp h e r 咖o n e ) 来实现信息正反馈的。蚁群算法的机理可以抽 象为以下过程；一群人工蚁( a - r t i f i c i a la n t s ) 相互协作在问题的解空间中搜索好 的解，这些人工蚁按照虚拟信息素和启发式信息的指引在问题的解空间一步一步 地移动以构造问题的解，同时他们根据解的质量在其路径上留下相应浓度的信息 素，蚁群中的其他蚂蚁倾向于沿着信息素浓的路径前进，同样这些蚂蚁也将在这 段路径上留下自己的信息素，这就形成了信息的正反馈( p o s i t i v ef c e d b a c k ) 。这 种正反馈机制将指引蚁群找到高质量的问题解。同时，为了避免正反馈中出现早 熟现象( s t a 弘a t i o n ) ，算法中还需引入负反馈( n g a t i v ef c e 曲a c k ) 机制。在蚁群 算法中，负反馈机制是利用信息素的挥发( e v a p o f a t i o n ) 来实现的。算法中信息 素的挥发强度不能太弱以防早熟现象的产生；另外，挥发强度也不能太强，否则 个体间的协作将受到抑制。在蚁群算法中另一个非常重要的组成要素是协同工作 机制：人工蚁之间通过虚拟信息素建立的协作行为( c 0 0 p e m t i v eb e h a v i o r ) ，个体 的行为通过协作行为被集中起来形成对环境的同步探索。 蚁群算法解决组合优化问题有着明显的优势：因为蚁群算法作为一种新的启 第二二章蚁群算法 9 发式算法具有以下特征【1 】： ( 1 ) 它是通用的( v e r s 8 t i l c ) 。它可以应用于求解多种组合优化问题。对不同问题， 不需要或仅需做少量的改动就可直接应用，例如：此算法既可以直接应用于t s p ， 也可不霈改动的应用于a t s p ( 不对称t s p ) ； ( 2 ) 它是鲁棒的( m b u s t ) 。它的性能不因组合优化问题的不同而不同； ( 3 ) 它是一种基于群体的方法( ap o p u l a t i o nb a s e d 印p r o a c h ) 。由多个个体 ( m u l t i a g e n t ) 组成，个体之间可以互相交流信息，并互相影响，使整体达到某个目 的。这个特征将使它可以将j 下反馈作为一种搜索机制，而且它也可以应用于并行 系统。 a c o 算法己被成功地用于求解组合优化的近似最优解4 1 。用a c o 算法求 解组合优化问题的关键在于：( 1 ) 将待求解问题表示成相应的带权图；( 2 ) 定义一种 正反馈过程( 如a s 算法中蚂蚁释放一定量的信息素到边上) ；( 3 ) 定义一种负反馈 过程( 如a s 算法中信息素的蒸发机制) ；( 4 ) 问题结构本身能提供解题用的启发式 信息( 如a s 算法中城市间的距离) ；( 5 ) 建立约束机制( 如a s 算法中的蔡忌表) 。 当解决了这些关键问题后，就可以构造解决特定问题的a c 0 算法。 一般而言，用于解决各种组合优化问题的a c o 算法都遵循如下的统一算法 框架1 2 1 2 4 】： 口r o c e d u r e 组合优化问题的a c o 算法 设置参数，初始化信息素分布； w h i l e 不满足结束条件d 0 f o r 蚁群中的每个蚂蚁 f o r 每个解构造步( 直到构造出完整解) 蚂蚁按信息素及启发式信息的指引构造一步问题的解： 进行信息素局部更新( 可选) ； e n do f f o r e n d o f f o r 以某些已获得的解为起点进行领域( 局部) 搜索( 可选) ； 根据某些已获得解的质量进行全局更新信息素； e n d0 f w 城l e e n do fp i d c e d u f e 下面，以m d o r i g o 等提出的第一个a c o 算法一a s 算法( a m ts y s t e m ) 求解 旅行商问题( t s p ) 为例来说明a c o 算法解决组合优化问题时的算法模型。假设 有n 个城市，t s p 问题的目标是寻找一个路径最短的最优旅行路线，旅行商经过 1 0 蚁群算法在组合优化中的应用 所有城市并回到原出发城市，除出发城市外，每个城市只允许经过一次，t s p 问 题的可行解即为除出发城市外所有城市的一个无重复序列。 显然，可将每个城市都映射为图中的节点，城市之间的道路映射为图中的连 接。在蚂蚁系统中，蚂蚁由个城市运动到另一个城市，逐步完成它们的搜索过 程。在算法迭代过程中，每只蚂蚁七忙- 1 2 ，以) 根据概率转换规则生成一个有 步过程的行动路线。算法的迭代次数记为f ，1 s f s f 。其中，f 。是预先设定的 算法最大迭代次数。 在第f 次迭代时，第七只蚂蚁由城市f 选择连接( f ，f ) 转到城市j 的概率为： 露o ) * h ( f ) 】。o ) r 。五哪矿啪妒 0 萄口f f o w 以t ( f ) 否则 ( 2 1 ) 卜- a c 0 算法迭代次数，每迭代一次，图各条连接上的信息素浓度都会发生 变化； p 。o ) 一蚂蚁七在第f 次迭代时选择节点f 到节点j 的连接的概率： 口砌眦破o ) 蚂蚁七在节点f 处所能到达的节点集合； 气( f ) 一连接( f ，j ) 上的信息素在第f 次迭代时的浓度： ( f ) 一连接( f ，) 的局部启发信息，是一种基于具体优化问题和蚂蚁已经构造 出的部分解的启发信息，通过利用一些局部经验构造商质量的解。在璐p 问题中， ( 1 ) 可以设为城市i 与城市j 之间距离的倒数； d 、口一协调连接上的信息素和局部启发信息这两种启发信息韵因子。 在a c o 算法中，连接上的信息素浓度( f ) 与基于具体优化问题的局部启发 信息巩( f ) 是引导蚂蚁构造问题解的两种启发信息。( f ) 是路过该连接的蚂蚁在完 成一条路径后，根据对所生成解的评价释放的信息素，解的质量越高，信息浓度 就越高；( f ) 则是基于具体的优化问题，以及蚂蚁当前走过的路径所对应的部分 解，利用构造该优化问题解的经验( 如最短路问题中的贪婪法则) ，判断选择该连 接的优劣，不考虑后面的路径和其他蚂蚁的经验。口、卢是协调上述两种信息的 因子。是两个可以调整的参数，用于控制信息素和局部启发信息的相对权值。如 果a 一0 ，则最近的城市容易被选择，信息素不再起任何作用，算法转化为经典的 第二章蚁群算法 1 1 随机贪婪算法。如果芦一0 ，则只有信息素放大机制在独自工作，这将导致算法迅 速获得一个可能是非最优的解。因此在信息素浓度和局部启发信息之间确定一种 折中关系是非常必要的。一般而言，对于适用贪婪法则的问题，口应较大；要加 快收敛，口应较大。 当蚂蚁完成一条路径( 在t s p 中是全部城市遍历一次) 后，各路径上的信息 素作更新，在a s 算法最初提出时有三种轨迹更新方式，分别称之为：a n t - q u 锄t i t y s y s t e m ，a i l t d e 璐i t ys y s t e m ，a n t c y c l es y s t e m ，它们的差别在于表达式a 定义的 不同：在a n t q u a n t i t y 算法中，从城市到，的蚂蚁在路径上残留的信息素量为一 个与路径无关的常量q ；在a n t - d e n s i t y 算法中，从城市f 到j 的蚂蚁在路径上残留 的信息素量为q d 由于略为城市f 到城市j 的距离，因而残留的信息素量会随 着城市间距离的不同而变化；在这两种方式中，蚂蚁每移动一步就要进行轨迹更 新，它们都属于在线逐步( 叩l i n es t e pb ys t 印) 的更新方式；而下面所用的更新方 式a t c v d e 则是在一个环游完成之后才更新相关弧的轨迹，它是一种在线延迟 ( o n l i n ed e l a y e d ) 的更新方式。有关模拟表明其寻优性能优于前两种方式。在 a n t c y d e 算法中，从城市f 到j 的蚂蚁在路径上残留的信息素量与该次循环中所获 得解( 路径) 的优劣有关，更新规则会让短路径( 较优解) 上对应的信息素量逐 渐增大。 在第f 次迭代结束后，每只蚂蚁七在路径( f ，) 上留下一定的信息素o ) 。 其计算公式如下： 礤) | q 觜 弦z ， 其中，s ( f ) 是第七只蚂蚁在第f 次迭代经过的路径，r o ) 是该路径的长度， q 是一个预置参数。 为了防止信息素过早地聚集到迭代初期找到的路径上，信息素要有个“挥发” 机制。没有信息索挥发的路径搜索方法并不能获得理想的效果，它很可能导致初 始化随机波动的进一步放大，从而得到一个非最优解。为了保证对解空间的充分 搜索，有必要引入信息素挥发机制，否则所有的蚂蚁都可能停滞于相同的路径。 在算法设计中，通过引入信息索挥发系数p ( 0 墨p 1 ) 来模拟挥发过程。每条路 径都遵循一致的信息素挥发规则： 1 2 蚁群算法在组合优化中的应用 o + 1 ) a ( 1 一p 心( f ) + ( f ) ( 2 3 ) 其中o ) 为所有蚂蚁在路径( f ，j ) 上留下一定的信息素之和，其定义如下： 峨o ) t 三，呓( f ) ( 2 4 ) m 是蚂蚁的数量。每条路径上的初始化信息素浓度是一个小的正常数。， 也就是说在f o 时刻，各条路径上信息素浓度相同。蚂蚁的数量m 是一个非常重 要的参数，在此算法中，它是一个不随时间变化的常数。如果川过大，则算法会 较早的强化次优解，并收敛于不好的解。但是偏小的，则出于信息素挥发问题而 不能获得预期的群体协作行为。m d o r i g o 等人建议预置m n ，也就是蚂蚁数量 等于图中的城市数目，在系统初始化时可将蚂蚁随机地分布到城市上或者每个城 市上分布一个。这两种初始化方法对算法效果没有显著影响，也不存在明显差异。 m d o f i g o 为了提高a s 的性能还提出了一种精英策略“e l i t i s ts t f a t e g y ”：一 定数量的精英蚂蚁“e l i t i s ta n t s ”将不断加强属于丁+ ( 从搜索开始以来最好的路 径) 的路径，每次增强的量值是q 三+ ，f 是r + 的长度。如此一来，r 的信息素 将得到增强，从而引导更多的蚂蚁向着比较好的路径上靠拢。仿真实验证明这种 精英策略能够改善算法特性。 蚁群算法的原理是一种基于“正反馈”的增强型学习系统：它通过“最优路 径上蚂蚁数量的增加一信息素强度增加一后来蚂蚁选择概率增大一最优路径上蚂 蚁数量更大增加”达到最终收敛于最优路径上；蚁群算法是一种分布式的优化方 法，不仅适合目前的串行计算机，而且适合并行计算机；蚁群算法是一种全局优 化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题， 或者是带有约束条件的优化闯题。 同时，蚁群算法主要是通过控制道路上的“信息素浓度”的变化来控制整个 蚂蚁社会的行动的。对每一个蚂蚁来讲，路径的选择都是一种随机的过程，但是 如果道路上的信息素过浓，那么就会犯“盲从”的错误，导致算法早熟；如果道 路上的信息素被不良的因素破坏，那么就会“盲目”，算法收敛性差；总之，该算 法的关键在于信息素浓度的有效控制和根据这些浓度选择每一只蚂蚁下一步路径 的概率计算上。 此外，蚁群算法的执行结构是线性的，每一步都可以由独立的运算单元构成， 所以可以很方便和其他的启发式算法以及基本搜索方法相结合，以增强算法的搜 索性能。 第二章蚁群算法 1 3 蚁群算法从其实现的机理来看是一种天然的解决组合优化问题的方法。其主 要特征是正反馈、分布计算以及结构性的贪心启发。正反馈使得它能很快搜索到 比较好的解：分布计算避免了算法陷入局部收敛而不能继续优化；而贪心启发机 制使它能在寻优的早期阶段就搜索到可接受的解。这些特征使蚁群算法成为解决 n p 完全组合优化问题的有力工具。 2 4 本章小结 蚁群算法( a - tc 0 1 0 n yo p t i m i z a t i o na l g o r i t h m ，a c o ) 是由意大利学者 m d o r i g o 等【1 1 人在2 0 世纪9 0 年代初通过模拟自然界中蚂蚁集体觅食的行为而提 出的一种基于种群的启发式仿生进化算法。 本章在介绍蚁群算法的基本原理的基础上，以经典组合优化问题t s p 问题 为例，详细介绍了其解决组合优化问题的基本框架。 1 4 蚁群算法在组合优化中的应用 第三章最大团问题的新型蚁群算法 本章用蚁群算法思想解决经典组合优化问题最大团问题。重点介绍了一种 针对子集类组合优化问题的新型蚁群算法。将最大团问题看作子集类问题，提出 了最大团问题的新型蚁群算法。大量的仿真实验研究表明，该算法较传统求解最 大团问题的蚁群算法有着更短的运行时间，更强的求解能力。 3 1 最大团问题 最大团问题( m a x i m u mc l i q u ep r o b l e m ，简记为m c p ) 是一个著名的组合优化 问题，这不仅仅因为它最早被证明是n p 完全问题之一，而且因为它在理论和实 践上有着重要的意义，如它在编码理论、差错诊断、计算