（计算机应用技术专业论文）蚁群算法的参数研究.pdf

蚁群算法的参数研究 计算机应用技术 硕士生：蒋玲艳 指导教师：陈有青副教授 摘要 蚁群算法( a n tc o l o n ys y s t e m ，a c s ) 是根据蚂蚁群体觅食过程中会选择最短 路径行进的生物学行为发展起来的一种群体智能优化方法。该算法是一种新型的 分布式优化算法，它有较强的解搜索能力、很好的适应性和鲁棒性，但如果算法 中各参数选择不当，算法的运行时间则会变长，或者算法陷于局部最优，达到停 滞状态。恰当的参数选择，可以使蚁群算法有较好的性能，较快地收敛到全局较 优解。本文以t s p 问题为例，通过采用不同参数匹配进行优化的数值实验，分 析了算法中参数a , p , p 对算法性能的影响，给出了一定指导性的建议。 本文致力于以上问题的研究，主要研究内容包括以下几方面： ( 1 ) 本文通过一系列研究，对大量文献进行比较，分析了目前各研究者对蚁 群算法参数研究时所采用的方法，比较这些方法的优缺点。在此基础上，用自己 的方法对算法中的参数进行了实验研究。 ( 2 ) 目前对蚁群算法中参数的研究中，有的研究者只是对仅，p , p 组合的几个 点的实验数据进行比较；有的研究者在研究时，每次只针对其中的一个参数，对 各个参数逐个进行分析，得出每个参数在其它参数取定值时能够使算法有较优性 能的取值范围。本文对参数的研究中，首先逐个分析每个参数在算法中所起的作 用，然后把这三个参数两两组合，分别在各自的区间内以一定的步长逐渐变化， 通过大量实验比较分析，得出了这些参数使算法有较优性能的取值区间。 ( 3 ) 本文在参数的研究过程中，采用参数两两组合的方式，避免了对各个参 数孤立地进行研究，体现了各参数之间的耦合性。 ( 4 ) 本文不是对一些离散的点进行实验，而是在某个区间进行实验分析，可 以得到参数在某区间内的较优取值范围。 关键词：蚁群算法，参数分析，组合优化，旅行商问题 r e s e a r c h e so ft h ep a r a m e t e r si nt h ea n tc o l o n ys y s t e ma l g o r i t h m c o m p u t e ra p p l i c a t i o n s n a m e ：j i a n gl i n g y a n s u p e r v i s o r ：c h e ny o u q i n g a b s t r a c t a n tc o l o n ys y s t e m ( a c s ) a l g o r i t h mw a si n t r o d u c e db ym d o r i g oa n d c o l l e a g u e sa san o v e ln a t u r e - i n s p i r e dm e t a h e u r i s t i cb a s e do nt h ep h e n o m e n o no fr e a l a n t sf o r a g i n gb e h a v i o ri nt h ee a r l y19 9 0 s a c sc a nh a v e ，i ft h ea p p r o p r i a t ep a r a m e t e r s a r es e l e c t e d ，ar a t h e ro p t i m i s t i cp e r f o r m a n c e ，a n dc a nr e a c ht h eg l o b a l o p t i m i s t i c s o l u t i o ne f f i c i e n t l y t h e r ea r em a n yp o s i t i v ec h a r a c t e r i s t i c si na c sa l g o r i t h m i tc a n ， f o ri n s t a n c e ，a d a p tt ot h en e wc i r c u m s t a n c e ss w i f t l y , a n di ti sar o b u s ta l g o r i t h m h o w e v e r , i ft h ep a r a m e t e r sa r ew r o n g l yc h o s e n ，a l lt h e s em e r i t sa r eg o n e i nt h i sp a p e r , l o t so fe x p e r i m e n t sa r er u nt ot e s th o wt h ep a r a m e t e r sa , f l , pw o r k ，a n ds o m eu s e f u l s u g g e s t i o n sa r eg i v e n t h ed i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho ft h ea b o v e - m e n t i o n e dp r o b l e m s t h e m a i nc o n t e n t si n c l u d et h ef o l l o w i n g s ： ( 1 ) t h r o u g has e r i e so fs t u d i e s ，t h i sp a p e rc o m p a r e st h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h em e t h o d sw h i c hp e o p l eu s e dt os t u d yt h ep a r a m e t e r si na c s b e f o r e o nt h i sb a s i s ，an e wm e t h o do fs t u d y i n gt h ep a r a m e t e r si sp r e s e n t e d ( 2 ) m a n yp a p e r sh a v ed o n er e s e a r c h e so nt h ep a r a m e t e r si na c s s o m eo ft h e m o n l yd i dr e s e a r c h e so n af e wd i s c r e t ep o i n t so ft h ep a r a m e t e r s a n ds o m eo ft h e mo n l y s t u d i e de a c hp a r a m e t e rs e p a r a t e l y t h i sp a p e rf i r s ts t u d i e st h er o l ea n dv a l u eo ft h e p a r a m e t e r ss e p a r a t e l y , a n dt h e ns t u d i e st h ep a r a m e t e r sb yg r o u p t h r o u g has e r i e so f e x p e r i m e n t s ，t h ep a p e rc a r r i e so u ta no p t i m u mi n t e r v a lc h o i c eo ft h ep a r a m e t e r s ( 3 ) t h em e t h o dt h i sp a p e ru s e df o ra n a l y z i n gt h ep a r a m e t e r si na c sp u t st h e p a r a m e t e r sb yg r o u pi no r d e rt oa v o i dt h ei s o l a t i o no f t h ep a r a m e t e r s ( 4 ) t h i sp a p e re x p e r i m e n t st h ep a r a m e t e r sn o to ns o m ed i s c r e t ep o i n t sb u ti na r a n g e ，s oi tc a nc a r r yo u ta no p t i m u mr a n g ef r o mac e r t a i nr a n g e k e yw o r d s ： a n tc o l o n y s y s t e m ( a c s ) ，p a r a m e t e ra n a l y z i n g , c 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 r a v e l l i n gs a l e s m a np r o b l e m ( t s p ) i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：砾哗 日期：加唱年j 月8 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：繇瓜i 钞 日期：力d 龟年j 月旷日 导师签名： 日期： 捌薛d 矿日 1 1 引言 第一章绪论 自然界一直是人类创造力的丰富源泉，人类认识事物的能力很多是来源于与 自然界的相互作用之中。而自然界中的许多自适应优化现象不断给人们启示：生 物体和自然生态系统可以通过一些自身的演化就能够使许多在人类看起来高度 复杂化问题得到完美的解决。地球上的生物物种在漫长的演化过程中形成了丰富 的行为特性，并且一直在不断地完善与发展，以便能够更好地适应其所生存的环 境。随着计算机的诞生，人们希望能够借助计算机程序的形式创造出一些新型的 智能体，于是对生物物种的社会行为以及生物界的进化过程进行了一系列的模拟 研究。 自从2 0 世纪4 0 年代以来，人们就一直在利用来自于生物系统的灵感来解决 许多实际问题，并且根据此构造出许多仿生优化算法，如人工神经网络、遗传算 法、人工免疫算法、蚁群算法、粒子群算法、人工鱼群算法等，这些都属于模拟 自然界生物系统行为或过程的最优化仿生智能算法。这些算法与经典的数学规划 原理截然不同，它们是试图通过模拟自然生态系统机制以求解复杂优化问题的仿 生优化算法。 1 2 课题背景 最优化问题可以被分为两种：对一系列连续变量操作的函数优化问题以及对 一组离散对象操作的组合优化问题。对于组合优化问题，它们的描述往往非常简 单，但对其进行最优化求解却很困难，那是因为随着组合优化问题规模的增加， 问题的复杂度将会成指数级增长，即所谓的“组合爆炸”。因此，确定性算法对 于求解组合优化问题，其复杂度将会变得难以想象，而上面所述的一系列的优化 算法，可以比较好地求得该类问题的近似解。 传统的优化方法如贪婪法、动态规划等有很多缺点，它们只适合问题规模小 的优化问题，并且它们对问题的求解时间过长。为更好的解决各种工程应用问题， 人们从自然界生物群体的社会行为中得到启发，提出了许多用于解决复杂优化问 题的模拟进化算法，如：遗传算法( g a ) 【1 1 、模拟退火算法( s a ) 2 1 、禁忌搜索算法 ( t s ) 【引、蚁群算法( a c s ) 【4 】等。 蚁群算法与目前流行的遗传算法、粒子群算法等都属于一类模拟自然界生物 系统、完全依赖生物体自身本能、通过无意识寻优行为来优化其生存状态以适应 环境需要的最优化智能算法【5 1 6 1 7 1 ，都是典型的元启发式算法。因此，这些仿生 优化算法有许多相同的特点。 ( 1 ) 都是一类不确定的算法。不确定性体现了自然界生物的生理机制，并且 在求解某些特定问题方面优于确定性算法。仿生优化算法的不确定性是伴随它的 随机性而来的，由于它的主要步骤含有随机因素，从而在算法的迭代过程当中， 事件是否发生带有很大的不确定性。 ( 2 ) 都是一类概率型的全局优化算法。由于非确定性，算法的优点在于有更 多的机会求得全局最优解。 ( 3 ) 都不依赖于优化问题本身的数学性质。仿生优化算法在优化过程中都不 依赖于优化问题本身的严格数学性质，如连续性、可导性等。 ( 4 ) 都具有突现性。仿生优化算法总目标的完成是在多个智能体个体行为的 运动过程中突现出来的。 ( 5 ) 都具有自组织性和进化性。当环境复杂且不确定时，仿生优化算法可以 通过自学习不断提高算法个体的适应性。 虽然蚁群算法与上述算法都属于仿生优化算法，但是它们在算法机理、实现 形式等方面存在着一定的不同之处。 蚁群算法来源于对蚂蚁群体协作行为的研究。在自然界中，蚂蚁的食物源总 是随机散布于蚁巢周围，而蚂蚁在经过一段时间后，总是能够找到一条从蚁巢到 食物源的最短路径。蚁群算法采用了正反馈机制，这是与其他仿生优化算法最显 著的不同之处。蚁群算法一般需要较长的搜索时间【4 】，而且较易出现停滞现象， 并且算法的收敛性能对初始参数的设置较为敏感。 遗传算法( g a ) 是一类借鉴生物界中自然选择和自然遗传机制的随机化自适 应搜索算法，遗传算法最先由美国m i c h i g a n 大学的h o l l a n djh 教授所提出【8 1 。 遗传算法主要是由选择、交叉和变异算子组成，分别模仿了达尔文进化过程中的 2 自然选择和群体遗传过程中发生的交配和突变等现象。遗传算法中的个体重组技 术采用了交叉算子，是算法产生新个体的主要方法，这个也是遗传算法区别于其 他仿生优化算法的一个重要不同之处。 粒子群算法( p s o ) 是由美国k e n n e d yj 和e b e r h a r tr c 受鸟群觅食行为的启发 而提出的一种仿生优化算法【9 】【l o 】。粒子群算法源于对鸟群捕食行为的研究，一群 鸟在随机搜寻食物，如果某区域内只有一块食物，那么找到该食物的最简单有效 的策略就是搜寻目前离食物最近的鸟的周围区域。该算法比较简单，并且算法受 所求问题维数的影响较小。 在这些算法中，蚁群算法采用正反馈机制并且具有良好的解发现能力。由于 它是一种本质上并行的算法，易于发现较好解。同时蚁群算法具有很好的通用性 和鲁棒性，是基于总体的优化方法【1 1 1 ，因此在解决n p 难问题，特别是各种不同 的组合优化问题，如旅行商问题( t s p ) 【1 4 】、二次分配问题( q a p ) 【1 2 】、作业安排调 度问题( j s p ) 【1 3 】等等，蚁群算法有一定的优越性。从上面对蚁群算法的介绍可知， 蚁群算法收敛性能对初始参数的设置较为敏感，但很多文章在用蚁群算法求组合 优化问题的最优解时，都是采用选取一个参数组合的固定的经验值进行求解，忽 略了参数对算法性能的影响，在参数选择不当的时候，对问题的求解会产生一定 的影响。也就是说，如果蚁群算法中各参数选择不当，算法的运行时间会变长， 或者算法陷入局部最优或者产生停滞等局面。因此，在该基础上，本文通过数值 实验对蚁群算法的参数进行了分析。 1 3 蚁群算法参数研究的分类介绍 目前，很多人对蚁群算法中的参数已经进行了研究，并且根据实验得出了一 些结论，这些对参数研究的方法主要可以分为以下三类： ( 1 ) 对多组参数进行了测试，其中这些a , f l , p 或是a , p 的组合是一些具体的取 值，对这些指定的具有代表性的参数进行分析、比较；实验的时候，保持每次只 改变其中一个参数，其它参数取默认值。按这种方法对多个组合所得出的实 验数据列表格进行比较，然后总结规律，指出较优区间，或者较优值【1 5 】【1 6 】【1 7 】【1 8 】 1 9 】。 由于这种方法保证每次只改变一个参数，便于分析每个参数各自对算法所产生的 影响以及在算法中的作用。但同时，这种分析方法只对一些代表性的参数组合进 3 行实验分析，只是对一些离散点的实验结果进行比较，所以只能得出某些特定参 数取值中的较优值，实验有一定的局限性。另一方面，由于算法中各参数并不是 孤立的，这种分析方法只是孤立地研究每个参数，不能体现各参数之间的耦合性， 实验结果可能只是对参数进行单个的分析，不能体现参数的联系性。 ( 2 ) 针对某一个参数，其它参数取默认值，把每个参数取值定在一定的区间 内，每次只改变其中的一个参数，对每一个参数都进行分析，根据实验结果，总 结得出每个参数使算法有较优性能的取值区间。在对各个参数的取值区间选取的 时候，部分实验还用相同参数对的不同实例进行了多次实验计算【2 0 】e 2 1 1 2 2 】【2 3 】【2 4 】 【2 5 】【2 6 】1 2 7 2 8 】【2 9 】【3 0 1 。这种方法不像第一种方法只是对一些离散的参数组合进行分 析，而是对每个参数都在一个连续的区间内进行实验分析，可以分别找出每个参 数在其它参数取固定值的较优取值范围。但与方法一相同，这种分析方法也是采 用固定其它参数，孤立地研究每个参数，实验结果不能体现各参数之间的耦合性。 ( 3 ) 把参数最优化选择问题本身看作是一个最优化问题求解，采用其它仿真 优化算法，如粒子群算法、遗传算法或均匀选择等，来优化蚁群算法的参数选择。 在求解过程中，用两个或两个以上具体实例的测试结果进行比较，根据实验结果 得出结论，指出每个参数较优区剐3 1 】【3 2 】【3 3 1 。这种方法把参数的选择看成是一个 最优化问题，能够找到较好的参数组合。但由于在用蚁群算法求解某具体问题的 时候，先用其它优化算法求解较优的参数组合，因此增加了问题的复杂性。 1 4 本文主要内容 本文通过一系列研究，分析了当前对蚁群算法参数研究所使用的方法，比较 它们的优缺点。在此基础上，用自己的方法对算法的参数进行了实验研究。 本文对蚁群算法参数的研究中，首先是对算法中的每一个参数单独进行研究 ( 其它参数取固定值，每次只对一个参数进行变化) ，分析每个参数在算法中所 起的作用。然后三个参数分别在各自一定的区间内进行两两组合，以一定的步长 逐渐变化，通过实验进行比较分析，得出蚁群算法各个参数较优的区间选择。 本文在对蚁群算法参数研究方面有以下几个特点： ( 1 ) 文章在参数的研究过程中，采用参数两两组合的方式，避免了对参数孤 立进行研究，体现了参数之间的耦合性。 4 ( 2 ) 本文不是对一些离散的点进行实验，而是在某个区间进行实验分析，可 以得到参数在某区间内的较优取值范围。 本文通过实验可得出以下结论： ( 1 ) 从对算法中每个参数的单独的实验分析结果中可以看出，仅影响算法的 收敛性，6 c 越大，算法收敛越快；与解的质量有关，适当的取值可以使得算 法收敛到近似最优解；p 的大小表示算法多大程度利用了经验知识，较小的p 使 算法更易选择以前走过的路径，较大的p 使算法更多机会开发其它路径。 ( 2 ) 从参数两两组合的实验结果可以看出，在0 j = 反 = d 3 ，3 邓 = 6 ， 0 p = n 3 这些取值范围时，算法总体上有较好性能，达到的最优解与全局最优 较接近，所需的迭代次数也较少，不易陷入局部最优或者停滞局面，因此在用 a c s 解决问题时，可以将参数选取在该范围，以期得到更好的运行结果。 1 5 本文结构 第一章首先对仿生优化算法的起源进行了概述，介绍了一些仿生优化算法及 它们在求解组合优化问题的优缺点。由于蚁群算法在求解过程中对参数比较敏 感，这一章介绍了目前几种对算法中参数研究的方法，并对这些方法进行比较。 最后，在第一章介绍了本文的主要内容以及论文的主要结构。 第二章从蚁群算法的起源，首先介绍了自然界中蚂蚁的行为。由于蚁群算法 是由自然界蚂蚁的觅食行为受到启发发展而来，因此本章还介绍了现实蚂蚁和人 工蚂蚁的异同点、蚁群算法模型的建立、蚁群算法的系统学特征以及算法的发展 和研究现状。在此基础上，该章详细介绍了蚁群算法的机制原理，针对t s p 问 题算法的数学模型，算法的实现步骤及流程以及算法的优缺点等。同时，本章还 研究了基本蚁群算法( a s ) ，最大最小蚁群系统( m m a s ) ，排序蚂蚁系统( a s m i l l ( ) ， 天才蚂蚁系统( e a s ) 等算法，并对某些算法进行了一些比较。最后，本章还介绍 蚁群算法在解决一些组合优化问题上的一些典型应用，包括最经典的旅行商问题 ( t s p ) 以及作业调度问题( j s p ) 、二次分配问题( q a p ) 、车辆路径问题( v r p ) 、多选 择背包问题( m k p ) 、网络路由选择问题( n r p ) 等。 第三章通过对t s p l i b 标准库( r e i n e l t , 1 9 9 1 ) 里面的实例a t t 4 8 以及k r o c l 0 0 进 行测试，通过大量的实验，获得不同参数组合下的统计数据，比较分析各参数对 5 算法性能的影响。本章开始就对实验的环境以及实验过程中所采用的方法进行了 说明，然后通过数值实验，对蚁群算法中参数进行了实验分析，并且得出了蚁群 算法各个参数的较优的区间选择。 第四章，通过对t s p l i b 中的几个实例进行测试以证明在第三章中所得的实 验结论的j 下确性。首先对o l i v e 3 0 做了测试，然后分别对b a y 2 9 ，a t t 4 8 ，s t 7 0 等 做了实验测试，通过对几个不同实例的测试所得的实验数据进行分析，一定程度 证明了第三章中所得结论的正确性。 第五章，总结了本文的研究内容，展望下阶段的研究重点。 1 6 本章小结 本章首先提出了仿生优化算法的起源，然后在介绍仿生优化算法特点及它们 在求解组合优化问题的优缺点中提出了本文的背景。由于蚁群算法在求解过程中 对参数比较敏感，本章还对目前几种对算法中参数研究的方法进行了比较，给出 本文对参数研究所使用的方法，最后介绍了本文的主要结构。 6 第二章蚁群算法 生物学家通过对蚂蚁的长期观察以及研究发现，虽然每只蚂蚁的智能并不 高，看起来没有集中的指挥，但是它们却能够协同工作，寻找食物，建立坚固漂 亮的蚂蚁巢穴并且抚养它们的后代，依靠群体的能力发挥出超出个体的智能。蚂 蚁群体，或者是一些具有更普遍意义的群居昆虫群体，它们都可以看作是一个分 布式系统。虽然系统中的每个个体非常简单，但是整个系统却可以表现出一种高 度结构化的群体组织。也正是因为这种群体组织的存在，蚂蚁群体才能够完成一 些远远超出单个蚂蚁能力的复杂工作。 蚁群算法( a c s ) 是最新发展起来的一种模拟昆虫王国中的蚂蚁群体智能行 为的一种仿生优化算法【2 9 1 ，它具有较强的鲁棒性、很好的分布式机制并且易于 与其它方法相结合等许多优点【3 4 】【1 l 】。尽管蚁群算法还没有很严格的理论基础， 并且国内外一些研究还处于实验探索和初步应用的阶段，但是目前人们对于蚁群 算法的研究已经由最初单一的旅行商问题( 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 ) 领域 渗透到了许多其它的应用领域，并且由解决一维静态优化问题发展到解决多维动 态组合优化问题，由离散范围的研究发展到连续范围的研究【3 5 1 ，从而这种新兴 的仿生优化算法展现出勃勃生机和广阔的发展前景。 本章从蚁群算法的起源，首先介绍了自然界中的蚂蚁的行为。由于蚁群算法 是由自然界蚂蚁的觅食行为受到启发发展而来，因此本章还介绍了现实蚂蚁和人 工蚂蚁的异同点、蚁群算法模型的建立、蚁群算法的系统学特征以及算法的发展 和研究现状。 在此基础上，本章详细介绍了蚁群算法的机制原理，算法针对t s p 问题的 数学模型，算法的实现步骤及流程以及算法的优缺点等。 a c s 是在a s 的基础上发展起来的。与a c s 类似，在a s 的基础上，针对 a s 的不足，很多学者提出了一些改进的蚁群算法，因此本章还研究了基本蚁群 算法( a s ) ，最大最小蚁群系统( m m a s ) ，排序蚂蚁系统( a s 柚，天才蚂蚁系统( e a s ) 等算法，并对某些算法进行了一些比较。 在本章最后，还研究了蚁群算法在解决一些组合优化问题上的一些典型应 7 用，包括最经典的旅行商问题( t s p ) 以及作业调度问题( j s p ) 、二次分配问题 ( q a p ) 、车辆路径问题( v r p ) 、多选择背包问题( m k p ) 、网络路由选择问题( n r p ) 世 守o 2 1 蚁群算法起源 2 1 1 蚂蚁的行为描述 蚂蚁是一种既渺小而又平常的社会性昆虫。蚂蚁在8 0 0 0 万年前就建立了自 己的社会，小小的蚂蚁能够建立起组织完好的复杂“城市”。蚂蚁有四种不同的 蚁型，即蚁后、雄蚁、工蚁和兵蚁。不同的蚁型有着不同的职责，“蚂蚁王国” 的蚂蚁地位彼此平等，各尽其责，为整个“蚂蚁王国”贡献力量。 化学通信是蚂蚁采取的基本信息交流方式，自然界里的蚂蚁会分泌一种化学 刺激物信息素( p h e r o m o n e ) 。蚂蚁它们的很多行为都受到信息素的调控，例 如蚁后分泌一种“女皇物质 的信息素来控制工蚁的发育情况。在遇警时，信息 素可以刺激蚂蚁兴奋，使蚂蚁按计划执行某项任务。蚂蚁的这些特有的控制自身 环境的能力，是在它们不断发展的社会行为中所获得的【3 6 1 【3 7 】【3 8 1 。 尽管蚂蚁个体比较简单，但是，整个蚂蚁群体却表现为一种高度机构化的社 会组织，并且，在很多情况下能够完成远远超过蚂蚁个体能力的一些复杂任务 【3 9 1 。这种能力主要是来源于蚂蚁群体中的个体协作行为，这些群体行为主要包 括寻找食物、任务分配以及构造墓地等。 1 寻找食物 自然界中，蚂蚁的食物源总是随机地散布在蚂蚁巢穴的周围。人们经过仔细 观察发现，在经过一段时间后，蚂蚁总可以找到一条从巢穴到食物源的最短路径。 自然界的蚂蚁其视觉感知系统通常是发育不全的，每只蚂蚁的智能并不高，由这 些蚂蚁组成的群体没有集中的指挥，但它们却能够通过释放信息素与其它的蚂蚁 互相合作，在其简单的行为规则下，很容易地找到它们的食物，依靠群体能力发 挥了超出个体的智能【1 1 】【柏1 。 蚁群算法是基于自然界蚂蚁寻找食物的群体过程所提出。现实中的蚂蚁可以 在没有视觉的情况下找到蚁巢与食物源之间的最短路径【4 l 】【4 2 】【4 3 1 。虽然个体蚂蚁 8 的行为比较简单，但整个蚂蚁群体的个体协作行为却能使蚂蚁完成非常复杂的任 务【3 9 1 。这是因为蚂蚁在寻找食物的过程中，能够在自己走过的路径上释放信息 素( p h e r o m o n e ) ，并且通过感知其它蚂蚁所释放的信息素从而寻找到合适的路径 【删【矧，各蚂蚁之间通过信息素间接进行信息交换。当之前的最短路径出现障碍 物时，蚂蚁又能再找到一条新的最短路径【4 5 1 。蚂蚁在行走过程中不仅能够释放 信息素，并且能够感知信息素的强度，选择信息素强度高的方向运动，以此指导 自己的行为m 】。这样，由大量蚂蚁组成的群体，它们的集体行为则表现出一定 的正反馈现象：越多的蚂蚁走过某条路径，该路径被后续蚂蚁选择的概率就越大。 单只蚂蚁的能力和智力都非常简单，但是通过协作，蚂蚁在觅食过程中可以 找到食物源和巢穴之间的最短路径4 5 】【4 7 1 。在现实生活中，人们总可以观察到大 量蚂蚁在巢穴与食物源之间形成了近乎于直线的路径，而不是曲线或其它形状， 如图2 - 1 ( a ) 所示。蚂蚁群体不但可以完成这种复杂的任务，并且能够适应外界环 境的变化，如果在蚂蚁群体运动路线上突然出现障碍物，初始时，各只蚂蚁均匀 地分布，不管路径的长短，蚂蚁总是按照相同的概率选择各条路径，如图2 - 1 ( b ) 所示。随着时间的推移，蚂蚁在运动过程中，在它们所经过的路径上留下信息素， 并且蚂蚁可以感知这种信息素的存在以及强度，在信息素的指导下，选择自己的 运动方向蚂蚁倾向于信息素浓度较高的方向移动。在相等的时间内，较短路 径上的信息素就留得比较多，因此，选择较短路径的蚂蚁数目也随之增多，如图 2 1 ( c ) 所示。可以看出，由于大量蚂蚁组成的群体行为体现出了一种信息正反馈 的现象，也就是某一条路径上走过的蚂蚁越多，后续蚂蚁选择这条路径的概率就 越大，蚂蚁个体之间就是通过这种信息交流来搜索食物，并且最终沿着最短路径 前进，如图2 1 ( d ) 所示。 9 节弘，上尹叫炒q k ，t 矗t tt j ，r ， 障蠢， ， ， 9 一 ，- ，- j 龟 l 一， 二 ，7 ， ， ， 朝 ， 爹殍锶 9 ， ， 争 。，_ a k 一一。r ， r ， 阳翻。，： ， ( d ) 图2 - 1 现实蚂蚁寻找食物的过程 g o s ss 等提出的著名的“双桥”实验【4 2 】，如图2 2 所示。对蚂蚁根据信息素 从蚁穴到食物源或从食物源到蚁穴的行为作了真实的仿真。该实验证明，蚁群最 终会选择一条从巢穴到食物源的最短路径。图2 2 ( a ) 为蚂蚁经过非对称双桥开始 觅食：图2 - 2 ( b ) 显示绝大多数蚂蚁选择较短的桥。 n i 酮 1 、 4 分钟 ( a ) n 薪n 1 - _ ， 8 分钟 ( b ) 图2 2 双桥实验 g o s ss 等通过进一步的研究，给出了“双桥实验的数学模型。首先，假定 在非对称桥上残留的信息素量与过去一段时间经过该桥的蚂蚁数成正比；其次， 假设在某一时刻蚂蚁按桥上信息素量的多少来选择某座桥，即蚂蚁选择某座桥的 1 0 概率与经过该桥的蚂蚁数成正比。在双桥实验中，设短桥为彳，长桥为曰，当有 m 只蚂蚁都经过两座桥以后，设彳小、既分别表示经过彳桥和b 桥的蚂蚁数目 彳朋+ 如= m ，则第m + 1 只蚂蚁选择a 桥的概率为 驰) = 雨糕 蚂蚁选择b 桥的概率为 最( 埘) = 1 一只( 所) ( 2 一1 ) ( 2 2 ) 上面的公式中，参数五和k 用来匹配真实的实验数据。第伽+ 矽只蚂蚁首先按式 ( 2 - 1 ) 计算选择概率n 俐，然后生成一个在区间 o 一1 上均匀分布的随机数伊，如 果缈只( 历) ，则选择彳桥，否则选择b 桥。 2 任务分配 任务分配是另一个典型的蚂蚁群体行为。蚂蚁群体中的各个蚂蚁都有着不同 的分工，不同的蚂蚁对不同任务的响应也是不完全相同的，但是这些蚂蚁可以通 过角色的协调以及相互的协作很好地完成许多任务。蚂蚁大致可以分为两种任 务：从事繁殖的个体以及从事日常工作的个体。其中从事日常工作的个体又可分 为寻找食物的蚂蚁和建筑巢穴的蚂蚁【4 8 1 。蚂蚁是在没有任何指导信息的情况下 进行上述分任务分配的，在这种任务分配过程中存在着一种科学的平衡。 蚂蚁群体能够以惊人的效率并且能有效地完成一些优化和控制的复杂任务， 这不仅引起了生物学家的极大兴趣，并且激发了计算机学家和系统优化学家的研 究兴趣。通过对蚂蚁群体的研究，产生了一些新型的、分布式的多智能体仿真算 法。d o r i g om 掣2 9 】 3 4 1 由蚂蚁群体的觅食行为行到启发而提出了蚁群优化模型； b o n a b e a ue 等【5 4 】由蚂蚁群体的分配任务行为受到启发而提出了简单阈值模型。 2 1 2 向人工蚂蚁转换 在自然界蚂蚁群体觅食行为的启发下【4 5 1 ，d o r i g om 等1 9 9 1 年在法国巴黎召 开的第一届欧洲人工生命会议( e u r o 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 ) 提出 了蚁群算法的基本模型【2 9 1 ，1 9 9 2 年，在其博士论文里，d o r i g om 进一步描述了 蚁群算法的核心思想【3 4 】。 将人工蚂蚁系统和真实蚂蚁系统的特点进行比较，可以帮助了解蚁群算法的 机理，对蚁群算法的改进也有一定的借鉴意义。 蚁群算法是源于现实世界中蚂蚁群体能够找到巢穴到食物源之间最短路径 的生物学现象而提出的，真实的蚂蚁系统还能实现很多其它复杂的功能【4 9 1 。蚁 群算法是对真实蚂蚁群体觅食行为加以抽象和改进【4 5 1 ，因此两者既有联系又有 区别。 人工蚂蚁具有双重特性：一方面，人工蚂蚁是真实蚂蚁的抽象，因此具有一 些真实蚂蚁的一些特性；另一方面，它们又有一些在真实蚂蚁中找不到的特性， 这些新的特性，可以使人工蚂蚁在解决实际的优化问题时，具有一些更好地搜索 较好解的能力。 2 1 2 1 人工蚂蚁与真实蚂蚁的相同点 由于蚁群算法是从自然界中真实蚂蚁的觅食行为得到启发而提出的，它的很 多观点都是来源于真实蚂蚁群体【4 5 】，因此算法中所定义的人工蚂蚁与真实蚂蚁 存在以下一些共同点： ( 1 ) 群体中个体都是利用信息素相互通信、协作 人工蚂蚁与真实蚂蚁都存在一种改变当前所处环境的机制。真实蚂蚁在它所 走过的路径上留下信息素，通过影响周围环境对后续蚂蚁寻找路径的行为产生影 响；人工蚂蚁也在它所走过的路径上留下了信息，即信息素量，用来影响本次迭 代或者下一次迭代蚂蚁选择该路径的概率。两个系统都是通过蚂蚁释放信息素来 影响系统环境，从而使蚂蚁之间可以相互交流、协作。 ( 2 ) 决策行为都是基于随机概率选择策略 真实蚂蚁在路口处面临选择时的选择策略和人工蚂蚁从一个节点移动到下 一个节点时的选择策略相同，都是根据当前信息素量的大小按照概率进行选择， 并且与路径的信息素量成正比。该策略使算法具有一种收敛的特性，即大部分蚂 蚁最终将集中在某一条路径上。这种随机概率选择方式也有利于搜索其它更好的 路径，避免算法陷入局部最优。 ( 3 ) 任务相同和局部的操作相似 人工蚂蚁与真实蚂蚁之间一个共同的任务就是寻找连接初始( 巢穴) 和目标 ( 食物源) 之间的最短路径( 或最小花费) 。真实蚂蚁一步一步地通过相邻的地域状 1 2 态，人工蚂蚁也是如此，只是在针对具体问题时所表述的状态和相邻的地域会因 问题而异。为了能在多次寻路过程中找到最短路径，应该记录当前的移动序列。 ( 4 ) 自组织特性 在真实的蚂蚁系统中没有监视者，不需要去组织协调每只蚂蚁的具体行为， 整个蚂蚁系统井然有序的运行着，并且通过多只蚂蚁之间的协作能够完成比较复 杂的任务：在一个或者多个蚂蚁个体停止工作时，整个系统仍然能够保持正常的 功能，具有很强的鲁棒性。人工蚂蚁系统正是基于真实蚂蚁系统的自组织特性而 提出的，因此人工蚂蚁系统也具有该特点，该特点表现在算法最终收敛到某一最 优解，即算法具有收敛性。 ( 5 ) j 下反馈和负反馈机制 真实蚂蚁依靠在最短路径上积累越来越多的信息素来吸引更多的后续蚂蚁 沿此路径前进，而更多蚂蚁沿最短路径行进的同时又会释放更多的信息素，进一 步加强了该路径的吸引力，形成了所谓的正反馈机制。蚁群算法中同样也拥有这 一机制，在蚂蚁构造解以后会通过质量函数进行评估，如果是好的解则会得到较 多的加强，使下一次迭代中具有更强的吸引力；如果是不好的解则被加强的程度 较弱或者不被加强，由于信息素挥发而逐渐失去吸引力，即所谓的正反馈机制。 正反馈机制与“雪球效应”类似，越来越多的蚂蚁被吸引到某一路径上，这对算 法的收敛起到了至关重要的作用。但单纯的正反馈也会有副作用，当蚂蚁发现的 解是局部最优时，大量的蚂蚁也会被吸引到这条路径上，从而阻碍了更优解的发 现，导致算法出现搜索停滞现象。 因此人工蚂蚁系统与真实的蚁群系统同时都存在负反馈机制，以平衡上述的 正反馈作用，它体现在蚂蚁的概率搜索技术上。人工蚂蚁在寻求最优解的过程中 在一定程度上接受解的退化，避免算法过早的收敛至局部最优解。而真实蚂蚁在 路口选择过程中也正是通过这种随机概率选择机制实现发现巢穴到食物源的最 短路径。 2 1 2 2 人工蚂蚁与真实蚂蚁的不同点 由于蚁群算法是对现实蚂蚁群体觅食行为的模拟，它是一种机理上的应用， 因此没有必要完全重现真实蚂蚁系统，同时为了改善算法的效率也会增加一些真 实蚂蚁系统所不具备的能力。人工蚂蚁系统具有如下几个真实蚂蚁群不具有的特 1 3 点： ( 1 ) 人工蚁群系统是一个二维的离散系统，人工蚂蚁的移动实质上是由一个 离散状态到另一个离散状态的改变；而真实蚂蚁是在一个三维世界中的连续爬行 行为。 ( 2 ) 人工蚂蚁能够记忆蚂蚁过去的行为，这为解决带约束的组合优化问题提 供了方便；而真实蚂蚁则没有表现这方面的能力。 ( 3 ) 人工蚂蚁释放的信息素量是它所构造解的优劣程度的一个函数，并且根 据更新策略的不同信息素释放的时机可以有多种选择，可以边移动边释放，也可 以完成解的构造以后再释放；真实蚂蚁释放的信息素量是一个定值，并且是边移 动边连续释放。 ( 4 ) 为了提高系统的整体性能，蚁群算法中可以增加一些额外的特性，如采 用局部优化策略、回退技术、增加与问题相关的启发式因子等；而真实蚂蚁系统 则不具备该特性。 2 1 3 蚁群算法模型的建立 1 蚂蚁个体的抽象 因为蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，是一种机理上的 应用，所以首先必须对真实蚂蚁进行抽象，而不可能也没有必要对蚂蚁个体进行 完全的再现【5 6 】。抽象的目的就是为了能够更加有效的刻画出真实蚁群中能够为 算法所借鉴的某些机理，同时抛弃与建立算法模型无关的一些因素。这样抽象出 来的人工蚂蚁可以看作是一个简单的智能体，能够完成所求问题简单解的构造过 程，也能通过一种通信手段相互的影响。 2 问题空间的描述 自然界中的真实蚂蚁存在于一个三维的空间中，而问题空间的求解一般是在 二维平面内进行的，因此需要将蚂蚁觅食的三维空间抽象为一个平面。另一方面， 由于计算机不能够完整的描述一个连续的平面，因为计算机处理的是离散事件， 因此必须将连续的平面离散化为由一组点组成的离散平面，人工蚂蚁便可以在抽 象出来的点上自由运动。因为蚂蚁是在连续平面上运动，但是其行动经过的总是 一些离散点。因此可以用数学工具图来描述蚁群算法所求解的空间。由于图 1 4 在很多的问题都可以用，这使蚁群算法能够得到广泛应用。 3 寻找路径的抽象 真实的蚂蚁在觅食过程中主要按照所处的环境中的信息量来决定其前进的 方向，人工蚂蚁是在平面的节点上进行运动，因此可以把觅食过程抽象成算法中 解的构造过程，将信息素抽象为存在于边上的某些轨迹。在每一个节点，人工蚂 蚁感知连接该节点与相邻节点那条边上的信息素轨迹浓度，并根据该浓度的大小 来决定走向下一节点的概率。可以用任意两个节点分别表示蚂蚁的巢穴( 初始节 点) 和食物源( 目标节点) ，人工蚂蚁从初始节点按照它所要求的一定状态转移概率 选择下一个节点，依此类推，最终选择行走到目标节点，这样便得到了所求问题 的一个可行解。 4 信息素挥发的抽象 真实蚂蚁总是在所经过的路径上连续不断的留下信息素，而同时信息素也会 随着时间的推移而连续不断地挥发。但因为计算机处理的是离散事件，所以必须 使信息素的挥发也是离散发生的。算法一般采取的做法是：当蚂蚁完成从一个节 点到下一个节点的移动后，即每经过一个时间单位之后，就进行一个信息素的挥 发，这种在离散时间点进行信息素挥发的方式与蚂蚁觅食过程的机理其实是一致 的。 5 启发因子的引入 上面所述是对蚂蚁觅食行为的一个抽象，整个过程体现了蚁群算法的一个特 点自组织性，但是这种自组织系统存在一个缺陷，也就是系统的演化需要耗 费较长的时间。在实际的应用中对算法的时间的要求也是一个必不可少的因素， 因此在决定蚂蚁在行走方向的状态转移概率时，算法引入了一个随机搜索的过 程，即引入了启发因子，在根据所求问题空间的具体特征，给蚁群算法一个初始 的引导，引入启发因子这个过程极大的增加了算法的时间有效性，从而使蚁群算 法的有效应用成为可能。 从以上几点分析可以看出，通过上述所描述的那些抽象过程，可建立一个蚁 群算法的基本模型。模型的空间是用图来描述的，解的获取是构造性的，并且在 解的构造过程中人工蚂蚁没有接受任何全局的指导信息，因而算法求解的过程是 自组织的。 1 5 在蚁群算法中，蚂蚁个体是算法的基本单元。而蚂蚁个体所拥有的知识又来 源于其它蚂蚁个体的通讯以及对周围环境的感知，因此，蚂蚁个体的知识积累是 一个动态的过程。蚂蚁个体通过随机决策机制以及相互协调机制可自适应的做出 选择并完成求解过程，蚂蚁个体之间的这种分布性和协作性正是蚁群算法所研究 的核心内容。 蚁群算法与真实蚂蚁类似，具有很强的自学能力，可以根据环境的改变和过 去的行为的一些结果对自身的知识库或者自身的组织结构进行再组织，从而实现 算法求解能力的逐渐进化。但是环境变化的不确定性以及算法机理的复杂性会增 加蚁群算法的不可预测性f 5 7 】。 2 1 4 蚁群算法的系统学特征 1 蚁群算法是一个系统 系统学是一个比较新的学科，它的基本特点是强调整体性。系统学十分庞大， 不同学科的研究范围和侧重点有所不同，因此往往对“系统”给出了不同的定义。 在基础科学层次，普遍采用系统学创始人b e t a l a n f f ylv 所给出的定义：“系统可 以确定为处于一定的相互关系中并与环境发生关系的各组成部分( 要素) 的综合 体”。上面这个定义强调的不是功能，而是系统元素之间的相互作用以及系统对 元素的整体作用。这个定义可更为精确化的表述为：如果对象s 满足以下两个条 件： ( 1 ) s 中至少有两个不同的对象。 ( 2 ) s 中的对象按照一定的方式互相联系在一起。 则称s 为一个系统，同时定义s 中的个体对象为系统的元素。 很显然，自然界中的蚂蚁群体具备了系统的这三个基本特征，即多元性、相 关性以及整体性，从而，蚁群构成了一个系统。在蚁群这个系统中，蚂蚁的个体 行为是系统的元素，蚁群行为的相互影响则体现了系统的相关性，整个蚁群可以 完成个体完成不了的任务则体现了系统的完整性，表现出系统整体大于部分之和 的整体突现原理。 蚁群算