（计算机应用技术专业论文）蚁群算法参数优化及其应用.pdf

硕士学位论文蚁群算法参数优化及其应用 摘要 作为一种新型的仿生优化算法，蚁群算法在本质上是一个复杂的智能系统，它 具有较强的鲁棒性、优良的分布式机制及方便与其它算法融合等优点，目前已经成 功地运用到许多应用领域。但是，蚁群算法在理论研究上还存在着许多需要解决的 问题。例如：收敛速度问题、信息素分配和参数选择问题等，其中参数选择对蚁群 算法的性能影响较大。鉴于此，本文着重研究蚁群算法参数优化问题。 论文中，全面分析了基本蚁群算法的性能、原理及机制，并通过旅行商问题 ( t s p ) 的仿真实验，深入研究了参数选择对算法性能的影响。特别是其中三个参 数启发式因子口、期望启发式因子及信息持久因子p 对算法性能的影响较大。文 中利用微粒群算法设计了一种参数优化方案，对这三个参数进行组合优化有效地改 善了算法的性能。并且针对o l i v e r 3 0 城市问题，用j a v a 编程语言进行了程序设计， 程序运行结果较好。该方案突破了传统靠经验和直觉确定参数的局限，发挥了三个 参数的组合效应，使得蚁群算法在实际优化问题中能够取得更好的效果。 为了进一步验证方案的可行性、实用性，将该方案又应用到车间作业调度问题 ( j s s p ) 中。文中对车间作业调度常用方法作了全面的综述，分析了j s s p 的基本 原型，并就蚁群算法建立了j s s p 的模型，以便于编程实现。最后针对j s s p 6 * 6 、 j s s p l 0 * 1 0 两个典型问题进行了仿真实验，得到了预期的效果。 总之，本文所提出的一种参数优化方案切实可行、仿真实验数据结果较好。为 日后进一步研究蚁群算法参数的优化工作，提供了参考和借鉴。 关键字：蚁群算法、参数优化、微粒群算法、车间作业调度问题 硕士学位论文 a b s t r a c t a san e wb i o n i co p t i m i z e da l g o r i t h m ，a n tc o l o n ya l g o r i t h mi sa c o m p l e xi n t e l l i g e n t s y s t e mi ne s s e n c e ，w h i c hh a st h ea d v a n t a g e so fs 仃o n gr o b u s t n e s s ，e x c e l l e n td i s t r i b u t i o n m e c h a n i s ma n dc o n v e n i e n ti n t e g r a t i o nw i t ho t h e ra l g o r i t h m s i th a sb e e ns u c c e s s f u l l y a p p l i e di nm a n yf i e l d s b u t , t h e r es t i l la l em a n y u n s o l v e dp r o b l e m si nt h et h e o r i e so fa n t c o l o n ya l g o r i t h m s u c ha s ：t h ec o n v e r g e n c er a t e ，t h ep h e r o m o n ea l l o c a t i o na n dt h e p a r a m e t e rs e l e c t i o n , a m o n gw h i c ht h ep a r a m e t e rs e l e c t i o na f f e c t st h ep e r f o r m a n c eo fa n t c o l o n ya l g o r i t h mm o s t t h e r e f o r et h i sp a p e rm a i n l yr e s e a r c h e st h eo p t i m i z a t i o no ft h e p a r a m e t e rs e l e c t i o nf o ra n tc o l o n ya l g o r i t h m i nt h i sp a p e r , t h ep e r f o r m a n c e ，p r i n c i p l ea n dm e c h a n i s mo fb a s i ca n tc o l o n y a l g o r i t h ma r ea n a l y z e dc o m p r e h e n s i v e l y t h ee f f e c to ft h ep a r a m e t e rs e l e c t i o no nt h e p e r f o r m a n c eo fa n tc o l o n ya l g o r i t h m i st h o r o u g h l yd i s c u s s e db yt h es i m u l a t i o n e x p e r i m e n t so ft h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) e s p e c i a l l yt h et h r e ep a r a m e t e r s t h a th a v em o l ea f f e c to nt h ea l g o r i t h m ，w h i c ha r et h eh e u r i s t i cf a c t o r0 【，t h ee x p e c t a t i o n h e u r i s t i cf a c t o rp ，a n dt h ei n f o r m a t i o np e r s i s t e n tf a c t o rp b a s e do nt h ep a r t i c l es w a r m o p t i m i z a t i o no s o ) a l g o r i t h m ，ap a r a m e t e ro p t i m i z a t i o n s c h e m ei s d e s i g n e d t o e f f e c t i v e l yi m p r o v et h ep e r f o r m a n c eo ft h ea l g o r i t h mb yo p t i m i z i n gt h ec o m b i n a t i o no f t h et h r e ep a r a m e t e r s b e s i d e s ，aj a v a p r o g r a ma i m i n ga tt h eo l i v e r3 0c i t i e sp r o b l e mi s w r i t t e n , w h i c hg e n e r a t e si d e a lr e s u l t s n l i ss c h e m eb r e a k st h et r a d i t i o n a ll i m i t a t i o n s w h i c hd e t e r m i n et h ep a r a m e t e r sb yt h ee x p e r i e n c e sa n dt h ei n s t i n c t s i n s t e a d ，i tp l a y st h e a s s o c i a t e de f f e c t so ft h et h r e ep a r a m e t e r s ，w h i c he n a b l e sb e t t e re f f e c t sw h i l eu s i n ga n t c o l o n ya l g o r i t h mi nt h ep r a c t i c a lo p t i m i z a t i o np r o b l e m s i no r d e rt ov 嘶黟t h ef e a s i b i l i t ya n dt h ep r a c t i c a b i l i t yo ft h es c h e m e ，i ti sa p p l i e d t ot h ej o b s h o ps c h e d u l i n gp r o b l e m s ( j s s p ) t h i sp a p e rm a k e s a no v e r a l l s u m m a r i z a t i o no nt h ec o m m o nm e t h o d so fj s s p , a n a l y z e st h ep r o t o t y p eo fj s s p , a n d e s t a b l i s h e san e wj s s pm o d e lb a s e do na n tc o l o n ya l g o r i t h m ，f o rt h ec o n v e n i e n c eo f p r o g r a m m i n g i nt h ee n d t w ot y p i c a lp r o b l e m s ，j s s p 6 6a n dj s s p l 0 幸1 0 ，a l es i m u l a t e d a n dt h ep r o s p e c t i v er e s u l t sa r eo b t a i n e d i ns u m m a r y , t h ep a r a m e t e ro p t i m i z a t i o ns c h e m ei nt h i sp a p e ri sp r a c t i c a b l e ，a n d t h es i m u l a t i o nr e s u l t sa l ei d e a l i tc a l lp r o v i d es o m er e f e r e n c e sf o rt h er e l a t e dr e s e a r c h w o r k so nt h ea n tc o l o n ya l g o r i t h m k e y w o r d s ：a n tc o l o n ya l g o r i t h r n , o p t i m i z i n gp a r a m e t e r s ，p a r t i c l es w a n l lo p t i m i z a t i o n , j o bs h o ps c h e d u l i n gp r o b l e m s ( j s s p ) 。 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均己在论文 中作了明确的说明。 研究生签名：年月 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：年月日 硕士学位论文蚁群算法参数优化及其应用 1 绪论 1 1 引言 社会性并非是人类独有的专利，其实在奇妙的大自然中生活着许多具有社会性 的昆虫。如：蚂蚁、蜜蜂等，它们个体虽然很简单，但却有着高度社会化的组织。 在它们的组织中，有着令人类赞叹的分工、协作和信息的传递。这使得一个具有社 会性的昆虫群体，能够完成超越个体能力的复杂任务。动物学研究表明，蚂蚁群就 具有这样奇妙特性的信息系统【4 】。蚂蚁在觅食走过的路径上释放一种特有的分泌物， 我们把它形象地称为信息素。蚂蚁个体之间正是通过这种信息素传递信息，从而相 互协作，完成从蚁穴到食物源寻找最短路径的复杂任务。 从蚂蚁群体觅食行为受到启发，意大利学者d o r i g om 在1 9 9 1 年提出了一种模 拟自然界蚁群行为的模拟进化算法“人工蚁群算法”，简称蚁群算法【l 】。这种算法具 有分布式计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种新型 启发式优化算法。起初该算法是从研究求解旅行商问题( t s p ) 提出的，但随着不 断的深入研究人们发现它在求解多种组合优化问题中获得了广泛的应用，例如在生 产调度、二次分配和网络路由等方面都取得了较为丰硕的成果。 1 2 蚁群优化算法的重要意义 当今，科学技术正处于多学科融合和交叉的时代。计算机技术则是一个典型的 成功范例，它又从根本上改变了人类的生产与生活。随着人类生存空间的扩大以及 认识世界范围的拓展，对科学技术提出了更高的要求，其中对高效的优化技术和智 能计算的要求也是日益迫切。 传统优化技术是一种以数学为基础，用于求解各种工程优化问题的应用技术。 作为对生产实际有广泛作用的科学分支，一直受到人们的高度重视，并在诸多工程 领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度和计算机 工程等。对于实际工程问题的复杂性、约束性、非线性、建模困难等特点，传统以 数学为基础的优化方法已经无能为力。寻求适合于大规模并行且具有智能特征的优 化算法已经是迫在眉睫了，为此人们开始热切关注仿生优化算法。 在诸多仿生优化算法中，除了业已得到公认的遗传算法、模拟退火算法、禁忌 搜索法及人工神经网络等【4 】，新近出现的蚁群算法也已开始崭露头角，为复杂问题 的系统优化提供了一个新的研究途径。尽管其思想尚处于萌芽时期，但人们已经认 识到它的重要性和积极意义。这种由欧洲学者提出的新颖系统优化思想，正吸引着 1 绪论硕士学位论文 越来越多的学者，其应用范围也逐步拓展到更多的工程应用技术领域。 1 3 蚁群算法研究进展及其存在问题 自意大利学者d o r i g om 提出“人工蚁群算法”后，又于1 9 9 6 年发表了 a n t s y s t e m ：o p t i m i z a t i o nb yac o l o n yo fc o o p e r a t i n ga g e n t s ”一文【3 1 ，这是蚁群算法发展史上 极为重要的奠基性论文。在这篇文章中，d o r i g om 等不仅系统地阐述了蚁群算法的 基本原理和数学模型，还同遗传算法、禁忌搜索算法、模拟退火算法等进行了仿真 实验比较，并把单纯地解决对称t s p 拓展到解决非对称t s p 、指派问题以及车间作 业调度问题。自此后的几年时间内，蚁群算法逐渐引起广大学者的关注，大量有价 值的研究成果陆续发表并不断地拓宽了其应用领域。 蚁群算法经过十多年的发展，其主要研究成果包括算法性能改进、算法理论和 收敛性证明以及应用领域的扩展等三个方面。 大量具有实际应用价值的改进算法，主要可以分为离散域算法的改进和连续域 算法的改进两大类。d o r i g om 等【5 8 】在基本蚁群基础之上提出了一种称之为a n t - q s y s t e m 的蚁群算法，该算法仅让循环中最短路径上的信息量作更新，并仅让信息量 大的路径以较大的概率被选中，充分利用学习机制强化信息的反馈；德国学者 s m t z l et 和h o o sh 提出了另一种改进的算法m m a s ( 最大最小蚂蚁系统) 【5 9 】， m m a s 限定了信息量允许值的上下限，这样各条路径上的信息量都在最大值和最小 值之间，从而避免了过早收敛的现象。除此以外，比较著名改进算法还有带精英策 略的蚂蚁系统、基于优化排序蚂蚁系统及最优最差蚂蚁系统等【4 】。b i l e h e vga 等【6 川 最早提出了一种连续域蚁群算法，求解问题时先使用遗传算法对解空间进行全局搜 索，然后利用蚁群算法对所得结果进行局部优化；高尚等【6 l 】提出了一种基于网格划 分的连续域蚁群算法；w a n gl 等【6 2 】将离散域蚁群算法中的“信息量留存”过程拓展 为连续域中的“信息量分布函数”，并定义了应用于连续函数寻优问题的改进算法。 由于国内外的学者提出的改进算法较多，这里就不再一一列举了。 对某些改进算法进行了收敛性证明，g u t j a h r w j 最先从有向图论的角度对一种 改进蚁群算法的收敛性进行了证明k 】；s t u e z l et 和d o r i g om 针对具有组合优化性质 的极小化问题提出了一类改进算法并对其收敛性进行了证明【5 】；丁建立等【6 3 】对一种 遗传蚁群算法的收敛性进行了m a r k o v 理论分析，并证明其优化解满意值序列单调 不增且收敛；h o uyh 等基于不动点理论对一类广义蚁群算法的收敛性进行了初步 分析【5 】o 自d o r i g om 等首次将蚁群算法应用于t s p 以来，许多学者对其应用进行了大 量的研究工作，将其推广到诸多优化领域并且取得了丰硕的应用性成果。这些应用 2 硕士学位论文 蚁群算法参数优化及其应用 领域包括：车间作业调度问题、网络路由问题、车辆路径问题、电力系统、机器人 领域、故障诊断、控制参数优化、聚类分析、数据挖掘、图象处理、武器分配、生 命科学化学工业等1 5 。 另外在蚁群算法的硬件实现上取得了突破性进展，在算法模型改进及与其他仿 生优化算法的融合方面也取得了相当丰富的研究成果等。 蚁群算法发展至今取得了令人瞩目的成就，但也存在着许多尚未解决的问题， 这就预示着它仍然具有广阔的发展前景。有待研究改进的主要方面有：模型的进一 步改进研究，主要包括提高模型的普适性和模型的智能化；蚁群算法的理论性分析， 大致包括统一框架下的收敛性证明、参数的优化选择及收敛速度问题等；蚁群算法 的并行实现；各种新型仿生算法的智能融合等【4 5 1 。 特别是参数的优化，对于蚁群算法的应用起到关键性的作用。因为，蚁群算法 所涉及到的参数值的确定，对算法的性能和优化结果有较大的影响。据此，本文对 蚁群算法参数的优化进行了一定的研究，并提出了一种参数组合优化的方案。该方 案突破了传统靠经验和直觉选择参数的局限，并且较容易实现和推广。 1 4 论文主要工作和研究内容 l 、- 本文在讨论蚁群算法基本模型的基础之上，分析了对蚁群算法影响较大的三个 参数启发式因子口、期望启发式因子及信息持久因子p 对算法性能的影响，结 合目前一些学者实验得出的参数合理范围。利用微粒群算法设计了一套参数优化方 案，对这三个参数进行组合优化。最后将这个设计方案应用到车间作业调度，并进 行了仿真实验。主要工作如下： 1 、通过基本蚁群算法，结合t s p 问题进行编程实验，研究了参数的选择对蚁 群算法性能及结果的影响。根据实验数据的图形分析，确定了相关三个参数的合理 取值范围，为后续参数的优化工作奠定了基础。 2 、根据微粒群算法，提出了一套蚁群算法参数的组合优化方案。该方案突破了 传统确定参数的局限性，发挥了参数的组合优化效应。 3 、对微粒群算法进行一定的改进，同时针对t s p 问题进行编程实现并对程序 运行结果进行了性能分析。 4 、将参数的优化方法应用到车间作业调度中，对车间作业调度中的两个典型问 题j s s p l 0 * 1 0 基准问题、j s s p 6 * 6 基准问题进行了仿真实验。进一步说明了该方案 的实用性。 3 1 绪论 硕士学位论文 1 5 本文组织 本文正文共计六章，各章的内容安排和论文的组织结构如下： 第一章介绍了蚁群算法的背景和研究进展，阐述了作为仿生优化算法的蚁群 算法在工程优化领域的作用和意义。列举了目前蚁群算法的研究成果，同时还分析 了蚁群算法研究中的不足之处。特别是参数值的确定，目前还缺乏有效的方法，直 接影响了蚁群算法的应用。同时明确了参数优化问题作为本文的中心研究内容。 第二章描述了自然界中蚂蚁的基本生活习性、觅食策略；分析了蚁群算法中 的人工蚂蚁基本模型；系统地说明了基本蚁群算法的原理和算法流程；为优化方案 和仿真实验编程作了铺叙。 第三章首先针对t s p 问题，进行了编程和仿真实验。分别讨论了三个参数启 发式因子口、期望启发式因子及信息持久因子p 对算法性能的影响，以及它们 对算法影响的组合效应。利用图象分析的方法，确定了三个重要参数的合理取值范 围，为后一章的参数优化奠定了基础。 第四章本章首先提出了一种蚁群算法参数组合优化方案，接着分析了基本微 粒群算法原理，并对微粒群算法进行了一定的改进以便应用到参数优化中。针对 o l i v e r 3 0 城市t s p 问题进行了编程实现，对程序运行的结果进行了分析和对比，说 明了该方案的可行性和有效性。 第五章本章介绍了蚁群算法在车间作业调度中的应用，描述了车间作业调度 的基本原形，并且建立了其应用模型。针对j s s p l 0 * 1 0 基准问题、j s s p 6 * 6 基准问 题进行了仿真实验，并对实验数据进行了定性的分析。从实际应用的角度说明了参 数优化的作用和有效性。 第六章对全文进行了总结和展望，说明了本文所完成的工作同时也指出了论 文的不足之处。最后对将来的研究工作进行了展望。 4 硕士学位论文 蚁群算法参数优化及其应用 2 蚁群算法基本原理 大自然不仅赋予了人类赖依生存的环境，同时又给予人类的智慧以启迪。自然 界一直是人类创造力的源泉，人类认识事物的灵感也常源于自然。自然界中的许多 自适应优化现象给人们以启示：生物体和自然生态系统可通过自身的演化就使许多 高度复杂的优化问题得到完美的解决。蚂蚁群体就具有这样的生态系统，它们个体 能力并不发达，但它们却能协同工作依靠群体力量发挥出超出个体的智能。 2 1 蚂蚁的基本生活习性 蚂蚁是一种最古老的社会性昆虫，它的存在大约可以追溯到恐龙时代。蚂蚁虽 然有成千上万种，但都是群体生活有自己的蚂蚁社会。它们像人类一样，几乎占据 了适宜居住的每一片土地。蚂蚁的个体结构和行为很简单，单个工蚁能够做的各种 动作不超过5 0 个，其中大部分是传递信息，但由这些简单的个体所构成的整个群 体一蚁群，却表现出高度结构化的社会组织可以完成远远超出蚂蚁个体能力的复 杂任务。蚂蚁中的个体从事不同的劳动，群体间进行严密的个体分工。除了组织分 工以外，还有相互的通讯和信息传递。它们有着独特的信息系统，其中包括视觉信 号、声音通讯和更为独特的信息素。 经过动物学家的观察，蚂蚁有着令人类感叹的信息系统 4 1 。这些信息系统包括 视觉信号、声音通讯和更为独特的无声语言信息素。它们通过化学物质的不同 组合、触角信号和身体工作在内的多个信息系统，来策动它们的同类。蚂蚁的许多 行为受信息素控制，例如蚁后通过信息素来调控工蚁的发育，信息素又可以为请求 或交换营养性卵和特殊臀区分泌物的表示。遇险时，信息素可以刺激蚁群兴奋，具 有使蚁群按照计划执行某项活动的作用。另外，蚂蚁以信息素来表明身份、识别同 伴。没有信息素的蚁巢就会失去生命，使蚁群无立足之地。 蚂蚁的行为更多地是以群体作为一个整体而存在，不是为了单个个体的存活。 也正是这种高度进化的社会性，使这些幼小的生灵能够在这纷繁的世界中立足，并 且不断繁衍，不愧为昆虫界的“智慧之花”。 2 2 自然界蚂蚁的觅食策略 蚂蚁是一种几乎没有视力的昆虫，生物学家经过长期的研究发现：蚂蚁作为一 个简单的个体，它的觅食行为是带有随机性的。但一群蚂蚁集体觅食时，它们常常 5 2 蚁群算法基本原理硕士学位论文 能够快速、准确地找到食物源。原来蚂蚁在搬运食物回巢时，本身会分泌一种化学 激素，我们称其为外激素( p h e r o m o n e ) 1 4 】。蚂蚁个体之间通过一种称为外激素的物 质来传递信息，蚂蚁在所通过的路径上会留下这种激素，而蚂蚁本身又会通过这种 信息的强弱来选择路径，从而达到互相协作，完成复杂任务。外激素在不断挥发， 距离越短的路径上相对走过的蚂蚁数就会越多，该物质的强度就会越大。由于蚂蚁 在运动中感知这种物质，并倾向于选择向该物质强度高的方向移动。这样就形成了 一种信息正反馈现象，即某条路径上走过的蚂蚁越多，那么后来的蚂蚁选择这条路 径的概率就越大。蚁群搜索食物源的过程是一个正反馈的过程，由此可以快速地找 到从蚁巢到食物的最佳路径。 辫砖躐帮警 一 f a ) - 一 1 ：i | | 一 一 t 口j 图2 1自然界蚁群觅食过程 图2 1 描述的是自然界中的蚂蚁觅食过程，设一群蚂蚁从巢穴到食物源觅食， 在图2 1 ( a ) 中，从巢穴到食物源可以直接到达没有阻碍物。而图21 、2 1 ( c ) 、21 ( d ) 中分别增加了一个障碍物。在图21 ( b ) 中，初始阶段由于路径上没有激素，一群蚂 蚁从巢穴随机运动，找到食物源。在图2 1 ( c ) 中，由于信息素的作用，逐渐有许多 蚂蚁选择较为短的路径饶过障碍物找到食物源。自然在觅食的初期，可能有一部分 6 硕士学位论文蚁群算法参数优化及其应用 蚂蚁觅食的路径较长。但经过一段时间，在短路径上经过的蚂蚁数就会多于较长路 径上的蚂蚁数，从而短路径上的信息浓度就会高于长路径上的信息浓度。这就是我 们在图2 1 ( d ) 中看到的，蚂蚁释放在短路径上的信息浓度越来越浓，自然就会有更 多的蚂蚁选择短的路径觅食。 崭 图2 2 蚁群觅食的不等长“双桥”实验 图2 2 就是著名的“双桥”实验【5 j ，这是d c n e u b o u r g 等人为了研究蚂蚁在受约束 条件下的觅食物行为。在实验中，蚁穴通过双桥与食物源相连，而桥的两个分支长 度不等。起初在两个分支上都没有信息素，蚂蚁选择两个分支的概率是相同的。但 是经过初期的一段时间震荡后，有更多的蚂蚁选择短路径的分支到达食物源。通过 自然界和实验室的这两个实验，我们可以明显地看到蚂蚁群体觅食行为的智能特 性。 2 3 蚂蚁系统基本模型 通过前面蚂蚁生活基本习性和两个实验的分析，我们在智能算法中模拟蚂蚁的 觅食行为，并且将自然界的蚂蚁行为约束如下： 1 、蚂蚁之间通过信息素互相通信，每只蚂蚁仅根据周围的信息素确定自己的 行为，同时也只对它周围的局部环境产生影响。 2 、蚂蚁对环境的反应由其内部模式决定。 3 、在个体水平上，每只蚂蚁仅根据环境做出选择。在群体水平上，单只蚂蚁 的行为是随机的，但蚁群可以通过自组织过程形成高度有序的群体行为。 由此行为约束可见，基本蚁群算法的寻优机制包含两个阶段：一是适应阶段， 各候选解根据积累的信息不断调整自身结构。路径上经过的蚂蚁越多释放的信息量 越大，则该路径越容易被选择；协作阶段候选解之间通过信息交流，以期望产生性 零渗 2 蚁群算法基本原理硕士学位论文 能更好的解，类似于学习自动机的学习机制。 为说明蚂蚁系统，这里以旅行商问题为例。旅行商问题简称为t s p 问题，它可 以形象地描述为：给定1 3 个城市，有一个旅行商从某一个城市出发访问各城市一次 且仅有一次后再回到出发城市，要求找出一条最短的路径。 按照组合理论，得到所有的可行路径共有( n - 1 ) ! 2 条。对于t s p 问题，我们 首先容易想到的是穷举法，比较所有可行的路径得到最优解。如果以路径比较作为 基本操作，则需要( n - 1 ) ! 2 1 次基本操作才能保证得到绝对最优解。假设以每秒 可以执行1 亿次浮点运算的计算机来说，当n = 1 0 时需要0 0 0 1 9 秒能够找到最优解； 但当n = 2 0 时就需要1 9 2 9 年才能找到最优解；当n = 3 0 时就需要1 4 x1 0 1 5 年才能找 到最优解。因此，对于较大规模问题进行穷举是不切实际的。1 9 9 1 年d o d g om 根 据蚂蚁的生活习性，提出了蚁群系统模型在能够允许的时间内找到了较好解【l2 3 】。 当然这不是精确解，而仅仅是较好的近似解。 为模拟蚂蚁系统的寻径方法，我们定义如下参数： m ：蚁群中蚂蚁的数量； 仇，：路径( f ，) 的能见度； 以：两城市i 和j 之间的距离； b i ( t ) ：t 时刻位于城市i 的蚂蚁的个数，m = 岛o ) ； 矽f 时刻在路径i 上的信息素量； 9 4 伊：蚂蚁k 在本次循环中留在路径扩上的信息量； p ：( f ) ：蚂蚁k 在，时刻由位置i 转移到位置歹的概率； 口：信息素的相对重要性( 口o ) ，称为启发式因子； ：能见度的相对重要性( o ) ，称为期望启发式因子； p ：信息素的持久因子( 0 p 1 ) ，1 p 表示信息素的衰减度又称挥发因子。 初始时刻，假设所有路径上的信息素浓度都相等，( 0 ) = c ( c 是一个常数) 。蚂 蚁k ( k = l ，2 ，妒) 在运动过程中，根据各条路径上的信息素的大小以一定的概率p 盯k ( f ) 决定转移方向，p ：( ，) 表示为： f 【( f ) 】口【( f ) 】夕 咖) = ，e 留艄切删 【0 8 歹a l l o w e d 量， 一o t h e r w i s e ( 2 1 ) a l l o w e d k _ 0 ，1 ，刃一1 - t a b u k 表示r 时刻蚂蚁j j 下一步允许选择的点。在蚁群算法 硕士学位论文蚁群算法参数优化及其应用 中，我们假设人工蚁群系统有记忆功能，用t a b u k ( k = 1 ，2 ，肌) 记录蚂蚁k 已走过 的节点，称为禁忌表也即人工蚁下一次选择路径的范围应该排除禁忌表中的节点。 当一个周期结束，进入f + 1 时刻，对路径上的信息素进行调整，调整信息素的公式 为式( 2 2 ) ： 纺o + 1 ) = p ( f ) + a q j o = 谫 k = l ( 2 2 ) 根据具体问题的不同，筋的表达形式有所不同。d o r i g om 给出了三种不同的 计算模型，分别称为蚁密系统a n t - d e n s i t ys y s t e m 、蚁量系统a n t q u a n t i t ys y s t e m 和蚁 周系统a n t c y c l es y s t e m 2 a 1 , 1 2 。 在a n t - d e n s i t ys y s t e m 模型中 f q 若蚂蚁硅本次循环中经过路径扩 缈；： 【0 否则 ( 2 3 ) 一器糊黼本等帕鼢彻 眨4 ) 公式( 2 4 ) 中，d i j 表示路径i j 的长度。 在锄t - c y c l e s y s t e m 模掣中 若蚂蚁臃本次循环中经过路径扩 其中q 是常数，表示蚂蚁循环一周所释放的总信息量。l k 表示第k 只蚂蚁在本 次循环中所走路径的长度，磊表示路径 ，的长度。在上面三种计算模型中，最后一 种蚁周系统用到了整体信息，而前两种只用到了局部信息。通常许多学者采用 a n t c y c l es y s t e m 作为基本模型讨论，因为它体现了全局范围内的最短路径，能够提 高系统搜索的收敛速度。根据一些文献研究的结果都可以反映出【l 捌5 】，这三个模 型中蚁周模型算法性能较优，下文重点对蚁周模型算法进行讨论。 2 4 蚁周模型算法伪代码 在蚁密系统和蚁量系统中，蚂蚁在建立方案的同时释放信息素，利用的是局部 9 2 蚁群算法基本原理 硕士学位论文 信息；而蚁周系统是在蚂蚁已经建立起完整的轨迹后再释放信息素，利用的是整体 信息。蚁周模型算法的实现过程可以用以下伪代码表示： l 、初始化过程 设t = - o ； t 时间计数器 n c = o 循环次数计数器 纯= c为每条路径( i j ) 设一个信息强度的初始值 纯= 0信息强度的增量初值设为0 嘞 由某中启发式算法确定，在t s p 中，f l u = l d i i t a b u k - - -在初始阶段，禁忌表为空 将m 只蚂蚁随机地放置于n 个节点上： 设置s - - - is 为禁忌表索引，将各蚂蚁的初始城市置于当前禁忌表中 f o r p 2 lt o n d o f o rk = lt ob i ( t ) d o t a b u k ( s ) = i 2 、重复n - 1 次直到禁忌表满为止 设置s = s + l f o r 净1t o n d o f o r k = lt o b i ( t ) d o 以概率p ；选择城市j ； 将蚂蚁k 移到j ； 将刚刚选择的城市j 加到t a b u k 中； 3 、f o r k = lt o m d o 根据禁忌表的记录计算l k ； f o rs = lt on - ld o 搜索蚂蚁k 的禁忌表 设( h ，1 ) = ( t a b u k ( s ) ，t a b u k ( s + 1 ) ) 缈( ，+ 功= a 缈( t + n ) + q l k 4 、对每一路径( i j ) ，根据公式( 2 2 ) 计算缈( f + 功 对于每条路径( i j ) 设缈o + 力) = o 5 、记录到目前为止的最短路径 i f n c 中变化，而其它参数利用 目前研究结果的较优值【4 5 ，6 1 。蚂蚁数m 可n t 城市规模1 5 】，期望启发式因子f l = 4 ， 信息量q = 6 0 0 ，p = 0 7 。通过多次实验得到数据表3 1 ，其中平均长度取1 0 次运行 结果的平均值。 表3 1 口对算法性能的影响 启发式因子口3 0 城市平均长度 06 5 0 1 2 0 55 8 4 2 0 3 9 1 6 5 14 7 2 9 9 8 9 6 9 9 1 54 8 6 5 5 3 3 24 9 3 2 1 2 54 9 7 17 5 7 4 6 9 34 9 0 8 8 5 6 3 55 1 8 2 7 2 3 4 4 7 4 2 9 8 7 4 55 8 4 0 4 6 1 55 4 7 3 9 8 5 66 3 0 7 1 0 6 1 7 3 参数对蚁群算法性能的影响硕士学位论文 图3 1 口与平均路径长度的关系 由图3 1 所示的实验结果不难看出，蚁群算法中启发式因子口对算法性能有较 大的影响。口过小收敛速度慢，而且容易陷入局部最优解；口值过大相当于给予信 息素作用的增强，这样将加强了局部最优路径上的正反馈性，算法会出现过早收敛 现象【2 3 乏5 1 。综合以上所述当口【1 0 ，4 o 】时，蚁群算法的综合性能较好。 3 2 期望启发式因子 蚁群算法中参数又称为期望启发式因子，在公式( 2 1 ) 中是作为能见度刁。的 幂次方。从公式不难得出的取值越大，短路径被选择的概率越大。 因此期望启发式因子罗体现了启发式信息在指导蚁群搜索过程中的相对重要 性，其大小反映了在寻优过程中先验性、确定性因素的作用强度。其值越大，则容 易选择局部的最短路径。从某种程度上来说可以加快算法的收敛性速度，但会导致 蚁群搜索最优路径的随机性减弱，易于陷入局部最优。 关于期望启发式因子的选择，本文也通过仿真实验来分析和确定其大致合理 的范围。以o l i v e r 3 0 城市问题为例，实验中仍然采用蚁群算法中的a n t c y c l e 模型。 期望启发式因子夕在集合 0 ，0 5 ，1 ，1 5 ，2 ，2 5 ，3 ，3 5 ，4 ，4 5 ，5 ，6 中变化，而其它参数利用 目前研究结果的较优值【5 】。蚂蚁数m = i n t 城市规模1 5 】，启发式因子口= l ，信息 量q = 6 0 0 ，p = 0 7 。通过多次实验得到数据表3 2 ，其中平均长度取l o 次运行结果 的平均值。 1 8 硕士学位论文蚁群算法参数优化及其应用 表3 2 对算法性能的影响 期望启发式因子平均长度 o11 6 8 0 2 5 o 5 9 3 7 7 4 9 6 15 0 6 5 8 7 2 1 54 6 2 3 8 5 5 2 4 5 9 4 3 61 2 54 6 8 6 2 0 6 34 5 9 0 7 0 6 3 54 5 9 6 3 6 9 4 4 5 8 1 6 1 5 4 5 4 7 9 9 5 1 8 5 5 1 0 5 5 3 8 611 0 3 0 3 4 图3 2 参数与平均路径的关系 。由图3 2 可见，蚁群算法中期望启发式因子对算法性能影响较大。过小， 将导致蚂蚁群陷入单纯的随机搜索，此时一般都很难找到最优解；过大( f l = 5 5 ) 时虽然产生的路径距离较短，但其收敛性能有变差的趋势。通过本文的实验数据并 考虑到其收敛速度，可以得出当【1 5 ，5 5 】时，蚁群算法的综合性能较好。 3 3 信息素挥发因子 蚁群算法中