（通信与信息系统专业论文）蚁群算法在图象分割中的应用.pdf

中文摘要 2 0 世纪9 0 年代初，意大利学者等人受蚂蚁在觅食过程中可以找出从巢穴到 食物源的最短路径的启发，提出了蚁群算法( a n tc o l o n ya l g o r i t h m ) ，它是继禁忌 搜索算法、模拟退火算法、遗传算法、人工神经网络等启发式搜索算法之后h 现的一种新的启发式搜索算法。蚁群算法不仅能够智能搜索、全局优化，而且具 有稳健性( 鲁棒性) 、正反馈、分布式计算、易与其它算法结合等特点，鲁棒性 强，在基本蚁群算法模型的基础上进行修改，便可用于其它问题；正反馈过程使 得该方法能很快发现较好解；分布式计算使得该方法易于并行实现，个体之间 不断进行信息交流和传递，有利于发现较好解，不容易陷入局部最优：与启发式 算法相结合，可改善算法的性能。它成功应用于解决许多组合优化问题。一些 初步研究和应用已显示出蚁群算法在求解复杂优化问题( 特别是离散优化问题) 方面的一些优越性。目前的研究主要集中在比利时、意大利、德国等国家，国内 的研究始于1 9 9 8 年末，主要在上海、北京、东北少数几个学校和研究所开展了此 项工作，主要围绕t s p 及相关问题的实验仿真。 图像分害4 方法的研究始于上世纪5 0 年代，它是图像处理中最为基础和重要 的领域之一，近年来对通用分割方法的研究倾向于将分割看作一个组合优化问 题，并采用一系列优化策略完成图像分割任务。 该文首先介绍了人工蚁群算法的基本原理，实现流程，分析了蚁群算法的 特性，提出一系列改进算法。并概述了这种算法在优化问题中的多种应用。然 后阐述了图象分割算法的现状，分割的原理和分类，以及一些常规的分割方法。 再根据蚁群算法和分割算法的特点，将两者进行结合。分割算法可以看作 一个组合优化问题，人工蚁群算法就是一种优化方法，因此，将人工蚁群算法 引入到图像分割处理中完全可行。实验结果也证明其方法是完全可行的。 最后，文章对蚁群算法和图象分割进行了总结和展望。 本文就是利用蚁群算法具有寻优特性，来寻找图象分割中的撮佳闽值。进 而达到分割的目的。 关键词：蚁群算法，图象分割，组合优化 a b s t r a c t a tt h ee n do f1 9 9 0 sa n tc o l o n ya l g o r i t h mi sp r o p o s e db yi t a l i a ns c h o l a r sm d o r i g o ，w h oi si n s p i r e db yt h ea n tf i n d i n gt h es h o r t e s tr o a df r o mt h en e s tt ot h e d e s t i n a t i o n i ti san e wk i n do fh e u r i s t i cs e a r c h i n ga l g o r i t h ma f t e rt h et a b us e a r c h ， s i m u l a t e da n n e a l i n ga l g o r i t h m ，g e n e t i ca l g o r i t h ma n da r t i f i c i a ln e u r a ln e ta n ds oo n a n tc o l o n ya l g o r i t h mn o to n l yh a st h ec h a r a c t e r i s t i c so fi n t e l l i g e n ts e a r c h ，g l o b a l o p t i m i z a t i o n b u ta l s oh a st h ec h a r a c t e r i s t i c so f s t a b i l i t yp o s i t i v ef e e d b a c k ， d i s t r i b u t e dc o m p u t i n ga n dc o m b i n a t i o nw i t hc e r t a i nh e u r i s t i ca l g o r i t h m s t a b i l i t yi s g o o d ，m o d i f yt h ea l g o r i t h mo nt h eb a s eo ft h et h ea n tc o l o n ya l g o r i t h mm o d l e ；t h e n i tc a nb eu s e di n t oo t h e rp r o b l e m p o s i t i v ef e e d b a c km a k e si tq u i c k l yt of i n db e t t e r s o l u t i o n s d i s t r i b u t e dc o m p u t i n gm a k e si t e a s i l yt oc o m et r u ep a r a l l e l ，t h eu n i t c o m m u n i c a t e sa n dp a s st h ei n f o r m a t i o n ，t h i si sg o o df o rf i n d i n gt h eb e t t e rs o l u t i o n s ， a n dn o te a s i l yp l u n g i n gi n t ot h ep a r t i a lo p t i m i z a t i o n c o m b i n a t i o nw i t hc e r t a i n h e u r i s t i ca l g o r i t h mc a l l i m p r o v et h ec a p a b i l i t yo ft h ea l g o r i t h m i t i su s e di n c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ms u c c e s s f u l l y s o m er e s e a r c ha n da p p l i c a t i o n p r o v et h es u p e r i o r i t yo ft h ea n tc o l o n ys o l v i n gt h ec o m p l e xo p t i m i z e dp r o b l e m ( e s p e c i a l l yt h ed i s c r e t eo p t i m i z e dp r o b l e m ) n o wt h er e s e a r c hi sm o s t l yi nb e l g i a m ， i t a l y , g e r m a n ya n ds oo n i nc h i n at h er e s e a r c hb e g a na tt h ee n do f1 9 9 8 ，s o m e s c h o o l sa n dg r a d u a t es c h o o l si ns h a n g h a i ，b e r i n ga n dt h en o r t h e a s tm a d et h i sw o r k , t h e ym o s t l yu s e dt h ea n tc o l o n ya l g o r i t h mt os o l v et s pp r o b l e m i m a g es e g m e n t a t i o nm e t h o di st r a c e dt o1 9 5 0 s i ti st h em o s tb a s a la n di m p o r t a n t d o m a i n n o wi m a g es e g m e n t a t i o nm e t h o di sr e g a r d e da sac o m b i n a t i o no p t i m i z a t i o n p r o b l e m ，a n du s e sas e r i e so fo p t i m i z e ds t r a t e g yt oc o m p l e l et h ei m a g es e g m e n t a t i o n t a s k a tf i r s tt h ee s s a yi n t r o d u c e st h ea n tc o l o n ya l g o r i t h mb a s i cp r i n c i p l e ，t h e r e a l i z a t i o nm e t h o d ，a n a l y z e st h ea n tc o l o n ya l g o r i t h mc h a r a c t e r i s t i c ，i tp r o p o s e sa s e r i e so fi m p r o v e da l g o r i t h m a n di n t r o d u c e sm a n yk i n d so ft h ea p p l i c a t i o ni nt h e o p t i m i z e dp r o b l e m t h e ni te l a b o r a t e st h ei m a g es e g m e n t a t i o np r i n c i p l ea n dt h e c l a s s i f i c a t i o n ，a n di n t r o d u c e ss o m ec o n v e n t i o n a ls e g m e n t a t i o nm e t h o d s a c c o r d i n gt ot h ec h a r a c t e r i s t i co fa n tc o l o n ya l g o r i t h ma n di m a g es e g m e n t a t i o n ， c o m b i n e st h ea n tc o l o n ya l g o r i t h ma n di m a g es e g m e n t a t i o n s e g m e n t a t i o np r o b l e mi s r e g a r d e d a sac 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 ，a n tc o l o n ya l g o r i t h mi sa l l l l o p t i m i z e dm e t h o d ，s ot h ea n tc o l o n ya l g o r i t h mi su s e di n t oi m a g es e g m e n t a t i o ni s f e a s i b l e f i n a l l y , t h ee s s a ym a k e st h es u m m a r ya n dt h ee x p e c t a t i o n t h i se s s a yu s e st h eo p t i m i z a t i o no fa n tc o l o n ya l g o r i t h mt of i n dt h eo p t i m a l t h r e s h o l d ，t h e na c c o m p l i s h e st h ei m a g es e g m e n t a t i o n k e yw o r d s ：a n tc o l o n ya l g o r i t h m ，i m a g es e g m e n t a t i o n ，c o m b i n a t i o no p t i m i z a t i o n l i i 此页若属实请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工人学或其它教育机构的学位或证书而使 用过的材料。与我同 ：作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：矗至亟日期罂堕鲤挣 关于论文使用授权的说明 本人完全了解武汉理：【：大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅： 学校可以公布论文的全部内容，可以采用影日1 、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) m 引隧衿超量竭廿州嘴以：扫谗垒川射一巡! l 注：请将此声明装订在论文的目录前。 武汉理工大学硕十学位论文 1 1 蚁群算法 第1 章概论 1 1 1 蚁群算法的历史和科学意义 2 0 世纪5 0 年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出 了许多用以解决复杂优化问题的新方法。如遗传算法1 1 “、进化规划、禁忌搜索 算法等。2 0 世纪9 0 年代初，意大利学者m d o r i g o 等人受蚂蚁在觅食过程中可 以找出从巢穴到食物源的最短路径的启发，提出了蚁群算法( a n tc o l o n y a l g o r i t h m ) 1 6 】。在管理科学、计算机科学和工程技术等许多领域中，存在着大量 组合优化问题，其中许多问题是n p 完全问题，对于这类问题，至今尚无很好的 解决办法，人们先后使用了禁忌搜索算法、模拟退火算法、遗传算法、人工神 经网络等启发式搜索算法。这些新的智能算法迅速发展，无论是理论研究还是 应用研究都空前活跃，而后一种新的模拟进化算法蚁群算法也逐渐发展起 来，并应用该算法求解t s p 问题1 7 1 、分配问题1 8 l 、i o b 。s h o p 调度问题i 叼取得了较 好的结果，受其影响，蚁群系统模型逐渐引起了其他研究者的注意，在图形着 色问题峨网络路由问题f l o 1 翻、车辆路由问题【1 5 1 、有序排列问题( s o p ) 1 1 6 1 、 频率分配问题上有了一定的应用，这些初步研究和应用已显示出蚁群算法在求 解复杂优化问题( 特别是离散优化问题) 方面的一些优越性。蚁群算法不仅能 够智能搜索、全局优化，而且具有稳健性( 鲁棒性) 、正反馈、分靠式计算、易与 其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算使该法 易于并行实现，个体之间不断进行信息交流和传递，有利于发现较好解，不容易 陷入局部最优；该方法易与多种启发式算法结合，可改善算法的性能；出于鲁棒 性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。因此，蚁群 算法为诸多领域解决复杂优化问题提供了存力的工具。这一切证明了它是一种 很有发展胁景的方法。 1 1 2 蚁群算法国内外研究概况 蚁群算法是种新生算法，具有很强的通用性和鲁棒性。目前蚁群算法的研 武汉理t 大学硕士学位论文 究学者主要集中在比利时、意大利、德国等国家，美国和日本在近几年也开始了 对蚁群算法的研究。国内的研究始于1 9 9 8 年末，主要在上海、北京、东北少数几 个学校和研究所开展了此项工作，主要围绕t s p 及相关问题的实验仿真。 蚁群算法已成功地在通讯、交通及人工智能等领域中应用。最突出的是求 解n p 困难的组合优化问题。d 州窖。等最初提出蚁群算法时，利用t s p 问题与蚁 群觅食的相似性，运用了正反馈原理和分布式算法，通过模仿蚂蚁的行为解决了 t s p 这个具有典型代表的组合优化问题。随后，他们又相继解决了二次指派问题 ( 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 ) 1 7 以8 1 、车间调度问题( j o bs h o p s c h e d u l i n g , j s p ) 1 9 】等，并做了大量的实验研究。结果表明，该算法具有明显的优越 性。1 9 9 7 年c o s t a 等又提出了求解指派类问题的蚁群算法一般模型，并用它来解 决了图形着色i b i s ( g r a p hc o l o r i n g ) 1 1 9 1 。近两年来，d o r i g o 以及其它研究者还将蚁 群算法用于解决网络路由问题( n e t w o r k i n gr o u t i n g ) l ”。”、车辆路由问题( v e h i c l e r o u t i n g ) 1 3 - 1 5 、机器安排问题( m a c h i n es c h e d u l i n g ) 、频率分配问题( f r e q u e n c y a s s i g n m e n t ) 1 2 8 】等。尤其是最近瑞士洛桑大学的k e l l e r 等将蚁群算法的程序编入 微型机器人中，众多微型机器人便可像蚂蚁样协同工作，去完成复杂任务【捌。这 项成果最近被国际知名刊物 n a t u r e ) 报道后，在国际上引起了强烈反响，以至于 在很多领域中掀起了研究热潮。另外，就在此前一个多月，n a t u r e 杂志还登载了美 国科学家b o n a b e a u 和蚁群算法发明者d o r i g o 的有关蚁群算法的综述文章。由此 可看出人们对这一崭新算法的宠爱程度，以上这些也充分显示出该算法的广阔应 用前景。 虽然蚁群算法有许多优点，但是，这种算法也存在一些缺陷，如：与其它方法相 比，该算法一般需要较长的搜索时间，蚁群算法的复杂度可以反映这一点；而且该 方法容易出现停滞现象( s t a g n a t i o nb e h a v i o u r ) ，即搜索进行到一定程度后，所有个 体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解对 于这两个问题，已经弓i 起了许多研究者的注意，并提出了若干改善方法如m d o r i g o 提出的a n t q s y s t e m 2 0 i ，t h o m a s 等人提出的m a x m i na n ts y s t e m 2 1 以5 1 ，基 于排序的蚂蚁系统( 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 r a n k ) 1 2 。”j 。蚁群算法 的研究刚刚开始，远未象g a 、s a 等算法那样形成系统的分析方法和坚实的数学 基础，有许多问题有待进一步研究。国内只是在1 9 9 8 年末开始才有少量公开报 道和研究成果，而且大多数局限于旅行商f r s p , t r a v e l i n g s a l e s m a np r o b l e m ) l 问题。 尽管该算法的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶 段，但从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑有 十分光明的前景，更多深入细致的【作有待进步腱丌。 武汉理工大学硕十学 i ) ：论文 1 2 图象分割 1 2 1 图象分割的科学意义和历史 在对图象的研究和应用中，人们往往仅对图象中的某些部分感兴趣。这些 部分常称为目标或前景( 其他部分称为背景) 它们一般对应图象中特定的、具 有独特性质的区域：为了辨识和分析目标，需要将它们分离提取出来在此基 础上才有可能对目标进一步利用。图象分割就是指把图象分成各具特性的区域 并提取出感兴趣目标的技术和过程。这里特性可以是象素的灰度、颜色、纹理 等，预先定义的目标可以对应单个区域，也可以对应多个区域。 图象分割( i m a g e ，s e g m e n t a t i o n ) 是一种重要的图象技术，它不仅得到人们，“ 泛的重视和研究，也在实际中得到大量的应用。图象分割在不同领域中有时也 用其他名称，如目标轮廓( o b j e c td e l i n e a t i o n ) 技术，阈值化( t h r e s h o l d i n g ) 技术， 图象区分或求差( i m a g ed i s c r i m i n a t i o n ) 技术，目标检测( t a r g e td e t e c t i o n ) 技术， 目标识别( t a r g e tr e c o g n i t i o n ) 技术，目标跟踪( t a r g e t t r a c k i n g ) 技术等，这些技术本 身或核心实际上也是图象分割技术口”。 图像分割是图像处理中最为基础和重要的领域之一，也是低级计算机视觉 中最基本最重要的研究内容，是成功进行图像分析、理解与描述的关键技术，因 为图像分割结果的质量直接影响以后进行的分析、识别和解释的质量。图像分 割方法的研究始于上世纪5 0 年代，研究已有几十年的历史，借助各种理论至今 已提出了上千种各种类型的分割算法i 嚣j ，而且这方面的研究仍在积极进行。 图象分割在实际中已得到广泛的应用，例如在工业自动化，在线产品检验， 生产过程控制，文档图象处理，遥感和生物医学图象分析，保安监视，以及军 搴，体育，农业工程等方面。概括来说在各种图象应用中，只要需对图象目 标进行提取、测量等都离不开图象分割。近年来，图象分割在对图象的编码中 也起到越来越重要的作用，例如国际标准m p e g - - i v 中的模型基目标基编码 等都需要基于分割的结果。 从1 9 9 6 年开始，由中国图象图形学会主办出版的中国图象图形学报_ l ： 每年都刊登国内发表图象技术文献较多，水平较高的1 5 种重要期刊上所发表的 舸一年有关图象工程文献统计分类的综述文章已形成系列。该系列综述将图 象技术方面的文献分1 8 个小类( 分属五大类) 其中有关边缘检测和图象分割的 是一个小类，另外与图象分割密切相关的目标识别，分类和提取是蜀一个小类。 武汉理t 大学硕士学位论文 综述的统计分析表明( 见表卜1 ) 这两小类技术是当前图象技术研究应用的热点 和焦点，研究文献数量比其他各小类的均值高一倍，在图象工程众多的研究内 容中占据了最重要的部分。由于期刊的选择考了多方面的因素有相当的代表 性，所咀这些统计数据比较可靠地反映了2 0 世纪最后5 年图象分割在图象工程 中的地位和影响i 拥。 表1 一l 统计分析表 分类年度 1 9 9 51 9 9 61 9 9 71 9 9 81 9 9 9 小计 边缘检测，图象分割 2 52 73 l4 26 21 8 7 目标识别，分类和提取 1 01 82 42 83 2l 1 2 文献总数 1 4 72 1 22 8 03 0 63 3 81 3 3 3 两类占总数的百分比 2 3 8 1 2 1 2 3 1 9 6 4 2 2 8 8 2 4 2 3 p 94 冀 1 2 2 图象分割的国内外研究概况 国内外各种文献中己提出了百余种图像分割的方法，大致可以分成以下六 大类：1 ) 基于门限化的方法；2 ) 基于边缘检测的方法；3 ) 基于象素分类的方法； 4 ) 基于人工神经网络的方法；5 ) 基于模糊集理论的方法；6 ) 基于多分辨率分析 的方法。 闺值分割就是简单地用一个或几个阙值将图像的灰度直方图分成几个类， 认为图像中灰度值在同一个灰度类内的像素属于同一个物体。近年来的方法有 j c y e n 等人提出的用最大相关性原则选择阈值的方法，这种方法其实只是用他 们定义的一个最大相关性原则取代了一般用的最大熵原则。a p i k a x 等人提出的 基于图像拓扑稳定状态的方法，这种方法认为实际物体是能在一个较宽的阈值 范围内稳定存在的，考虑将阀值设黄在某个灰度时所得到的具有某种连通性如 四连通的一定大小的物体的个数，考察随着闽值的改变，这个个数的稳定状态， 从而决定阚值的方法。n p a p a m a r k o s 等人提出的先找出灰度直方图的峰值点， 后用有理多项式来拟合灰度直方图两个峰闻的区域，然后求出相应的有理多项 式的极小值，从而决定阙值的方向。l k h u a n g 等人提出的通过极小化图像的 某种模糊测度来决定灰度阈值的方法，他们提到的模糊测度包括熵和所谓的 y a g e r 测度。其它方法包括g - c o m e l o p 等人提出的通过对灰度共生矩阵的分析来 决定闽值的方法，u j 等人提出的通过对图像的二维真方图作f i s h e r 线性映射来 决定闽值的方法等。基于最大熵原则选择阚值是最重要的闽值选择方法之， 近年来对最大熵原则的研究包括e s a h o o 等人提出了用r e n y i 熵代管常规熵的最 大嫡原则，a d b r i n k 把这种方法扩展到：维灰度直方图。h d c h e n g 等人将 4 武汉理l 人学硕十学位论文 模糊调度函数的概念引入最大熵原则，提出了模糊c 一分类最大熵原则。 边缘检测方法通常分成两大类，即串行或顺序的边缘检测技术，和并行的检 测技术。前属于集合a 的程度。 图象分割可叙述成一个约束满足问题( c o n s t r a i n ts a t i s f a c t i o np r o b l e m c s p ) 2 9 l ，并用约束满足神经网络( c o n s t r a i n ts a t i s f a c t i o nn e u r a ln e t w o r k ，c s n n ) 末 解决。约束满足神经网络包括一组目标一组标号，一组约束关系和一组描述 不同目标间邻域关系的拓扑约束。约束满足神经网络可看作一组内部连通神经 元，其结构可表达约束满足问题中的约束。这种分割方法对断层扫描( c t ) 图象 和核磁共振图象( m r i ) 效果较好。在文档类图象的多目标分割中，基于人类视觉 感知模型中相关神经激活理论而设计的振予神经网络( o s c i l l a t o x ynn ) 1 3 0 1 得到了 应用，这种方法具有对知觉( 包括神经生理和心理物理学) 研究的理论基础并有 生理实验基础1 3 1 i 。另外在神经网络的设计中将马尔算子的特征结合进去，也能 提高对边缘检测的整体性能【3 “。 在模式识别问题中，模糊集合可以设定在特征级，表示输入特征对于某些特 定属性集合的隶属度：也可以设定在分类级，表示模式分类对于某些特定类型集 合的隶属度。模糊集台可以和模式识别过程中的不同阶段相结合。比如：模糊 门限值技术、模糊聚类技术、模糊边缘捡漠i 技术。 在图像分割方面，多分辨分析首先被用于具有双蜂直方图的图像分割。把被 分割的原始图像作为最高分辨的图像，然后，按着某种准则，将相邻排列的若f 个( 一般为4 个) 象素划为一组连接成一个交接点，于是便形成了一幅缩小的新图 像或一个新的分层。对于这一层图像再使用同样办法进一步的归并，直到顶层为 一个元素( 根结点) 为止。这就是所谓的金字塔形的结构。利用这种金字塔结构 形成的各层图像，就空间分辨率而言，是越向上层越低，但由于平滑作用的结果， 区域或类的分辨率却越向上层越商。于是在金字塔的某一上层( 辟如说仅有6 4 6 4 个象索) ，实行某种图像分割算法，从丽锝到一种分类分割结果，然后，再把 这种分割结果向下层传递，便可以得到高空间分辨率的分割结果。各种不同的多 分辨图像分割方法的区别，仅仅是在上层所进行的分割。 近年来对通用分割方法的研究倾向于将分割看作一个组合优化问题，并采 用一系列优化策略完成图像分割任务。主要思路是在分割定义的约束条件之外， 根据具体任务再定义一个优化目标函数，所求分割的解就是该目标函数在约束 条件下的全局最优解。以组合优化的观点处理分割问题，主要是利用一个目标 函数综合表示分割的各种要求和约束，将分割变为目标函数的优化求解。 人工蚁群算法就是一种优化方法，因此，将人工蚁群算法引入到图像分割 武汉理_ _ i = 大学硕士学位论文 处理中完全可行。人工蚁群算法作为一种通用型随机优化方法，通过其内在的 搜索机制己在一系列困难的组合优化问题求解中取得成效，该方法为复杂系统 的优化问题提供了新的具有竞争力的求解算法。尽管一些思想尚处于萌芽状态， 但该方法正受到越来越多人的注意和研究，应用范围也开始遍及许多领域。 武汉理二大学硕士学位论文 第2 章蚁群算法的基本原理 2 。1 蚂蚁的群体行为及信息系统 蚂蚁是最古老的社会昆虫之一，它的个体结构和行为虽简单，但由这些简 单个体构成的蚂蚁群体，却表现出高度结构化的社会组织。蚂蚁王国俨然是一个 小小“社会”。这里，有专司产卵的后蚁；有为数众多的从事觅食打猎、兴建屋 穴、抚育后代的工蚁；有负责守卫门户、对敌作战的兵蚁等等。 蚂蚁是社会性昆虫，组成社会的三要素之一就是社会成员除有组织、有分：r 之外，还有相互的通讯和信息传递。研究表明，蚁群有着奇妙的信息系统。其中 包括视觉信号、声音通讯和更为独特的无声语言，即包括化学物质不同的组合、 触角信号和身体动作在内的多个征集系统，来策动其它个体。蚂蚁特有的控制自 身环境的能力，是在商级形式的社会性行为及不断进化过程中获得的m 州l 。 觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究，发现蚂 蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环 境变化适应性地搜索新的路径，产生新的选择。虽然单个蚂蚁的行为极其简单， 但由大量的蚂蚁个体组成蚂蚁群体却表现出极其复杂的行为，能够完成复杂的 任务。生物学家和仿生学家研究发现，蚂蚁在觅食走过的路径上释放一种蚂蚁特 有的分泌物信息激素( p h e r o m o n e ) 。蚂蚁个体之间正是通过这种信息激素进 行信息传递，从而能相互协作，完成复杂任务。在一定范围内蚂蚁能够察觉到这 种信息激素并指导它的行为，当一些路径通过的蚂蚁越多，则留下的信息激素 轨迹( t r a i l ) 也就越多，招致后来更多的蚂蚁选择该路径的概率也越高，于是越 发增加了该路径的信息素强度。这种选择过程称之为蚂蚁的自催化过程，形成一 种诈反馈机制，可理解为增强犁学习系统，蚂蚁最终可以发现最短路径。 蚁群算法吸收了蚂蚁群体行为的典型特征：一是能察觉小范围区域内状况， 并判断出是否有食物或其他同类的信息素轨迹；二是能释放自己的信息素：j 是所遗留的信息素数量会随时间而逐步减少。 较为简单的主体的聚集相互作用，必然会涌现出复杂的大尺度行为。遗传算 法之父霍兰德称这种现象为突现聚集特性1 5 3 j 。生物群体的复杂适应性行为就是 从组成群体的适应性个体行为中涌现出来的一种全局性质。 模拟蚁群突现聚集行为的蚁群算法，是作为一类新的计算模式引入的，并 被称为蚂蚁系统，该系统基于以下基本假设： 武汉理r 人学硕士学位论文 1 、蚂蚁之间通过环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反 应，也仅对其周围的局部环境产生影响。蚂蚁之| 日j 通过激素相互影响，并趋向于 选择化学激素浓度高的方向。 2 1 蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行 为实际上是其基因的适应性表现。也就是说，蚂蚁是反应型适应性主体。 3 ) 在个体水平上，每只蚂蚁仅根据环境做出独立选择。在群体水平上，单只 蚂蚁的行为是随机的，但蚁群通过自组织过程形成高度有序的群体行为。 以上基本假设构成了基本蚁群算法。基于以上基本假设的蚂蚁系统，实际上 是一类多主体系统【5 4 1 ，如图2 1 所示。在人工蚂蚁系统中，人工蚁是一类反应型 主体，它包括一个感知器，一个效应器和一个内部执行系统。感知器收集环境信 息，效应器则改变环境。反应型主体的执行系统是一组条件动作规则，将主体的 感知器与效应器连接起来。 蚂蚁系统的主体一环境模型 图2 1 作为人工蚂蚁系统模型的多主体系统 蚂蚁算法通过候选解组织群体的进化过程来寻求最优解，这一过程包括适 应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身的结构； 在协作阶段各候选解间通过信息交流，以便产生性能更好的解。在蚁群算法中， 一个有限规模的人工蚁群体，通过相互协作搜索用于解决优化问题的较优解。每 只蚂蚁根据问题依赖的准则，从被选的初始状态出发建立一个可行解或是解的 一个组成部分。在建立蚂蚁自己的解决方案中，每只蚂蚁都搜集关j ：问题拓征和 其自身行为的信息，并且使用这些信息来修改问题的表现形式，正如其它蚂蚁 所看到的那样。蚂蚁既能共同的行动又能独立的工作，显示出了一种相互协作的 武汉理工大学硕士学位论文 行为，它们之间不使用直接通讯，而使用信息激素指导着蚂蚁问的信息交换。蚂 蚁使用一种结构上的贪婪启发式搜索可行解。根据问题的约束条件列出了一个 解，作为经过问题状态的最小代价( 最短路径) 。每只蚂蚁都能够找出一个解，但 町能是较差解。蚁群中的个体同时建立了很多不同的解决方案，找出高质量的解 是群体中的所有个体之间全局性的相互协作的结果。 2 2 蚁群算法的原理 人工蚁群算法是受到对真实的蚁群行为的研究的启发而提出的我们下面我 们引用m d o r i g o 所举的例子1 3 5 娟j 来具体说明蚁群系统的原理如图2 2 所示， 设a 是巢穴，e 是食物源，h c 为一障隘物由于障随物存在，蚂蚁只能经由h 或 c 由a 到达e ，或由e 到达a 。，其中b 到h 、d 到h 的距离为1 ，b 到c 和d 到c 的距离为0 5 。下面分别考虑在时刻t = o ，1 ，2 时蚁群的运动情况。如图 2 2 b ，在时刻t = o ，设有3 0 只蚂蚁从a 运动到b 。此时路径b h 、b c 上没有外激 素( 蚂蚁留下的信息量) ，故蚂蚁将以相同的概率向b c 、b h 运动，于是各有1 5 只 蚂蚁分别选择路径b h 和b c 。在真实蚁群中，岁 激素的数量会随时间的流逝而蒸 发掉一部分，为说明方便，此处假设：所有蚂蚁运动的速度相等：外激素蒸发 量与时间成正比例，即路径上外激素的剩余量与路径的长度成反比：蚂蚁选路 的概率与所选路上外激素的数量成f 比。因为路b h d 的长度是路径b c d 的2 倍，当b 点的蚂蚁到达d 点后，路径b c d 上的外激素是b h d 上的2 倍。如图2 - 2 c ， 在时刻t = 1 有3 0 只蚂蚁从e 到达d 。因为路径d c 上的外激素量是d h 上的2 倍，根据蚂蚁选路特点，将会有2 0 只蚂蚁选择d c ，丽只有1 0 只蚂蚁选择d h 。以 此类推，当t = 2 ，3 ，4 时，将会有更多的蚂蚁选择路径b c d 。经过较长时间运动 后，蚁群最终会沿着最优路径a b c d e 运动。从而找到由蚁巢到食物源的最短路 径 武汉理：e 火学硕十学位论文 i h 茏 i 回i 茏 i t 3 0 a n t s 圜一9 帕娃售津鹰瑚图 b l 在自然界中，蚁群的这种寻找路径的过程表现为一种讵反馈的过程，与人工 蚁群的寻优算法极为一致。如我们把只具备了简单功能的工作单元视为“蚂蚁”， 那么上述寻找路径的过程可以用于解释人工蚁群的寻优过程。由以上分析可知， 人工蚁群和自然界蚁群的相似之处在于，两者优先选择的都是含“外激素”浓度 较大的路径：这在两种情况下，较短的路径上都能聚集比较多的外激素：两者的 工作单元( 蚂蚁) 都是通过在其所经过的路径上留下一定信息的方法进行间接的 信息传递。而人工蚁群和自然界蚁群的区别在于，人工蚁群具有一定的记忆能 力。它能够记忆已经访问过的节点：另外，人工蚁群在选择下一条路径的时候并 不是完全盲目的，而是按一定的算法规律有意识地寻找最短路径( 如在t s p 问题 中，可以预先知道下一个目标的距离) 。 2 3 蚁群系统模型 现在用t s p 问题的分析，来说明基本蚁群算法a s ( a n ts y s t e m ) 是如何实现的 【3 7 1 。对于其它问题，可以对此模型稍作修改便可应用i 捌。为模拟实际蚂蚁的行为， 首先引进如下记号：设m 是蚁群中蚂蚁的数量，d i ( i ，j = ：l ，2 ，n ) 表示城市i 和 城市j 之间的距离，( ) 表示t 时刻位于城市i 的蚂蚁数，m - 罗b ，( f ) 。z 。( t ) 表示 舒 t 时刻在日连线上残留的信息量初始时刻，各条路径上信息量相等，r 。，( 0 ) = c ( 为 常数) 。蚂蚁k ( k - - 1 2 ，m ) 在运动过程中，根据备条路径上的信息量决定转移方 向，p ：o ) 表示在t 时刻蚂蚁k 由位置i 转移到位置j 的概率，每个人t 蚂蚁的行为 l o 卜少 e篡7i三 团甏 武汉理工大学硕士学位论文 符合下列规律： 1 ) 根据路径上的激素浓度，以相应的概率来选取下一步路径： 2 ) 不再选取自己本次循环已经走过的路径为下一步路径。用一个数据结构 ( t a b u l i s t ) 【3 8 l 来控制这一一点： 3 ) 当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更 新走过的路径上的信息素浓度。 t 时刻蚂蚁k 由位置i 转移到位置i 的概率： p k ( t ) t型汀j a l lowedkkc ：a l l o w e d ki v i 女o ) r f p ) ，( 2 - 1 ) 其中，a l l o w e d 。t 0 ，1 ，n 一1 ) 一t a b u 。表示蚂蚁k 下一步允许选择的城市与 实际蚁群不同，人工蚁群系统具有记忆功能，t a b u 。( k = l ，2 ，m ) 用以记录蚂蚁 k 当前所走过的城市，集合t a b u 。随着进化过程作动态调整随着时问的推移，以 前留下的信息逐渐消逝，用参数卜p 表示信息消逝程度，经过i 1 个时刻，蚂蚁完 成一次循环，各路径上信息量要根据下式作调整： 勺( 1 ) 。p r i j ( t ) + a 。q ( t ) ( 2 - 2 ) a 巧一篇a 噶( 2 - 3 ) 其中是第k 个蚂蚁在时问t 到t + l 之间，在边( i j ) 上增加的信息素变量。 它的值出以下公式确定： 苟。层如果锹只蚂蚁在洲劂“1 之阈经过边( “) 。， f 0否则 否则其中q 是一个常量，用来表示蚂蚁完成一次完整的路径搜索后，所释放 的信息素总量；l k 是第k 个蚂蚁的路径总花费，它等于第k 个蚂蚁经过的各段路 径上所需的花费c 日的总和。如果蚂蚁的路径总花费越高，那么其在单位路径上 所释放的信息素浓度就越低。很显然，蚂蚁不会在其没有经历过的路径上释放信 息素。a ，卢分别表示蚂蚁在运动过程中所积累的信息及启发式因予在蚂蚁选择 路径中所起的不同作用表示由城市i 转移到城市j 的期望程度，可根据某种启 发式算法具体确定 根据具体算法的不同，r “o ) ，a v 。( t ) ) 及p ；p ) 的表达形式可以不同，要根据具 武汉理j ：大学硕士学位论文 体问题而定。m d o r i g o 曾给出三种不同模型，分别称之为a n t c y c l es y s t e m 、 a n t q u a n t i t ys y s t e m 、a n t d e n s i t ys y s t e m l 4 0 1 。它们的差别在于表达式( 4 ) 的不同。 在a n t q u a n t i t ys y s t e m 模型中： 噶；层若第职蚂蚁在时泣间经过边( ) 5 ) 。1 0 否则 在a n t d e n s i t ys y s t e m 模型中 噶- 侣鬻只蚂警在时楸到“蝴经过扒l ( 2 _ 6 ) 它们的区别在于：后两种模型中，利用的是局部信息，而前者利用的是整体 信息，文献f 3 7 l 中给出了上述3 种方法的比较，结果是a n t c y c l es y s t e m 算法的效果 最好，这是因为它用的是全局信息一彤：而其余两种算法用的是局部信息一 和q 。这种更新方法很好地保证了残留信息不至于无限累积，如果路径没有 被选中，那么上面的残留信息会随时间的推移而逐渐减弱，这使算法能“忘记” 不好的路径，即使路径经常被访问也不至于因为勺的累积，而产生) ) 使期望 值的作用无法体现参数q ，c ，a ，b ，p 可以用实验方法确定其最优组合 武汉理工人学硕士学位论文 2 3 蚁群算法的实现 蚁群算法实现的流程图 图2 - 3a n t - c y c l e 算法框图 在初始化的时候，m 个蚂蚁被放置在不同的城市上，赋予每条边上的信息素浓 度为f i ( 0 ) 。每个蚂蚁的t a b ul i s t 的第一个元素赋值为它所在的城市。当蚂蚁们 完成了一次完整的寻径过程后，计算r ：，并且更新每条边上的信息素浓度。然后 开始新。轮的循环。当循环的次数达到事先定义好的c 时或者所有的蚂蚁都 选择了同一种路径方式时，整个程序终止。 a n t c y c l e 程序的伪代码如下： 1 ) 初始化： s e t i = o ，n c = 0 ，每条边上的( o ) = 0 ，并且a z o = 0 ，放置m 个蚂蚁到n 个 城市上 武汉理j 二大学硕 ：学位论文 2 ) 令s = l ，( s 是t a b u l i s t 的下标) f o r k = l t o md o 把第k 个蚂蚁的初始城市号码放置到t a b u k ( s ) 【 a 3 ) r e p e a tu n t i lt a b u l i s ti sf u l l s e ts = s + l f o r k = lt o i l l _ d o 根据概率只，来选择下一步应该到达的城市，将第k 个蚂蚁移到城市j ，并将j 插入到t a b u k ( s ) q h 4 ) f o r k = lt o m d o 计算第k 个蚂蚁的总路径长度k ，更新找到的最短路径。 f o r k = l t