（计算机应用技术专业论文）蚁群算法及其应用研究——基于旅行商问题和图像分类.pdf

摘要 摘要 蚁群算法是m a r c od o f i g o 等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度 创新性的元启发式搜索算法。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神 经网络算法等之后提出的又一种应用于解决组合优化问题的启发式搜索算法。试验表 明，蚁群算法具有较好的求解能力，但是蚁群算法存在收敛速度慢，容易陷入局部最优 解等不足。本文主要研究如何改进算法模型并应用于相关领域，主要工作包括以下两部 分。 首先，对蚁群算法进行基础理论研究，改进并提出分类蚁群算法( c b a c 0 ) ，将其应 用于t s p 问题。旨在对蚁群算法近年来的研究进展进行总结，归纳算法的成功和存在的 不足，对不足之处进行理论分析并改进，目的在于提高蚁群算法的总体性能。改进后的 模型在智能蚁群的基础上引入随机蚁群以便扩大搜索空间，不同蚁群实行各自不同的搜 索前进策略和信息更新机制，从而避免算法陷入早熟，以获取更大的解空间。并可通过 调节随机蚁群与智能蚁群的比例来控制收敛速度，从而提高算法的运行效率。试验表明， 将其应用于t s p 问题可以获取更好的求解性能。 其次，针对基本蚁群算法分类图像速度慢的缺点，根据蚁群算法的聚类和离散性特 点，改进蚁群算法并应用于图像分类。随机蚂蚁在图像中识别类、构建类别表，并确定 聚类中心、生成相应类的智能蚂蚁，指导智能蚂蚁分类的过程；智能蚂蚁按相应的搜索 前进策略向聚类中心聚集，识别目标。同时所有的蚂蚁在搜索前进过程中对图像进行边 缘提取，以便提高算法对图像边缘分类的准确度。试验表明，相比基本蚁群算法求解图 像分类问题，由于该改进引入初始聚类中心和识别边缘，算法的分类效率和对边缘信息 点分类的准确度得到提高，并实现了图像的自动分类。 关键字：旅行商问题；随机蚁群；智能蚁群；图像分类；类别表 a b s t r a c t a b s t r a c t a n tc o l o n y a l g o r i t h mw a sp r o p o s e df i r s tb yi t a l ys c h o l a rm d o r i g o i ti s a n o t h e r h e u r i s t i cs e a r c ha l g o r i t h ma p p l i e di nc o m b i n a t i o n a lo p t i m i z e dp r o b l e mf o l l o w e db ys i m u l a t e d a n n e a l i n ga l g o r i t h m ，h e r e d i t ya l g o r i t h m ，t a b o os e a r c ha l g o r i t h m ，a n na l g o r i t h ma n ds oo n t h ee x p e r i m e n ti n d i c a t e st h ea l g o r i t h mh a sg o o dc a p a b i l i t yo ff i n d i n gt h es o l u t i o n b u ta n t c o l o n ya l g o r i t h mh a ss o m ed i s a d v a n t a g e sa sd i s c o n v e r g e n c e ，f i n d i n gt h el o c a ls o l u t i o na n d s oo n t h i sp a p e rr e s e a r c ht h ea l g o r i t h mm o d e la n dt h ea p p l y i n ga r e a s t h ew o r ki n c l u d e sa s f o l l o w f i r s t l y ，i ts u mu pt h ea p p l y i n ga r e a so fa n tc o l o n ya l g o r i t h ma n di t sd i s a d v a n t a g e s ， d e e p l ya n a l y z i n gt h ed is a d v a n t a g ei no r d e rt oi m p r o v et o t a lc a p a b i l i t yo fa n tc o l o n ya l g o r i t h m i ti m p r o v e st h ea n tc o l o n yt h r o u g hb yt h er e a l i z i n gs t o c h a s t i ca n tc o l o n yf o re x t e n tz o n e ，a n d i m p l e m e n t st h er e c e n ti n f o r m a t i o nr e n e w a la n dt h es e a r c hs t r a t e g yi no r d e rt oe n h a n c et h e s o l u t i o np e r f o r m a n c e t h en e wa l g o r i t h mc a na d j u s tt h ep r o p o r t i o nb e t w e e nt h es t o c h a s t i ca n t c o l o n ya n dt h ei n t e l l i g e n ta n tc o l o n yi no r d e rt oc o n t r o l s t h ec o n v e r g e n c er a t e t h e e x p e r i m e n ti n d i c a t e st h a ti m p r o v ec a na v o i dt h ea l g o r i t h mc o n v e r g i n gq u i c k l ya n de n h a n c e t h ec a p a b i l i t yo ff i n d i n gt h es o l u t i o n s e c o n d l y ，t oi m p r o v ec a p a b i l i t yo fa u t oc l a s s i f i c a t i o na n dt h es p e e do fa l g o r i t h m ，t h e a n tc o l o n ya l g o r i t h mb a s e do nc l a s s i f i c a t i o nw a sp r o p o s e d t h es t o c h a s t i ca n t sc o n s t r u c t c l a s s i f i c a t i o nt a b l e ，e s t a b l i s hi n t e l l e c t u a la n t sa n da s c e r t a i nt h ec e n t e ro fc l a s s i f i c a t i o n t h e i n t e l l e c t u a la n tc l a s s i f yt h ei m a g e m e a n w h i l et h ea l la n t sb e g i nt oe x t r a c tt h ee d g eo fi m a g e c o m p a r i n gt h eb a s i ca n tc o l o n ya l g o r i t h m ，t h ei m p r o v ec a na d v a n c et h ec a p a b i l i t yo ff i n d i n g t h es o l u t i o na n dt h ep r e c i s i o no fa u t oc l a s s i f i c a t i o n k e y w o r d ：t r a v e l i n gs a l e s m a np r o b l e m ；s t o c h a s t i ca n tc o l o n y ；i n t e l l e c t i v ea n tc o l o n y ；i m a g e c l a s s i f i c a t i o n ；c a t e g o r yt a b l e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签 名：蒸丝扬 日 期：2 21 丝塑兰! 旦 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名：荚镏杨 导师签名： 第一章概述 第一章概述 1 1 蚁群算法 1 1 1 蚁群算法的历史及学科意义 2 0 世纪5 0 年代中期创建了仿生学，人们从生物进化的机理中受到启发，提出了许多 用于解决复杂优化问题的新方法。如遗传算法( g a ) 、神经网络( n n ) 倥3 、粒子群算法 ( p s o ) 剐等。2 0 世纪9 0 年代初期，意大利学者m d o r i g o 等人受蚂蚁在觅食过程中可以找 到从巢穴到食源最短路径的启发，提出了蚁群算法( a n tc o l o n ya l g o r i t h m ) r 4 - 7 。在管理 学、计算机科学和工程技术等许多领域中，存在着大量的组合优化问题，其中许多问题 是n p 完全问题，对于这类问题，至今尚无很好的解决办法。人们先后使用了禁忌搜索算 法、模拟退火算法、遗传算法、人工神经网络等启发式搜索算法来解决这些问题。这些 新的智能算法迅速发展，在理论研究和具体应用上都取到了空前的成果。在此之后，一 种新的模拟进化算法一蚁群算法也逐渐发展起来，并应用于求解t s p 问题哺1 、分配问题 驯、路径规划问题1 ，取到了较好的效果。受其影响，蚁群系统模型逐渐引起了其他学 者的注意，并在网络路由问题m 1 、下料问题“扪、图像分割n 3 叫制、边缘提取n 5 - 1 6 1 、图像分 类利、分类规则发现n 町、模式识别口钔等问题上获得了应用，这些初步研究与应用已经显 示出蚁群算法在求解复杂问题( 特别是离散问题) 方面的可行性。蚁群算法不仅具有智 能搜索、全局优化、而且具有稳定性、正反馈、分布式计算、易于其他算法结合等特点。 利用正反馈，可以加速算法的进化过程；分布式使得算法易于并行实现，个体之间不断 进行信息交流和传递，有利于发现较好解，避免陷入局部最有解；该方法易与多种启发 式方法结合使用，以便提高算法的求解性能；由于鲁棒性强，对算法进行修改后可应用 于其他问题；因此说蚁群算法可广泛应用于多个领域，具有广泛的发展前途险0 2 。 1 1 2 蚁群算法的国内外研究概况 ( 1 ) 模型改进 人们针对不同的具体问题提出了许多不同类型的蚁群算法改进模型，但这些蚁群 算法模型通用性不强，同时基本蚁群算法模型也不能直接应用于解决具体的优化问题。 另外，自然界中的真实蚁群还有许多其他智能行为，因此开发设计不同的蚁群算法模 型是一条新的发展思路。基于此，可从以下几个方面对其模型进行改进。 1 ) 设计一种通用的蚁群算法通用性模型乜2 2 刚。首次提出蚁群算法是用于解决t s p 问 题，后来的一些蚁群算法改进基本是针对某一类问题而设计的，而现实中的问题千差 万别，并不是每一个问题都能够很容易化归到这样一个拥有高度社会性的蚁群智能模 型中，而且系统高层次的行为是通过低层次昆虫之间简单行为的交互涌现而产生的。在 算法的通用性研究方面，应进一步探索蚁群算法模型的高层次统一机制，并结合复杂 性系统展开研究，提出更通用的蚁群算法模型。蚁群算法的正反馈机制就是一个很好的 通用性模型。 江南大学硕士学位论文 2 ) 研究自然界真实蚁群行为，提出更加智能化的蚁群混合行为模型啪3 。从深度上说， 虽然蚁群算法是基于蚂蚁觅食行为而发展起来的，但是自然界中的真实蚂蚁觅食机理 并不那么简单，仍有许多借鉴之处，今后应继续挖掘蚂蚁觅食中一些未知的行为，得 到新的蚁群算法模型：从广度上说，蚂蚁等昆虫除了寻找食物之外，还有着任务分配、 构造墓地、建造巢穴、繁衍后代、清除垃圾、保卫领地等多种复杂的社会行为，将蚁群 的这些行为与其觅食行为进行融合、统一，提出更加智能化的蚁群算法混合行为模型， 还有待于从昆虫学、社会学、仿生学、信息学等综合角度对其进行深入研究。 3 ) 对蚁群算法的模型和相关的参数设置进行研究口们。蚁群算法作为一种新型的智能 算法，其相关的模型尚缺乏严格的数学基础；尤其是蚁群算法模型中，参数较多，且相 关参数的设置在目前的研究中主要是依靠大量的试验获取，参数设置的主观性较大，缺 乏严格的理论说明，因此如何建立蚁群算法参数之间的数学模型，并为各参数的设置提 供准确的理论依据是一个重要的研究课题。 ( 2 ) 理论分析 蚁群算法是一种概率搜索算法，相比确定性算法，从数学角度对其正确性与可靠性 进行证明较困难。自w j g u t j a h r 最先从有向图论的角度对一种改进蚁群算法的收敛性进 行理论证明至今口，人们在其收敛性研究方面己经取得了相当丰富的理论研究成果，但 是这些理论成果都对蚁群算法模型进行相应限制的情况下获得的，从而缩小了其应用范 围。例如w j g u t j a h r 给出了基于图的蚁群算法的收敛性证明，其理论基础是把最优路径 上的信息素强度描述为离散时间的非齐次马尔可夫随机过程，据此进行证明。其局限性 在于，为了符合这一描述，对算法作了较多的条件约束，例如算法中的优化路径仅有一 条，仅在这条最优路径上进行全局信息素更新，不支持局部更新，所有蚂蚁都从唯一的 起点出发。t s t l a e z l e 矛l l m d o r i g o 也对蚁群算法的收敛性进行了理论证明b 副，但是仅依据 信息素进行分析，分析条件与实际情况也有一些差距。这些文献的共同特点是主要考虑 了信息素的影响，且只考虑了局部或全局信息素更新中的一种情况，关于算法的相关参 数( 如启发信息等) 对算法的影响没有进行分析，实际指导意义不强。朱庆保对蚁群算法 模型的收敛性进行了证明，同时分析了模型中各参数对模型收敛性的影响b 副，赵霞对 m a x m i n 模型的收敛性给出了证明婚4 1 等等。 这些证明并没有将蚁群算法的理论分析统一到一个共同的框架内。此外，在蚁群算 法的理论研究方面还存在许多问题需要进一步解决，比如初始化参数选择问题、信息素 分配问题、收敛速度问题等，这些均带有经验性和直觉性，至今没有经过严格的数学论 证；同时，连续域蚁群算法的收敛性证明仍存在许多研究空白。蚁群算法的收敛性证明 和理论分析仍然是一个非常具有挑战性的研究方向。 ( 3 ) 并行实现 蚁群算法本身隐含着一定的并行性，单只蚂蚁在一次循环中独立于其他蚂蚁。因此， 本质上蚁群算法应以分布式的协同优化计算方式为特征，而在串行计算机上对蚁群算 法的进行模拟并不能真正体现蚁群算法的本质特征，进一步的研究工作应开展蚁群算 法的并行机实现。并行机实现中往往需要在计算与通信之间寻求一种平衡，蚁群算法的 2 第一章概述 并行机实现主要集中在最优的并行化。所谓最优的并行化是指使用适量的处理机以最小 的代价使得并行化蚁群算法性能达到当前情况下的最好，或者说当并行化蚁群算法性 能不变时，应竭力减少计算和通信的成本。研究蚁群算法并行机实现问题，需要解决对 蚁群算法并行化过程中并行计算模型的选择以及对蚁群算法的分解、映射方法的改进等 问题，还需要解决蚁群算法并行化过程中粒度处理标准的问题，使并行处理过程具有 较好的扩展性，并具有良好的负载均衡性。主要存在以下几个问题： 1 ) 在不考虑处理机之间差异、选择同步更新方法的情况下，如何确定问题规模与加 速比之间的关系：在处理机增多的情况下，如何选择处理机的最佳数目以使计算时间 减少。 2 ) 在不考虑处理机之间差异、选择同步更新方法的情况下，当处理机一定时，如何 选择最优的蚁群规模i n 以使效用函数的值最大。 3 ) 在不考虑处理机之间差异、选择异步更新方法的情况下，当问题规模一定时，如 何分配处理机数目和各处理机上的蚁群规模使效用函数值最大。 4 ) 当并行机实现时，局部迭代若干次后需要交换信息。局部迭代次数的增大也会使 得蚁群算法早熟的概率增大，而局部迭代次数减小则会增加通信时间，因此还要努力 解决如何有效避免蚁群算法的过早停滞和减少通信开销之间的平衡问题。 ( 4 ) 应用领域 从目前公开发表的蚁群算法相关学术论文来看，大约五分之三的论文是蚁群算法在 不同优化领域中的应用研究成果。虽然蚁群算法的应用范围已经几乎涉及到各个优化领 域，但还存在很多不足，在应用上着重从以下两方面对其进行研究 1 ) 纵向而言，蚁群算法的应用深度还不够。从公开发表的研究成果来看，大部分应 用还仅仅停留在仿真阶段，而且所做的研究大都是在对实际问题实验条件或约束条件 进行简化的前提下进行的。尤其在动态优化闯题、随机优化问题、多目标优化问题等方 面研究还需要进一步深化： 2 ) 横向而言，蚁群算法的应用领域还需要进一步拓宽。不同的应用领域都有许多不 同的实际问题，尝试蚁群算法在不同具体问题中的实际应用是今后的一项重要研究内 容。如何抽象实际问题，使蚁群算法的求解更接近工程实际，是广大蚁群算法研究者所 共同关注的一个关键性问题。 1 1 3 蚁群算法的特点 蚁群算法是受真实蚂蚁行为的启发而提出的，他是群体智能系统中最成功的例子之 ，已被应用到从典型的旅行商问题到数据挖掘问题等许多领域，从而体现出了这种新 思想在求解n p 难题过程的寻优能力。 该算法的主要特点在于： ( 1 ) 较强的鲁棒性：对基本蚁群算法模型稍加修改，便可以应用于其他问题。 ( 2 ) 分布式计算：蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行 实现。 3 江南大学硕士学位论文 ( 3 ) 易于与其他方法结合：蚁群算法很容易与多种启发式算法组合如与遗传算法结 合解决图像分割问题等n 副，以改善算法的性能。 众多研究已经证明蚁群算法具有很强的发现解的能力，这是因为该算法不仅利用了 正反馈原理，在一定程度上可以加快进化过程，而且本质上是一种并行算法，不同个体 之间不断进行信息交流和传递，从而能够相互合作，有利于发现解。 1 2 旅行商问题 旅行商问题描述为：给定n 个城市，有一个旅行商从某一城市出发，访问各城市一 次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。 t s p 可分为对称t s p ( s y m m e t r i ct r a v e li n gs a l e s m a np r o b l e m ) 和非对称t s p ( a s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ) 两大类，若两个城市往返的距离相同，则为 对称t s p ，否则为非对称t s p ，本文研究对象为对称t s p 。 t s p 的数学描述为： 、- 1， m i n 乙d x 1 1 以 x 玎= 1 j = l 玎 x 扩= 1 f = l 勤- 1 s i _ 1 i , j e s 丐 i o ，1 ) i , j = l , 2 ，以z 1 2 1 3 1 4 1 5 其中式1 5 中的决策变量鼍，= 1 表示商人行走的路线包含从城市i 到城市j 的路径。 鼍，= o 表示商人没有选择这条路径。目标函数式1 1 要求距离之和最小。式1 2 要求商 人从城市i 出来一次，式l - 3 要求商人走入城市j 只有一次，式1 2 ，1 3 只能保证每 个城市经过一次，但并不能保证没有回路。式1 4 要求商人在任何一个城市子集中不形 成回路。其中lsi 表示集合s 中元素个数。 t s p 是图论中具有代表性的组合优化问题，是n p h a r d 问题，常被用来验证智能 启发式算法的有效性。几十年来对于求解t s p 问题出现了很多传统方法，其中有精确算 法如线性规划方法、动态规划方法、分支定界方法：近似优化算法如插入法、最近邻算 法、生成树法、概率算法等。近年来，有很多解决该问题的较为有效的方法不断被推出， 例如禁忌搜索方法、遗传算法、模拟退火算法、贪婪算法等。但是这些算法对系统参数 要求较高，例如遗传算法就必须选择种群数目、杂交概率、变异概率等，参数选的好， 就会得到比较好的实验结果，反之，可能导致实验的失败。 蚁群优化算法刚一提出就用于解决旅行商问题，之所以选择t s p ，不仅因为该问 4 第一章概述 题为大家所熟悉，是n p 问题，而且也较容易阐明蚁群优化算法的原理。由于该算法 具有较强的鲁棒性，具备较好的全局优化能力和分布式计算的能力，对于参数的要求 也比遗传算法简单，同时还容易与其他方法相结合，因此特别适合于求解困难的组合 优化问题。目前蚁群优化算法应用最多的还是旅行商闯题，很多改进的蚁群算法也都 是用于解决旅行商问题。实验也表明，蚁群优化算法在解决旅行商问题上取得了良好的 效果，优于其他几种启发式算法。 1 3 图像分类 1 3 1 图像分类的意义及原理 视觉是人类从自然界中获取信息的主要手段。据统计在人类获取的信息中，视觉信 息约占6 0 ，听觉信息约占2 0 ，通过其他手段获取的信息约占2 0 ，由此可见视觉信 息对人类的重要性，而图像正是人类获取视觉信息的主要途径。然而直接获取的图像并 不能很好的满足人类的需求，必须对图像做进一步的处理，这就是图像处理。在计算机 时代，图像处理主要是指数字图像处理，也就是利用计算机对图像进行处理。 计算机对数字图像处理的目的是为了获得满足特定要求的图像，是从图像到图像的 过程，是图像理解与分析的初级阶段。图像分类是计算机视觉的一个重要研究课题，其 目的是让计算机根据特定目标模式来识别各种不同的图像目标，以达到使计算机具有人 类视觉的美好愿望。 图像分类是利用计算机对图像进行定量分析，把图像中的每个像元或区域划归为若 干个类别中的一种，以代替人工视觉判断的技术。从目视角度来说，对图像进行提高对 比度、增加视觉维数、进行空间滤波或变换等处理的目的就是使人们能够凭借知识和经 验，根据图像亮度、色调、位置、纹理和结构等特征，准确地对图像景物类型或目标做 出正确的判读和解释。 计算机智能化图像分类技术可以根据应用需求从图像中自动找出感兴趣的目标。计 算机图像分类是人工目视判读的延续和发展，得益于现代计算机技术的快速进步，计算 机图像分类比人工图像分类的速度快，分类精确度也达到了较高的水平。在“信息爆炸” 的当今世界，图像的获取和使用越来越方便，图像文件的交换和传输也越来越频繁，海 量图像信息的处理成了一个难题。在这种情况下，如何依靠计算机的高速计算能力迅速 准确的自动识别图像内容，如何选择合适的方法来对图像进行分类具有重要研究价值和 意义。 1 。3 。2 图像分类的研究现状 当今国际上图像分类技术的研究有三个方向；( 1 ) 利用从图像数据中提取的新信息 和新特征进行分类；( 2 ) 应用新理论进行分类，如基于支持向量机b 刨、神经网络碡 、共 生矩阵璐副、图像纹理提取b 钔等方法对图像进行分类；( 3 ) 新的分类方法，其实现途径干 差万别，但一般从两个方面入手：1 ) 改进经典算法，由于经典算法仍有不足之处，由此 江南大学硕士学位论文 对其进行改进是发展新的分类算法的有效途径；2 ) 构造新算法，随着人们对理论知识的 深入研究，可以将新的理论应用于解决问题和创造算法。构造新算法既可以完全抛弃旧 算法，从头开始，也可以借鉴旧算法的优点。总的来说，图像分类研究目前正朝着精度、 快速的方向发展。 国内外学者从不同角度提出了许多表征图像特征的方法，如基于像素的灰度共生矩 阵、基于纹理基元的结构法等；近年来一些学者引入新的数学工具，提出了基于小波理 论的图像分类1 、决策树h 、分形特征h 2 1 等表示方法。小波分形是2 0 世纪8 0 年代中期发 展起来的应用数学理论，具有良好的时频局部特征、方向性特征，使其在图像处理、模 式识别、计算机视觉等众多学科领域得到了广泛的应用，在纹理分析方面也获得了一些 应用。将上述方法提取的图像特征输入分类器进行处理就可以得到分类结果。典型的分 类方法包括监督分类和无监督分类，比较常用的无监督分类方法有k 一均值法；监督分类 法有最小距离法、马氏距离法。近年来，人们又提出了一些新的分类方法和理论，如聚 类分析、神经网络、支持向量机、蚁群算法等。 聚类分析m 叫1 属于无监督模式识别，是模式识别研究中的一个重要分支。数据聚类 是没有任何关于样本的先验知识，不需要利用已知类的信息，分类系统通过种有效的 方法发现样本的内在相似性，使得同类型的样本尽可能的相似，而不同类型的样本尽可 能的不同。他将从图像中提取出的特征向量以聚类的形式分组，达到图像分类的目的。 支持向量机是b o s e r ，g u y o n 和v a p n i k 等人于1 9 9 2 年提出的一种基于统计学理论的学 习机模型m “副。支持向量机与其他机器学习方法相比在解决小样本、非线性及高维模式 识别上表现出许多特别的优势，具有良好的推广能力和很强的普适性，可用于模式识别、 回归估计及函数逼近等方面。支持向量机的最终求解可以转化为一个线性约束凸二次规 划问题，不存在局部最小。在模式识别方面，支持向量机已经被用于手写体识别、目标 识别、语音识别、文本分类以及雷达目标识别中。 蚁群算法是种新型的智能仿生模型，其刚提出就被广泛的应用于各个领域，在图 像领域中，蚁群算法在图像分割h 2 | 、边缘提取n 副、图像分类n 们中都有成功的应用。在已 有的应用中，蚁群算法取得了初步的研究成果，但是由于蚁群算法模型本身及图像处理 的复杂性，使得蚁群算法用于解决图像问题的效率较低，需要作进一步的研究。 6 第一章概述 1 4 本文的研究内容 1 4 1 c b a c o 及其在旅行商问题中应用 针对蚁群算法本身存在的问题，结合t s p 问题对蚁群算法进行改进，提出群体分类 的蚁群算法( c h a r a c t e r - b a s ea n tc o l o n yo p t i m i z a t i o n ) ，以便能加速算法收敛速度， 并且扩大蚂蚁的搜索范围，使蚁群避免陷入局部最优解，获得更优解。主要方法是改变 蚁群算法模型，加入随机蚂蚁，改变蚁群的搜索前进策略和刷新策略，促使蚂蚁跳出局 部最优解，获取更优的解，提高算法寻求最优解的能力。试验证明，这种改进可以提高 算法求解t s p 问题的能力。 1 4 2 s a c b a c o 及其在图像自动分类中应用 已有的研究已经表明蚁群算法可以应用于图像处理、图像分析与理解、图像分割、 图像分类等领域。从已经发表的论文看n 4 _ 埘，将蚁群算法应用于图像分类已取得了一定 的成果，证明了其可行性。但是由于将所有的蚂蚁进行随机的搜索，从而产生了大量的 无效搜索，导致算法的收敛速度相对较慢，算法的运行效率较低。本文将改进的蚁群算 法模型s a c b a c o ( s e l f a d a p t i n g c h a r a c t e r b a s ea n tc o l o n yo p t i m i z a t i o n ) 应用于 图像分类，随机蚂蚁搜索图像类别，构建类别表，确定初始聚类中心，指导智能蚂蚁搜 索相应类别，加速算法的收敛速度，提高了算法分类的效率；同时所有的蚂蚁在搜索前 进过程中对图像进行边缘提取，从而提高了算法对图像边缘分类的准确度。试验表明， 相比基本蚁群算法求解图像分类问题，由于该改进引入初始聚类中心和识别边缘，算法 的分类效率和对边缘信息点分类的准确度得到提高。 7 江南大学硕士学位论文 第二章蚁群算法理论 在智能自动化研究领域，目前具有群体智能特征的算法研究正受到越来越多的关 注。作为群体智能的一种典型实现，蚁群算法的研究也进一步的深入。这是一种基于种 群寻优的启发式搜索算法，由m d o r i g o 等人于1 9 9 1 年首先提出 4 - 5 o 它充分利用了生物 蚁群能通过个体问简单的信息传递，搜索从蚁穴至食物源最短路径的集体寻优特征，以 及该过程与旅行商问题求解之间的相似性，得到了具有n p 难题的旅行商问题的优化解 答。同时，该算法还被用于求解j o b s h o p 调度问题、二次指派问题、背包问题等，显示 了其适应于组合优化类问题求解的优越特征。正因为如此，为进一步促进世界范围内相 关领域的研究工作，i e e e 进化计算会刊于2 0 0 2 年8 月出版了蚁群优化算法特刊，在其中 以蚁群算法的成功应用领域一一离散优化问题求解为重点，发表了许多优秀的研究论 文，集中体现了蚁群算法研究和应用领域的成功进展。因此，蚁群算法己成为当前群智 能领域中最令人感兴趣和最富有魅力的研究课题之一。 2 1 蚂蚁算法概述 2 1 1 蚁群算法起源 自2 0 世纪5 0 年代中期创立了仿生学以来，人们从生物进化的机理中受到启发，提出 了许多用以解决复杂优化问题的方法，如遗传算法、进化规划、进化策略等。蚁群优 化算法( a n tc o l o n yo p t i m i z a t i o na c o ) 是受到人们对自然界中真实蚁群行为研究而提出 的一种基于种群的模拟进化算法，属于随机搜索算法。它首先由意大利学者m d o f i g o 等人提出来，他们称之为蚂蚁系统( a n ts y s t e m ) “3 。蚂蚁算法充分利用了蚁群搜索食物的 过程与著名的旅行商问题( t s p ) 之间的相似性，通过人工模拟蚂蚁搜索食物的过程( 即： 通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解t s p 问题。像蚂蚁这类群居昆虫，虽然单个蚂蚁的行为极其简单，但由这样的单个简单个体 所组成的蚁群群体却表现出极其复杂的行为，能够完成复杂的任务。不仅如此，蚂蚁还 能够适应环境的变化，如在蚁群运动路线上突然出现障碍物时蚂蚁能够很快地重新找到 最优路径( 如图2 - 1 所示) 。 蚂蚁算法来源于对自然界蚂蚁寻找从蚁巢到食物的最短路径并找到回巢路径方法 的研究，是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生进化算法。蚂蚁算法中 采用有记忆的人工蚂蚁，通过个体之间的信息交流与相互协作来找到从蚁穴到食物源的 最短路径。研究发现，蚂蚁个体之间是通过一种称为信息素( p h e r o m o n e ) 的物质进行信 息传递，从而相互协作，完成复杂任务。蚂蚁在运动过程中能够在所经过的路径上留下 该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己 的运动方向。蚂蚁是自然界中常见的一种生物，蚁群寻找食物时会派出些蚂蚁分头在 四周游荡，它们总能找到条从食物到巢穴之间的最优路径。 8 第二章蚁群算法理论 cd 图2 1 蚂蚁路径示意图 f i g 2 1a n tt r a i ls k e t c hm a p 2 1 2 双桥试验及其模型 很多种类的蚂蚁所具有的视觉感知系统都是发育不全的，甚至有些种类的蚂蚁是完 全没有视觉的。事实上，关于蚁群行为的早期研究表明，群体的个体之间以及个体与环 境之间的信息传递大部分都是依赖于蚂蚁产生的化学物质进行的。人们把这种化学物质 称为信息素( p h e r o m o n e ) 。蚂蚁这种特有的信息传递方法，不同于人类以及其他高级种 群之间所使用的以视觉和听觉为主的感知方式。对于某些蚂蚁来说，在他们的群居生活 中，最重要的就是路径信息( t r a i lp h e r o m o n e ) 的作用。这是一种特殊的信息素，蚂蚁正 是通过感知其他蚂蚁释放的信息素来沿途寻找食物的所在地。 ( 1 ) 双桥试验h 。 蚂蚁在寻找食物时，都是以信息素作为媒介而间接进行信息传递的。当蚂蚁从食物 源走到蚁穴，或者从蚁穴走到食物源时，都会在经的地面上释放信息素，从而形成一条 含有信息素的路径。蚂蚁可以感觉到路径上信息素的大小，并且以更高的概率选中信息 素浓度最高的路径。 目前已有学者对蚂蚁通过信息素浓度选择路径的行为进行了可监控的试验。其中最 巧妙的是有d e n e u b o u r g 和其同事设计完成的双桥试验，他们使用双桥来连接蚂蚁的蚁穴 和食物源。他们在试验中测试了一组不同比例的r = l 1 l 2 的双桥，其中r 是双桥两个分支 的比例，l 1 是较长分支的长度，l 2 是较短分支的长度。在第一个试验中，桥上的两个分 支的长度是相同的( 即r = l ，如图2 - 2 ( a ) 所示) 。开始的时候，蚂蚁可以自由的在蚁穴 和食物源之间移动。试验的目的就是观察蚂蚁随时间推移选择两条路径中的一条的概 率。试验的最终结果显示，尽管最初蚂蚁随机选择一条路径，但最后所有的蚂蚁都会选 择相同的一条路径。其原因是在刚开始的时候两条路径上都不存在信息素，因此蚂蚁对 这两条路径的选择不存在任何的偏向性，蚂蚁将以相同的概率在两条路径上进行随机的 选择。然而，由于随机波动的出现，选择某一条分支的蚂蚁数量可能会比另外一条多。 正是因为蚂蚁在移动的过程中会释放信息素，那么当有更多的蚂蚁选择某条分支路径 时，则此路径上的信息素将相应的增加，而这种增加的信息素将所有的蚂蚁都吸引到此 q 江南大学硕士学位论文 路径上，最终所有的蚂蚁都将收敛于一条路径。而在第二个试验中，我们设定两个分支 的长度比例为2 ，即一条分支的长度是另一条分支长度的2 倍，在这中设置下，观察显示， 最终所有的蚂蚁都将收敛于较短路径的分支上，与第一个试验一致，蚂蚁离开蚁穴寻找 食物源，当来到第一个决策点时，所有的蚂蚁将随机地选择两条路径中的一条，因此两 条路径对于蚂蚁来说被选中的概率是相同的，但是，观察显示经过段时间后所有的蚂 蚁都将集中于较短的路径上，这是因为，蚂蚁开始时是随机选择路径，但随着时间的推 移，较短路径上的蚂蚁走完全程所用地时问将较短，在相同的时间内，较短路径上的蚂 蚁来回于蚁穴和食物源的次数将大于较长路径上的蚂蚁，因此较短路径上的信息素的总 量将大于较长路径上的信息素的总量，而这种较浓的信息素将会促使更多的蚂蚁再次选 择这一分支，这一过程一直进行，直到最后所有蚂蚁都集中到某一条分支路径上，这种 正反馈的过程，实际上就是蚂蚁的自组织行为。 让人感兴趣的时，如果当蚂蚁在较短的路径上形成比较稳定地信息素的时候即当所 有的蚂蚁都集中于较短路径上，此时再为蚂蚁在蚁穴和食物源之间提供更短的路径，只 有很少的蚂蚁能寻找到这条新添加地路径，大部分蚂蚁都还将困死在先前选择的路径 上。这是因为刚才被蚁群所选中地路径上形成的信息素强度很高，对蚁群具有很强的吸 引力，而新添加地更优的路径信息素很低，因此蚁群无法摆脱高信息素的束缚，从而无 法寻找到更优地路径。 a 、 两支分支具有相同的长度 a 、d o u b l ee q u a ll e n g t h b r i d g e b 、两支分支具有不同的长度 b 、d o u b l e d i f f e r e n tl e n g t hb r i d g e 图2 - 2 双桥试验 f i g 2 - 2d o u b l eb r i d g ee x p e r i m e n t a t i o n ( 2 ) 随机模型h 儿5 d e n e u b o u r g 和他的同事提出了一个简单的模型，用以描述在双桥试验中观察得到的 蚁群动态行为，在这个模型中，每秒钟有沙只蚂蚁以恒定的速度v c m s 从某方向过桥， 并在分支上释放一个单位的信息素。给定短分支长度和长分支长度，选中短分支的 蚂蚁可以用t = l s 秒通过，而选择了长分支的蚂蚁则需要用，1 秒钟，其中，= 厶厶。 一只到达决策点i = ( 1 ，2 ) 上的蚂蚁选择分支口= ( s ，) 的概率是( n ，其中s ，分别 代表短路径和长路径，p i a 被设置为分支上信息素总量的函数纥( f ) t ，这个函数的值与 时刻f 前使用那条分支的蚂蚁总数成正比。例如，选择短分支的概率玩可用如下公式 1 0 第二章蚁群算法理论 表示： 圳= 而蔫 亿， 这个模型假设分支中的信息素总量与过去使用这条分支的蚂蚁数量成正比。换句话 说，在这个模型中并没有考虑任何的信息素蒸发。 描述随机系统演化过程的微分方程如下所示： d 妒括d t = p 声( t t 。) + l p 如( f ) ( 2 2 ) d 妒f ，d t = 沙p ，z ( ，一t ) + p j z ( f ) ( 2 3 ) 式2 2 表示：在r 时刻，决策点i 上分支s 的信息素瞬间变量的大小，等于蚂蚁的流 量少乘以在( f t ) 时刻选择决策点歹上短分支的概率，加上蚂蚁的流量乘以在f 时刻选择 决策点i 上短分支的概率，其中y 假设为常量。常量代表的是时间延时，也就是蚂蚁 通过短分支所需要的时间。式2 3 是针对长分支表达方式。 2 1 3 人工蚁群系统研究 蚁群算法( 又称人工蚁群算法) 是受到真实蚁群行为启发而提出来的。为了说明人工 蚁群系统的原理，先从蚁群搜索食物的过程谈起。像蚂蚁、蜜蜂、飞蛾等群居昆虫，虽 然单个昆虫的行为极其简单，但有单个简单的个体所组成的群体却表现出极其复杂的行 为。仿生学家经过大量细致的观察研究后发现，蚂蚁个体之间是通过一种称为外激素 ( p h e r o m o n e ) 的物质进行信息传递。蚂蚁在运动过程中，能够在它所经过的路径上留下 该物质，而且蚂蚁在运动过程中能够感知该物质，并以此指导自己的运动方向。因此， 有大量蚂蚁组成的蚁群，其集体便表现出一种信息的正反馈现象：某一路径上走过的蚂 蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达 到搜索食物的目的。 h a h a t = 0 时刻 图2 - 3 蚁群系统示意图 f i g 2 - 3a n ts y s t e ms k e t c hm a p c h a t = i 时刻 蚁群系统的原理如图2 3 所示，设每个时间单位由3 0 只蚂蚁由a 到达b ，又有3 0 只由e c 江南大学硕士学位论文 到达d 点，蚂蚁过后留下外激素为l ，为便于讨论，设外激素停留时间为1 在初始时刻， 由于路径b h ，b c ，d h ，d c 上均无信息存在，位于b 和e 上的蚂蚁可以随即选择路径。从统 计的角度可以认为他们以相同的概率选择b h ，b c ，d h ，d c 。经过一个时间单位后，在路径 b c d 上的信息量是路径b i d 上信息量的两倍。在t = l 时刻，将由2 0 只蚂蚁由b 和d 到达c ，由 l o 只蚂蚁由b 和d 到达h 。随着时间的推移，蚂蚁将会以越来越大的概率选择b c d ，最终完 成选择路径b c d ，从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信 息交换是一个正反馈过程。 双桥试验清晰的显示了蚂蚁具有的一种内在的优化能力：它们可以通过使用基于局 部信息的概率规则找出所在环境中两点之间的最短路径。此试验启发我们试图去设计一 种人工蚂蚁，让其找出蚁穴和食物源两点之间的最短路径。 作为人工蚂蚁定义的第一步，首先设计试验的装置，包含两个结点( 结点1 和结点2 ， 分别代表蚁穴和食物源) ，这两个结点分别有一个长路径和一个短路径相连，此外，还 假设时间是离散的( r = 1 ，2 ) ，在每一个时间步内，每一只蚂蚁都以一个恒定的速度( 每 一个单位时间都移动一个单位长度) 朝着相邻点移动。当移动到相邻点时，蚂蚁会在所 使用的路径上释放一个单位的信息素。蚂蚁在图中的移动是基于一定的概率来选择路径 的：见s ( t ) 是位于结点f 的蚂蚁在，时刻选择短边的概率，而只以) 是选择长边的概率。这 些概率都是位于结点i 的蚂蚁在分支a 上的信息素够a 的函数。 础，2 d 粼嘉删= 耐粼嘉 亿4 ， 两条分支上的信息素更新按式2 5 和式2 6 进行 o ) = 9 i s ( t 一1 ) + p f s ( t 一1 ) m f ( f 一1 ) + p s 。( t 一1 ) m ，o 1 )( 2 5 ) i = 1 ，j = 2 ；i = 2 ，j = 1 够z o ) = 够f o 一1 ) + p i f o 1 ) m f ( f ) - 1 ) + p j l ( t - r ) m ，o 一，) ( 2 6 ) i = 1 ，j = 2 ；i = 2 ，j = 1 其中朋，【f ) 是时刻，在结点i 上的蚁群个数，并由式2 7 给出 m ，o ) = p j , ( t d m ，( f 一1 ) + p o r ) m ，( f 一，) ( 2 7 ) i = 1 ，歹= 2 ；i = 2 ，歹= l 2 2 蚁群算法模型及实现 2 2 1 基本蚁群算法原理 蚂蚁在寻食过程中总能找到一条食源和栖息地之间的最短路经，研究发现蚂蚁之间 是通过一种体外激素来相互传递信息的，从而相互协作，完成复杂的任务。蚁群之所以 能保持有序并完成复杂的任务，信息的相互交流起着重要作用，蚂蚁能感知路径上外激 素的存在和强弱，并选择激素强的路径前进，因此，蚁群的具体行为就表现出是一种信 息的正反馈现象：即当某条路径上的蚂蚁越多，遗留的信息量就越强，后来的蚂蚁