（计算机应用技术专业论文）蚁群算法及其在数据挖掘中的应用.pdf

中文摘要 摘要 近年来自然计算已经是计算机科学的一个重要且具有巨大发展前景的分支。早 期有遗传算法，免疫算法，神经网络等自然计算方法，而从上世纪九十年代以来 又产生了蚁群算法，量子计算，d n a 计算，膜计算等一些具有重大前景的自然计 算方法。 蚁群算法是根据蚂蚁群落的种种行为而提出来的。蚁群算法具有系统协作，分 布式运作，全局收敛等特点。依据所参照的蚁群行为的不同，蚁群算法在寻优方 面有基于蚂蚁觅食行为的蚁群优化算法；在聚类分析方面有基于蚁穴清理行为的 蚁群聚类算法等。目前，蚁群优化算法己从单纯的组合优化问题求解拓展到了网 络路由，机器人路径规划，图象处理等领域；蚁群聚类算法也应用于数据挖掘， 数据分析，图的着色问题等领域。 将蚁群算法应用于数据挖掘领域中的数据分类和聚类是近年来的研究热点，但 相关的研究成果并不多。本论文旨在对蚁群算法进行详细分析的基础上，通过调 节蚁群行为的作用机制使蚁群算法能够更好的运用于数据挖掘。 本文的主要研究工作及获得的结论包括： 对蚁群算法的发展历程以及当前的研究现状进行了系统的阐述 以t s p 为例，详细分析了蚁群算法的参数设置；在大量数值实验的基础上， 获得了蚁群算法参数间的关系；分析并给出了算法参数组合与算法效率、算法 性能间的关系；为蚁群算法的参数优化配置提供了一种方法。 详细分析了a n t - m i n e r 算法的特性，针对数据分类规则挖掘提出了对a n t - m i n e r 改进的策略。包括：引入了两步走策略，扩大了蚁群的搜索空间；改进了信息 素更新机制，提高了算法效率和性能。 分别根据蚁穴清理和蚁群觅食行为提出了不同的数据聚类算法。 本文对蚁群算法参数的分析研究有助于对蚁群算法更深入的理论与实验分析； 对蚁群算法中参数组合的研究有助于获得性能与效率更高的蚁群算法；对 a n t m i n e r 算法的分析研究及改进有助于获得更好的数据分类算法。 关键词：自然计算，蚁群算法，数据挖掘，分类，聚类 英文摘要 a b s t r a c t n a t u r a lc o m p u t a t i o nh a sd e v e l o p e dt ob e 姐i m p o r t a n tb r a n c ho fc o m p u t e rs c i e n c e a n di so fg r e a td e v e l o p m e n tp r o s p e c t t h e r ea l em a n yn a t u r a lc o m p u t a t i o na l g o r i t h m s u n d e rr e s e a r c h , f o re x a m p l eg e n e t i ca l g o r i t h m , i i i m u n ea l g o r i t h m , n e u r a ln e t w o r k sa t e a r l yt i m ea n dm a n yn e wn a t u r a lc o m p u t a t i o na l g o r i t h m sp r o p o s e di n1 9 9 0 s t h en e w n a t u r a lc o m p u t a t i o na l g o r i t h m si n c l u d ea n tc o l o n ya l g o r i t h m , q u a n t u mc o m p u t i n g , d n a c o m p u t i n ga n dm e m b r a n ec o m p u t i n g a n t c o l o n ya l g o r i t h mi sp r o p o s e db yt h ed i f f e r e n tb e h a v i o r so fa n tc o l o n ya n dh a s t h ec h a r a c t e r so fs y s t e m a t i s m , d i s t r i b u t i o n , g l o b a lc o n v e r g e n c ee t c a c c o r d i n gt ot h e d i f f e r e n c eo f a n tc o l o n yb e h a v i o r s ，a n tc o l o n ya l g o r i t h mi sc l a s s i f i e di n t od i f f e r e n tt y p e s w h i c h 黜t h ea n tc o l o n yo p t i m i z a t i o nb a s e do na n tc o l o n yf o r a g i n gb e h a v i o r , t h ea n t c o l o n yc l u s t e r i n ga l g o r i t h mb a s e do na n tn e s tc l e a n i n gb e h a v i o r sa n do t h e r s s of a r , t h e a p p l i c a t i o nf i e l d so fa n tc o l o n yo p t i m i z a t i o nh a v eb e e ne x t e n d e df r o mc o m b i n a t i o n o p t i m i z a t i o nt on e t w o r kr o u t i n g , r o b o tp a t hp l a n n i n g , i m a g i n ep r o c e s s i n ge t ca n dt h ea n t c o l o n yc l u s t e r i n ga l g o r i t h mh a sb e e na p p l i e di n t ot h ef i e l d so fd a t am i n i n g , d a t a a n a l y s i s ，g r a p hc o l o r i n gp r o b l e me t e i ti st h er e s e a r c hh o t s p o tr e c e n t l yt h a tt h ea p p l i c a t i o no fa n tc o l o n ya l g o r i t h mi n d a t am i n i n gf i e l d ，s u c ha sd a t ac l a s s i f i c a t i o na n dd a t ac l u s t e r i n g , b u tt h e r ea r en o t e n o u g hr e l a t i v er e s e a r c ha c h i e v e m e n t s t h i sp a p e ri st oa n a l y z et h ea n tc o l o n y a l g o d t h mi nd e t a i la n dc h a n g et h er u n n i n gm e c h a n i s mo fa n tc o l o n ya l g o r i t h mt o i m p r o v et h ea p p l i c a t i o no f a l g o r i t h mi nd a t am i n i n g , t h em a i nr e s e a r c hw o r k i n ga n da c h i e v e m e n t si nt h ep a p e ra sf o l l o w s ： e x p o u n d t h e h i s t o r y a n dr e s e a r c h h o t s p o t o fa n t c o l o n ya l g o r i t h m s y s t e m a t i c a l l y ；, a n a l y s i st h ec o n f i g u r a t i o no fp a r a m e t e r si na n tc o l o n ya l g o r i t h mi nd e t a i l b a s e do nt s p ；g e t 也er e l a t i o n s h i pb e t w e e nt h ed i f f e r e n tp a r a m e t e r so fa n t c o l o n ya l g o r i t h m st h r o u g hl o t so f n u m e r i c a lc x p o r i m e n t s ；a n a l y s i sa n dg e tt h e r e l a t i o n s h i pb e t w e e nc o n f i g u r a t i o no fp a r a m e t e r sa n da l g o r i t h me f f i c i e n to r p e r f o r m a n c e ；p r o p o s e dan e ww a y i nc o n f i g u r a t i o no f p a r a m e t e r s a n a l y s i st h ec h a r a c t e r so fa n t - m i n e ri nd e t a i l a n dp r o p o s e di m p r o v e d s t r a t e g i e so na n t - m i l l e ra i ma td a t ac l a s s i f i c a t i o nr u l em i n i n g t h ei m p r o v e d s t r a t e g i e si n c l u d et w o s t e ps t r a t e g yu s e dt oe x p a n dt h ea n t ss e a r c h i n g1 0 0 1 1 1 m 重庆大学硕十学 寺论文 a n dt h ei m p r o v e dp h e r o m o n eu p d a t i n gm e c h a n i s mw h i c hc a l li m p r o v et h e a l g o r i t h me f f i c i e n ta n dp e r f o r m a n c e i n t r o d u c ed i f f e r e n ta n tc l u s t e r i n ga l g o r i t h m sb a s e do na n tc o l o n yf o r a g i n g b e h a v i o ra n da n tn e s td e a n i n gb e h a v i o r t h ea n a l y s i so fc o n f i g u r a t i o no fp a r a m e t e r si nt h i sp a p e ri sb e n e f i tf o rt h e t h e o r e t i c a la n de x p e r i m e n t a n a l y s i s o fa n tc o l o n ya l g o r i t h m ；t h er e s e a r c ho i l c o m b i n a t i o n a lo fa n tc o l o n ya l g o r i t h mp a r a m e t e r si sh e l p f u lt og e tm o r ee 伍o e n ta n d b e t t e rp e r f o r m a n c ea n tc o l o n ya l g o r i t h m ；t h ei m p r o v e ds t r a t e g i e so na n t m i n e r i n t r o d u c e di nt h i sp a p e ri sh e l p l f u lf o rd i s c o v e r i n gb e t t e rd a t ac l a s s i f i c a t i o na l g o r i t h m s k e y w o r d s ：n a t u r a lc o m p u t a t i o n ，a n tc o l o n ya l g o r i t h m ，d a t am i n i n g , c l a s s i f i c a t i o n ， c l u s t e r i n g 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重鏖太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：荔75 签字日期：乙一1 年妇9 日 学位论文版权使用授权书 本学位论文作者完全了解重庆盍堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 0 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：了i ls 鼍 签字日期：埘年0 月5 日 r 一名：钾孑 签字日期劬7 年月g 日 i 绪论 1 绪论 当今，随着信息量的急剧膨胀，数据挖掘技术【5 “矧越来越体现出自己的应用 价值。为了从巨量的数据信息中提取有价值的模式，需要高效率的算法。在数据 挖掘中所使用的算法有一些比较传统，比如关联规则挖掘中的a p r i o r i 算法p 】，在 聚类分析中的k - 均值算法 4 1 ，在数据分类中的判定树归纳算法【5 】。但是这些算法在 具体的实现方面仍然存在不足。比如a p r i o r i 算法会产生过多的频繁模式；k - 均值 算法存在局部最优化和不能确定聚类数目的问题；判定树算法的町伸缩性能不强。 因此，为了获得更高效率的算法，除了在原有传统算法的基础之上进行改进，也 逐渐引进了一些新的算法，其中最近逐渐引起关注的自然计算开始应用于数据挖 掘模式提取。例如在数据分类分析中引进了遗传算法和神经网络方法。 自然计算是近年发展起来的一类算法，它具有自适应、自组织、自学习能力， 能够解决传统计算方法难于解决的复杂问题。自然计算的应用领域包括复杂优化 问题求解、智能控制、模式识别、网络安全、硬件设计、社会经济、生态环境等 方面的应用。蚁群算法【l5 l 是最近引起广泛关注的自然计算算法。它具有系统协作， 分布运行，正反馈，易于与其他算法相结合等特点，已经运用于组合优化 6 , 7 , 8 , 9 1 ， 网络路由【l o j t ，图象处理f 1 2 1 ，数据挖掘 1 3 , 1 4 1 等多个领域。本章着莺阐述数据掘和 蚁群算法的研究背景，本论文的主要研究思路，研究目的和研究意义，最后介绍了 本论文的主要内容和组织架构。 1 1 研究现状 半个世纪以来，人们利用信息技术生产和搜集数据的能力在不断提高。当前 有大量数据库用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将 持续发展下去。特别是近年来，i n t e r n e t 经过迅猛发展，已经成为一个巨大的、分 布广泛的和全球性的信息服务中心。于是，一个挑战被提了出来：在这被称为信 息爆炸的时代，信息过量几乎成为人人需要面对的问题。为了不被信息的汪洋大 海所淹没，从中发现有用的知识，提高信息的利用率使其真正成为有意义并有助 于做出正确决策的资源，就必须充分利用大量数据中所包含的与本身应用相关联 的模式信息才行。否则数据可能成为包袱，甚至成为垃圾。因此，面对1 言息爆炸、 但知识匮乏”的挑战，数据挖掘技术应运而生，并得到蓬勃发展，越来越显示出强 大的生命力。 在1 9 9 5 年于加拿大召开的第一届知识发现和数据挖掘国际学术会议上，由于 将“数据”比喻成矿床，由此术语“数据挖掘”就广泛地流传开了。数据挖掘就是对观 莺庆大学硕十学衍论文 测到的大量原始自噪音的数据进行分析，发现潜在有用的模j 和以数据拥有者町 以理解并对其有价值的新颖方式来总结数据的非平凡过程。数据挖掘由f 是从大 量的数据中获取有价值的模式，所以也被称为数据库中的知识发现。另外，还有 一些术语i d 样也表达的数据挖掘的含义，比如数据库中知识挖掘，知识提取，数 据模式分析，数据考占和数据捕捞等1 1 捌。 自1 9 8 9 年以来，伴随着网络和数据库技术的发展，数据挖掘逐渐成为了计算 机学科的热点研究领域。从数据库中知识发现首次于第1 1 届国际联合人工智能学 术会议上提出以来，截至至2 0 0 4 年，美国人工智能协会重办的k d d 国际研讨会 已经召开了8 次，规模也由以前的专题讨论会发展到国际学术大会。研究的藿点 也逐渐从发现方法向系统应用，注重多种发现方法和策略的集成，以及多种学科 之间的相瓦渗透。1 9 9 9 年，在北京召开的亚太区第三届p a k d d 会议收到了1 5 8 篇论文。i e e e 的k n o w l e d g ea n d d a t a e n g i n e e r i n g 会刊率先于1 9 9 3 年推出了k d d 技术专刊。并行计算，计算机网络和信息工程等其他领域的国际学会，学刊也把 数据挖掘和知识发现列为专题或专刊讨论。此外，在i n t e r n e t 上还有不少k d d 电 子出版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威。 目前在国外随着理论研究的深入以及实际需求的不断增长，已经开发出了一 些具有实用价值数据挖掘系统，其中比较有影响的有：s a s 公司的e n t e r p r i s e m i n e r ， i b m 公司的i n t e l l i g e n tm i n e r ，s g i 公司的s e t m i n e r ，s p s s 公司的c l e m e n t i n e ，s y b 鸽e 公司的w a r e h o u s es t u d i o ，r u l e q u e s tr e s e a r c h 公司的s e e 5 ，还有c o v e r s t o r y ， e x p l o r a ，k n o w l e d g ed i s c o v e r yw o r k b e n c h ，d b m i n e r ，q u e s t 等。 与国外相比，国内在数据挖掘和知识发现这一领域的研究起步较晚，没有形 成整体力量。1 9 9 3 年，国家自然科学基金首次支持了这一领域的研究项目。目前 我国的许多科研单位和高等院校都开展了数据挖掘的基础理论及其应用研究，其 中包括了清华大学，中科院计算技术研究所，空军第三研究所等。北京系统工程 研究所对模糊方法在数据挖掘中的应用进行了深入的研究。北京大学开展了数据 立方体代数的研究。中国科技大学，复旦大学，浙江大学等高等院校开展对关联 规则开采算法的优化和改造。上海交通大学，南京大学等研究了非结构化数据的 知识发现以及w e b 数据挖掘。 随着网络技术的发展，目前数据挖掘技术有向分布式数据挖掘方向发展的趋 势。同时数据挖掘所处理的对象也逐渐在朝着复杂数据类型的方向演化，比如多 媒体数据挖掘和空间数据挖掘。 在当前的工程应用领域方面存在许多问题是传统方法所不能解决或者不能有 效地解决，而一些模仿自然现象所得到的算法反而具有较高的求解效率。通常将 这类对自然对象的运行机制进行仿真而得到的算法称为自然计算算法【l ”。在自然 2 1 绪论 对象中，尤其是生物系统，通常都星现出一种系统的，集群并行的运作方式。受 这种运作方式启发所得出的算法通常都具有比较强的健壮性和比较高的求解效 率。 目前，研究较多的自然计算算法有发展较为成熟的遗传算法( g e n e t i c a l g o r i t h m ) 【1 7 j ，人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 1 8 】以及最近引起广泛关注 蚁群算法( a n tc o l o n y a l g o r i t h m ) 1 s td n a 计算( d n a c o m p u t i n g ) 0 9 1 ，量子计算 ( q u a n t u mc 细叩u 协t i ) 【2 0 】和膜计算( m 蹦曲锄ec o m p u t i n g ) 2 1 噜。其中，遗传算法是 一类借鉴生物界适者生存，优胜劣汰遗传机制演化而来的随机化搜索算法。算法 包含了编码，选择，交换，变异等过程。它是由美国的j h o l l a n d 教授在1 9 7 5 年首 先提出，目前在组合优化、机器学习、信号处理等领域都有应用。人工神经网络 是对人脑或自然神经网络若干基本特性的抽象和模拟。人工神经网络以对大脑的 生理研究成果为基础，其目的在于模拟大脑的某些机理与机制，实现某个方面的 功能。人工神经网络几乎在人工智能诞生之初就出现了，目前在模式识别、信号 处理、知识工程等领域都有应用。d n a 计算是a d l e m a n 于1 9 9 4 年首先提出，其 作用原理是在酶的催化下使得d n a 四种碱基发生相互作用而实现相应的计算。研 究表明【1 9 】，d n a 计算具有相当高的运行效率，这为解决困难问题提供了新的途径。 蚁群算法是通过模拟蚁群部落的群体行为而得出的一种仿生算法，作为一种 自然计算算法已经得到了广泛的认可和应用。蚁群算法最初是由意大利学者 d o r i g om 于1 9 9 1 年提出来的，仿照蚂蚁觅食行为成功地解决了t s p 问题。经过 d o r i g om ，b o n a b e a ue ，s t u t z l e 等学者的完善，逐渐建立起了较为完善的数学模型， 得出了基于蚁群觅食行为的蚁群最优化( a n tc o l o n yo p t i m i z a t i o n ) 1 2 2 。蚁群算法具 有很好的健壮性，优良的分布式计算控制，容易与其他方法相结合，求解效率高 等特点。蚁群算法自创立以来，无论在算法理论还是在算法的应用方面都取得了 很多突破性研究进展。针对不同的具体问题提出了许多不同类型的改进蚁群算法 模型，在算法的收敛性方面的研究也取得了一定的成果。而蚁群算法的应用范围 几乎已经涉及到各个优化领域。与此同时，蚁群算法仍然存在若干不足之处： 在蚁群依据信息素确定行走路径的过程中，可能会出现蚁群陷入局部最优 解的情况，造成了算法求解的偏差。 蚁群算法是一种基于蚁群群体行为的算法，群体各个个体需要通过交换信 息素实现相互通讯，并通过信息素的差异分布构造问题的解。算法求解问 题过程中需要问题空间中存在信息素的差异，而这一差异的出现常常需要 耗费算法一部分的时间，在某些情况下会很大程度地降低算法的运行效 率。 在算法实现方面存在许多不确定的因素，比如，信息素初始数值的确定， 重庆人学硕卜学伊论文 不同的蚁群算法设置为不同的数值，而且具有很大的差异；在信息素的更 新方面，同样具有差异很大的很多不同的方式；另外，算法还育许多参数 的取值要在算法中确定，这些参数在不同取值的情况f ，常常会对算法的 性能和求解效率产生重大影响。 另外，蚁群算法在理论分析，模型改进，硬件实现等其他方面同样值得进一 步研究。1 9 9 8 年在比利时布鲁塞尔召开了第一届蚁群算法国际研讨会，吸引了来 自世界各地的5 0 多位蚁群算法研究者，会议论文均由著名的s c i 检索。2 0 0 0 年， d o r i g om 和b o n a b e a ue 等在n a t u r c 上发表了蚁群算法的研究综述，从而把蚁 群算法的研究推向了国际学术的最i l 沿。最近几年，n a t u r e ) ) 曾多次对蚁群算法 的研究成果进行了报道，f u t u r e g e n e r a t i o n c o m p u t e r s y s t e m ) ) 和( ( i e e e t r a n s a c t i o n s o i le v o l u t i o n a r yc o m p u t a t i o n ) ) 分别f2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊。如 今，在国内外许多学术会议和期刊上，蚁群算法已经成为一个备受关注的研究热 点和前沿性课题。 1 2 研究意义、目的 尽管目前对蚁群算法的严格理论基础尚未确定，算法的正确性证明也很困难， 研究还处于实验分析阶段，但是它的应用范围已经得到了很大的拓展，由最初的 t s p 问题逐渐渗透到了数据挖掘，网络路由，图像处理等多个应用领域；由解决 一维静态优化问题发展到解决多维动态组合问题；由离散域范围内的研究逐渐拓 展到连续域范围的研究【2 3 1 。蚁群算法在硬件实现上也取得了很多突破性的进展州， 同时蚁群算法的模型改进及与其他仿生优化算法的融合方面取得了相当丰富的研 究成果【2 5 2 6 0 7 1 ，使这种新兴的仿生优化算法展现出蓬勃生机和广阔的发展前景。 蚁群算法已经成功地应用f 数据挖掘领域，目前主要集中在数据分类和聚类 两方面 1 3 1 4 。但是在算法的实现机制方面显得比较单一：应用于数据挖掘领域中 的蚁群算法在信息素的更新策略，在选路策略，在信息素初始数值的设置，在参 数设置等方面还有进一步研究的余地，而这螳研究将有助于完善蚁群算法在数据 挖掘领域中的应用。 本论文的研究目的是为了进一步地对蚁群算法的某些实现细节进行研究，其 中重点研究的是蚁群算法参数对蚁群算法性能的影响，提供蚁群算法更好的参数 配置建议。探讨蚁群算法在数据分类中的应用，并引入新的实现机制以改善蚁群 算法当前在数据挖掘分类分析中的应用。对蚁群算法在聚类分析中的不同应用进 行分析。 1 3 论文的主要内容与框架 本论文主要的研究内容包括了两个方面，一个方面侧重于：蚁群算法的研究； 4 1 绪论 另一个方面侧重于蚁群算法在数据挖掘中的应用。 在蚁群算法研究方面，本论文阐述了蚁群算法的基本特征以及发展历程，并 在此基础上对算法的参数设置进行了研究，论述了相互关联的两个参数在特定的 关系之下同时变化对算法性能的影响以及在相互关联的两个参数不同取值组合下 算法优解的分布，以此更进一步地分析蚁群算法中各个参数对算法的影响。 在蚁群算法于数据挖掘中应用这一方面，介绍了a n t - m i n 一1 3 l 算法的主要实现 机制并进行了详细分析；针对a n t m i n e r 的主要问题提出了改进方法。简要地介绍 并分析了蚁群算法在聚类分析中的实现机制。 论文的主要框架：第一章绪论部分主要介绍了论文的研究背景，研究目的， 研究意义等内容。第二章详细地阐述了蚁群算法借鉴的生物模型，发展历程，以 及最新的研究现状。第三章对具有代表性的蚁群算法一蚁群系统的参数进行了组 合化分析，力图揭示出参数之间的相互关系对算法的影响。第四章介绍了蚁群算 法在数据挖掘分类中的应用，详细介绍了a n t m i n e r 的实现，并针对算法的不足给 出了自己的改进策略。第五章介绍并分析了蚁群算法在数据挖掘聚类中的应用。 第六章对全文进行了总结和概括。 2 蚁群算法概述 2 蚁群算法概述 蚁群算法从广义的角度来讲是对基于蚂蚁群落各种特定行为而得出的一系列 仿生算法的总称。从狭义的角度来讲指的是基于蚁群觅食行为的蚁群最优化算法 ( a n tc o l o n yo p t i m i z a t i o n , a c o ) 。蚁群最优化算法在各种蚁群算法中发展最为迅速， 应用范围最广，理论研究也相对更加透彻。在本论文中，没有特定指明的情况下， 一般蚁群算法都是指蚁群最优化算法。 2 1 广义蚁群算法的生物原型 蚂蚁是一种高度社会化的生物，社会性高于个体性。蚁群通过高度社会化的 组织和分工协作，常常可以完成一些对于单个蚂蚁而言不可完成的任务。在蚁群 群落中，有三种具有代表性的群体行为引入关注：觅食行为1 2 引，任务分配行 2 9 1 和巢穴清理行为1 3 0 】。 2 1 1 觅食行为 蚁群发现食物后总能找到食物源与巢穴之间的最短路径并将食物搬回巢穴。 生物学家更是发现，无论外部环境如何，蚁群搬运食物所走的路径总是食物源弓 巢穴之间的最短路径，蚁群能自动适应外部环境的变化并找出最短路径。 在觅食最初阶段，各个蚂蚁分散地出去寻找食物，在蚂蚁移动的同时，会释 放出一种称为信息索的化学物质，而且能够感知这种物质的存在，且偏向于向信 息素浓度较高的路径移动。在蚂蚁寻找食物的过程中，当不同路径上信息素的差 异不明显时，蚂蚁采用一种随机的概率去寻找食物。对于两条可选择的路径，相 对较长的路径而占，短路径上相同时间内通过的蚂蚁数目更多，获得的信息素也 更多。随着时间的推移，两条路径上的信息素差异就会体现出来，后续蚂蚁更倾 向于朝着信息素浓度更高的路径移动，而这些路径正是短路径。这样蚁群通过信 息素的引导，不断地修正自己走过的路径，并最终找到蚁穴与食物源之间的最短 距离。不难看出，蚁群在选择路径过程中表现出了一种正反馈现象，某条路径上 走过的蚂蚁数目越多，则后续蚂蚁选择改路径的可能性就越大。由于寻找最短路 径的过程可以视为一种优化过程，所以基于这种现象得出的蚁群算法被称为蚁群 优化算法或蚁群最优化，一般称为蚁群算法。 2 1 2 任务分工 蚁群的任务分工是指蚁群内部能根据任务的紧急度合理分配蚂蚁数量，这是 蚂蚁群体行为的一个非常显著的特点。研究表明，蚁群是一种高度社会化的群体， 内部分工非常明确，有的负责生育，有的负责蚁穴的建筑，有的负责整个群落的 安全，有的负责寻找食物等等。不同分工的蚂蚁对不同任务具有不同的响应，但 7 蘑庆人学硕十学何论文 是它们町以通过角色的协调和相瓦协作柬很好地完成许多任务，使得从事不同任 务的蚂蚁之间数量k 的比例是会变动的【3 “。也就是说，从事任务a 的蚂蚁町能会 根据需要而从事任务b 。当i f 在执行任务的蚂蚁收到外部环境所赋予的新任务时， 相于受到一个刺激。当蚂蚁受到的刺激较小时，蚂蚁仍然执行着自己正在做的 任务。随着时间的推移，新任务对蚂蚁的刺激将变得越来越大，直到超过了该蚂 蚁的反应阂值，蚂蚁就会放弃正在执行的任务而去处理新任务。 在基于蚁群任务分工行为的模型中，规定了每只蚂蚁的反应闽值( r e s p o n s e t h r e s h o l d ) ，同时每一个任务都有一个相关的激励( t a s k r e l a t e ds t i m u l i ) 。蚂蚁的反 应阈值与任务相关的激励之间的关系是：当某个新任务的激励数值没有达到蚂蚁 的反应阈值，那么蚂蚁将不会理会新任务而保持原有的状态，直到新任务的激励 数值比蚂蚁的反应阈值大为止。 2 1 3 巢穴清理 在蚂蚁部落中，有一部分蚂蚁专门从事巢穴的清理工作。一个有趣的现象是， 蚁群通常会在巢穴中构造一个固定的场所作为墓地专门存放死去的蚂蚁，死蚂蚁 被堆积为一个个大堆。对f 一只死蚂蚁，蚂蚁会判断周围死蚂蚁的量，如果死蚂 蚁数量很少，那么蚂蚁就会将死蚂蚁拖动到其他位置。在一只蚂蚁拖动死蚂蚁的 过程中，会判断目前位置周围死蚂蚁的数量，如果死蚂蚁的数量很多，那么蚂蚁 就将目前拖动的蚂蚁放于当前位置，否则继续拖动死蚂蚁到其他位置。这是一个 正反馈现象，某个区域的死蚂蚁数量越大，那么更多的死蚂蚁将被放于该区域： 某个区域的死蚂蚁数量越少，那么该区域的死蚂蚁将更可能被移动到其他区域而 变得更少。这样，蚂蚁就将随机散痈于巢穴中的死蚂蚁存放到了一个固定的区域 起到清理蚁穴的作用。蚁群在安排蚂蚁幼体的位置时，会按照幼体大小不同丽分 别将其堆积在蚁穴的周围和中央位置。这两种蚁群行为由f 与聚类操作相类似， 所以也将这两种行为称为蚁群的聚类行为。目前，基于蚁群聚类行为的算法在数 据聚类分析中已经获得成功应用。 2 2 蚁群算法的特征 蚁群算法中所使用的蚂蚁是现实蚂蚁行为特征的一种抽象，称为人工蚂蚁 3 3 】。 人工蚂蚁与现实蚂蚁一样，都需要通过使用信息素进行间接通讯；都是通过相瓦 协作以群体的方式完成一个共同的任务。但是如果完全依照现实蚂蚁行为机制来 设计蚁群算法，实验表明算法需要很多的时间才会收敛，而且町能会收敛于一些 局部优解。故人工蚂蚁又有不同于现实蚂蚁的地方。以下以t s p 问题为例介绍人 工蚂蚁与现实蚂蚁的区别： 人工蚂蚁有一定的记忆能力，它可以记住已经走过的路径，以保证不会重 2 蚁群算法概述 复走相同的城市。现实的蚁群没有记忆，蚂蚁问的信息交换主要依靠留在 所经过路径上的信息素实现。 人工蚂蚁不仅仅依据信息素来确定要走的路径，还引入了与问题相关的启 发信息，比如相邻边的长度。 人工蚂蚁处于一个离散的时间环境下。我们仅考虑人工蚂蚁位于某个城市 的状态，而不考虑人工蚂蚁在城市间的移动过程，即只考虑人工蚂蚁在某 些离散时间点上的存在。而现实世界中的蚂蚁处于一个连续的时间维中。 2 2 1 系统性 蚁群具备了系统的三个基本特征：多元性、相关性和整体性。在蚁群系统中， 蚂蚁的个体行为是系统的元素，各个蚂蚁之间的相瓦影响体现了系统的相关性， 而蚁群群落在完成任务的过程中所体现出来的协作性和彼此之间相互依存体现了 系统的整体性。作为基于蚁群行为抽象的蚁群算法，如果把算法本身看成是一个 整体，同样也将蚁群的多元性，相关性和整体性引入到算法中，体现了系统性。 这也是仿生优化算法最重要的特征之一。 2 2 2 自组织 自组织性是指系统在没有外界特定于预的情况下，自行完成某些特定功能。 更抽象地讲，自组织性就是在没有外界作用下使得系统熵增加的过程( 系统从无 序到有序的过程) 。在蚁群算法中，单只人工蚂蚁无序地寻找解。经过一段时间的 算法演化，人工蚂蚁越来越趋向于寻找一些接近最优解的解，这正体现了一种从 无序到有序的自组织过程。自组织大大增强了算法的鲁棒性。传统的算法都是针 对某一具体问题丽设计的，这往往建立在对该问题有了全面清晰认识的基础上， 通常很难适应其他问题。而自组织的蚁群算法只需要了解问题的目标并且结合与 目标相关联的启发信息就可以应用于问题的求解过程中来。 2 2 _ 3 正反馈 正反馈是指系统当前的行为对于未来是起一种增强的作用。蚁群算法的求解 过程中，开始时整个求解空间中信息素平均分布，蚂蚁更多地在与问题相关的启 发因子的引导下构造解。蚂蚁所构造的解将获得更多的信息素，从而使得解空间 中的信息素产生差异化分布，这种信息素的差异化分布将导致正反馈现象的产生。 蚁群算法的正反馈性体现在：当某个解较优时，该解就会得到更多的信息素，而 信息素的增多，会吸引更多的蚂蚁选择该解，解越优，获得蚂蚁选择的概率就越 大。这个正反馈的作用使得蚂蚁的选择朝最优解收敛，最终获得最优解。 2 2 4 负反馈性 负反馈性是指系统当前的行为对于未来是起一种削弱的作用。系统的自组织 性需要正反馈和负反馈同时存在，这样系统才能实现自我创造和更新。在蚁群算 9 重庆大学硕士学侮论文 法中，负反馈性体现在蚂蚁构造解的过程中所采用的概率选择技术。在蚂蚁构造 解的过程中，并不是完全依照概率大小来选择解，而是采用赌轮机制来确定。这 意味着即使某个解的被选择概率很大，但是蚂蚁仍然不会选择该解。这在一定程 度上是对解的一种退化，但是这样使得蚂蚁在解宅间的搜索范围进一步地扩大。 正反馈的作用是不断地增加优解的被选择概率，促使算法朝着优解收敛；负反馈 是不断地扩大蚂蚁的搜索范围，使得解具有多样化，避免最终收敛f 局部优解。 在正反馈和负反馈的共同作用f ，蚁群算法以一种自组织的方式进化并最终得出 问题的最优解。 2 2 5 分布并发性 蚁群总是多个蚂蚁个体同时协作完成某项任务，并且单个蚂蚁出现的偏差并 不会影响到整个蚁群的正确运作。以t s p 问题为例来讲蚁群算法的实现，整个蚁 群是随机分布于t s p 图的多个结点上并且同时构造自己的路径，在构造路径的过 程中，各个个体之间还会通过互相交换信息素来实现彼此之间的通讯，引导对方 的搜索。这样在问题空间的多个点同时进行解的搜索，不仅使得算法具有较强的 全局搜索能力，也增加了算法的町靠性。 此外，蚁群算法还有易f 与其他算法相结合等其他特点。比如通过与遗传算 法，免疫算法等算法的结合，可以取长补短，得出一些更有应用价值的新算法。 2 3 蚁群算法的发展历程 本节以t s p 问题为对象，按照时间的先后顺序阐述了几个经典的蚁群算法的 实现细节，介绍了蚁群算法是如何逐步地发展成熟的。 2 3 1 蚂蚁系统( a n ts y s t e m ) 蚂蚁系统【3 2 】是第一个蚁群算法，它是m d o r i g e 等人于1 9 9 1 年首先提出来的。 蚂蚁系统有三种基本模型，分别是蚁周模型、蚁密模型、蚁量模型。 三种模型的实现大致相同，主要区别是在信息素的更新方式上。在用蚂蚁系 统解决t s p 问题时，蚁量模型和蚁密模型在蚂蚁构建一条合法路径的过程中进行 信息素的更新：当蚂蚁走过一条边之后，就对该边进行信息素的更新，后文将这 种信息素更新称为局部更新。而蚁周模型是在所有蚂蚁都构建了一条合法路径之 后才对各边进行信息素更新，后文将这种信息素更新称为全局更新。并且三者在 蚂蚁释放信息素的量上面也不同。蚁密模型中，蚂蚁在自己所走过的边上所释放 的信息素是一个常量q ；蚁量模型中，蚂蚁在自己所走过的边i j 上释放的信息素 是尹其中q 是一个常量，而吐是蚂蚁走过边i j 的长度。蚁周模型中蚂蚁释放 信息素的量在后文说明。 由f 蚁周模型是三种模型中性能最好的，下面蔓要从蚁周模型的角度来讨论 i o 2 蚁群算法概述 蚂蚁系统，本论文以后所讲的蚂蚁系统均指蚁周模型。 蚂蚁系统的基本思想足：预先初始化各边信息素强度以及各蚂蚁的禁忌表。 各蚂蚁按照一定的概率规则，在禁忌表的制约下选择下一个要到达的结点，直 到最终形成一条合法路径。计算各蚂蚁所产生的路径长度，路径长度是路径中 各边长度之和。更新各边的信息素，各边先进行信息素挥发操作，然后根据各 蚂蚁产生的路径长度获取蚂蚁所释放的信息素。当所有蚂蚁均完成了信息素的 更新操作之后，记录当前的最短路径，并且对各只蚂蚁的禁忌表以及信息素的增 加值a r , ( t ，f + 1 ) 进行初始化，并转到步骤2 。依此循环下去，直到满足算法的终了 条件为止，比如解无法得到进一步的改进或者达到了事先规定的循环次数。 蚂蚁系统的实现具体包括了三个方面的内容。 初始化。对于每条边上的信息素初始化为一个较小的数值知；对每只蚂蚁， 需要一个禁忌表记录自己已经走过的结点，初始化时禁忌表长度为1 ，存放该蚂蚁 当前所在的结点。蚂蚁在各边上释放信息素的量被初始化为0 。 蚂蚁构造路径。蚂蚁按照一定的概率确定下一步要到达的城市，这样过程 也称为状态转移。概率的计算如2 1 式所示。 l 娑i f j 。l l o 。d 珊( f ) = 。三。f ) 】锄m r 仆 ( 2 1 ) 1 0 o t h e r w i s e 2 1 式表示蚂蚁在t 时刻由城市i 选择城市j 的概率，也称之为状态转移规则。 口是信息素在概率计算中所占的权重，本论文中称之为信息素权重参数。它的值 越大，信息素在蚂蚁状态转移过程中起到的作用越大。口是启发因子( 在t s p 问 题中常以或的倒数来表示) 在概率计算中所占的权重，本论文中称之为启发因子 权重参数。它的值越大，启发因子在蚂蚁状态转移过程中所起的作用越大。a l l o w e d 是不在蚂蚁禁忌表中的城市集合。2 1 式说明，蚂蚁不会选择禁忌表中的城市，这 样就保证了解的合法性。 对信息素的操作。在蚁周模型中，当所有的蚂蚁都找到了一条合法路径之 后，就进行信息素的更新操作，如2 2 式。 r o ( t + 1 ) = p 白o ) + j ，0 ，f + 1 ) ( 2 2 ) 其中，x l j ( t ) 表示在t 时刻边i j 上的信息素。尸是信息素维持因子，l p 是信 息素的挥发因子。a r o ( t ，f + 1 ) 是t 到t + 1 时间内所有蚂蚁在边i j 上所释放的信息素 的总和，如2 3 式。 a r p ( t ，f + 1 ) = a r ；( t ，f + 1 ) ( 2 3 ) 其中m 是蚂蚁的数量，露( f ，f + 1 ) 是蚂蚁k 在t 到t + 1 时间内在边i j 上所释放的 莺庆人学硕十学伊论文 信息素： 。i 导如果蚂蚁k 所形成的路径包括边i j ( l k 是蚂蚁k 形成的路径长度) ( t , t + 1 ) = 。 “ l o否则 大部分的蚁群算法都是在蚂蚁系统的基础上发展而束的。它们部是将蚂蚁系 统与具体问题相结合，并且在蚂蚁系统的基础之上引入一砦新的控制机制。故， 通常都是把蚂蚁系统认为是蚁群算法的先驱与研究的基础。 2 3 2 蚁群系统( a n tc o l o n ys y s t e m ，a c s ) 蚂蚁系统是第一个蚁群算法，在解决舰模较小的t s p 问题时效果很好，但是 随着问题的规模扩大，蚂蚁系统