（应用数学专业论文）蚁群算法的改进及其在车辆路径问题中的应用.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。 作为一个重要的科学分支，它一直受到人们的广泛重视，并在工业生产、经济 等领域得到迅速推广和应用。鉴于实际工程优化问题的复杂性、约束性、非线 性、建模困难等特点，寻求一种适于大规模并行且具有智能特性的优化算法已 成为有关学科的一个主要研究目标和引入注目的研究方向。 2 0 世纪8 0 年代以来，通过模拟或揭示某些自然现象而产生了一些新颖的启 发式智能算法，如遗传算法，模拟退火算法、禁忌搜索算法，蚁群算法等。这 些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了全局优化领 域的研究热潮，尤其是近十多来发展起来的蚁群算法。 蚁群算法( a n tc o l o n yo p t i n l i z a t i o n 简称a c o ) 是意大利学者m d o r i g o 等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。蚁群算法采 用分布式并行计算机制，易与其他方法结合，具有较强的鲁棒性等特点。因此， 蚁群算法的研究无论是理论上还是应用上，都有较高的价值。 本文主要研究了蚁群算法的改进及应用，主要研究内容如下： ( 1 ) 分析基本蚁群算法的原理与模型，实现步骤，算法特点，通过实验分析 了基本蚁群算法中几个关键参数的选择。 ( 2 ) 针对基本蚁群算法收敛速度慢和易陷入局部最优等缺点，提出一种改进 的蚁群算法。该改进算法借鉴最大最小蚁群算法中利用限制信息素范围 的思想，这样可以抑制由于最短路径和最长路径信息量差距加剧而引起 的停滞现象，同时引入局部信息素更新及局部搜索策略，有效抑制早熟 现象，加快了算法的求解速度，在此基础上通过改进信息素的全局更新 机制，使算法能够更快地收敛到全局最优解，通过三种t s p 问题的测试， 结果表明该算法的搜索能力和性能都得到显著提高。 ( 3 ) 对蚁群算法在车辆路径问题中的应用进行研究。 关键词：蚁群算法；组合优化；旅行商闽题；车辆路径问题 西南交通大学硕士研究生学位论文第l l 页 a b s tr a c t o p t i m i z a t i o nt e c h n o l o g yi sat e c h n o l o g yb a s e do nm a t h e m a t i c sa n d a p p l i e dt oa l lk i n d so fo p t i m i z a t i o ns o l u t i o nt oe n g i n e e r i n gp r o b l e m s a sa ni m p o r t a n tb r a n c ho fs c i e n c e ，i ti sa l w a y sa t t a c h e dw i d ei m p o r t a n c e t oa n dr a p i d l ye x t e n d e da n da p p l i e dt oi n d u s t r ya n de c o n o m y ，a n ds oo n b e c a u s eo fc o m p l i c a t i o n ，l a r g e s c a l e ，n o n i i n e a ra n dd i f f i c u l t i e so f m o d e l i n gi ne n g i n e e r i n go p t i m i z a t i o n ，i th a sb e e na m a i nr e s e a r c ho b j e c t a n dd i r e c t i o nt h a tf i n d sa ni n t e l l i g e n ta n dg e n e r a l p u r p o s eg l o b a l o p t i m i z a t i o nm e t h o df o rl a r g e s c a l ep a r a l l e l i z a t i o n s i n c e1 9 8 0 s ，s o m en o v e lh e u r i s t i c sa l g o r i t h m sa r ec r e a t e db y s i m u l a t i n go rs h o w i n gs o m en a t u r a lp h e n o m e n a ，s u c ha sg e n e t i ca l g o r i t h m s ， s i m u l a t e da n n e a l i n g ，t a b o os e a r c h ，a n tc o l o n yo p t i m i z a t i o n t h e p a r t i c u l a ra d v a n t a g ea n dm e c h a n i s mo ft h e s ea l g o r i t h m sh a v eb r o u g h ta h o t s p o to fr e s e a r c h ，e s p e c i a l l ya n tc o l o n yo p t i m i z a t i o nh a sb e e n d e v e l o p e df o rm o r et h a nt e ny e a r s ap o p u l a t i o n b a s e ds i m u l a t e de v o l u t i o n a r ya l g o r i t h mc a l l e da n t c o l o n yo p t i m i z a t i o n ( a c of o rs h o r t ) w a sp r o p o s e db yi t a l i a nm d o r i g o a c o a d o p t sp a r a l l e lc o m p u t a t i o nm e c h a n i s m ，h a ss t r o n gr o b u s t n e s sa n d i s e a s yt oc o m b i n e 可i t ho t h e rm e t h o d si no p t i m i z a t i o n b e c a u s eo fi t s c h a r a c t e r i s t i c s ，t h er e s e a r c ho ft h e o r ya n da p p l i c a t i o no fa c oh a sg r e a t m e r i t f i r s t l y ，t h i sp a p e ra n a l y z e st h eb a s i ct h e o r ya n dm o d e lo fa c o ， i n t r o d u c e st h ef e a t u r e so fa c oa n ds e l e c t ss o m ek e yp a r a m e t e r s v a l u e o fa c ob ye x p e r i m e n t s s e c o n d l y ，t h es l o wc o n v e r g e n c ea n ds t a g n a t i o n b e h a v i o r 。s oa ni m p r o v e da l g o r i t h mi sp r o p o s e d t h i sa l g o r i t h mi sa b l e t or e s t r a i ns t a g n a t i o nd u r i n gt h ei t e r a t i o np r o c e s se f f e c t i v e l y ，a n d 西南交通大学硕士研究生学位论文 第l li 页 e n h a n c et h ec a p a b i l i t yo fs e a r c h t h ei m p r o v e da l g o r i t h mi sa p p l i e dt o t r a v e l i n gs a l e s m e np r o b l e m ( t s p ) e x p e r i m e n t a lr e s u l t sf o rs o l v i n g t s pa r e p r o v e dt ob ee f f e c t i v e f i n a l l y ，t h ei m p r o v e da l g o r i t h mi sa p p l i e dt o v e h i c l er o u t i n gp r o b l e m ( v r p ) s i m u l a t i o nr e s u l t so ft h ev r pe x a m p l e d e m o n s t r a t e dt h ee f f e c t i v e n e s so ft h i sa l g o r i t h m k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ，c o m b i n a t i o n a lo p t i m i z a t i o n ， t r a v e l i n gs a l e s m e np r o b l e m ，v e h i c l er o u t i n gp r o b l e m 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 蚁群算法的研究现状 受蚁群在觅食过程中总能找到从蚁巢到食物源的最短路径的启发，2 0 世纪 9 0 年代初，意大利学者m d o r i g o ”脚。1 等首次提出一种新型的智能优化算法一 蚂蚁系统( a n ts y s t e m ，简称a s ) 并成功用于求解旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ，简称t s p ) ，实验结果表明a s 算法具有较强的鲁棒性和发现 较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等。 该算法的出现引起了学者们的广泛关注，并提出一些改进的蚁群算法。1 9 9 5 年， l m g a m b r a d e l l a ，m d o r i g o “提出了a n t 咱算法，该算法用伪随机比例状态转 移规则替换a s 算法中的随机比例选择规则，从而使a n t - q 算法在构造解的过程 中能够更好地保持知识探索与知识利用之间的平衡。此外，该算法中还引入了 局部信息素更新机制和全局信息素更新中的精英策略。1 9 9 6 年，m d o r i g 0 0 1 等 在a n t q 算法的基础上提出了蚁群系统( a n tc o l o n ys y s t e m ，简称a c s ) ，该算法 作为a n t - q 算法的特例实现起来更为简单，但在求解t s p 问题时具有相同的性 能。1 9 9 9 年，t s t u t z l e 等人提出了最大一最小蚂蚁系统( m a x - m i na n ts y s t e m ， 简称m m a s ) ，该算法的主要特点是为信息素设置上下限来避免算法出现停滞现 象。 国内直到2 0 世纪末才有学者开始关注a c o 算法，目前对该算法的研究主要 停留在算法的改进和应用方面。1 9 9 9 年，吴庆红和张纪会等通过向基本蚁群算 法中引入变异机制，充分利用2 一交换法简洁高效的特点，提出了具有变异特征 的蚁群算法。吴斌和史忠植首先在蚁群算法的基础上提出了相遇算法，提高了 蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合，提 出一种基于蚁群算法的t s p 问题分段求解算法。王颖和谢剑英通过自适应地改 变算法的挥发度等系数，提出一种自适应的蚁群算法以克服限于局部最小的缺 点，覃刚力和杨家本根据人工蚁所获得解的情况，动态地调整路径上的信息素， 西南交通大学硕士研究生学位论文第2 页 提出了自适应调整信息素的蚁群算法。 继m d o r i g o 首先将a s 算法应用于t s p 问题之后，1 9 9 9 年，v m a n i e z z o ”1 等人将a s 算法应用于指派问题( 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 ) 。 a c o l o r n i 等人首先将a s 算法应用于车间作业调度问题( j o b s h o ps c h e d u l i n g p r o b l e m ，简称j s p ) 。c o s t a 和h e r z 。1 提出增强的a s 算法，并应用于分配类型 的问题。该算法在求解图的着色问题时，得到了完全可以和其它启发式算法相 媲美的结果。a c o 在通讯网络领域( 特别是解决网络路由问题) 的应用受到越来越 多学者的关注，d ic a r o 和d o r i g o 将a c o 算法应用于网络路由问题，并称这种 算法为a n t n e t 。除了各种组合优化问题之外，a c o 算法还在函数优化、系统辨 识、机器人路径规划、数据挖掘、大规模集成电路中的综合布线设计等领域取 得了引人注目的成果。 1 2 本文的研究工作和安排 本文主要工作包括三个方面：一、综述基本蚁群算法原理、实现步骤、算 法特点及对基本蚁群算法的参数进行分析，得出参数的最佳配置；二、介绍几 种国内外学者提出的改进蚁群算法，在这几种改进蚁群算法的基础上，提出一 种新的改进蚁群算法，该改进算法借鉴最大最小蚁群算法中利用限制信息素范 围的思想，这样可以抑制由于最短路径和最长路径信息量差距加剧而引起的停 滞现象，同时引入局部信息素更新及局部搜索策略，有效抑制早熟现象，加快 了算法的求解速度，在此基础上通过改进信息素的全局更新机制，使算法能够 更快地收敛到全局最优解，通过三种t s p 问题的测试，结果表明该算法的搜索能 力和性能都得到显著提高；三、介绍蚁群算法在车辆路径问题中的应用。 本文的主要结构如下： 第一章：介绍蚁群算法的研究现状以及本文的研究工作； 第二章：首先介绍几种典型的组合优化问题，然后介绍组合优化问题邻域 函数的概念，最后简介求解组合优化问题的常用智能优化算法： 第三章：首先分析基本蚁群算法的原理，然后以t s p 问题为例建立基本蚁 西南交通大学硕士研究生学位论文第3 页 群算法的数学模型，最后总结该算法的优缺点； 第四章：通过仿真实验对基本蚁群算法中的参数进行研究，得出较合适的 参数配置方案； 第五章：首先介绍几种改进的蚁群算法，并比较几种算法性能，然后在已 有算法的基础上作者提出一种新的改进蚁群算法，通过三种t s p 问题测试，该 算法较基本蚁群算法在搜索能力和性能都得到了显著提高，最后对蚁群算法的 收敛性进行分析； 第六章：介绍自适应蚁群算法在车辆路径问题中的应用。 西南交通大学硕士研究生学位论文第4 页 第2 章求解组合优化问题的智能优化算法 2 1 组合优化问题 定义2 f 1 组合优化问题( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过数学方 法的研究去寻找离散事件的最优编排、分组、次序或筛选等，它是运筹学的一 个重要分支，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、 通信网络等诸多领域。 组合优化问题的一般形式为： m i nf ( x ) s t h ( x ) 之0 x e d 式中，f ( x ) 为目标函数，h ( x ) 为约束函数，x 为决策变量，d 为决策变量的 定义域。 一个组合优化问题可用三参数( d ，h ，f ) 表示，其中d 表示决策变量的定义域， h = 工i 石d | i l o ) 20 ) 表示可行域，f 表示目标函数。组合优化问题的特点是 可行解的集合h 为有限点集，决策变量的定义域d 通常也是有限点集，只要将d 中有限点逐一判别是否满足h ( x ) 的约束和比较目标值的大小，该问题的最优解 一定存在且可以得到。 2 2 几种典型的组合优化问题 2 2 1 旅行商问题( t r a v e li n gs a i e s m a np r o b i e m ，简称t s p ) 给定n 个城市，有一个旅行商从某一城市出发，访问各城市一次且仅有一 次后再回到原出发城市，要求找出一条最短的巡回路径。也可用图论描述：设 c 一 o 工，n 一1 是n 个城市的集合，工。| c ； c ，c ) 是集合c 中元素( 城市) 西南交通大学硕士研究生学位论文第5 页 两两连接的集合，d 。j ( i ，- 1 , 2 , ，n ) 是的欧氏距离，即 嘞- 似一_ ) 2 + 以一y j ) 2 ，g ：( c ，l ) 是一个有向图，从有向图g 中找出长度最短， 的h i m i l t o n 圈。 t s p 可分为对称t s p ( 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 ( 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 ) 两大类，若略一d f ，则称对 称t s p ，否则为非对称t s p 2 2 2o - 1 背包问题( k n a p s a c k p r o b ie m ) 设有一个容积为b 的背包，n 个尺寸分别为；o - 1 , 2 h ) ，价值分别为 c ，( f - 1 2 ，h ) 的物品，如何装包以使装入的物品的总价值最大。 2 2 3 图着色问题( g r a p hc o l o ri n gp r o b i e f f l ) 对于n 个顶点的无环图，要求对其各个顶点进行着色，使得任意两个相邻 的顶点都有不同的颜色，且所用颜色种类最少。 上述问题描述都非常简单，但求解却很困难。由组合优化问题的定义可知， 每个组合优化问题都可以通过枚举的方法求得，然而枚举是以时间为代价的， 有的时间可以接受，有的则不可能接受。例如，对于一个有n 个的城市对称t s p 问题可能路径为鱼掣，若以路径比较为基本操作，则需要垒j 掣一1 次基本操 二二 作。尤其对较大规模问题进行穷举是不切实际的，许多优化问题所需要的计算 时间和存贮空间是难以承受的，所以算法可解的问题在实践中并不一定可解。 因此，解决组合优化问题的关键在于寻求有效的优化算法。 2 3 邻域函数及局部搜索 在组合优化中，邻域函数的基本思想是在一个解附近搜索另一个下降的 点。下面以t s p 为例给出组合优化问题邻域函数的概念。 西南交通大学硕士研究生学位论文第6 页 定义2 3 1 对于组合优化问题( d ，h ，f ) ，d 上的一点到d 的子集的一个映射 n ：x e d 一( x ) 2 。 r x n ( x ) ，称为一个邻域映射，其中2 。表示d 的所有子集组成的集合，o ) 称 为x 的邻域，y ) 称为x 的一个邻居。 t s p 问题解的另一种表示法为d 一 s - ( 1 ，f 2 ，) k ，如是1 ，2 ，厅的排列) ， 定义它的邻域映射为2 - o p t ，即s 中两个元素进行交换。如排列( o ，l ，2 ，3 ) 可表示 4 个城市t s p 的一个解，k 个点交换可认为是一种邻域函数，则两个点交换对应 的邻域函数将产生( 1 ，0 ，2 ，3 ) ，( 2 ，1 ，0 ，3 ) ，( 3 ，1 ，2 ，0 ) ，( 0 ，2 ，1 ，3 ) ，( 0 ，3 ，2 ，1 ) ， ( 0 ，1 ，3 ，2 ) 。 定义2 3 2 若x 日满足f ( x ) ，( 力，且z 0 ) n i l ，则称石为f 在h 上的局部最小解。 定义2 3 3 若f ( x ) f ( x ) ，r x e i t ，则称x 为f 在h 上的全局最小解。 局部搜索算法是从一个初始解出发，利用邻域函数持续地在当前解的领域 中搜索比它好的解，虽然局部搜索算法简单易行，但搜索性能完全依赖邻域函 数和初始解，邻域函数设计不当或初值选取不合适，则算法最终的性能将会很 差。如图2 1 ，若以x = 4 为起点按局部搜索算法找最小值点，则搜到x = 3 停止， 而x = 3 是局部最小值点，这种方法可能造成最终解是非全局最优值。由此可见， 若不在搜索策略上进行改进，要实现全局优化，局部搜索算法采用的邻域函数 将导致解的完全枚举，穷举的方法对于大规模问题在时间上是不允许的。鉴于 局部搜索算法的缺点，智能优化算法如遗传算法、模拟退火算法、蚁群算法等， 从不同的角度利用不同的搜索机制和策略实现对局部搜索算法的改进，来取得 较好的全局优化性能。 西南交通大学硕士研究生学位论文第7 页 2 4 部分智能优化算法简介 2 4 1 遗传算法嘲 图2 - 1 遗传算法是模拟生物界“适者生存，优胜劣肽”的法则演变而来的随机搜 索算法，由美国的j h o l l a n d 教授1 9 7 5 年首先提出，其主要特点是以群体中的 所有个体为对象进行操作，并利用随机策略对一个被编码的参数空间进行搜索。 其中，选择、交叉和变异构成了遗传算法的基本操作，参数编码、初始群体的 设定、适应值函数的设定、遗传操作设计、控制参数的设定五个要素组成遗传 算法的核心内容。作为一种新的全局优化算法，遗传算法以其简单通用、鲁棒 性强，内在的隐并行性等显著特点，被人们广泛地应用于组合优化、机器学习、 信号处理、自适应控制和人工生命等领域，取得良好的效果，并逐渐成为重要 的智能优化算法之一。 2 4 2 模拟退火算法。町 模拟退火算法是一种基于m e n t ec a r l o 迭代求解的全局概率型搜索算法， 2 0 世纪8 0 年代开始应用于组合优化问题，后来逐渐地应用于其它领域。 模拟退火算法是模拟热力学经典粒子系统的降温过程来求解规划问题的极 值。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力平衡状 态，最后系统将达到本身的最低能量状态即基态，这相当于能量函数的全局极 西南交通大学硕士研究生学位论文第8 页 小点。由于模拟退火算法能够有效地解决大规模的组合优化问题，且对规划问 题的要求极小，引起研究人员的重视。 2 4 3 蚁群算法o u 蚁群算法是受自然界中蚂蚁觅食行为的启发而发展的一种模拟进化算法。 2 0 世纪9 0 年代初期，由意大利学者m d o r i g o 等首先提出，主要是通过一种叫 做信息素的物质对信息进行交流，根据信息素的多少进行选择和更新，经过数 次迭代产生全局最优解。最初用于求解t s p 问题，由于该算法采用了分布式并 行机制，易于与其他方法结合，而且具有较强的鲁棒性，后来逐渐被用于解决 其它组合优化问题，如指派问题、车间调度问题、车辆路径问题、图着色问题 和网络路由等问题。 西南交通大学硕士研究生学位论文第9 页 第3 章基本蚁群算法原理 3 1 引言 蚁群算法最早成功地应用于解决t s p 问题，该算法采用了分布式并行计算 机制，易于与其他方法结合，而且具有较强的鲁棒性，但搜索时间长，易陷于 局部最优解是其最为突出的缺点。 本章首先介绍基本蚁群算法原理及其算法特点，然后以t s p 问题为例建立 基本蚁群算法数学模型，最后分析基本蚁群算法的优缺点。 3 2 基本蚁群算法原理“2 1 3 2 1 蚁群行为描述 蚁群算法是对真实蚁群行为研究而提出的。仿生学家经过长期研究发现： 蚂蚁在寻找食物时，能在其经过的路径上释放一种特殊的分泌物信息素， 使得一定范围内的其它蚂蚁能够感觉到这种物质，且倾向于朝着该物质强度高 的方向移动，因此，蚁群的集体行为表现为一种信息正反馈现象：某条路径上 经过的蚂蚁数越多，其上留下的信息量也就越多( 当然，随时间的推移会逐渐 蒸发掉一部分) ，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上信 息素的强度。这样最优路径上的信息量越来越大，而其他路径上的信息量却会 随着时间的流逝而逐渐减少，最终整个蚁群会找出最优路径。在整个寻径过程 中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群具有非 常高的自组织性，蚂蚁之间交换着路径信息，最终通过蚁群的集体自催化行为 找出最优路径。下面通过图例来说明蚁群的搜索原理。 西南交通大学硕士研究生学位论文第10 页 k l 鼻。t 蛳 1 酗 扛l 图3 一l 蚁群如何找到最优路径 3 1 ( a ) 所示，在蚁巢和食物之间有两条路径n e s t - a b - d - f o o d 和 n e s t a - c d - f o o d 其长度分别为4 和6 单位时间内蚂蚁可移动一个单位长度的 距离。开始时所有路径上没有信息素。 3 1 ( b ) 在t = o 时刻，2 0 只蚂蚁从蚁巢出发移动到a ，由于所有路径上没有信 息素，它们以相同的概率选择左侧或右侧的道路，则有1 0 只蚂蚁走左侧，另外 1 0 只蚂蚁走右侧。 3 1 ( c ) 在t = 4 时刻，第一组先到达食物源的蚂蚁将折回。 3 1 ( d ) 在t = 5 时刻，两组蚂蚁将在d 点相遇，此时b d 上的信息量与c d 上的信 息量相同，因此，返回的l o 只蚂蚁中有5 只选择b d ，另5 只选择c d 3 1 ( e ) 在t = 8 时刻，前5 只将返回蚁巢，而在a c 、c d 和a b 上各有5 只蚂蚁。 3 1 ( f ) 在t = 9 时刻，前5 只蚂蚁又回到a 而且再次面对往左还是往右的选择， 1胁蛳 西南交通大学硕士研究生学位论文第11 页 此时a b 上的信息素量是2 0 而a c 上的是1 5 ，因此将有较为多数的蚂蚁选择 往右，增强了a b 上的信息素量，随着该过程的继续，两条道路上的信息量的差 距将越来越大，直到所有的蚂蚁都选择了最短路径。 3 2 2 人工蚂蚁和真实蚂蚁的异同 人工蚂蚁具有双重特性：一方面，他们是真实蚂蚁的抽象，具有真实蚂蚁 的特性，另一方面，他们还有一些在真实蚂蚁中找不到的特性，这些新的特性， 使人工蚂蚁在解决实际优化问题时，具有更好地搜索较好解的能力。 人工蚂蚁和真实蚂蚁相同点：( 1 ) 都是一群相互协作的个体：( 2 ) 都通过信 息素间接通讯；( 3 ) 都使用随机状态转移策略：( 4 ) 人工蚂蚁利用真实蚂蚁觅食 行为中的正反馈机制和信息素的挥发机制 人工蚂蚁和真实蚂蚁不同点：( 1 ) 人工蚂蚁生活在离散的世界，从一种离散 的状态到另一种离散的状态；( 2 ) 人工蚂蚁具有内部状态。即人工蚂蚁具有一定 的记忆能力，能记忆所走过的地方；( 3 ) 人工蚂蚁释放的信息素量是其生成解的 质量的函数；( 4 ) 人工蚂蚁更新信息素的时机依赖于特定的问题。 3 2 3 蚁群优化的特点 从蚁群算法的原理可以看出，蚁群的觅食行为实际上是一种分布式的协同 优化机制，单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径，但找到最短路 径的可能性极小，只有当多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁的智 能发现最短路径的能力，在寻找最短路径的过程中，蚁群使用种间接通 信方式，即通过向所经过的路径上释放一定量的信息素，其他蚂蚁通过感知这 种物质的强弱来选择下一步要走的路，这种个体问通过改变环境、感知环境的 变化来彼此间接通讯的方式机制被称为协同机制，该通信机制可以非常容易地 扩展到人工多主体模型，即首先用状态变量来表示问题的状态，然后让人工主 体只访问局部状态变量信息，因此，人工蚂蚁可以通过更新问题的状态变量来 模拟真实蚂蚁更新信息素的行为。 西南交通大学硕士研究生学位论文第12 页 在蚁群的觅食行为中，另一种重要的方面是自催化机制和解的隐式评估， 自催化机制实际上是一种正反馈机制，解的隐式评估指蚁群将先走完较短的路 径，自催化机制和解的隐式评估相结合，极大地提高了问题的求解效率，即对 于越短的路径蚂蚁将越早走完，从而使更多的蚂蚁将会选择该路径，自催化机 制对基于群体的算法非常有效，如在遗传算法中，通过选择和复制机制来实现， 因为他奖励好的个体，可以指导搜索方向，在使用自催化机制时，要努力避免 早熟现象。在蚁群算法中，使用信息素蒸发和随机状态转移来弥补自催化机制 的缺陷。 蚁群算法的主要特点概括如下： ( 1 ) 采用分布式控制，不存在中心控制； ( 2 ) 每个个体只能感知局部的信息，不直接使用全局信息； ( 3 ) 个体可改变环境，并通过环境来进行间接通讯； ( 4 ) 具有自组织性，即群体的复杂行为是通过个体的交互过程中突现出来的 智能； ( 5 ) 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会 求得全局最优解； ( 6 ) 其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性 及目标函数和约束函数的精确数学描述； ( 7 ) 是类基于多主体的智能算法，各主体之间通过相互协作来更好地适应 环境： ( 8 ) 具有潜在的并行性，其搜索过程不是从一点出发，而是从多个点同时进 行，这种分布式多智能体的协作是异步并发进行的，分布并行的模式将大大提 高整个算法的运行效率和快速反应的能力。 3 3 基本蚁群算法数学模型嘲嘲嘲 以求解平面n 个城市的t s p 问题( 用( o 上，l 一1 ) 表示城市序号) 来说明基本 蚁群算法。 西南交通大学硕士研究生学位论文第1 3 页 首先弓i z t a t i g 号：m 为蚁群中的蚂蚁数；d , j ( f ，- 1 , 2 , oo t , 厅) 为城市i 和 城市j 之间的距离；毛( f ) 为t 时刻路径( i ，j ) 上的信息量；n 为城市的数量。 初始时刻，各条路径上的信息素相等，设毛( o ) - c ( c 为常数) ，蚂蚁 k ( ki 1 ，2 ，m ) 在运动过程中根据各条路径上的信息素量决定转移方向。基本蚁 群算法所使用的状态转移规则被称为随机比例规则，它给出了位于城市i 蚂蚁k 转移到城市j 的概率。露( f ) 为在t 时刻蚂蚁k 由城市i 转移到城市j 的状态转 移概率 p ：( f ) i器靴砒础 。， 0否则 式中，a l l o w e d 。一帆，甩一1 ) 一t a b u 。表示蚂蚁k 当前能选择的城市集合； t a b u 。为禁忌表，它记录蚂蚁k 已走过的城市； 口为信息启发式因子，表示轨 迹的相对重要性；( f ) 为t 时刻的能见度，反映由城市i 转移到城市j 的期望程 度；口为期望启发因子，表示能见度的相对重要性 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一 步或者完成对所有n 个城市的遍历后，要对残留信息进行更新。经过n 个时刻， 所有蚂蚁完成一次循环，各路径上的信息素按式( 3 2 ) 和( 3 3 ) 更新 勺( f + 一) - ( 1 - p ) r g ( f ) + 勺 ( 3 2 ) 。荟露 。3 式中，p 表示信息素挥发系数，则1 一p 信息素残留因子，为防止信息的无 限积累，通常设置o p l ；a 表示本次循环中路径o ，) 上的信息素增量，a 西南交通大学硕士研究生学位论文第1 4 页 表示第k 只蚂蚁在本次循环中留在路径( f ，) 上的信息量。 根据信息素更新策略不同，m d o r i g o 提出三种不同的基本蚁群算法模型，分 别是a n t - c y c l e 模型，a n t - q u a n t i t y 模型及a n t d e n s i t y 模型，其差别在于a 求法不同。 在a n t - c y c l e 模型中 磁层若第k 只蚂蚁在本次循环中经过( i ，j ) ( 3 4 ) 一 k 、 7 ( 3 4 ) l0否则 式中，q 表示信息素强度，它在一定程度上影响算法的收敛速度；k 表示 第k 只蚂蚁在本次循环中所走路径的总长度。 在a n t - q u a n t i t y 模型中 弓。慝若第k 只蚂蚁在t 和t + l 之间经过( i ，j ) ( 3 5 ) 10否则 在a n t d e n s i t y 模型中 舞若第帜蚂蚁在需1 之鼢踯。 ( 3 6 ) 式( 3 5 ) 和式( 3 6 ) 利用的是局部信息，即蚂蚁完成一步后更新路径上的信 息素；而式( 3 4 ) 利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的 信息素，求解t s p 时性能较好。 3 4 基本蚁群算法实现步骤 ( 1 ) 参数初始化令t = o 和循环次数也= 0 ，设置最大循环次数f 。，将m 只 蚂蚁随机地放到n 个城市，将每条边( f ，) 上的信息素设为个常数，且一0 ， 将出发点城市设置到禁忌表中； ( 2 ) 按式( 3 1 ) 选择下一个城市； 西南交通大学硕士研究生学位论文第15 页 ( 3 ) 修改禁忌表，即选择好之后将蚂蚁移动到下一个城市，并把该城市移动 到蚂蚁个体的禁忌表中； ( 4 ) 循环执行第( 2 ) 步和第( 3 ) 步直到每只蚂蚁都生成一条路径； ( 5 ) 计算第k 只蚂蚁所走路径的总长度； ( 6 ) 根据式( 3 2 ) 和式( 3 3 ) 更新所有路径上的信息量； ( 7 ) 若循环次数札c 。，则循环结束并输出计算结果，否则清空禁忌表 并转到第( 2 ) 步。 3 5 基本蚁群算法的优缺点 基本蚁群算法具有很强的发现解的能力，这是因为该算法不仅利用了正反 馈原理，在一定程度上可以加快进化过程，而且是一种本质上并行的算法，不 同个体之间不断进行信息交流和传递，从而能够相互协作，有利于发现较好解。 具有如下的优点： ( 1 ) 分布式本质并行算法，它是一种基于种群的进化算法，本质上具有并行 性，易于并行实现； ( 2 ) 具有较强的鲁棒性，对其模型稍加修改，便可以应用于其他问题； ( 3 ) 易于与其他方法结合，基本蚁群算法很容易与多种启发式算法结合，以 改善算法的性能； ( 4 ) 其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性 及目标函数和约束函数的精确数学描述； ( 5 ) 是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会 求得全局最优解； 基本蚁群算法是一种有效的随机搜索算法，但也存在一些缺陷： ( 1 ) 与其他方法相比，该算法般需要较长的时间； ( 2 ) 该算法易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的 解完全一致，不能对解空间进一步搜索，不利于发现更好的解。 西南交通大学硕士研究生学位论文第1 6 页 第4 章蚁群算法中参数的设置 4 1 引言 在蚁群算法中，信息素挥发系数p 、信息启发因子口、期望启发式因子口、 信息素强度q 、蚂蚁数目m 等都是非常重要的参数，其选取方法和选取原则直接 影响到蚁群算法的全局收敛性和求解效率。同时，蚁群算法中各参数的作用是 紧密联系的，其中对算法性能起着最关键作用的是信息素挥发因子p 、信息启 发因子口、期望启发式因子p - - 个参数。如果口、p 、p 的组合参数配置不当， 会导致求解速度很慢且所得解的质量特别差，因此，研究关键参数口、口、p 的 最佳组合配置策略有着非常重要的意义。本章将通过仿真对蚁群算法中的主要 参数口、口、p 的选择进行分析。 4 2 参数对算法性能影响的实验分析“州1 町 4 2 1 信息素残留因子对蚁群算法性畿的影响 在蚁群算法中，人工蚂蚁具有人类记忆功能，随着时间的推移，以前留下 的信息将要逐渐消失。信息素挥发系数p 的大小直接影响蚁群算法的全局搜索 能力及其收敛速度；而信息素残留因子1 一p 反映个体的相互影响的强弱。由于 信息素挥发因子p 的存在。当处理的问题规模比较大时，会使那些从来未被搜 索到的路径上的信息素减小到接近于0 ，因而降l e t 算法的全局搜索能力，当p 过大时，以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机 性能和全局搜索能力；反之，通过减小p 虽然可以提高算法的随机性能和全局 搜索能力，但又会使算法收敛速度降低。信息素挥发因子p 对算法性能的影响， 西南交通大学硕士研究生学位论文第仃页 可以通过仿真实验来分析。 对t s p l i b 中的o l i v e r 3 0t s p 大量的仿真实验的基础上对蚁群算法中信息 素通过残留因子1 一p 的选择做进一步探讨。本实验采用了蚁群算法中的全局搜 索机制，即采用了a n t - c y c l e 模型，设置a 一1 ，p - 1 q 一1 0 0 ，州一厅，算法的停止 条件为最大循环次数1 0 0 0 次。该实验所得1 一p 与最优路径长度l 之间的关系如 图4 1 所示。 图4 - 1 1 一p 与最优路径长度之间的关系 由图4 1 可以看出，在其他初始化参数的相同的条件下，信息素通过残留 因子1 一p 的大小对蚁群算法的收敛性能影响很大，特别是当1 一p 很小时，信息 的正反馈作用相对较强，搜索的随机性减弱，因而收敛速度加快，易陷入局部 最优状态；当1 一p 比较大时，由于路径上的残留信息占主导地位，信息的正反 馈作用相对较弱，搜索的随机性增强，而且存在于环境中的信息素保持时间较 长，解空间对问题空间的反馈信息较弱，因而蚁群算法的收敛速度很慢。综合 考虑算法的收敛速度和全局搜索能力两方面因素，当1 一p 【o 5 ，o 7 】，算法的性 能比较稳定和一致，搜索的全局性和收敛速度都比较好。 西南交通大学硕士研究生学位论文第1 8 页 4 2 2 信息启发因子a 对蚁群算法性能的影响 信息启发因子a 反映蚂蚁在运动过程中所积累的信息量在指导蚂蚁搜索中 的相对重要性，其值越大，蚂蚁选择以前走过的路径可能性就越大，搜索的随 机性减弱；当信息启发因子口过小时，易使蚁群的搜索过早陷于局部最优。 关于信息启发因子口对蚁群算法性能的影响及其在实际应用中的选择，可 以通过仿真实验来分析和选定。本实验以t s p l i b 中的o l i v e r 3 0 t s p 为研究对象， 仍采用了a n t - c y c l e 模型，设置卢一1 ，q 一1 0 0 ，m - n ，p - o 3 算法的停止条件为 最大循环次数1 0 0 0 次。该实验所得信息启发因子a 与最优路径长度l 之间的关 系如图4 2 所示。 图4 - 2 信息启发因子口与最优路径长度之间的关系 从图4 - 2 可以看出，在蚁群算法中信息启发因子口对算法性能有极大的影 响，a 过小，不仅收敛速度慢，而且易陷入局部最优解；口过大，蚂蚁在搜索 的过程中信息素相对重要，将导致局部最优路径上的正反馈作用很强，算法会 出现过早收敛现象。上述实验表明a 仉2 】时，蚁群算法求解性能比较好。 4 2 3 期望启发式因子鼻对蚁群算法性能的影响 期望启发式因子口反映启发式信息在指导蚁群搜索过程中的相对重要程 度，其大小反映了蚁群寻优过程中的先验性、确定性因素的作用强度。其值越 西南交通大学硕士研究生学位论文第1 9 页 大，则蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然这时算法的 收敛速度得以加快，但蚁群搜索最优路径的随机性减弱，易于陷入局部最优。 关于期望启发式因子一对蚁群算法性能的影响及其在实际应用中的选择， 可以通过仿真实验来分析和选定。本实验以t s p l i b 中的o l i v e r 3 0t s p 为研究 对象，仍采用了a n t - c y c l e 模型，设置口一l ，q - 1 0 0 ，m 一7 1 , p - 0 3 ，算法的停止 条件为最大循环次数1 0 0 0 次。该实验所得期望启发式因子口与最优路径长度l 之间如图4 - 3 所示。 图4 3 期望启发式因子口与最优路径长度l 的关系 从图4 3 可以看出，在蚁群算法中期望启发式因子口对算法性能影响较大。 芦过小，将导致蚂蚁群体陷入纯粹的随机搜索，在这种情况下一般很难找到最 优解：芦过大时，算法的收敛速度增快，但其收敛性能有变差的趋势。上述实 验表明卢【垆】时，蚁群算法求解性能比较好。 4 2 4 口、芦、p 组合配置对蚁群算法性能的影响 信息启发因子口和期望启发式因子芦关联性很强，蚁群算法的全局寻优性 能，首先要求蚁群的搜索过程有较强的随机性，而蚁群算法的快速收敛性能又 西南交通大学硕士研究生学位论文第2 0 页 要求蚁群的搜索过程必须具有较高的确定性。因此，a 、口、p 对蚁群算法性 能的影响和作用是相互配合、密切相关的。只有正确选定它们的搭配关系，才 能避免在搜索过程中出现过早停滞或陷入局部最优。 下面通过实验来分析参数a 、口、p 在三种不同的基本蚁群算法 n t - c y c l e 模型，a n t - q u a n t i t y 模型及a n t d e n s i t y 模型中的最佳配置。实验以t s p l i b 中的o l i v e r 3 0 t s p 为研究对象，采用改变一个参数、其他不变的策略来讨论参 数设置对蚁群算法性能的影响。参数设置口- 1 卢一t q l o o , p - 0 3 , m n ，算法 的停止条件为最大循环次数1 0 0 0 次，每组数据实验1 0 次取最优解、最差解及 平均值作比较。a n t - c y c l e 模型、a n t - q u a n t i t y 模型及a n t - d e n s i t y 模型的实 验结果分别如表4 - i 、表4 吧