（计算机应用技术专业论文）tsp问题中的蚁群优化算法研究.pdf

t s p 问题中的蚁群优化算法研究 摘。要 蚁群优化算法是一种仿生型的智能优化算法，具有正反馈、分布计算和启发 性搜索等特点。作为计算智能和群智能的重要分支之一，蚁群优化算法已经成功 地应用于许多组合优化问题的求解。 本文在对几种常见的蚁群优化算法进行了比较深入、系统分析的基础上，着 重讨论采用蚁群优化算法求解旅行商( t s p ) 问题。论文首先采用国际上通用的 测试问题库t s p l i b 中的几种t s p 问题作为测试对象，对几种蚁群优化算法进行 了性能比较，并对算法参数的最优化配置进行了仿真实验和分析。结果表明，对 于小规模的t s p 问题，各种算法都表现出优越的性能，能在较短时间内找到最优 解；但在大规模的t s p 问题上，现有的算法都不能在有限的时间内找到最优解， 容易陷入局部最优局面，算法过早收敛停滞。因此，有必要对算法进行改进，使 算法在中大规模的t s p 问题上有较好的性能。 针对基本蚁群算法求解t s p 问题容易出现停滞现象的缺陷，本文提出了一种 改进的蚁群算法。算法的基本思想是将信息素分为局部和全局二种不同的信息 素，在搜索过程中，对局部和全局信息素采用不同的更新策略和动态的路径选择 概率，使得在搜索的中后期能更有效地发现全局最优解。利用t s p l i b 的数据进 行的实验结果表明，改进后的算法对于中大型t s p 问题，具有更好的发现最优解 的能力。 本文引入了解的性能分布的概念，通过对算法求解t s p 的解的性能分布分析 和运行时间分布分析，得出了一些有意义的结论：算法找到最优解的概率是随着 运行时间的增加而增大的；算法运行前期改进解的性能速度较快，但后期明显减 慢：可以通过重启策略获得与最优解距离在一定范围内的解。 关键词：旅行商问题；蚁群优化；信息素 a b s t r a c t a n tc o l o n y o p t i m i z a t i o n( a c o )i s ab i o n i c i n t e l l i g e n c ea l g o r i t h mf o r o p t i m i z a t i o n ，w h i c h h a st h ec h a r a c t e r i s t i c so f p o s i t i v e f e e d b a c k ，d i s t r i b u t i n g c o m p u t i n g a n dh e u r i s t i cs e r a c h a sa n i m p o r t a n t b r a n c h o fc o m p u t a t i o n a l i n t e l l i g e n c ea n ds w a n i ii n t e l l i g e n c e ，a c oh a v eb e e ns u c c e s s f u l l ya p p “e dt os o l v e m a n yc 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 t h i sp a p e rm a k e sa ne x h a u s t i v e 粕ds y s t e m a t i cs t u d yo fs o m et ) ，p i c a la c o a l g o r i t h m s ，m a i n l yd i s c u s su s i n ga c o t os o l v et s p t h r o u g hu s i n gt s p l i ba st h e b e n c h m a r k ，s o m ea n a l y s e s 距dr e m a r k sa r em a d et oc o m p a r et h ep e r f o m a n c co f s o m et y p i c a la o oa l g o i l i t h m s ，a n dt h eo p t i m u mp a r a m e t c rs e t t i n g sa r et e s t e da n d a n a l y s e d t h er e s u l t so fe x p e r i m e n t ss h o wt h a tt h ea c oa l g o “t h m sh a v eh i g h p e r f o 皿a n c ef o rs o l v i n gs m a ut s p c a nf i n dt h eo p t i m a ls o i u t i o ni ns h o r tt i m e ，b u tf o r t h el a r g et s p t h ec u r r e n ta c oa l g o r i t h m sc 锄tf i n dt h eg l o b a lo p t i m a ls o l u t i o ni na l i m i t e dt i m e ，i tc o u l de a s i l yr e a c ht h es t a g n a t i o np h a s ea n dg e tt h el o c a lo p t i m u m s o i ti sn e c e s s a r yt oi m p r o v et h ec u r r e n ta c oa l g o r i t h m s ，w h i c hw o u l dh a v eb e t t e r p e r f o m a n c ef o rs o l v i n gl a 唱et s p i no r d e rt oc o 仃e c tt h es h o n c o m i n go ft h eb a s i ca c o e a s i l yg e t t i n gs t u c k ，t h i s p a p e rp r o p o s e d a n i m p r o v e da c oa l g o r i t h m ，n a m e l ym p a s t h eb a s i ci d e a i s ：d i v i d i n gt h ep h e r o m o n e si n t ol o c a lp h e r o m o n e sa n dg l o b a lp h e r o m o n e s ，a n dt h e n u p d a t i n gp h e r o m o n e su s i n gd i f f b r e n ts t r a t e g i c s a n d d y n a m i cp a t h s e l e c t i o n p r o b a b i l i t yd u r i n gs e a r c h i n gp r o c e s s ，i tc a ne f f i c i e n t l yf i n dg l o b a lo p t i m a ls o l u t i o ni n t h el a s ts e a r c h i n gp e r i o d m a n ye x p e r i m e n t sb a s e do nt h ed a t ao ft s p l i bs h o wt h e i m p r o v e da l g o r i t h mh a sb e t t e ra b i l i t yt of i n dg l o b a lo p t i m a is o l u t i o ni nl a r g et s p t h i sp a p e rp r o p o s e dt h ec o n c e p to fs o l u t i o np e r f 0 m a n c ed i s t r i b u t i o n ，g i v i n gt h e p e r f o m a n c ea n a l y s i s o fm p a sf o r s o l v i n g t s pt h r o u g ht h e t 1 l n n i n g t i m e d i s t r i b u t i o n so fm p a sa n dt h es o l u t i o np e r f o m a n c ed i s t r i b u t i o n so fm p a s ，o b t a i n s s o m ep r a c t i c a lc o n c i u s i o n st h a tm a yg i v eg u i d a n c et os o i v ct h et s p t h ep r o b a b i i i t y o ff i n d i n go p t i m a ls o l u t i o ni si n c r e a s i n ga st h er u n n i n gt i m eb e c o m e sl o n g e r ；t h e s p e e do fi m p r o v i n gs o l u t i o ni sf a s ti nt h ee a r l i e rp h a s eb u tb e c o m e ss l o we v i d e n t l y i nt h el a t e rp h a s e ；i tc a nr e d u c et h er u n n i n gt i m ea n di n c r e a s et h ep r o b l b i l i t yo f o b t a i n i n go p t i m a ls o l u t i o nb yw a y o fr e s t a r t i n gt h ea l g o r i t h m k e yw o r d s ：t r a v e l i n gs a l e s m a np r o b l e m ；a n tc o l o n yo p t i m i z a t i o n ；p h e r o m o n e t s p 问题中的蚁群优化算法研究 插图索引 图2 1 蚂蚁搜索路径示意图1 1 图4 1 五城市t s p 示意图3 2 图5 1e i l 5 1 t s p 的运行时间分布图4 2 图5 2l i l l 3 1 8 t s p 运行时间分布图4 2 图5 3p c b 4 4 2 t s p 的运行时间分布图4 3 图5 4m p a s 求解l i n 3 1 8 t s p 所得解的性能分布图4 4 图5 5m p a s 求解p c b 4 4 2 t s p 所得解的性能分布图4 5 u l 高校教师硕士学位论文 附表索引 表3 1q 的不同取值求解结果2 0 表3 2b 的不同取值求解结果2 l 表3 3q 和b 不同的组合求解结果2 l 表3 。4p 的不同取值求解结果2 2 表3 5m 的不同取值求解结果2 2 表3 6g n 的不同取值求解结果2 3 表3 7a c 0 算法求解e i1 5 1 t s p 结果。2 4 表3 8a c o 算法求解l i n 3 1 8 t s p 结果2 4 表3 9 c o 算法求解p r 2 3 9 2 t s p 结果2 4 表3 1 0 候选列表长度比较2 6 表3 1 1 未添加局部搜索求解1 i n 3 1 8 t s p 结果2 7 表3 1 2 添加局部搜索求解l i n 3 1 8 t s p 结果2 7 表5 1 求解e i l 5 1 t s p 的结果4 6 表5 2 求解l i n 3 1 8 t s p 的结果4 6 表5 3 求解l i n 3 1 8 t s p 的结果4 7 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：旁眷 日期：2 。_ 字年；月岁汐日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密日。 ( 请在以上相应方框内打“ ) 作者签名：彭誊 日期：2 。，占年弓月岁。日 刷醴辄曾弋嗍锄日 高校教师硕十学位论文 1 1 选题背景及意义 第1 章绪论 t s p 是一个典型的组合优化问题，而且是一个n p 完全难题，是众多领域内出 现的优化问题的集中概括和简化形式，是各种启发式算法的间接比较标准，如果 一个算法能在t s p 上取得较好的性能，则往往在其他组合优化问题上也能取得好 的性能。因此，快速、有效地解决t s p 有着重要的理论价值和应用价值。 许多领域的优化问题都可以归结为t s p 问题，例如，电路板钻孔问题，交通 线路规划问题，超大规模集成电路制造问题、车辆调度问题、网络路由问题等等。 总之，凡是可以抽象成为遍历所有城市一次且仅一次，求代价最小的路径的问题， 都可以当作t s p 问题来解决。以电路板钻孔问题为例，在文献中描述了一个有 1 7 0 0 0 个点的电路板钻孔问题，要解决的问题就是如何布线才能节约材料达到节 省成本的目的，这个实例就是t s p 的一个应用例子。 同实用价值相比，t s p 问题的理论意义也非常重大t s p 问题事实上是作为 所有组合优化问题的范例而存在的，已经成为测试新算法的标准问题。这是因为， t s p 问题展示了组合优化的所有方面：从概念上来讲非常简单，但求解难度很大 的。如果针对t s p 问题提出的某种算法能够取得比较好的计算效果，那么对其进 行修改，就可以应用于其它类型的组合优化问题并取得良好的效果。基于上述原 因，t s p 问题吸引了许多不同领域的学者进行研究，包括数学、运筹学、物理、 生物和人工智能等领域，t s p 问题已成为当前研究的热点问题。 蚁群优化算法比1 是求解t s p 从多算法中取得较好性能的一种启发式算法，自 创立十多年来，无论在算法理论还是在算法应用方面都取得了很多突破性进展， 已成为一个前沿性的热点研究领域，其应用范围涉及到各个优化领域，取得了许 多重要的成果。蚁群优化算法的产生时间不长，在这一领域还有一些问题需要进 一步研究和解决，但是理论研究和实际应用表明它是一种很有前途的算法。随着 人类认识的进步和社会发展的加速，仿生智能及最优化系统理论将越来越成为科 学认识和工程实践的有力工具。因此，关于蚁群优化算法理论及其应用的研究必 将是一个长期的研究课题，具有更加广阔、更加引人注目的发展前景口1 。 蚁群优化算法的应用研究领域是非常广泛的，本文研究的是应用蚁群优化算 法来求解t s p 问题，比较、分析蚁群优化算法求解t s p 的性能并提出改进的算法。 选择求解t s p 作为研究蚁群优化算法的平台的原因主要有：t s p 是一个涉及多种 应用领域的n p 难问题，但同时也是一个比较易于理解的问题，易于使用蚁群优 化算法来求解。t s p 还是新算法思想的标准测试平台，因为一个算法能在t s p 上 表现良好的性能往往证明该算法在组合优化领域同样具有良好的性能，因为t s p 是组合优化领域内经典的问题。 t s p 问题中的蚁群优化算法研究 1 。2t s p 问题 许多科学和工程的问题都可以归结为最优化问题，易于表达但难于求解的组 合优化问题始终是研究中的一个热点，组合优化问题就是找出一组离散变量的 值，使得所给定的目标函数的解达到最优，其数学模型的一般描述是h 1 卿厂( x ) ，j e ， 其中x 为决策变量，f ( x ) 为目标函数，f 为可行域，f 中的任何一个元素称为 该问题的一个可行解，满足厂o ) = m i i l 矿( 力fx f ) 的可行解工称为该问题的最 优解，对应的目标函数称为最优值。 旅行商问题( t r a v e l i n gs a l e s 腿np r o b l e m t s p ) 是一个经典的组合优化问 题，由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应 用，长期以来吸引了国内外众多学者对它进行研究。 1 2 1t s p 问题的定义 直观地说，t s p 问题就是指一位商人，从自己的家乡出发，希望能找到一条 最短的路径，途经给定的城市集合中的所有城市，最后返回家乡，并且每个城市 都被访问一次且仅一次叩1 。 形式上，t s p 问题可以用一个带权完全图g = ( n ，a ) 来描述，其中n 是城市 的结点集合，a 是所有边的集合。每一条边( i ，j ) a 都分配一个权值( 长度) d 它代表城市i 和j 之间的距离。t s p 的目的就是寻找图中的一条具有最小成 本值的汉密尔顿回路。汉密尔顿回路是指一条访问图g 中的每一个结点一次且仅 一次的闭合路径。这样，t s p 的一个最优解就对应于结点标号为 1 ，2 ，3 ，n ) 的一个排列，并且使得长度最小。f ( 兀) 的定义为璐3 ： 型 厂( 万) = 以( 咖( 件1 ) + 厶( 咖( 1 ) 一般地，t s p 的数学模型描述为川： m i i l 略而 j j j = l ，f = l ，k ，刀 j = i 而= 1 ，j f = l ，2 ，刀 f 宣i 矗 0 ，1 ) ，f ，_ ，= l ，2 ，j l ，f ， ( 1 1 ) ( 1 2 ) ( 1 3 ) ( 1 4 ) 式( 1 1 ) 要求距离之和最小，式( 1 2 ) 要求商人从城市i 恰好出来一次，式( 1 3 ) 2 高校教师硕士学位论文 要求商人恰好走进城市j 一次，式( 1 2 ) 和( 1 3 ) 合起来表示每个城市恰好经过一 次，式( 1 4 ) 中的决策变量h = l 表商人行走的路线包含从城市i 到城市j 的路径， = 0 表示商人没有选择走这条路。 1 2 2t s p 问题的研究进展 t s p 作为一个经典的组合优化问题历史很久，最早的描述呻1 是欧拉研究的 骑士周游问题，也就是对于国际象棋棋盘中的6 4 个方格，走访6 4 个方格一次且 仅一次，并且最终返回到起始方格。早期的研究者使用精确算法求解该问题，但 是，随着问题规模的增大，精确算法将变得不可能，因为所花的时间代价太大。 因此，在后来的研究中，研究者重点使用近似算法或启发式算法对t s p 进行研究， 并且结合多种方法成为研究的主流。 求解t s p 的方法有很多，可以归纳为以下几种：( 1 ) 使用各种纯数学的方法 构造时间复杂度为多项式的近似算法。( 2 ) 使用启发式算法和迭代算法。( 3 ) 使 用遗传算法、蚁群算法、模拟退火算法、粒子群算法和神经网络等仿自然算法 由于遗传算法、蚁群算法和粒子群算法具有较强的群体搜索能力，但同时又存在 可能陷入局部最优的问题，因而研究者通常将局部搜索算法和这些算法相融合构 造出更高效的混合算法，采用多种方法相结合的混合算法是求解t s p 的一个有效 途经和方向。 由于t s p 具有广泛的实际应用背景，在未来相当长的时间内，t s p 仍将是算 法研究领域的一个热点问题。 1 2 3t s p 问题的求解方法概述 对于组合优化问题的求解存在两种类型的方法：精确性算法和近似算法。 精确性算法可以保证找到问题的最优解，而且对于组合优化问题实例来说， 算法都可以在一个与问题有关的运行时间内得到最优解，但可能时间代价太大。 对于n p 难问题，在最差情况下精确性算法需要指数级的时间来寻找最优解，时 间代价太大了。例如，对于规模比较小的解决背板配线的问题，在一台8 0 0 m h z 的p e n t i u m i p c 上运算大约需要1 8 0 小时的时间婚3 。随着问题规模的增大，用精 确性算法求解变得不太现实了。 如果不能在可接受的时间内得到最优解，可行的方法就是降低最优值的精度 以换取计算效率的提高。近似算法就是寻求在相对较低的计算成本下，例如在多 项式时间内找到接近最优解的近似解，但不保证找到最优解，牺牲找到最优解的 保证作为代价。蚁群优化算法就是一种近似算法，目前性能最好的蚁群优化算法 解决背板配线的问题只需要1 0 秒钟哺1 。 几种典型的解决t s p 问题的算法列举如下： 倦p 问题中的蚁群优化算法研究 1 2 3 1 穷举法 从理论上讲是可以通过穷举法解决t s p 问题的，只要搜索全部的路径，一定 能够找到最短的一条。也就是说，使用穷举法一定能找到最优解。但是，t s p 问 题的搜索空间会随着城市数n 的增加而急剧增加，所有路径的组合数是 ( n 一1 ) ! 2 。那么，5 个城市的t s p 问题对应1 2 个方案，1 0 个城市则对应1 8 1 4 4 0 个方案，l o o 个城市就要对应4 6 6 6 3 1 0 1 5 5 个方案。使用穷举法在如此巨大 的搜索空间中寻求最优解，即使是速度很快的计算机，也要花费很长的运行时间 去求解。如果城市规模更大，则用穷举就变得不现实了。 1 2 3 2 线性规划算法 线性规划算法是求解t s p 比较早的一种算法，主要是采用整数规划中的割 平面法，即先求解模型中由前二个约束构成的松驰l p 问题，然后通过增加不等 式约束产生割平面，逐渐收敛到最优解。但是，由于该方法在寻找割平面时常常 要凭借经验，因此后来很少作为一般方法使用1 。 1 2 3 3 分支定界算法 分支定界法是一种应用范围很广的搜索算法，它通过有效的约束界限来控 制搜索进程，使之能向着状态空间树上有最优解的分支推进，以便尽快找出一个 最优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分 支定界法。分支定界法对于较大规模的问题并不十分有效口1 。 1 2 3 4 模拟退火算法 模拟退火算法阳1 利用固体物质的退火过程与组合优化问题之间的相似性， 是基于迭代求解策略的一种随机寻优算法。s a 算法由某一较高初温开始，结合具 有概率突跳特性的m e t r o p o l i s 抽样策略在解空间中随机寻找目标函数的全局最 优解，伴随温度参数的不断下降重复抽样过程，最终得到问题的全局最优解。s a 通过以一定的概率接受较差解来避免陷入局部最小。 1 2 3 5 遗传算法 遗传算法是一种并行、随机和自适应的进化算法，其思想基于自然界的遗传 原理。它将问题的求解表示成“染色体刀的适者生存过程，通过“染色体 群的 一代代不断进化，包括复制、交叉和变异等操作，最终收敛到“最适应环境的个 体，从而求得问题的最优解或满意解阳1 。 1 2 3 6 神经网络优化算法 神经网络优化算法n 们就是利用神经网络中神经元的协同并行计算能力来构 造的优化算法，它将实际问题的优化解与神经网络的稳定状态相对应，把实际问 4 高校教师硕上学位论文 题的优化过程映射为神经网络系统的演化过程。h o p f i e l d 网络通过在网络中引 入能量函数以构造动力学系统，并使网络的平衡态与能量函数的极小解相对应， 从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。 利用h o p f i e l d 网络对t s p 求解时，首先将问题的合法解映射为一个置换矩阵， 并给出相应的能量函数，然后将满足置换矩阵要求的能量函数的最小值与问题的 最优解相对应1 。 1 2 3 7 禁忌搜索算法 禁忌搜索是一种启发式搜索技术，它是对局部邻域搜索的一种扩展，是一种 全局逐步寻优算法，是对人类智力过程的一种模拟。t s 算法通过引入一种灵活的 存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌 的优良状态，进而保证多样化的有效探索以最终实现全局优化1 。 1 2 3 8 蚁群优化算法 蚁群优化算法是一种新型的启发式算法，由意大利学者m d o r i g o 等人口1 在9 0 年代首先提出。通过研究蚂蚁行为，发现一群互相协作的蚂蚁能够找到食 物源和巢之间的最短路径。蚂蚁间相互协作的方法是它们在运动过程中，能够在 所经过的路径上留下一种称为信息素的物质进行信息传递，而且蚂蚁在运动过程 中能够感知信息素这种物质，并以此指导蚂蚁的运动方向，因此由大量蚂蚁组成 的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则 后来者选择该路径的概率就越大。该算法已经成功地解决诸如t s p 等多种组合优 化问题，应用范围非常广泛。 1 2 3 9 各种方法的优缺点及比较 穷举法、线性规划算法、分支定界算法属于精确性算法，对于解决较大规模 的t s p 问题所花的时间代价太大。 遗传算法的优点是将问题参数编码成染色体后进行优化，而不针对参数本 身，从而不受函数约束条件的限制：搜索过程从问题解的一个集合开始，而不是 单个个体，具有隐含并行搜索特性，可大大减少陷入局部最小的可能。遗传算法 的主要缺点是对于结构复杂的组合优化问题，搜索空间大，搜索时间比较长， 往往会出现早熟收敛的情况；对初始种群很敏感，初始种群的选择常常直接影响 解的质量和算法效率u 剔，实际应用时易出现收敛性能差的缺点。 模拟退火法具有质量高、初值鲁棒性强、通用易实现的优点，所得解的好坏 与初始状态、温度函数等都有一定的联系，降温较快的效果不一定很好，效果好 的，其降温过程又极其缓慢。但由于该方法适用范围广，并可人为控制迭代次数， 反复求解，因此具有很强的实用性，但模拟退火法可能优化时间较长。 禁忌搜索算法一种局部搜索能力很强的全局迭代寻优算法，但对初始解的依 t s p 问题中的蚁群优化算法研究 赖性较强，好的初始解有助于搜索很快地达到最优解，而较坏的初始解使搜索 很难或不能够达到最优解。搜索过程是串行的迭代搜索，不是并行搜索。 h o p f i e l d 神经网络优化算法具有规范、快速等优点，但易于收敛到非法解 或局部极小解，以及算法对模型参数和初始条件具有很强的依赖性，不能很好地 求解t s p ，存在严重的不稳健性，其优化性和鲁棒性比较差。 蚁群优化算法利用正反馈原理，在一定程度上可以加快进化过程，而且是 一种本质上并行的算法，个体之间不断进行信息交流和传递，有利于发现较好 解。但是蚁群优化算法也具有速度慢、易陷入局部最优等缺点，算法容易过早停 滞收敛。 蚁群优化算法是一种新型的启发式算法，尽管目前对a c 0 的研究只有十几 年，理论基础比较薄弱，一些思想尚处于萌芽状态，但初步的研究结果已显示出 该算法在求解复杂优化问题方面的优越性。虽然a c 0 严格的理论基础尚未成熟， 有关研究仍停留在实验探索阶段，但从当前的应用范围和效果来看，这种模仿自 然界的启发式算法具有十分光明的前景本文重点研究蚁群优化算法求解t s p 问题。 1 3 本文所做的的工作 本文主要研究了蚁群优化算法求解t s p 这个有意义的n p 难问题。对几种蚁 群优化算法进行了分析和研究，并提出了一种基于多信息素的蚁群算法。本文主 要工作包括如下内容： l 、阐述了蚁群优化算法求解t s p 问题的基本原理，并介绍了几种常见的蚁 群优化算法。 2 、对几种常见的蚁群优化算法进行了比较探入、系统的分析和研究，并采 用国际上通用的测试问题库t s p l i b 中t s p 问题作为测试对象，通过实验得出了 有关参数的最佳设置范围，对蚁群优化算法中初始化参数对其性能的影响作了初 步探讨。对几种蚁群优化算法求解t s p 问题进行了性能比较和分析。 3 、对蚁群优化算法的改进策略一候选集合策略和添加局部搜索策略作了实 验研究，从实验角度验证这些改进策略是可以提高算法求解质量的。 4 、对基本蚁群算法提出新的改进算法一基于多信息素的蚁群算法，并进行 仿真实验，以若干t s p 问题作为测试标准，通过仿真实验，表明了本文提出的改 进算法相对于基本蚁群算法的优越性。 本文的主要结构如下： 第l 章简单介绍t s p 问题的定义、研究意义、研究进展、求解t s p 问题的方法。 第2 章概述了蚁群优化算法产生的背景、基本原理、研究进展，并介绍了几种 求解t s p 问题的蚁群优化算法。 高校教师硕士学位论文 第3 章对蚁群优化算法求解t s p 进行仿真实验，得出使算法具有较好性能的参 数设置范围，以便对使用算法解决实际问题有一定的指导意义。对几种蚁群算法 求解t s p 问题进行了性能比较和分析。 第4 章针对蚁群优化算法在求解中大规模t s p 时的不足，提出改进方法一基于 多信息素的蚁群算法。 第5 章对改进算法求解t s p 进行了实验，从运行时间分布和解的性能分布对算 法的性能进行了分析，得出了一些有意义的结论。对改进算法与常见几种蚁群优 化算法求解t s p 作了实验比较，验证了改进算法的有效性。 结论对本文进行总结，指出不足和指明了继续研究的方向。 7 t s p 问题中的蚁群优化算法研究 第2 章蚁群优化算法概述 本章介绍了蚁群优化算法的研究现状，阐述了算法求解t s p 问题的基本原 理，介绍了最早的蚁群优化算法一蚂蚁系统及后续的几种常见的改进算法。 2 1 引言 蚂蚁是日常生活中常见的一种昆虫，单只蚂蚁虽然很简单，但蚂蚁构成的群 体能完成远超越其个体能力的复杂任务，比如最短路径的搜索。研究表明，蚂蚁 在觅食走过的路径上释放一种特有的分泌物一信息素( p h e r o m o n e ) ，短路径上信 息素的积累速度要比长路径的快，而蚂蚁总是沿着信息素浓度最强的路径行走， 所以蚂蚁最终会找到从蚁穴到食物源之间的最短路径 蚂蚁能寻找最短路径的行为模式启发了计算机科学家建立新型算法的灵感。 意大利学者m d o r i g o 根据蚂蚁能寻找最短路径的原理，于1 9 9 1 年提出了第一 个蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c 0 ) 模型一蚂蚁系统( a n ts y s t e m ， a s ) ，用于求解旅行商问题( t s p ) 。随后，m d o r i g o 等人从两方面对a s 进行了 发展，一方面将a s 不断应用到各种具体问题之中；另一方面又针对a s 中存在的 问题进行了改进，提出新的算法模型。 蚁群优化算法是一种源于大自然中生物世界的新的仿生进化算法，具有很强 的鲁棒性，从提出到现在只有短短的十几年时间，但其在离散型组合优化问题中 表现很突出，引起了广大学者的关注。自从蚁群优化算法在著名的t s p 问题和工 件排序问题上取得成效以来，已陆续应用到其它问题领域中，如：二次分配问题， 广义分配问题，图着色问题，大学课程时间表，通讯网络中的负载问题，网络路 由选择，车辆调度问题，机器人视线规划等等，表现出良好的性能，显示出其强 大的生命力和美好的发展潜力。 2 2 研究现状 受蚂蚁群体在觅食过程中总能找到一条从蚁巢到食物源的最短路径的启发， 意大利学者m d o r i g o 于1 9 9 1 年提出了一种新型的智能优化算法一一蚂蚁系统 ( a s ) 并成功用于求解t s p 他1 。实验结果表明a s 算法具有较强的鲁棒性和发现 较好解的能力，但也存在收敛速度慢、易出现停滞现象的缺陷。该算法的出现引 起了学者们的关注，并陆续引出了一些改进算法。m d o r i g o 等朝提出了精英蚂 蚁系统( e a s ) ，这是对基本a s 的第一次改进，它的思想是对算法从开始到目前 为止找到的最优路径释放额外的信息素。lmg a m b a r d e l l a ，m d o r i g o 提出了 a n t q 算法，该算法用伪随机比例状态转移规则替换a s 算法中的随机比例选择 8 高校教师硕士学位论文 规则，从而使a n t q 算法在构造解的过程中能够更好地保持知识探索与知识利用 之间的平衡，蚁群算法的关键是找到探索和利用之间的平衡，避免过早停滞。 m d o r i g o 等人u 6 1 在a n t q 的基础上提出了蚁群系统( a c s ) ，该算法作为a n t q 的特例实现起来更为简单，但在求解t s p 时具有相同的性能。s t n t z l e 和h o o s n 6 1 8 1 提出了最大最小蚂蚁系统( m m a s ) ，该算法的主要特点是对信息素限制在一个区 间内，避免某条路径上信息素过多算法出现停滞现象。b u l l n h e i m e r 等n 盯提出了 基于排序的蚂蚁系统( r a s ) ，该算法在完成一次迭代后，将蚂蚁所经路径的长度 按从小到大的顺序排列，只有排在前面的若干只蚂蚁才能释放信息素。c o r d 6 n 等人心们提出了最好最差蚂蚁系统( b w a s ) ，该算法主要特点是对于当前迭代的最 差蚂蚁构建的路径中的边，如果该边不属于至今最优路径，则信息素更新时要减 去该边的部分信息素。以上改进算法的性能都要比a s 算法好，但在求解大规模 t s p 问题的解时发现最优解的能力较差。 国内近年来有不少学者开始关注蚁群优化算法，目前对算法的研究主要是对 算法提出改进和应用到具体领域方面。吴庆洪等他通过向基本蚁群算法引入变 异机制，提出了具有变异特征的蚁群算法。吴斌与史忠植瞳2 1 首先在蚁群算法的 基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并 行策略的分段算法相结合，提出了一种基于蚁群算法的t s p 分段求解算法。王颖 和谢剑英乜3 1 通过自适应地改变算法的挥发度等系数，提出一种自适应的蚁群算 法以克服陷于局部最小的缺点。黄国锐等心们等提出基于信息素扩散的蚁群算法， 该算法通过建立信息素扩散模型，使相距较近的蚂蚁之间能更好地进行协作。覃 刚力和杨家本瞳5 1 根据人工蚂蚁所获得解的情况，动态地调整路径上的信息素， 提出了自适应调整信息素的蚁群算法。柯良军和冯祖仁等陷刚提出有限级信息素 蚁群算法，将信息素分成有限个级别，通过级别的更新实现对信息素的更新。 随着对蚁群优化算法研究的不断深入，m d o r i g o 等人心7 2 盯提出了蚁群优化 元启发式( a n tc o l o n yo p t i m i z a t i o nm e t ah e u r i s t i c ，简称a c o m h ) 这一求 解复杂问题的通用框架。a c o m h 为蚁群优化算法的理论研究和算法设计提供了 理论依据。在a c o 的收敛性方面，wjg u t j a h r 心9 圳作了开创性工作，提出了基 于图的蚂蚁系统元启发式( g b a s ) 这一a c o 通用模型，该模型在一定的条件下能 以任意接近1 的概率收敛到最优解。文献口们证明了与模拟退火相似的结果，即 算法能以概率1 收敛到最优解。t h o m a ss t n t z l e 和m d o r i g o 在忽略启发信息 的影响下，对彳岱，。，这类算法的收敛性进行了证明，其结论可以推广到两类证 明是最成功的a c o 算法一一m m a s 和a c s 。 对a c 0 的应用研究非常活跃，第一个a c 0 算法蚂蚁系统就是用于解决t s p 问 题的。由于t s p 是诸多领域内出现的多种复杂问题的集中概括和简化形式，且是 一个n p 难问题，已成为各种启发式算法的间接比较标准。因此，快速、有效地解 9 t s p 问题中的蚁群优化算法研究 决t s p 有着重要的理论价值和极高的实际应用价值，a c o 算法的大部分成果都集 中在t s p 上。 对于其他领域的应用，vm a n i o z z o 2 1 等人将蚂蚁系统应用于指派问题， g a m b a r d e l l a b 3 1 发表了用蚁群系统求解指派问题的文章。目前，蚁群算法已是求 解指派问题较为有效的算法之一。 ac 0 1 0 r n i 等入口钉将蚂蚁系统应用于车间作业调度问题，但与其他方法比较 没有优势，未能显示出蚁群算法的优势。但在用删a s 算法求解流动车间调度问 题时，实验结果显示姗a s 算法优于模拟退火和禁忌搜索算法，显示出蚁群算法 的优势。 c o s t a 和h e r z 口副提出增强的a s 算法，并将其应用于分配类型的问题，该算 法在求解图的着色问题时，得到了完全可以和其他启发式算法相媲美的结果。 b u l l n h e i m e r 等叫用基于排序的蚂蚁算法来求解车辆路径问题，取得了和最 优解非常相近的结果。g a m b a r d e l l a 对车辆路径问题的研究，对一些基准问题 的最优解有所提高，得出了以往没有的最优解。 在通讯领域( 特别是解决网络路由问题) 方面，d ic a r o 和m d o r i g o 已在 文献口引中将a c o 应用于网络路由问题，并称这种算法为a n t n e t ，并发展到用a c o 算法解决移动网络问题。 除了各种组合优化问题之外，a c o 算法还在函数优化口9 。、系统辨识引、机器 人路径规划、分类规则挖掘h 引、综合布线设计h 引、交通规划h 4 1 等领域取得了 令人注目的成果，a c 0 的应用领域越来越广泛。 蚁群优化算法是一种新型的启发式算法，尽管目前对a c o 的研究刚刚起步， 一些思想尚处于萌芽状态，但初步的研究结果已显示出该算法在求解复杂优化问 题方面的优越性。虽然a c o 严格的理论基础尚未奠定，国内外的有关研究仍停留 在实验探索阶段，但从当前的应用效果来看，这种模仿自然生物的启发式算法具 有十分光明的前景。 2 3 蚁群优化算法的基本原理 根据仿生学家的研究结果，蚂蚁能够找到蚁巢与食物之间的最短路径，其原 理在于：蚂蚁在所经过的路径上留下一种称为信息素的挥发性分泌物。蚂蚁在觅 食过程中能够感知这种物质的存在及其浓度，并以此来指导自己的运动方向，倾 向于朝着这种物质浓度高的方向移动，即选择该路径的概率与当时这条路径上该 物质的浓度成正比。信息素浓度越高的路径，选择它的蚂蚁就越多，则在该路径 上留下的信息素的浓度就更大，而浓度大的信息素又吸引更多的蚂蚁，从而形成 一种正反馈。通过这种正反馈，蚂蚁最终可以发现最佳路径，导致大部分的蚂蚁 都会走此路径。 l o 高校教9 币硕士学位论文 下面用一个形象化的图示( 如图2 1 所示) 来说明蚂蚁群体的路径搜索原理 和机制m 1 。 图2 1 蚂蚁搜索路径示意图 假定障碍物的周围有两条道路可从蚂蚁的巢穴到达食物源：n e s t a b d f o o d 和n e s t a c d f o o d ，分别具有长度4 和6 。蚂蚁在单位时间内可移动一个单位长 度的距离。开始时所有道路上都未留有任何信息素。 在t = 0 时刻，2 0 只蚂蚁从巢穴出发移动到a ，它们以相同概率选择左侧道路 或右侧道路，因此平均有1 0 只蚂蚁走左侧，1 0 只走右侧。 在t = 4 时刻，第一组到达食物源的蚂蚁将返回，此时第二组蚂蚁到达c d 中 点处。 在t = 5 时刻，两组蚂蚁将在d 点相遇。此时b d 上的信息素和c d 上的相同， 因为各有1 0 只蚂蚁选择了相应的道路，从而有5 只返回的蚂蚁将选择b d 而另5 只将选择c d ，第二组蚂蚁将继续向食物源方向移动。 在t = 8 时刻，前5 只蚂蚁将返回巢穴，此时在a e 中点处、c d 中点处及b 点 上各有5 只蚂蚁。 在t = 9 时刻，前5 只蚂蚁又回到a 并有再次对往左还是往右的选择。 这时，a b 上的信息素轨迹数是2 0 而a c 上是1 5 ，因此将有较多的蚂蚁选择 往左，从而增强了该路径上的信息素。随着该过程的继续，两条道路上的信息素 数量的差距将越来越大，直至大多数蚂蚁都选择了最短路径。正是由于一条道路 要比另一条道路短，在相同的时间区间内，短的路径会有更多的机会被选择。 蚁群算法不需要任何的先验知识，最初只是随机地选择搜索路径，随着对解 t s p 问题中的蚁群优化算法研究 空间的“了解一，搜索变得有规律，并逐渐逼近直至最终达到全局最优解。蚁群 算法对搜索空间的。了解机制主要包括三个方面： ( 1 ) 蚂蚁的记忆。一只蚂蚁搜索过的路径下次搜索时就不会再被选择，由 此在蚁群算法中建立禁忌表来进行模拟。 ( 2 ) 蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上释放一种叫做 信息素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样 信息素就成为蚂蚁之问进行通信的媒介。 ( 3 ) 蚂蚁的集群活动。通过一只蚂蚁的运动很难找到到达食物源的最短路 径，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在 路径上留下的信