（计算机软件与理论专业论文）蚁群算法及群体智能的应用研究.pdf

蚁群算法及群体智能的研究应用 摘要 自然界里蚂蚁、蜜蜂等，虽然他们个体的智能并不高，却表现出很高的群体 智能。群体智能起源于科学家对群居性昆虫的观察和研究。群体智能是指任何启 发于群居性昆虫群体和其它动物群体的集体行为而设计的算法和分布式问题解 决装置。群体智能以其简单性、灵活性、分布性、健壮性在组合优化问题、知识 发现、通信网络、机器人等研究领域显示出巨大的潜力和优势，并推动复杂科学 的发展。 蚁群算法是一种新型仿生类进化算法，是继模拟退火、遗传算法、禁忌搜索 等之后的又一启发式智能优化算法。蚂蚁有能力在没有任何提示下找到从巢穴到 食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选 择。根本原因是蚂蚁在寻找食物时，能在其走过的路上释放一种特殊的分泌物 信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当 时这条路径上信息索的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留 下的信息素也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路 径上的信息索强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈 机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。蚁群算法由意大利学 者m d o r i g o 等人首先提出，并成功地应用于求解t s p 、二次分配、图着色、车 辆调度、集成电路设计及通信网络负载等问题。蚁群算法从提出到现在，短短十 余年的时间，以其在离散型组合优化问题中的突出表现，吸引了人们的极大关注。 论文研究了群体智能的多个模型，研究的目的，一方面是探索和验证群体智 能在解决分布式问题方面的特性，另一方面是拓宽群体智能的应用领域。文章的 研究工作主要包括以下几个方面： ( 1 ) 蚁群算法的研究。提出一种求解t s p 问题的分段交换蚁群算法。分段交 换蚁群算法把小窗口、随机分段优化求解、模拟退火充分交换的思想引入蚁群算 法，把蚁群算法和模拟退火算法融合。该算法在蚁群算法陷入局部最优解的情况 下，能改进其局部最优解，并可减少迭代次数。 ( 2 ) 蚁群算法应用于o - l 背包问题的研究。0 - 1 背包问题是典型的n p 完全问 题，且蚁群算法己成功地解决了许多组合优化的难题。因此，文章介绍一种基于 “ 摘要 蚁群算法求解o l 背包问题的算法，并对此算法进行优化，提出一种求解0 1 背 包问题的快速蚁群算法。当物品数较大时，也取得了较好的求解质量。 ( 3 ) 蚁群算法应用于圆排列问题的研究。本章提出一种求解圆排列问题的快 速蚁群算法。优化后的该算法，大大减少了蚁群算法的搜索时间，有效改善了蚁 群算法易于过早地收敛于非最优解的缺陷。 ( 4 ) 改进蚁群算法及两类应用模型的研究。论文通过改变概率的计算时机， 按“概率之和为u 的轮盘赌”方式选择下一个元素，基于模拟退火的分段交换优 化当前最优解，对基本的蚁群算法进行改进，提出一种改进的蚁群算法。文章还 对蚁群算法解决组合优化问题进行总结，提出了蚁群算法的两类应用模型。 ( 5 ) 基于群体智能求解n 后问题的研究。文章提出一种求解n 后问题的蚂蚁 模型算法，它受启发于群体智能的蚂蚁算法和多a g e n t 系统，又吸收了回溯算法 的优点。该算法是一种随机搜索算法，从根本上改变了回溯算法的系统地搜索机 制，避免了大量的冗余搜索，又保证了必要的搜索。在求解n 后问题的第一个解 时，大大减少求解时间和求解步数，当n 较大时，也可得到较好的求解效果。 关键词：群体智能，蚁群算法，模拟退火算法，多a g e n t 系统，分段交换蚁群算 法，背包问题快速蚁群算法，圆排列问题快速蚁群算法，蚂蚁模型算法。 蚁群算法及群体智能的研究应用 a b s t r a c t ht h en a t u r ea n t sa n db e e so f t e nc 卸a c h i e v eac o m p l e xt a s kw h i l eas i n g l eb o d y m a yb ef a i l u r e s w a r mi n t e l l i g e n c ee m e r g e do u to fs o c i a li n s e c tc o l l e c t i v eb e h a v i o r s w a r mi n t e l l i g e n c ei s d e f i n e d 雒a n ya t t e m p tt od e s i g na l g o r i t h m so rd i s t r i b u t e d p r o b l e m s o l v i n gd e v i c e si n s p i r e db yt h ec o l l e c t i v eb e h a v i o ro ft h es o c i a li n s e r t c o l o n i e sa n do t h e ra n i m a ls o c i e t i e s s w a r mi n t e l l i g e n c ee x h i b i t san u m b e ro f i n t e r e s t i n gp r o p e r t i e ss u c h 硝f l e x i b i l i t y , r o b u s m e s s ，d e c e n t r a l i z a t i o n a n d s e l f - o r g a n i z a t i o n t h ei n s t a n c e so ft h e s ea l g o r i t h m so nt h ed o m a i n so fo p t i m i z a t i o n t e l e c o m m u n i c a t i o nn e t w o r k , k n o w l e d g ed i s c o v e r ya n dr o b o t sa r eo b v i o u s l yi n e r e a s e d s w a r mi n t e l l i g e n c eh a sb e c o m eah o tr e s e a r c ha r e , af o ra r t i f i c i a l i n t e l l i g e n c e r e s e a r c h e r s a n tc o l o n yo p t i m i z a t i o na l g o r i t h m si sak i n do fe v o l u t i o nc o m p u t a t i o n a l g o r i t h m sb a s eo nb i o n i c s ，w h i c hh a st h ec h a r a c t e ro fp o s i t i v ef e e d b a c ka n dp a r a l l e l p r o c e s s i n g a n t s 啪f i n dt h eb e s tr o u t eb e t w e e nah o l ea n df o o d s t h er e a s o ni st h a t t h ea n tr e l e a s ev o l a t i l ep h e r o m o n ei nt h e 仃a i l a n t sc o m m u n i c a t ew i t l lo t h e r sb yt h e p h e r o m o n et h a ti sl e f to nt h er o a da n dt h e i rb e h a v i o r sa r et r e n d i n gt ot h et r a i lo f d e n s e p h e r o m o n e b e c a u s et h ep h e r o m o n e si nt h eo p t i m a lr o u t ev o l a t i l el e s s t h e r ea r em o r e a n dm o r ea n t sp a s st h l o u g ht h i sr o u t e sa n ds t r e n g t h e nt h eo p t i m a lr o u t e t h ep r o c e s s o ft h eo p t i m a lr o u t ei sf o r m i n gb yp o s i t i v ef e e d b a c k a n tc o l o n ya l g o r i t h mw a sf i r s t p u tf o r w a r dt os o l v et h ef a m o u st r a v e l i n gs a l e s m a np r o b l e mb ym a r c od o r i g oa n dh i s c o l l e a g u e s n o wi t h a sb e e ns u c c e s s f u l l yu s e dt os o l v em a n yk i n d so fc o m b i n a t i o n o p t i m i z a t i o np r o b l e m ss u c ha sq u a d r a t i ca s s i g n m e n t ，g r a p hc o l o r i n g ，v e h i c l er o u t e ， s e q u e n t i a lo r d e r i n ga n ds oo n t h i sd i s s e r t a t i o nf o c u s e s0 1 1an u m b e ro fs w a r mi n t e l l i g e n c em o d e l s ，1 1 1 eg o a lo f t h i sd i s s e r t a t i o ni st oe x p l o r ea n df u r t h e rp r o o f t h ep r o p e r t i e so f t h ea l g o r i t h m s o nt h e o t h e rh a n d ，t h i st h e s i se x t e n d st h ea p p l i c a t i o nd o m a i n so fs w a r mi n t e l l i g e n c e t h e c o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r ea sf o l l o w s ： a b s t r a c t ( 1 ) r e s e a r c ho n a n tc o l o n ya l g o r i t h m s as u b s e c t i o n e x c h a n g ea n tc o l o n y a l g o r i t h mo fs o l v i n gt s p i sp r e s e n t e d ，t h ei d e ao fs m a l lw i n d o w s ，r a n d o ms u b s e c t i o n a n de n o u g he x c h a n g eo fs i m u l a t e da n n e a l i n ga r ei n t r o d u c e di n t oa n tc o l o n y a l g o r i t h m i tc o m b i n e sa n tc o l o n ya l g o r i t h m 、析t hs i m u l a t e da n n e a l i n g o nt h e c o n d i t i o no f f a l l i n gi nl o c a lb e s to f a n tc o l o n ya l g o r i t h m i t 啪i m p r o v et h ep r e c i s i o n i ta l s oc a nr e d u c et h en u m b e ro fs e a r c h i n g s i m u l a t i o nr e s u l t ss h o wt h mb e t t e re f f e c t s a r co b t a i n e d ( 2 ) r e s e a r c ho na p p l i o c a t i o no fa n tc o l o n ya l g o r i t h mt o0 - 1k n a p s a c kp r o b l e m 0 - 1k n a p s a c kp r o b l e mi sad i f f i c u l tn pp r o b l e m a n tc o l o n ym g o f i t h mw a sa p p l i e d s u c c e s s f u l l yt om a n yh a r dc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m s s o ，a na n tc o l o n y a l g o r i t h mo fs o l v i n g0 - 1k n a p s a c kp r o b l e mi si n t r o d u c e d b yo p t i m i z i n gi t ，aq u i c k a n tc o l o n ya l g o r i t h mo fs o l v i n g0 - 1k n a p s a c kp r o b l e mi sp r e s e n t e d w h e nt h en u m b e r o f a r t i c l ei sb i gi ta l s oc a no b t a i nb e t t e re f f e c t s ( 3 ) r e s e a r c ho i la p p l i o c a t i o no fa n tc o l o n ya l g o r i t h m t oc i r c l ep e r m u t a t i o n p r o b l e m aq u i c ka n tc o l o n ya l g o f i t h mo fs o l v i n gc i r c l ep e r m u t a t i o np r o b l e mi sp u t f o r w a r d ，b yo p t i m i z i n gi t , i tg r e a t l yr e d u c e st h es e a r c h i n gt i m e o fa n tc o l o n y a l g o r i t h m i ta l s oe f f e c t i v e l ya m e l i o r a t e st h ed i s a d v a n t a g eo fe a s i l yf a i l i n gi nl o c a l b e s to f a n tc o l o n ya l g o r i t h m ( 4 ) r e s e a r c ho l la ni m p r o v e da n tc o l o n ya l g o f i t h ma n dt w ot y p e so fa p p l i c a t i o n m o d e l s b yc h a n g i n gt h et i m eo fc a l c u l a t i n gt h ep r o b a b i l i t ya n du s i n go fr o u l e t t e - w h e e lw h i c hs 眦o fp r o b a b i l i t yi sua n ds u b s e c t i o ne x c h a n g eb a s e do l ls i m u l a t e d a n n e a l i n g ，a ni m p r o v e da n tc o l o n ya l g o r i t h mi sp u tf o r w a r d t w ot y p e so f a p p l i c a t i o n m o d e l so f a n tc o l o n ya l g o r i t h ma r ea l s op r e s e n t e d ( 5 ) r e s e a r c ho ns o l v i n gnq u e e n sp r o b l e mb a s e do i ls w a r mi n t e l l i g e n c e a na n t m o d e la l g o r i t h mo f s o l v i n gn q u e e n sp r o b l e mi sp u tf o r w a r d i ti si n s p i r e db ys w a r m i n t e l l i g e n c ea n da n ta l g o f i t h r aa n dm u l t i - a g e n ts y s t e m i ta b s o r b sa d v a n t a g e so f b a c k t r a c ea l g o r i t h m a n tm o d e l a l g o r i t h mi sar a n d o ms e a r c h i n ga l g o r i t h m i tr a d i c a l l y c h a n g e st h et e c h n i q u eo f s y s t e m i cs e a r c h i n ga n da v o i d sl a r g ea m o u n to f r e d u n d a n t s e a r c h i n ga n de n s u r e st h en e c e s s a r ys e a r c h i n g i tg r e a t l yr e d u c e ss e a r c h i n gt i m ea n d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得墨徽大摩或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 寻会薯放 签字日期： ) 口口7 年y 月玎日 学位论文版权使用授权书 本学位论文作者完全了解搜徽六学 有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授蛳摩可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：l 会翠蠢 签字日期：j 口d 1 年中月二r 日 学位论文作者毕业去向： 工作单位： 通讯地址： 锄鲐穆z 净厶、 锣挑 签字日期：勿7 年l t 月矽厂日 电话： 邮编： 第一章绪论 第一章绪论 1 1 群体智能 1 1 1 群体智能 群体智能作为一个新兴领域，自从2 0 世纪8 0 年代出现以来，引起了多个 学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学 科的热点和前沿领域”。 群体智能的概念源于对蜜蜂、蚂蚁、大雁等这类群居生物群体行为的观察 和研究，是一种在自然界生物群体所表现出的智能现象启发下提出的人工智能 实现模式，是对简单生物群体的智能涌现现象的具体模式研究，即“简单智能 的主体通过合作表现出复杂智能行为的特性”。“该智能模式需要以相当 数目的智能个体来实现对某类问题的求解功能o ”。 通过对群居性昆虫行为的模拟，一种启发于群体智能的用于解决计算机传 统问题和实际应用问题的新方法也相继产生。这些研究就是群体智能的研究。 b o n a b e a u 等人定义群体智能是指任何启发于群居性昆虫群体和其它动物群体的 集体行为而设计的算法和分布式问题解决装置川。群体智能利用群体优势，在 没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决 方案提供了基础旧3 。 群体智能提供了设计智能系统的另一种选择途径，这种方法用自治、涌现 和分布式运行代替了控制、预先编制程序和集中。它强调分布式、相对简单主 体之间直接或间接交互作用( 通信) 、适应性和鲁棒性。群体智能的研究不仅在 多主体仿真、系统复杂性以及n p 问题等方面为人工智能、认知科学、计算经济 学等领域的基础理论问题的研究开辟了新的研究途径。同时，也以其分布性、 简单性、灵活性和健壮性为诸如优化问题求解“。“1 、电力系统“7 。5 ”、计算机 、冶金自动化”1 、知识发现、机器人协作、通信网络、电信路由控制等实 际工程问题提供了新的解决方法，显示出巨大的潜力和优势并推动复杂科学的 蚁群算法及群体智能的研究应用 发展。群体智能无人驾驶飞机的研制更显示了群体智能研究的军事意义。因此， 群体智能的研究具有重要意义和广阔的应用前景。 m i l l o n a smm 在1 9 9 4 年提出群体智能应该遵循五条基本原则。分别为： ( 1 ) 邻近原则( p r o x i m i t yp r i n c i p l e ) ，群体能够进行简单的空间和时间计 算； ( 2 ) 品质原则( q u a l i t yp r i n c i p l e ) ，群体能够响应环境中的品质因子； ( 3 ) 多样性反应原则( p r i n c i p l eo fd i v e r s er e s p o n s e ) ，群体的行动范围 不应该太窄； ( 4 ) 稳定性原则( s t a b i l i t yp r i n c i p l e ) ，群体不应在每次环境变化时都改 变自身的行为： ( 5 ) 适应性原则( a d a p t a b i l i t yp r i n c i p l e ) ，在所需代价不太高的情况下， 群体能够在适当的时候改变自身的行为。 这些原则说明实现群体智能的智能主体必须能够在环境中表现出自主性、 反应性、学习性和自适应性等智能特性。但是，这并不代表群体中的每个个体 都相当复杂，事实恰恰与此相反。就像单只蚂蚁智能不高一样，组成群体的每 个个体都只具有简单的智能，它们通过相互之间的合作表现出复杂的智能行为。 可以这样说，群体智能的核心是由众多简单个体组成的群体能够通过相互之间 的简单合作来实现某一功能，完成某一任务。其中，“简单个体”是指单个个体 只具有简单的能力或智能，而“简单合作”是指个体和与其邻近的个体进彳亍某 种简单的直接通信或通过改变环境间接与其它个体通信，从而可以相互影响， 协同动作。群体智能具有如下特点： ( 1 ) 控制是分布式的，不存在中心控制。因而它更能够适应当前网络环境下 的工作状态，并且具有较强的鲁棒性，即不会由于某一个或几个个体出现故障 而影响群体对整个问题的求解。 ( 2 ) 群体中的每个个体都能够改变环境，这是个体之间间接通信的一种方 式，这种方式被称为“激发工作”。由于群体智能可以通过菲直接通信的方式进 行信息的传输与合作，因而随着个体数目的增加，通信开销的增幅较小，因此， 它具有较好的可扩充住。 ( 3 ) 群体中每个个体的能力或遵循的行为规则非常简单，因而群体智能的实 2 第一章绪论 现比较方便，具有简单性的特点。 ( 4 ) 群体表现出来的复杂行为是通过简单个体的交互过程突现出来的智能， 因此，群体具有白组织性1 。 1 1 2 群体智能的研究现状 早在1 9 8 6 年c r a i gr e y n o l d s 实现了生物群体行为的仿真模型b o i d ，1 9 8 7 年c h r i sl a n g t o n 正式提出人工生命的概念，1 9 9 1 年m a r c od o r i g o 提出蚁群 算法，但群体智能s w a r mi n t e l l i g e n c e 概念正式提出的时间并不长。在1 9 8 9 年g e r a r d ob e n i 曾指出群体智能是显示集体智能行为的非智能机器人所组成 系统的一种特性。另一个标志可以说是1 9 9 9 年牛津大学出版社出版了由 e b o n a b e a u 和m d o r i g o 等人编写的一本专著群体智能：从自然到人工系 统“s w a r mi n t e l l i g e n c e ：f r o mn a t u r a lt oa r t i f i c i a ls y s t e m ”。 m d o r i g o 等人从1 9 9 8 年开始组织了两年一次的关于蚁群算法和群体智能 国际会议。1 9 9 9 年进化计算大会召开了蚁群算法专题会议。期刊下一代计算 系统“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 sj o u r n a l ”在2 0 0 0 年为蚁群算 法作了一次专辑。一些有影响的刊物，如科学美国人“s c i e n t i f i ca m e r i c a n ”、 自然“n a t u r e ”分别在2 0 0 0 年3 月和7 月刊登文章介绍蚁群算法和群体智 能。i e e e 进化计算汇刊也在2 0 0 2 年出版蚁群算法和群体智能专辑。m d o r i g o 也是由欧洲联盟资助的s w a r m b o t s 项目的主要负责人。s w a r m - b o t s 项目的主 要目标是研究设计并实现自组织及自装配( s e l f a s s e m b l i n g ) 装置的新途径。它 的理论基础是群体智能和蚁群算法的近期研究成果，即对群居性昆虫和其他动 物群体的自组织和自装配能力的研究。 目前，群体智能的研究比较多而且也比较成熟的算法有蚂蚁优化算法、蚂 蚁聚类算法、粒子群优化算法，还有对蚂蚁分工的研究。如表卜l 所示。 蚂蚁优化算法、粒子优化算法等为解决一类优化问题提供了新的思路，众 多研究者纷纷给予改进，使之得到了扩展和完善，在解决某些问题方面表现出 了比传统优化算法更好的性能。但是单纯对优化算法的研究很难再有其他大的 突破。然而，生物群体拥有巨大的潜力供人们研究，目前还没有形成系统的理 论，许多问题有待回答。以下几个方面将是研究的热点：刺激产生新算法的生 蚁群算法及群体智能的研究应用 物群体的行为模型；各种算法的完善和结合在实际问题上的应用：群体机器人 的研究；群体智能系统的底层机制的研究；系统的建模、仿真以及实际应用。 表卜1 群体智能研究的主要算法 新的行为模型。根据蚂蚁群体以及鸟群、鱼群等生物群体行为提出的算法 都得到了广泛的应用。生物的奥秘是无穷的，从生物学甚至社会学的角度出发， 新的有益的行为模式有待去发现和提炼。 群体智能系统的底层机制研究主要包括：自组织( s e l f o r g a n i z a t i o n ) 、间 接通信( s t i g m e r g y ) 、涌现( e m e r g e n c e ) 。 ( 1 ) 自组织。自组织是一种动态机制，由底层单元( 部件) 的交互而呈现出系 统的全局性的结构。交互的规则仅依赖于局部信息，而不依赖于全局的模式汹1 。 自组织并不是外部的影响施加给系统而体现的种性质，而是系统自身涌现出 的一种性质。系统中没有一个中心控制模块，也不存在一个部分控制另一部分。 自组织的特点：通过利用同一种介质或者媒体创建时间或空间上的结构。比 如蚂蚁筑的巢、寻找食物时的路径等。正反馈( p o s i t i v ef e e d b a c k ) 群体中的每 个具有简单能力的个体表现出某种行为，会遵循已有的结构或者信息指引自己 的行动，并且释放自身的信息素，这种不断的反馈能够使得某种行为加强。尽 管一开始都是一些随机的行为，大量个体遵循正反馈的结果是呈现出一种结构。 自然界通过系统的自组织来解决问题。理解了大自然中如何使生物系统自组织， 就可以模仿这种策略使系统自组织。 ( 2 ) 间接通信。群体系统中个体之间如何进行交互是个关键问题。个体之间 4 第一章绪论 有直接的交流，如触角的碰触、食物的交换、视觉接触等，但个体之间的间接 接触更为微妙，已经有研究者用s t i g m e r g y 来描述这种机制：也就是个体感知 环境，对此做出反应，又作用于环境。g r a s s e 首先引入s t i g m e r g y 来解释蚂蚁 筑巢中的任务协调。3 。s t i g m e r g y 在宏观上提供了一种将个体行为和群体行为 联系起来的机制。个体行为影响着环境，又因此而影响着其他个体的行为。个 体之间通过作用于环境并对环境的变化做出反应来进行合作。总而言之，环境 是个体之间交流、交互的媒介。从蚂蚁寻食到蚂蚁聚集尸体到蚂蚁搬运、筑巢， 个体之间的通信机制总是离不开s t i g m e r g y 机制，对于环境的作用，通常由各 种各样的信息素来体现。 ( 3 ) 涌现。群体智能中的智能就是大量个体在无中心控制的情况下体现出来 的宏观有序的行为。这种大量个体表现出来的宏观有序行为称为涌现现象。没 有涌现现象，就无法体现出智能。因此，涌现是群体智能系统的本质特征。只 知道孤立的个体行为并不能了解整个系统( 如蚁群) 的情况，仅仅研究孤立的部 分无法有效地研究整体性质，因此，对涌现现象的研究必须既研究各个部分， 又研究各个部分之间的相互作用3 。“遗传算法之父”约翰霍兰在文献”4 3 中对 涌现现象进行了较为深入的探索。他认为涌现现象的本质是“由小生大，由简 入繁”，并且把细胞组成生命体，简单的走棋规则衍生出复杂的棋局等现象都视 为涌现现象。他认为神经网络、元胞自动机等可算作涌现现象的模型。群体智 能的涌现现象与系统论和复杂系统中阐述的涌现本质上是相同的，它是基于主 体的涌现。1 9 7 9 年霍夫施塔特对基于主体的涌现作了描述，整个系统的灵活的 行为依赖于相对较少的规则支配的大量主体的行为。研究群体智能系统，要弄 清涌现现象的普遍原理，建立由简单规则控制的模型来描述涌现现象的规律。 群体智能系统建模与仿真。对群体智能系统提出较为通用的模型将是今后 研究的一个重点。该模型用来反映智能在群体系统中的涌现过程。建立这个模 型，首先需要对群体系统的基本的特征和机制有相当的理解。在此基础上，构 建个体之间能够交互，具有一定学习能力的智能系统，进而解决具体的问题。 s w a r m 平台是由美国桑塔费研究所开发的开放式仿真平台。s w a r m 拥有可扩展 的类库和精巧的架构，提供了用于多a g e n t 系统这样的设计、实现、运行和分 析的工具。s w a r m 的基本思想是：描述一系列独立的个体，通过独立事件进行 蚁群算法及群体智能的研究应用 交互作用。在s w a r m 中，个体行为的组合决定了整个群体的行为，而群体行为 决定了个体做出它们行为选择的环境。利用s w a r m 平台进行群体智能系统的仿 真，可以在一定程度上反映系统的自组织、间接通信和智能涌现的特点。 在群体智能的范畴内，已经取得了相当多的研究成果。研究和掌握群体智 能系统的特性与规律，是一个具有理论和应用两个方面重要意义的课题。它的 研究与发展，将为人工智能领域带来新的活力，提供解决问题的全新的角度和 方法，同时由于它广阔的市场前景，也是和人类社会经济密切相关的，现实意 义非常明显。可以预见，对群体智能的研究将全面展开，必将在某些方面出现 新的成果m ”。 1 2 蚁群算法 1 2 1 蚁群行为描述 根据仿生学家的长期研究发现：蚂蚁虽没有视觉，但运动时会通过在路径 上释放出一种特殊的分泌物信息素来寻找路径“。”。当它们碰到一个还没 有走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长度有关的 信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这 个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反 馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间 的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境 的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快地重新找到最 优路径。可见，在整个寻优过程中，虽然单只蚂蚁的选择能力有限，但是通过 信息素的作用使整个蚁群行为具有非常高的自组织性，蚂蚁之间交换着路径信 息，最终通过蚁群的集体自催化行为找出最优路径。这里用如图i - i 所示的形 象图例来进一步说明蚁群的搜索原理。 图卜l 中，设a 点是蚁巢，d 点是食物源，e f 为一障碍物。由于障碍物的 存在，蚂蚁只能经由a 经e 或f 到达d ，或由d 到达a ，各点之间的距离如图 卜1 ( a ) 所示。假设每个时间单位有3 0 只蚂蚁由a 到达d 点，有3 0 只蚂蚁由d 到 达a 点，蚂蚁过后留下的信息量为l 。为了方便起见，设该物质停留时间为l 。 6 第一章绪论 在初始时刻，由于路径b f 、f 1 c 、b e 、e c 上均无信息素存在，位于a 和d 的蚂蚁 可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择b f 、f c 、 b e 、e c ，如图卜l ( b ) 所示。经过一个时 径b e e 上信息量的2 倍。又经过一段时 d ，如图卜1 ( c ) 所示。随着时间的推移 b f c ，最终将会完全选择路径b f c ，从而 问单位后，在路径b f c 上的信息量是路 间，将有2 0 只蚂蚁由b 、f 和c 点到达 ，蚂蚁将会以越来越大的概率选择路径 找到由蚁巢到食物源的最短路径“3 1 e ee 图1 1 自然界中的蚂蚁觅食模拟 d 1 2 2 蚁群算法模型的建立 1 对蚂蚁个体的抽象 由于蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，是一种机理上 的应用，因此首先必须对真实蚂蚁进行抽象，而不可能也没有必要对蚂蚁个体 进行完全的再现“。抽象的目的就是为了能够更加有效的刻画出真实蚁群中能 够为算法所借鉴的机理同时抛弃与建立算法模型无关的因素。这样抽象出来 的人工蚂蚁可以看作是一个简单的智能体，能够完成所求问题简单解的构造过 程，也能通过一种通信手段相互的影响。 2 问题空间的描述 自然界中的真实蚂蚁存在于一个三维 在平面内进行的，因此需要将蚂蚁觅食的 计算机不能够完整的描述一个连续的平面 此必须将连续的平面离散化为由组点组 7 境中 而问题空间的求解一般是 空间抽象为一个平面。但是由 为计算机处理的是离散事件， 离散平面人工蚂蚁可以在抽象 f f f 于因 环维因的 的三 ，成 蚊群算法及群体智能的研究应用 出来的点上自由的运动。因为蚂蚁在连续平面上的运动，但是其行动经过的总 是离散点。因此可以用数学工具图来描述蚁群算法所求解的空间问题。由 于图在很多的问题都可以用，这使蚁群算法的广泛应用成为可能。 3 寻找路径的抽象 真实的蚂蚁在觅食过程中主要按照所处环境中的信息量来决定其前进的方 向，而人工蚂蚁是在平面的节点上运动，因此可以把觅食过程抽象成算法中解 的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一个节点，人工蚂 蚁感知连接该节点与相邻节点边上的信息素轨迹浓度，并根据该浓度的大小来 决定走向下一节点的概率。用任意两个节点分别表示蚂蚁的巢穴( 初始节点) 和 食物源( 目标节点) ，人工蚂蚁从初始节点按照一定状态转移概率选择下一个节 点，依次类推，最终选择行走到目标节点，这样便得到了所求问题的一个可行 解。 4 信息素挥发的抽象 自然界中的真实蚂蚁总是在所经过的路径上连续不断的留下信息素，而信 息素也会随着时间的推移而连续不断地挥发。由于计算机处理的是离散事件， 所以必须使信息素的挥发也是离散发生的。一般采取的做法是：当蚂蚁完成从 一个节点到下一个节点的移动后，即经过一个时间单位之后，进行一个信息素 的挥发，而这种在离散时间点进行信息素挥发的方式与蚂蚁觅食过程的机理是 一致的。 5 启发因子的引入 上述几点是对蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组织性， 但是这种自组织系统存在一个缺陷，即系统的演化需要耗费较长的时间。而在 实际的应用中对算法的时间的要求也是必不可少的，因此在决定蚂蚁在行走方 向的状态转移概率时，引入了一个随机搜索的过程，即引入了启发因子，在根 据所求问题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大的增 加了算法的时间有效性，从而使蚁群算法的有效应用成为可能。 从以上分析可以看出，通过上述描述的一些抽象过程，可建立一个蚁群算 法的基本模型。其空间是用图来描述的，解的获取是构造性的，而且在解的构 造过程中人工蚂蚁没有接受任何全局的指导信息，因而求解的过程是自组织的。 8 第一章绪论 在蚁群算法中，蚂蚁个体是蚁群算法的基本单元。蚂蚁个体所拥有的知识 来源于其它蚂蚁个体的通讯以及对周围环境的感知，因此，蚂蚁个体的知识积 累是一个动态的过程。蚂蚁个体通过随机决策机制和相互协调机制可自适应的 做出并完成，蚂蚁个体之间的这种分布性和协作性正是蚁群算法所研究的核心 内容。 蚁群算法具有很强的自学的能力，可根据环境的改变和过去的行为的结果 对自身的知识库或自身的组织结构进行再组织，从而实现算法求解能力的进化。 然而环境变化的不确定性和算法机理的复杂性增加蚁群算法的不可预测性“”。 1 2 3 蚁群算法的系统学特征 1 蚁群算法是一个系统 系统学是一门较新的学科，其基本特点是强调整体性。系统学十分庞大， 由于不同学科的研究范围和侧重点不同，往往对系统”给出了不同的定义。 在基础科学层次，通常采用系统学创始人b e r t a l a n f f ylv 所给出的定义：“系 统可以确定为处于一定的相互关系中并与环境发生关系的各组成部分( 要素) 的 综合体”。这个定义强调的不是功能，而是系统元素之间的相互作用以及系统对 元素的整体作用。该定义可更为精确化的表述为：如果对象s 满足以下两个条 件： ( 1 ) s 中至少包含两个不同的对象。 ( 2 ) s 中的对象按照一定的方式互相联系在一起。 则称s 为一个系统，同时定义s 中的个体对象为系统的元素。 很显然，自然界中的蚁群具备了系统的三个基本特征，即多元性、相关性 和整体性，从而，构成了一个系统。在这个系统中，蚂蚁的个体行为是系统的 元素，蚁群行为的相互影响体现了系统的相关性，而蚁群可以完成个体完成不 了的任务则体现了系统的完整性，显示出系统整体大于部分之和的整体突现原 理。 作为对蚁群觅食行为抽象的蚁群算法，如果把算法本身看作一个整体，就 会发现它具备了系统的特征，这也是仿牛优化算法最重要的特征之一”“。对于 个传统的算法而言，比如说一个求无约束值的解析方法牛顿法，由于算 9 蚁群算法及群体智能的研究应用 法各个组成部分完成的功能之和就等于算法最终完成的功能( 具有加和性) ，所 以不能看作一个系统。然而在蚁群算法中，采用多只蚂蚁的求解结果明显好于 单只蚂蚁的求解结果，因此不具有加和性，整体大于部分之和，因此蚁群算法 是一个系统。 2 分布式计算 将蚁群算法作为一个系统来研究，它还具备一些更为重要的特征，使它具 备了系统学上更加深刻的意义。 生命系统是一个分布式系统，它使得生命体具有强的适应能力。比如说人 体的很多细胞相互独立完成同一项工作，当一个细胞停止工作或新陈代谢之后， 整体的功能不会因此而受到影响。这就是分布式带来的强适应能力，它依赖于 个体行为，但并不单独依赖于每一个体的行为。 仔细分析可以发现，自然界中的真实蚁群行为也出现了分布式。当蚁群需 要完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终 任务的完成不会由于某些个体的缺陷而受到影响。 蚁群算法作为对蚁群觅食行为的抽象，也体现了群体行为的分布式特征。 每只人工蚂蚁在问题空间的多个点同时开始相互独立地构造问题解，而整个问 题的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。 具体到不同的优化问题而言，蚁群算法体现出的分布式特征就具有了更加 现实的意义。因为所有的仿生优化算法均可看作按照一定规则在问题解空间搜 索最优解的过程， 算法寻优的效率。 限制，可能得不 智能体系统，它 较强的全局搜索 3 自组织 搜索点的初始选取就直接关系到算法求解结果的优劣和 解许多复杂问题时，从一点出发的搜索受到局部特征的 问题的满意解；而蚁群算法则可看作是一个分布式的多 空间的多点同时独立地进行解搜索，不仅使得算法具有 也增加了算法的可靠性。 蚁群算法的另一个重要特征是自组织，这也是遗传算法、人工神经网络、 微粒群算法、人工免疫算法、人工鱼群算法等仿生优化算法的共有特征。 自组织的概念是随着系统科学的发展而建立起来的。通常把系统论中的组 织行为分为自组织和他组织两大类。其根本区别在于组织力或组织指令是来自 j 0 以求求题 ，所当所问力到在能 第一章绪论 于系统内部还是来自于系统外部，前者称为自组织，而后者即为他组织。如果 系统在获得时间的、空间的或者功能的结构过程中，没有外界的特定干预，则 称该组织是自组织的。 最典型的自组织就是生物体，在生物学上有一个观点，即类似蚂蚁、蜜蜂 这样的昆虫，由于个体作用简单，而个体之间的协作作用特别明显，因而可把 它们当作一个整体来研究，甚至把它们看作一个