（计算机应用技术专业论文）一个蚁群优化算法及其在cvrp问题中的应用研究.pdf

一个蚁群优化算法及j f 在c v r p 问题中的应用研究摘要 一个蚁群优化算法及其在c v r p 问题中的应用研究 摘要 该文通过对蚁群优化算法发展现状的分析，着重对取得较大成功的 蚁群优化算法m m a s 和基于均匀分布度的自适应蚁群算法进行研究，基于 此提出一个新的蚁群优化算法n d l a c o ，给出了算法设计模型。通过利用 适应度地形分析蚁群对解空间的搜索覆盖程度和对局部搜索方法的分 析，把最近邻居选择法和3 - o p t 局部搜索方法融入n d l a c o 算法中。通过 吸纳基于均匀分布的自适应思想，有效地处理了蚁群算法中存在的蚁群 加速收敛和防止算法出现早熟、停滞想象这对矛盾。 本文成功地把n d l a c o 算法运用于解c v r p 问题。通过对实验数据的 分析发现，此算法运用于解c v r p 问题时在不影响所得解质量的前提下， 对算法中参数值的设置有一定的容忍度。 关键词：蚁群优化算法，n d l a c o ，v r p ，c v r p ，局部搜索法，适应度地形 分析 作者：任善全 指导老师：钱培德、吕强 垒! ! 笪璺! ! ! 生垦! 兰! ! 生! ! 垒墼! ：! 婆竺竺旦型墅坚坐旦竺三垦巳 t h er e s e a r c ho na p p l y i n ga na c oa l g o r i t h mt oc v r p a b s t r a c t b a s e do na n a l y zi n gt h ed e v e l o p m e n to fa c 0a lg o r it h m s ，t h i s p a p e rb r i n g su p an e wa c oa l g o r i t h mn d l a c ob ys t u d y i n gm m a sa n d a n a d a p t i v e a n tc o l o n ya l g o r i t h m b a s e do ne q u i l i b r i e mo f d i s t r i b u t i o n a f t e rr e s e a r c h i n gl o c a ls e a r c hm e t h o da n do b s e r v i n g t h ed e g t e et h a ta n t sc r a w li nt h es o l u t i o ns p a c ew i t ha n a l y s i so f f i t n e s s d i s t a n c ec o r r e l a t i o n ，b o t ht h en e a r e s tn e i g h b o ra n d3 - o p t l o c a ls e a r c h i n gm e t h o d sa r ei n t e g r a t e dt on d l a c oa l g o r i t h m n d l a c o a l s oa d a p t st h ea d a p t i v ei d e ab a s e do ne q u i l i b r i e mo fd i s t r i b u t i o n a n dd e a lw i t ht h ec o n t r a d i c t o r yb e t w e e na n t sc o n v e r g e n c es p e e d a n da v o i d i n gp r e c o c i t ya n ds t a g n a t i o n t h et h e s i ss o l v e st h ec a p a c i t a t e d v e h i c l er o u t i n g d r o b l e m s ( c v r p ) s u c c e s s f u l l yu s i n gn d l a c oa l g o r i t h m b a s e d o n a n a l y z i n gt h er e s u l t so b t a i n e db yc o n c e r n e de x p e r i m e n t s ，w ef i n d n d l a c oc a nt o l a r a n ts o m ep a r a m e t e r s sv a r i a t i e s w h e r e v e r ，i t d o e sn o ti n f l u e n c et h eq u a l i t yo fs o u t i o n s k e y w o r d s ：a c oa l g o r i t h m ，n d l a c o ，v r p ，c v r p ，l o c a l s e a r c hm e t h e d ， a n a l y s i so ff i t n e s s d i s t a n c e w r i t t e nb y ：r e ns h a n q u a n s u p e r v is e db y ：q i a np e i d e ，l vq i a n g 7 8 1 4 4 9 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：叠王薹全日期：越，f 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印什和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏卅i 大学学位办办理。 研究生签名：4 主薹全r 期：量q 车： 导帅签名：# 台- 卜一日 期：2 唑丘扯 个蚁群优化算法发其在c v r p 问题中的应用研究 第一章05 击 1 1 课题背景 第一章引言 上世纪5 0 年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出了 许多用于解决复杂优化问题的新方法。当时，研究群居性昆虫行为特性的科学家发现， 昆虫在群落一级上的合作基本上是自组织的，但是它们却可以解决复杂的问题。这种 由群居性生物产生出来的一种集体行为，即产生的群集智能引起了包括计算机科学家 在内众多研究人员的兴趣，就是利用群集智能解决组合优化问题的舆型例子【l i 。蚁群 算法( a n tc o l o n ya l g o r i t h m ) ，4 1 5 1 是出意大利学者m d o r i g o ，m a n i e z z o 等人在2 0 世纪9 0 年代初首先提出来的。它是续模拟退火算法( s i m u l a t e da n n e a l i n g ) 、遗传算 法( g e n e t i ca l g o r i t h m ) 、禁忌搜索( t a b us e a r c h ) 算法、人工神经网络算法等启发式 搜索算法之后的又一种应用于组合优化问题的局部搜索算法。遗传算法1 6 j ( g e n e t i c a l g o r i t h m ) 是一种借鉴生物界自然选择思想和自然遗传机制的全局随机搜索算法。它 把问题的可能解组成种群，把每一个可能的解看作种群的个体，运行时算法在整个种 群空间内随机搜索，按一定的评估策略( 或称适应度函数) 对每一个体作评价，不断使 用选择、交叉、变异这3 种遗传算子，使问题的解不断进化，直至产生最优解。模拟 退火算法 7 1 ( s i m u l a t e da n n e a l i n g ) 模拟的是高温物体退火过程，其基本思想是把某 类优化问题的求解过程与统计热力学中的热平衡问题进行对比，试图找出优化问题的 全局最优或近似全局最优解。蚁群算法用于寻找最短路径是来源于蚂蚁寻找食物的行 为，它首先运用于求解旅行商问题( t s p ) 并获得成功，续而应用于解决另外几种 n p h a r d 的组合优化问题，如车辆调度问题( v r p ) 、资源二次分配问题( q a p ) 和通讯 网络8 1 等问题，显示出蚁群算法在求解复杂优化问题方面的优越性。近几年来的研究 成果表明：蚁群算法具有很强的发现较好解的能力、具有分却式计算、易于与其他方 法相结合和鲁棒性强等优点。 1 2 研究内容 蚁群算法目前在国内外己取得了很多研究成果，也有很多应用证实了它在解 n ph a r d 的组合优化等问题时的优越性。但其中还有一些方面的问题有待进一步研 究。比如，蚁群算法由于是一种近几年出现的新型优化算法，还没有像g a 等算法那 样形成系统分析的方法和坚实的数学基础，各种实验参数的确定也没有理论上的指 导。目前国际上诸多研究成果还都是基于实验数据的分析，还有许多理论问题有待研 第一章引言一个蚁群优化算法及其托c v r p 问题中的心用研究 究：算法运行过程中，蚂蚁群的加速收敛和防止蚂蚁早熟停滞现象仍然是一对难以解 决的矛盾：蚂蚁在搜索过程中对解的利用和搜索空间之问的关系：蚁群算法中 口，口，p 等参数值的设置原理及各参数的变化与所得解质量之问的关系。基于以上研 究背景，本论文着重研究的内容展开如下： 1 所得解的利用和算法搜索空间之间的关系 许多局部算法都会遇到类似的问题：在算法运行过程中，过分强化现有解的作用 就会导致解空间的搜索范围变小从而降低了算法取得最优解或接近最优解的概率；如 果过于忽略算法运行过程中已得解在算法运行后期的作用就会导致增加无效的搜索 而使算法计算量增大，降低算法的性能。在a c o 中主要通过对信息素的有效管理来缓 和这种矛盾，对已有解的利用最简单的办法就是使信息素的增量是解质量的函数，改 进的策略有“e l i t i s ts t r a t e g y ”等。对解空间的探索主要体现为随机的解构造过程。 如果没有启发信息的作用，算法会过早收敛。为解决这一问题，在a c s 3 0 l 中，引入了 局部信息素的更新机制；，在姒a s o o l 中，设定了信息素量变化的上下界等等，这些都 是为了扩大对解空间的搜索范围。维持二者平衡的另外不可忽视的因素是参数a 和 b 作用，它们决定了信息素和启发因子的相对重要性。其中a 暗含了对已有解的重 视程度，b 代表了对启发因子的利用情况。基于此，本文将研究算法中对所得解的 利用程度与算法搜索空间之间的关系。 2 蚁群算法中解的质量与局部搜索算法的关系 在求解大部分n p h a r d 组合优化问题时，蚁群算法与局部搜索算法( l o c a s e a r c h a l g o r i t h m ) 配合使用时，能大幅度地提高解的质量。蚁群算法本身作为一种粗粒度算 法所构造的解可以通过充分的局部搜索算法得到局部优化；而蚁群算法在算法运行过 程中对解的分析、利用反过来又可以为局部搜索算法提供更为合理的初始解。所以两 者之间相辅相成、相得益彰。基于此，本文将着重研究蚁群算法所得解的质量与局部 搜索算法之间的关系，即局部搜索算法对蚁群算法解质量提高的贡献程度。 3 改进蚁群算法并应用于解c v r p 问题 目前比较成功的蚁群优化算法有m m a s 算法和基于动态均匀分布的蚁群算法。m m a s 算法的特点：不对信息素进行局部更新，选择蚁群中每代最好解进行信息素的全局更 新：限定信息素的大小范围：每代蚁群的进化速度较慢时对信息素进行重新初始化。 基于动态均匀分布的蚁群算法：利用蚂蚁所走路径的当前分布情况来进行信息素的动 一个蚁群优化算法及其在c v k p 问题中的应用研究第一章引吉 态更新( 包括局部更新和全局更新) ，从而有效地引导后代蚂蚁，达到缩小了蚂蚁的实 际搜索空间又不降低所求得解的质量。 本论文通过对以上两个问题的研究和对a c o 算法运用于解c v r p 问题现状的分析， 并通过研究m m a s 和基于动态均匀分布的蚁群算法两种目前比较成功的蚁群优化算 法，优化出一种新的蚁群优化算法n d l a c o ，并成功应用于求解c v r p 问题。在此优化 算法中，并研究口，口，p 等参数值的设定对所求解问题解质量的影响情况。 1 3 课题意义 算法的研究一般考虑两个方面：提高算法本身的性能，通过吸纳成功算法中的精 髓思想对目前算法进行不断地优化与改进，来提高此算法的运行效率；提高算法的实 际运用能力，针对具体类型的问题，对算法中的模型、参数进行必要的修改来提高此 算法在解决具体问题时的能力，提高解的质量。 研究蚁群算法中对所得解的利用策略与算法实际搜索空间之间所存在的关系，能 使我们理解蚂蚁加速收敛和导致早熟、停滞现象这对矛盾发生的机理，有助于在蚁群 算法的改进、优化过程中更好地处理这对矛盾。 对蚁群算法中解质量的提高与局部搜索算法使用之间关系的研究，有助于我们掌 握在蚁群算法中如何使用局部搜索策略能使所得解的质量得以提高，这样也避免了在 蚁群算法改进过程中乱用局部搜索策略，那样不但不能有效地提高解的质量，反而大 大降低了算法的运算效率。 a c o 是一种新的并在不断发展的模拟优化算法。由于是种新的算法策略，目 前它在理论上还没有形成充实的数学理论基础，特别是算法中各种参数值的确定是通 过多次、重复的实验而主观确定的，而且不同实例需要及时更改参数值，没有理论i ： 的指导，类似的这些问题还有待进一步的研究。本文在通过设固定的参数值，来解 系列的c v r p 问题，通过基于实验数据的分析，希望对蚁群算法中参数值的理论研究 能提供一定的参考价值。 蚁群算法对于在解v r p 和网络路由服务质量( q o sn e t w o r k s ) 【8 9 】等问题时，不但 具有科学的理论研究价值，还具有实际的商业应用价值。如v r p 问题的研究成果可以 运用于物流等类似行业中去，不仅能缩短物流公司完成作业的时间，提高作业效率， 还能降低公司的运营成本；在网络路由方面研究成果的运用，可以有效地改善网络中 的交通堵塞情况，平衡网络中的网络负载和路由路径问题，从而改进网络中的路由状 1 第一市引苦一个蚁群优化算法及j c 在c v r p 问题中的应用研究 况和提高网络的利用效率。 1 4 本文结构 本文的主要目的是想通过对当前蚁群优化算法的应用研究，提出一种新的蚁群优 化算法，并运用于解c v r p 问题。 第二章分析了组合优化问题传统的解决方案，介绍蚁群优化算法及其当前的研究 现状，并对取得较大成功的蚁群优化算法进行了详细分析。 第三章首先介绍v r p ( 车辆调度) 问题，对解决v r p 问题的基本解法加以分析， 并研究了运用蚁群算法解此类问题的发展和现状。 第四章介绍了元启发和适应度地形方法，并利用适应度地形方法对蚁群算法解 c v r p 问题进行了基于试验的分析研究。 第五章详细介绍了三种局部搜索方法2 - o p t 、2 - h - o p t 和3 - o p t 方法，并通过大量 的试验结果分析这三种局部搜索方法在运用于初始化信息素和优化初始完整解两阶 段对提高蚁群优化算法解质量的贡献程度。 第六章详细介绍了本论文提出的一种蚁群优化算法n d l a c o 的设计模型，并给 出了此优化算法在解c v r p 问题时的主要数据结构和算法描述。 第七章对蚁群优化算法n d l a c o 中四个主要参数进行了基于实验数据的分析， 并给出了此算法在解c v r p 问题时与其它优化算法的比较。 最后对所做的工作进行了小结，并结合蚁群优化算法n d l a c o 目前设计还有待 改善的地方，对进一步要做的工作进行了说明。 一个蚁群优化算法肚其柞- c v r p 问题中的应用研究 第一章蚁群算法简介及州究现状 第二章蚁群算法简介及研究现状 2 1 组合优化问题的传统解决方案 在解组合优化类问题时，通常有两种类型的算法：精确算法( e x a c ta l g o r i t h m ) 年l l 近似 算法( a p p r o x i m a t ea l g o r i t h m ) 。 ( 1 ) 精确算法：确保在确定时间内找到最优解，并且这个确定时间与问题规模大 小有多项式关系。对于n p h a r d 的问题，精确算法在最坏情况下，需要指数时问才能 找到最优解。精确算法对大多数n p h a r d 的组合优化问题，表现的性能和结果都不理 想【4 8 】。我们通常把精确算法返回的结果称之为“全局最优解”，或简称为“最优解”。 ( 2 ) 近似算法：通常，如果可以证明某个算法在固定时间内总能返回比最优解差 一点的解，这样的算法则可以被称为近似算法【4 9 1 。事实上，由于最优解难以获取，可 以理解近似算法的返回结果是近似的最优解。我们通常把近似算法的返回结果称为 “最好解”，或称“局部最好解”或“近似最好解”。 近似算法又可以被分成两类：构造法( c o n s t r u c t i v e ) 和局部搜索法( 1 0 c a ls e a r c h ) 。 ( 1 ) 构造法：从空白解逐步增加可能的解的元素，从而构造出一个解。这种方法 的先决条件是，面向问题的解，可以通过依次增加元素( 或称部件) 来构造。 ( 2 ) 局部搜索法：局部搜索法从一些初始解开始( 例如，可以通过贪心法获得) ， 反复地利用本地调整( 1 0 c a lc h a n g e s ) 来改善当前解的质量。常用的技术手段是通过从当 前解的邻居( n e i 曲b o r h 0 0 d s ) 中选择较好解来替换当前解。所谓当前解的邻居，也就是 同当前解的构造元素相差无几的解。这样，当前解就可以简单地通过替换几个构造元 素，就可以达到优化自己的目的。从形式上来说，所谓邻居的描述，可以通过一个s x s 矩阵柬描述，s 是所有可能的解，s 。= 1 表示解s i 和s 是邻居， = 0 表示解和s 不is u s 是邻居。 局部搜索法的性能取决于邻居的设计：第一是发现这些邻居的代价必须是可接受 的：第二是能否把全局最优的要求落实在邻居中间。 近似算法有时也被称为“启发式方法”( h e u r i s t i c s ) 。我们可以把启发式方法抽象 到“元启发( m e t a h e u r i s t i c ) ”策略，这是一组算法概念，用来定义启发方法，从而可以 应用到广泛的许多问题的解决上面。模拟退火( s i m u l a t e da n n e a l i n g ) 、禁忌搜索( t a b u s e a r c h ) 都是成功的元启发。蚁群优化( a n tc o l o n yo p t i m i z a t i o n ) 是一种较新的元启 发。 第二章蚁群算法简介及研究现状一个蚁群优化算法及其n ：c v r p 问题中的应用研究 2 2 蚁群算法简介 蚁群算法是一种模拟进化算法，d o r i g o 等人充分利用了蚁群搜索食物的工程与 著名的旅行商问题( t s p ) 之间的相似性，吸取了昆虫王国中蚂蚁的行为特性，通过人 工模拟蚂蚁搜索食物的过程( 即通过个体之间的信息交流与相互协作最终找到从蚁穴 到食物源的最短路径) 来求解t s p 问题。为了区别于真实蚂蚁群体系统，我们称这种 算法为“人工蚁群算法”。为了阐述“人工蚂蚁算法”的机理，首先简单介绍一下蚂 蚁搜索食物的具体过程。 像蚂蚁这类群居昆虫，虽然视觉极其微弱，却能找到由蚁穴到食物源的最短路 径。仿生学家们经过大量细致的观察研究发现，生物世界中的蚂蚁在搜索食物时，能 在其走过的路径上释放一种信息素，使得在一定范围内的其他蚂蚁能够观察到并影响 其搜索行为。蚂蚁个体之间是通过一种称之为外激素( p h e r o m o n e ) 的通讯介质相互传 递信息，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的 路径上留下该物质，而且蚂蚁在运动过程中，能过感知到在路径上这种物质的存在及 其存在的强度，以此来指导后代蚂蚁的运动方向，蚂蚁倾向于朝着该物质强度较高的 方向移动。因此，由大量蚂蚁组成的蚁群( a n tc o l o n y ) 的集体行为便表现出一种信息 正反馈的现象：当某路径上经过的蚂蚁越多时，留在相应路径上信息素的迹( t r a il ) 也越多，以致信息素的强度增大，后来的蚂蚁选择该路径的概率也越高，从而近一步 增加了该路径上信息素的强度。这样的选择过程被称为蚂蚁的自催化( a u t o c a t a l y t i c b e h a v i o r ) 。蚂蚁个体之间就是通过这种信息的交流达到快速搜索食物的目的。 人工蚂蚁算法在受到人们对自然界中真实的蚂蚁集体行为研究成果的启发，而 提出了一种基于种群的模拟进化算法，属于随机搜索、全局优化算法。与其它模拟进 化算法样，通过多个可行解组成的群体的进化过程并以最大概率逼近问题的最优 解，甚至达到最优解。该过程包括两个基本阶段：适应阶段和协作阶段。在适应阶段， 各个可行解根据积累的信息不断调整自身的结构；在协作阶段，可行勰之间通过信息 交流，以期产生性能更好的解。蚂蚁群成功地搜索一轮所形成的是一组可行解，然后 记录其中的最好解，各蚂蚁所遗留下的信息素的迹也将按持久程度( 即挥发状况) 保留 到以后各轮搜索中，从而为蚂蚁此后的路径搜索产生特有的生物行为影响。 个蚁群优化算法及其在c v r p 问题中的应用研究 第二章蚁群算法简介及研究现状 2 3 蚁群算法研究现状 a c 0 与g a 一样，都属于m e t a h e u r i s t i c 范畴，而a c 0 算法则是指具体的一一种 算法( 蚁群算法或蚁群优化算法) ，m m a s 和a c s 都称之为a c 0 算法。a c 0 算法主要有以 下几种： ( 1 ) b a s 川( b a s i ca n ts y s t e m ) ：最基础的蚂蚁算法的实现，相当于蚁群算法的 初始解法、原型； ( 2 ) e a s 【3 0 】( e l i t i s ta n ts y s t e m ) ：优质蚂蚁系统，主要改进思想是在蚂蚁搜索过 程中利用每代取得较好解的蚂蚁进行信息素的更新，引导后代蚂蚁向好的路径上爬 行： ( 3 ) r b a s p 叫( r a n k b a s e d v e r s i o n o f a n ts y s t e m ) ：对每代已取得解的蚂蚁根据所 得解的优劣进行等级划分，对排名前几名的蚂蚁在信息素全局更新时进行奖励制度， 即在信息素挥发时对其进行补偿。通过实验发现，一般取排名前六位的蚂蚁进行奖赏， 取得的效果较好。此算法与e a s 不同之处在于对优质蚂蚁不是一视同仁的，进行等 级分配后区别对待，在信息素更新时各自发挥的作用也不一样。 ( 4 ) b w a s l 3 0 l ( b e s t w o r s ta n ts y s t e m ) ：在每代蚂蚁搜索完成之后，利用本代蚊群 中取得最好解和取得晟差解的蚂蚁进行信息素的全局更新，在信息素更新时执行赏罚 制度，即对取得最好解的蚂蚁进行奖赏，对获得最差解的蚂蚁进行惩罚。这样不但能 引导后代蚂蚁向好的路径上聚集，而且避免了后代蚂蚁朝劣质路径上爬行。可见此算 法于r b a s 不同的是在进行信息素全局更新时，赏罚并用。 ( 5 ) a c s f 3 0 i ( a n tc o l o ys y s t e m ) ：称之为蚁群系统，相对于其他的蚁群优化算法而 言，不同的是每个蚂蚁在结点i 选择下一结点i 时，使用了两种选择策略，而在这两 种策略中选择何巾策略时通过产生一个随机数q ( o 0 ，z m a x rm a 。，则q = f 。，类似 的，如果t i j , g - m m 则互 = r 。； 1 关于f 。的设定 确定限制信息素范围的两个值f m i n ，f m a x ，怎样来合理的确定这两个数的值比较 合适昵? 根据收敛性这个原则来确定，如果一条解上的所有路段的信息素值都是 f 。，而其他所有可选解的路径段上的信息素值是l - 。m ，则m m a s 已经收敛，通过 选择所有信息素为f 。的路径段所构成的解将是典型的全局最优解。收敛与早熟、 停滞是不同的，早熟、停滞是所有的蚂蚁集中到相同的路径上，而收敛与之区别的是 在给信息素加以l r j 的情况下出现的现象。 下面通过给出一个最大可能的信息素是个无可争议的边界值来简化提出的有关 收敛的概念。对于任意一个fi j 有： 嬲i m r o ( h 1 ) _ q 圭南志 3 f ( s 叫) 是每代搜索或各代的最优质解的代价，而信息素在每代中都增加l f ( s 。p t ) ， 所以在蚂蚁搜索到第t 代时信息素的最大值由公式( 2 5 ) 所求得， f 呵) 。舌p 卜f ( l s 。p t ) + p 勺( o ) 4 相应的，因为p f 。a x ，设定f = f 。 2 4 3 局部搜索策略 m m a s 算法被认为是目前最好的蚁群优化算法之一，在蚂蚁的搜索过程中，算 法的设计思想添加了局部搜索策略。2 一o p t 搜索法，3 - o p t 搜索法和l k 局部搜索法被 运用，其中l k 局部搜索法使用的效果最好，在测试过程中，解得的效果比遗传算法 中使用此l k 局部搜索解法求解同样的问题要好。在m m a s 算法中2 - o p t 搜索法取得 的效果次于l k 局部援索法。 2 4 4 信息素的刷新机制与m m a s 分类 f 9 6 表示根据s 9 6 刷新信息素的概率，由于s m 是每代都刷新信息素，产6 的取值对 求得的解的影响很大。目前一种比较有效的刷新信息素的策略是这样安排的： 0 一个蚁群优化算法及j e n - c v r p 问题中的应用研究 第二章蚁群算法简介及研究现状 如果t 。 2 5 时，只使用s i b 进行信息素刷新( t 表示蚂蚁搜索的代数) ； 如果2 5 t 7 5 时，s g b 每5 代进行次信息素刷新； 如果7 5 t 1 2 5 时，s g b 每3 代进行一次信息素刷新； 如果1 2 5 2 5 0 时，s g b 缚1 代进行一次信息素刷新； 基于信息素更新机制的区别，m m a s 算法可以分为： m m a s - - n r i ：算法假设运行了1 0 0 次迭代，在5 0 次迭代中，没有更好质量的 解出现，则使算法重新开始，但不重新初始化信息素，并使用f g o ；： m m a s + r i ：算法假设运行了1 0 0 次迭代，在5 0 次迭代中，没有更好质量的解 出现，则使算法重新开始，且重新初始化信息素，并使用f g o ； m m a s + r s ：算法假设运行了2 5 0 次迭代，在2 5 次迭代中，没有更好质量的解 出现，则使算法重新开始，且重新初始化信息素，保留f 9 6 的使用； 从实验中得出结论，在解各种t s p l i b 中的问题中，上述算法的优劣次序是： m a s + r s ，m m a s + r i ，m m a s n r i 。 2 5 基于均匀分布的自适应蚁群算法的分析 2 5 1 自适应蚁群算法” 通过对蚁群算法的分析不难发现：蚁群算法的主要依据是信息正反馈原理和某 种启发式算法的有机结合，自适应蚁群算法在构造解的过程中，利用随机选择策略， 这种选择策略使得进化速度较慢，正反馈原理旨在强化性能较好的解，却容易出现停 滞现象这是造成蚁群算法的不足之处的根本原凶。因而从选择策略方面进行修改， 采用确定性选择和随机选择相结合的选择策略，并且在搜索过_ f 早中动态地调整作确定 性选择的概率，当进化到一定代数后，进化方向已经基本确定，这时刈路径i ：信息量 作动态调整，缩小最好和最差路径上的信息量的差距，并且适当加大随机选择的概率， 以利于对解空间的更完全搜索，从而可以有效地克服基本蚁群算法的两个不足。 2 5 2 基于分布均匀度的自适应蚁群算法“幻 基于分布均匀度的自适应蚁群算法是针对蚁群算法加速收敛和早熟、停滞现象的 第一市蚁群算法简介驶研究现状 个蚁群优化算法发j 再：c v r p 问题中的j 衄用研究 矛盾而提出的，此算法根据优化过程中解的分布均匀度，动态地调整信息量更新策略 和选择路径概率，这样就可以在加速收敛和防止早熟、停滞现象之间取得很好的平衡。 ( 1 ) 基于分布均匀度的自适应蚁群算法的优点 基于分布均匀度的自适应蚁群算法是根据当前蚂蚁所走路段分布的均匀情况( 聚 度) 来决定蚂蚁每次选择路径的概率和信息量更新的策略。当聚度较小时，说明各个 蚂蚁所走的路径段的分布情况相对比较分散最优的信息量难以得到强化，导致算法 的搜索速度缓慢。相应的措藏是让较少的几个优质路径上的信息素得到较大程度的增 强：当聚度较大时，表明当前路径上蚂蚁的分如情况相对比较集中，易而导致蚂蚁的 早熟、停滞现象。相应的缓解措施是使解趋向多样化，让较多的路径来使信息素得以 增强：基于分布均匀度的自适应蚁群算法的优点主要体现在以下三大方面：聚度的引 入、信息权重的引入和自适应的信息量更新策略。 ( 2 ) 聚度的引入 设从城市f 共有，条路径到达另外r 个城市f l ，i 2 ，另设上一次迭代中经过 这，条路径上的蚂蚁数分别为口l ，0 2 ，珥，如图2 1 所示，记 斤 咖( f ) 2 j 苫( 堕叫z ) 2 为城市i 的聚度。可见当蚂蚁均匀地 若所有的蚂蚁只集中在条路径上， s m c 。2 砉( 盟) 2 + 一予) 2 = ( 2 1 0 ) 分布在城市i 的r 条路径上，口f 2 孚，n s t a ( i ) 为。 此时聚度s t a ( i ) 最大，为 卅1 一上( 2 1 1 ) v， 记该值为m a x s l , 8 ( i ) ，即最大可能聚度值。 卅= i ：芸；：等( ，一1 ) + 0 5 j + l ( 2 1 2 ) w 为蚂蚁处于城市i 点时下步可选城市的数量；r 为城市i 的相邻的城市数，公式 ( 2 1 2 ) 含义表示为： 1 当城市i 的聚度大时，说明蚂蚁只集中在少数路径上，此时w 就大，易引起早 熟停滞现象，则强制增加在城市i 时蚂蚁有较多的选择路径，迫使s t a ( i ) 降低： 2 当城市i 的聚度小时，说明蚂蚁分散在较多路径上，此n e w 就小，易导致收敛 速度较慢则强制减少在城市i 时蚂蚁下步可选路径变少，迫使s t a ( i ) 增大； 这样通过公式( 2 1 2 ) 来协调早熟停滞现象和收敛速度这对矛盾，达到一个平衡 点。 一个蚁群优化算法及) e 在c v r p 问题中的应用研究 第二章蚁群算法简介及研究i 兕状 c i i y i l 图2 1 城市i 的相邻城市路径上的蚂蚁分布情况 ( 3 ) 信息权重的引入 般蚁群算法中蚂蚁的选择策略主要依赖于其所在的当前城市i 选择下一城市j 的期望程度j 7 疗( 即可访问度或透明度，一般值1 d i j ) 和以i 为起点的各条路径上的信 息量强度为万群( f ) ，这会在一定程度上误导大量的蚂蚁聚集于当前信息量较大的几条 局部距离较短的路径上，基于分布均匀度的自适应蚁群算法通过引入信息权重知对 此情况进行了改善。 引入信息权重蠡的目的： 1 减少蚂蚁在选择下条路径时的误导行为，使信息量大和当前局部距离小的路 径被选择的概率大些； 2 若各条路径上的信息量分布比较集中，则应当使各条路径上的信息量及期望程 度对选择概率的影响的差别小些，各条路径被选中的概率相对均匀些； 3 若信息量分布比较分敬，则应当使信息量和期望程度对选择概率的影响的差 别大些。蚂蚁选择的路径相对更集中一些； 丘：j q 小1 当朋肛露【，】w( 2 1 3 ) 1 0否则 r a n k 是对以城市i 为起点m r 条相邻路径按其信息素由高到底的排序，r a n k j 是 对应的路径( i ，j ) 的序号，q ：w r ( w 由公式( 2 1 2 ) 所得) ： 莉：p 抑缈溉积i u 聊盆触f ，o w 哦陇1 4 ) l 0o t h e r w i s e 对公式( 2 1 4 ) 的分析： ( 1 ) 当几次迭代下来，若城市i 的相邻城市的蚂蚁分布较分散时，城市i 的聚度 第二章蚁群算法简介及研究现状一个蚁群优化算法及其n ：c v r p 问题中的应用酬究 较小，w 和q 值也小，信息权重钰的差距就较大，城市i 为起点的路径被选择的概率分 布就比较集中； ( 2 ) 当儿次迭代下来，若城市i 的相邻城市的蚂蚁分布较集中时，城市i 的聚度 较大，w 和q 值也大，信息权重知的差距就较小，城市i 为起点的路径被选择的概率分 布就比较分散； 公式( 2 1 4 ) 的功能类似于若蚂蚁引起交通堵塞时，强制蚂蚁下次选择时分流；若 蚂蚁在路径中的分布较分散时，强制蚂蚁下次在此城市i 选择下个城市时集中。 基于分布均匀度的自适应蚁群算法的最大特点是在信息素的局部更新和全局更 新时都考虑了当前蚂蚁的分布情况，白的引入是此自适应性算法的核心和灵魂；蚂 蚁在城市i 选择根据相邻城市选择下个城市时也考虑了当时的前代蚂蚁在各个路径上 的蚂蚁分布情况，而且蒸发系数p = w r 为动态变化的。 由于采用自适应选择和动态调整策略，算法的性能明显得到改善，此方法不仅能 够加快收敛速度，节省搜索时闽，而且能够克服停滞行为的过早出现，有利于发现更 好的解，这对于求解大规模优化问题是十分有利的。 一个蚁群优化算法及j 在c v r p 问题中的m 用研究笫三章车辆调度问题( v r p ) 概述 第三章车辆调度问题( v r p ) 概述 3 1v r p 问题的提出和发展 v e h i c l er o u t i n gp r o b l e m 通常称为车辆路由问题或车辆调度问题，简称v r p 。 这个问题首先由线性规划大师d a n t z i g 和r a m s e r 在1 9 5 9 年提出的【l ”。他们把需求 的对象称为顾客( c u s t o m e r 或c o n s u m e r ) ，把顾客的所在位置称为需求结点( n o d e ) ， 把满足顾客的需求称为服务( s e r v i c e ) ，把提供服务所使用的工具称为服务车辆 ( v e h i c l e ) ，把车辆的出发地称为车辆中心( d e p o t ) ，从而v r p 问题可以表述为由一 个中心向具有确定位置的顾客提供服务，而中心的车辆又有容量和最大行程的限制， 求满足顾客需求且行程最短或费用最小的派车方案。 d a n t z i g 和r a m s e r 提出v r p 的同时给出了一个计算方法，后来他们两人又改进 了这个算法【1 4 】。但是这两个算法都没有太注意到路径的节省，而仅仅是路线的组成。 到了1 9 6 4 年c l a r k e 和w r i g h t 提出了一种节省算法1 1 5 】。随着7 0 、8 0 年代数学规划 和网络分析的发展，人们提出了解决这一问题的精确的数学规划方法“”1 。到了 9 0 年代人工智能的发展促进了v r p 算法的研究。人们采用了诸如模拟退火，遗传算 法和t a b u 搜索等智能化算法f 1 92 0 2 ”。总之，v r p 一直得到人们的关注，四十多年 来许多学者和商业公司都投身于v r p 问题的研究并拓展了这个问题。 3 1 1v r p 问题发展三个阶段 第一阶段为古典的v r p 问题研究阶段。这个阶段主要研究一些具体的问题，并 提出了一些著名的算法。但是这时的算法多数注重的是具体问题的派车方案，不太 注意路径长度或费用的节省，而且只能处理顾客较少的问题，可移植性较差。 第二阶段为基于数学规划或刚络分析的v r p 问题的研究阶段。这个阶段因为数 学规划和网络分析有了一定的发展，人们开始用数学规划和网络的最大和最小流来 研究v r p 问题，可以说这个阶段的算法是十分精确的。但是因为v r p 问题是离散的， 所建立的数学规划或网络模型是整数规划或复杂的网络。它们的求解很困难，甚至 不能求解，即使能求得解，也是处理小规模的问题。 第三阶段为基于人工智能算法的v r p 问题的研究阶段。人们利用模拟退火算法、 遗传算法、t a b u 搜索和人工神经网络算法来研究v r p 问题，这些算法是模拟固体退 第三章下辆调度问题( v r p ) 概述个蚁群优化算法肚j e nc v r p 问题中的j 帆昭研究 火过程，生物遗传繁殖，人类的思维过程得到的智能算法，它们能处理大规模的v r p 问题，可移植性较强，能在合理的时间内给出问题的接近最优解或近似最优解，是 值得推广的算法。 3 1 2v r p 问题一般组合条件 合的 ( 1 ) 各结点的需求量：固定需求量，随机需求量； ( 2 ) 服务中心的个数：一个服务中心，多个服务中心： ( 3 ) 服务车辆的类型：一种类型的车辆，多种类型的车辆； ( 4 ) 各结点之间以及结点和服务中心之间的路径：无方向的，有方向的，混 ( 5 ) 车辆的数量：固定的车辆数，车辆的数量无限制： ( 6 ) 服务某一个结点的时间：实现确定的时间，时间窗，时间不确定 ( 7 ) 服务的费用：路径变动费用，固定费用： ( 8 ) 目的：仅最小化路径费用，最小化路径费用和固定费用之和： 3 2v r p 问题的基本解法 ( 1 ) 先分组后确定路线法：首先将一些距离较近的节点分成组，然后在各个 小组内寻求较为节省的路线，最后获得近似最优解1 2 “。 ( 2 ) 先确定路线后分组法：首先产生一条较大的路或圈，而且一般是不可行 的路或圈，再将这个路或圈分成一些含结点较少，可行的路线。 ( 3 ) 节省或插入法：一般从不可行的路线出发，在满足一定约束条件f ，每 一步将一个结点插入，最后得到可行的路线，进而得到近似最优解。如著名的 c l a r k e w r i g h t 算法。 ( 4 ) 改进或交换法：从一条可行的路线中拿出一些结点和另外条可行的路 线的一些结点进行交换，改进路线得到近似解。一般常用的是 2 - o p t ，2 - h o p t ，3o p t 2 3 , 2 4 和l k 2 5 l 局部启发算法( 交换算法) 。 ( 5 ) 基于数学规划方法：一般是采用精确数学语言描述并解决问题，它包括 用数学规划，l a g r a n g e 松弛，动态规划和随机规划来建立v r p 问题的数学模型。其 中最成功的是f i s h e r 和j a i k u m a r 所做的工作，他们将d a n t z i g r a m s e r 的v r p 问题 一个蚁群优化算法及其在c v r p 问题中的应用研究第三章车辆调度问题( v r p ) 概述 建成数学规划模型，并将该问题分解成旅行商问题( t s p ) 和指派问题( q a p q u a d r a t i c a s s i g n m e n tp r o b l e m ) 的组合，从而利用二者已有的研究成果，给出了较好的启发式 算法 2 6 , 2 7 】。 ( 6 ) 智能优化法：一般是采用模拟退火、遗传算法、禁忌( t a b u ) 搜索和人工 神经网络等算法，它们是分别通过模拟固体退火过程，动物的遗传规律，人类的思 维模式等得到的算法。它们运用于求解n p - h a r d 的组合优化问题时能够在合理的时 间内给出近似最优解。蚁群算法是续模拟退火，遗传算法等之后的模拟进化算法， 也属于智能优化算法范畴。 ( 7 ) 精确方法：一般包括分支定界方法，切平面法【2 8 , 2 9 。 3 3 蚁群算法运用于c v r p 问题的研究现状 由上述3 1 卜3 1 2 节可见，c v r p 问题是v r p 问题的一种情况，也是v r p 问题 中最基本的问题。因此把a c o 算法运用于v r p 问题时，首先求解c v r p 问题也变得理 所当然的。c v r p 属于n p h a r d 问题，因为t s p 问题属于c v r p 问题的子问题，即c v r p 问题的一种特殊情况。实际上，c v r p 问题比t s p 问题更难于求解。c v r p 问题包含两 种子问题：b i n p a c k i n g 问题( 背包问题) ，目标是在每辆车子承载量规定的前提下， 使所有顾客进行分组组合，使每辆车子达到或接近最大承载量：最短路径问题，目 标是对于每辆车子而言，访问车内所有顾客的路径达到最小，这就类似于求解一个 t s p 问题。1 9 9 9 年上半年b u l l n h e i m e r f 5 0 】提出了运用于解c v r p 问题蚁群算法 a s r a n k ( a s r a n k c v r p ) 。此后，在2 0 0 2 年r e i m a n n 等【5 l 】又对此算法进行了优化，称 之为a s r a n k c v r p s a v 【j 。 求解c v r p 问题的目标是发现一组路径并且使得所有车辆运行的时间最小或路 径最短。其要求为： a 每俯顾客只需被任何车辆服务一次： b 每辆车子的路线必须从车辆巾心驶出，最后还驶进车辆中心： c 每辆车子的装载顾客的重量不得超过车子的最大承载量： 下面，我们简要地描述一下a s r a n k c v r p 算法和a s r a n k c v r p s a v 算法： 构造图表：a s r a n k c v r p 算法和a s r a n k c v