（计算机软件与理论专业论文）蚁群算法在物流配送路径优化问题上的应用研究.pdf

江苏大学硕士学位论文 摘要 在全球经济一体化的大背景下，伴随着我国经济的飞速发展，物流作为”第 三利润源泉”在我国得到了长足的发展。物流配送是物流活动中直接与消费者相 关联的环节，在物流的各项成本中，配送的成本占了相当高的比例，因此，配送 线路安排得是否合理直接影响着企业的成本支出【。在满足多样化用户需求的前 提下，如何有效地利用现有资源进行车辆调度以减少企业的运行成本，给企业带 来更大的利润，是物流行业发展的目标，也是研究者关注的重点问题。 物流配送问题实质是车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r e ) ，车辆路 径问题具有很高的计算复杂性，属于n p h a r d 问题1 2 3 1 4 1 。随着问题规模的扩大， 传统的基于确定性的优化算法在求解组合优化问题时遇到了困难。于是人们在仿 生学中受到启发，提出了许多启发式智能优化算法，为解决复杂的组合优化问题 ( 如n p h a r d 问题等) 提供了崭新的思路。 蚁群算法便是人类在观察自然界真实蚂蚁觅食的过程中总结出来的仿生优 化算法，它在短短的十余年的发展历程中展现出顽强的生命力，成功地应用于解 决旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，车间作业调度问题( j o b s h o p s c h e d u l i n gp r o b l e m ，j s p ) ，车辆路径问题等组合优化问题。蚁群算法作为新兴的 仿生优化算法，因其具有分布式计算，自组织性和正反馈性质而得到广泛应用。 但搜索时间长，易陷入局部最优解等也是基本蚁群算法的致命的缺点，针对此问 题，本文在研究了遗传算法基础上提出了一种改进的蚁群算法一g 蚁群算法。通 过对解决t s p 问题的实验表明，g 蚁群算法在收敛速度和解的全局性上有更优 的性能。 为了验证算法的性能，我们在v c 6 0 下进行编程实验，并开发出针对对t s p 问题和v r p 问题的应用软件，实验结果表明，利用改进的蚁群算法进行v r p 和 t s p 问题的求解，能够得到令人满意的效果。 最后，针对快速发展的物流配送行业的发展，提出了对开发物流配送车辆计 算机调度管理系统的设想并分析了当前存在的问题，为后来者的相关研究提供了 理论支持和实用的参考意见。 关键词：蚁群算法；车辆路径；组合优化；物流 江苏大学硕士学位论文 a b s t r a c t u n d e rt h eg l o b a lc o n t e x to fe c o n o m i ci n t e g r a t i o n ，w i t ht h er a p i dd e v e l o p m e n to f c h i n a se c o n o m y ，l o g i s t i c s ，w h i c hi sk n o w na s “t h et h i r dp r o f i ts o u r c e ”，h a sm a d e r a p i dp r o g r e s si no u rc o u n t r y d i s t r i b u t i o no fl o g i s t i c sa c t i v i t i e sa s s o c i a t e dd i r e c t l y w i t ht h ec o n s u m e r - r e l a t e ds e c t o r sa n da c c o u n t e df o rav e r yh i g hp e r c e n t a g eo fa l lt h e c o s to fl o g i s t i c s t h e r e f o r e ，h o wt oa r r a n g er e a s o n a b l e n e s sd i s t r i b u t i o nl i n e si m p o s e s ad i r e c ti m p a c to nt h ec o s t so fb u s i n e s s u n d e rt h ep r o m i s eo fm e e t i n gd i v e r s eu s e r r e q u i r e m e n t s ，h o wt ou s ee x i s t e dr e s o u r c e se f f e c t i v e l yt or e d u c et h ec o r p o r a t ev e h i c l e s c h e d u l i n go p e r a t i n gc o s t sa n dt h e nb r i n gg r e a t e rp r o f i t st ot h ee n t e r p r i s ei st h eg o a l o ft h el o g i s t i c si n d u s t r y , a n da l s oi st h ef o c u so fa t t e n t i o na m o n gr e s e a r c h e r s d i s t r i b u t i o np r o b l e mi so n eo ft h em o s ti m p o r t a n ti s s u e so ft h el o g i s t i c si n d u s t r y , w h i c hi se s s e n t i a l l yav e h i c l er o u t i n gp r o b l e m ( v r p ) ，v r ph a sh i g hc o m p u t a t i o n a l c o m p l e x i t y , a n di sn p - h a r dp r o b l e m 。w i t ht h ee x p a n s i o no fs c a l eo ft h ep r o b l e m ， t r a d i t i o n a lo p t i m i z a t i o na l g o r i t h mb a s e do nt h ed e t e r m i n i s t i ce n c o u n t e r e dd i f f i c u l t i e s i ns o l v i n gc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，a n dt h e np e o p l ew e r ee n l i g h t e n e di n t h eb i o n i c s ，a n dp u to u tan u m b e ro fh e u r i s t i ci n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s w h i c hp r o v i d e san e wi d e ao ns o l v i n gc o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s 。 a n tc o l o n ya l g o r i t h mi sab i o n i co p t i m i z a t i o na l g o r i t h mw h i c hi ss u m m e du pb y h u m a nt oo b s e r v et h ep r o c e s so fa n tf o r a g i n g 。i ti sj u s ti na b o u tt e ny e a r so f d e v e l o p m e n th i s t o r yt os h o wi t sv i t a l i t y 。i th a sb e e ns u c c e s s f u l l ya p p l i e dt os o l v e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ss u c ha st 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 ) ， j o b - s h o ps c h e d u l i n gp r o b l e m ( j s p ) ，a n dv e h i c l er o u t i n gp r o b l e m ( v r p ) a n tc o l o n y a l g o r i t h m ，w h i c hi san e w b i o n i co p t i m i z a t i o na l g o r i t h m ，i sw i d e l yu s e db e c a u s eo fi t s d i s t r i b u t e dc o m p u t i n g ，s e l f - o r g a n i z a t i o na n dt h en a t u r eo fp o s i t i v ef e e d b a c k 。b u tt h e l o n gs e a r c h i n gt i m e ，a n de a s yt of a l li n t ol o c a lo p t i m a ls o l u t i o ni sa l s ot h ef a t a l s h o r t c o m i n g so ft h eb a s i ca n tc o l o n ya l g o r i t h m f o rt h i sp r o b l e m ，t h i sp a p e rp r o p o s e s a l li m p r o v e da n tc o l o n ya l g o r i t h mb a s e do ns t u d y i n gt h eg e n e t i ca l g o r i t h ma sw e c a l l e dg - a c a t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tg a n tc o l o n ya l g o r i t h mh a sb e t t e r o v e r a l lp e r f o r m a n c ei nc o n v e r g e n c es p e e do fr e c o n c i l i a t i o n t ov e r i f yt h ep e r f o r m a n c eo ft h ea l g o r i t h m ，w ee x e c u t e de x p e r i m e n t su n d e r v c 6 0 ，a n dd e v e l o paa p p l i c a t i o ns o f t w a r er e s p o n s et ot h et s pp r o b l e ma n dt h ev r p i i i 江苏大学硕士学位论文 p r o b l e m e x p e r i m e n t a l r e s u l t ss h o wt h a tw ec a ng e ts a t i s f a c t o r yr e s u l t su s i n g i m p r o v e da n tc o l o n ya l g o r i t h mo ns o l v i n gv r p a n dt s e a n df i n a l l y , f o rt h er a p i dd e v e l o p m e n to fl o g i s t i c sa n dd i s t r i b u t i o ni n d u s t r y , w e h a v ep u tf o r w a r dt h ei d e ao nd e v e l o p i n gl o g i s t i c sa n dd i s t r i b u t i o nm a n a g e m e n t s y s t e mf o rd i s p a t c h i n gv e h i c l e s ，a n da n a l y s i so ft h ec u r r e n tp r o b l e m s ，a n dp r o v i d ea t h e o r e t i c a ls u p p o r ta n dp r a c t i c a lr e f e r e n c ef o r t h es u b s e q u e n tr e s e a r c h e r s k e yw o r d s ：a n tc o l o n ya l g o r i t h m ；v e h i c l er o u t i n gp r o b l e m ；c o m b i n a t o r i a l o p t i m i z a t i o n ；l o g i s t i c s ； i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密口。 学位论文作者签名：寥t 陪辞 叫年， 月彤e t 指导撕签名身以 即年f 矿月c 厶日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中己注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：私- 啸辞 日期： 伊7 年f 月“日 江苏大学硕士学位论文 第一章序言 本章重点介绍了物流配送路径优化问题的课题背景及研究意义，物流配送路 径优化问题的研究现状。根据本文的研究背景，提出了本文的主要研究内容并在 本章的最后介绍了本文的章节组织结构。 1 1 课题的背景 随着全球经济一体化和信息技术的发展，国家之间、区域之间、城市之间、 企业之间的合作日益加强，物流业成为全球最具发展潜力的新兴行业之一，其发 展程度己日益成为衡量一个国家、一个地区或一个城市现代化水平和综合经济实 力的重要标志喳1 。 经济的发展推动了物流配送业的在我国的迅猛发展。物流配送是指按客户的 订货要求，在配送中心进行分货、配货、并将配好的货物及时送交客户的活动。 现代物流配送流程中存储环节的要求日益减弱，配送成为最重要的环节。而配送 的核心部分是配送车辆的集货、货物配装及送货过程，车辆配送路线的合理优化， 它对于整个物流运输速度、成本、效益的影响都是至关重要的。有数据显示货物 配送在整个物流活动中所占的费用比例在5 0 左右1 。进行配送环节优化，尤其 是对配送车辆的优化调度己成为物流行业的首要任务。 在物流业的发展中，各个企业必须从实际出发，抓住企业发展的最根本的两 大问题：降低成本和满足客户需求，换句话说，就是物流配送调度系统必须在满 足客户需求的情况下，合理地去配置货物，派遣最少的车辆数量并为配送车辆指 派运输时间和运输费用最省的路线，从而以最小的开支完成预定任务。 正确合理地安排车辆的配送线路，提高车辆的利用率，实现合理线路运输能 极大地降低运输成本，节约运输时间，提高客户服务水平，提高经济效益，从而 达到科学管理物流的目的。 1 2 问题的提出 国外将物流配送车辆调度问题归结为车辆路径问题( v e h i c l er o u t i n g p r o b l e m ，v r p ) ，它最早是由d a n t z i g 和r a r n s e r 于1 9 5 9 年提出n m 5 1 ，自此，很快引 起运筹学、应用数学、组合数学、物流技术和计算机应用等领域专家的重视，成 江苏大学硕士学位论文 为运筹学和组合优化领域的前沿和热点问题，各学科专家对此问题进行了大量的 理论研究和实验分析并取得了很大进展。 v r p 问题的一般定义是：对一系列装卸货点，组织适当的行车路线，使调度 车辆有序通过它们，在满足一定约束的条件下( 如货物需求量、发送量、交发货 时间、车辆容量限制、行车路程限制、时间限制等) ，达到一定的优化目标( 如行 车路程最短，费用最低，使用车辆最少，运时间最短等) h 7 1 。 v r p 是一个n p h a r d ( n o n p o l y n o m i a l h a r d ) 问题伫m 儿4 1 ，近二十多年吸引了物 流、数学、计算机等众多领域的专家和学者进行研究。当用户需求点和道路数相 对较少时，v r p 可以通过传统的精确求解方法求得优解，但是，在实际的物流配 送中，往往需要根据实际问题加上许多必要的约束，而且求解规模会很大，形成 各种v r p 问题的变形问题，如多配送中心的v r p ( 简称m d v r p ) 、需要按照客户规定 时间进行送货的带有时间窗的v r p ( 简称v r p t w ) 等等，考虑的约束条件越多，越接 近实际配送情况，问题也就越复杂，求解起来难度就非常大，传统的基于精确求 解的方法就显得力不从心了。 于是，根据物流配送的实际特点，有必要找到一种运算简单，比较容易实现 的非传统算法，在有限的时间内求得较优解，这样，就可以更科学合理地确定配 送线路，提高物流配送车辆效益、实现物流配送科学化，这对物流业的发展具有 重要意义。 1 3 课题研究的意义 从实际应用方面看，物流配送路径优化，是物流配送优化中最关键的一环。 对货运车辆进行路径优化，可以提高物流经济效益、实现物流科学化。车辆调度 是物流管理中最重要的部分。随着社会的发展，消费者对服务质量要求在不断的 提高，高效的车辆调度并找出一条最优的车辆行驶路线，不但有利于降低物流中 货物库存的费用，缩短商品上市的周期，而且逐渐成为物流企业成败的关键。可 见，研究车辆路径问题，进行车辆路线优化，以提高物流效率、降低物流成本、 提高服务质量，并对于促进经济健康稳定的发展都具有十分重要的价值。 从理论研究方面看，车辆路径问题在理论上属于复杂的组合优化问题( 确切 地说是n p - h a r d 问题) 瞳儿3 引，传统的求解小规模的精确算法的求解复杂度在这里 是完全不能接受的，大批的数学家和计算机科学家在n p h a r d 问题上花费了大量 2 江苏大学硕士学位论文 的精力，最终取得了显著的成就，那就是应用仿生学来求解组合优化问题协9 1 。 在这一方面做得最好的莫过于蚁群算法，蚁群算法从提出至今只有十几年，还停 留在仿真阶段，尚未提出数学解释，不过虽然研究时间不长，但已显示出在求解 复杂优化问题方面的优势，其应用前景非常广阔。 可以看出，蚁群算法是一个处于发展阶段，并有广阔的发展空间和巨大的发 展潜力的算法，只要投入足够的精力，就可能在理论上有所突破，这就体现出其 巨大的理论研究价值。本文在研究遗传算法的基础上对蚁群算法进行改进，并验 证了算法的优异的性能。本文对蚁群算法的改进，对组合优化问题的研究是一种 新的尝试。 近些年来，人们在用各种优化算法解决现实中的各种组合优化问题上进行了 探索，如在生产调度问题和旅行商问题中的应用，本文对现有的优化算法进行了 分析和改进，将改进的蚁群算法运用于物流配送路径优化问题中，既有实际的应 用价值，更有深远的理论研究价值，为以后继续深入研究各种组合优化问题和物 流配送车辆调度优化的计算机实现等打下基础。 1 4 本文的研究内容 本文以物流行业发展的客观需要为背景，探讨了物流配送问题的实质属性， 抽象出了物流配送系统的模型，然后针对该问题的研究现状，探讨了解决此类问 题的传统方法和最近几年发展起来的非传统方法，分析了传统方法在解决v r p 问题上的先天不足，最后本文根据基本蚁群算法在求解v r p 问题上出现的问题， 提出了对算法的改进，并通过实验用数据证明了改进的算法在求解v r p 问题上 的性能优势。本文的主要内容如下： ( 1 ) 概述物流配送路径问题的发展需求和研究现状。 ( 2 ) 详细分析了在求解v r p 问题上的传统方法的缺陷，并由此引入了近几年才 发展起来的仿生优化算法，并以t s p 问题为例介绍了蚁群算法在求解组合优化问 题时的步骤。 ( 3 ) 详细分析了基本蚁群算法在求解组合优化问题时遇到的局部最优的问 题。 ( 4 ) 针对基本蚁群算法的不足和遗传算法的特点，提出了基于遗传学的蚁群 算法，并用实验数据证明了在求解组合优化问题上改进算法的优势所在。 ( 5 ) 抽象出了车辆路径问题的数学模型，并把改进的蚁群算法应用到解决v r p 江苏大学硕士学位论文 问题上，同时在v c 6 o - f 开发出了蚁群算法实验室软件。 ( 6 ) 最后针对本文的研究工作，提出了在车辆路径问题上尚存在的问题，并 为以后的研究工作提出了建设性意见。 1 5 本文的组织结构 针对本文的选题和现阶段研究课题的发展现状，将本文的章节及内容安排如 下： ( 1 ) 第一章引言 概述了本文课题研究的背景和意义以及研究的主要问题和内容。 ( 2 ) 第二章基本蚁群算法 本章全面介绍了基本蚁群算法，分析了蚁群算法的生物学原理，建立了蚁群 算法的数学模型，然后以t s p 问题为例讲述了基本蚁群算法在求解t s p 问题上的操 作步骤，同时分析了基本蚁群算法的系统特性，最后，本章详细分析了基本蚁群 算法在求解组合优化问题时存在的缺陷。 ( 3 ) 第三章基于遗传学的蚁群算法 本章根据第二章基本蚁群算法在求解组合优化问题时存在的缺陷，提出了基 于遗传学的蚁群算法，分析了在求解组合优化问题时参数的设置对算法性能的影 响，并以实例验证了各个参数的最优组合，最后，作者自行开发出了针对t s p 问 题和v r p 问题的蚁群算法实验室应用软件，并以实验数据为依据，验证了改进的 蚁群算法在求解t s p 问题上的优势。 ( 4 ) 第四章物流配送路径优化问题的研究 本章从现实生活中存在的车辆调度问题入手，对v r p 问题进行了数学模型的 抽象，然后介绍了解决v r p 问题的几种方法，分析了传统方法在求解v r p 问题时的 缺陷，由此引入了仿生算法在v r p 问题上的应用。最后详细论述了n p c 问题和 n p h a r d 问题的关系，说明了v r p 问题的在组合优化问题中的所属范畴。 ( 5 ) 第五章g 一蚁群算法在物流配送问题中的应用 本章首先论述了蚁群算法在求解t s p 和v r p 问题上的区别，然后探讨了如何由 t s p 问题的求解转向对v r p 问题的求解。论述了带有时间窗的v r p 问题的数学模型， 以及改进的蚁群算法在v r p 问题上的应用，给出了算法求解的流程图以及操作过 程中的关键步骤。最后以两个实例作为对改进算法的验证，论证了改进的算法在 4 江苏大学硕士学位论文 求解v r p 问题上的优势。 ( 6 ) 第六章总结 本章最后对本文的工作进行了总结，并对以后的工作提出建设性意见。 5 江苏大学硕士学位论文 第二章基本蚁群算法 本章以t s p 问题为例重点介绍了基本蚁群算法。首先介绍了自然界中蚁群的 觅食行为，然后分析了基本蚁群算法的机制原理，详细论述了基本蚁群算法的数 学模型并以求解t s p 问题为例介绍了算法的实现步骤。分析了算法的系统特性和 复杂度。最后，本章详细论述了基本蚁群算法在求解组合优化问题时容易出现的 问题并分析了导致此问题的原因。 2 1 自然界中蚁群的行为 在自然界中，单只蚂蚁的能力和智力非常有限，但整个蚂蚁群体却表现出高 度机构化的社会组织，许多情况下整个蚁群协作完成的任务要远超过蚁群中单只 蚂蚁所完成的任务的叠加之和，蚁群在集体活动中所表现出的高度社会性使他们 能胜任各种复杂的任务。现实生活中，我们常可以观察到大量蚂蚁觅食时在巢穴 和食物源之间形成的轨迹，我们惊奇地发现几乎每次觅食时他们所走的路径都是 最短的，不用担心他们多走了什么弯路或冤枉路，觅食轨迹如图2 1 ( a ) 所示。 另外，蚁群在觅食途中还表现出高超的自适应性，蚁群能够根据环境的变化 自动调整觅食轨迹。如在蚁群觅食轨迹路线上突然出现障碍物时，刚开始时蚂蚁 在不同路线上的分布是大致均匀的，不管路径长短，蚂蚁会以相同的概率选择不 同的路线，整个蚁群就表现出大致等同的两种选择，如图2 1 ( b ) 所示。蚂蚁在运 动过程中，能够在其经过的路经上分泌一种化学刺激物一信息素( p h e r o m o n e ) 。 而且每只蚂蚁都能够感知这种物质的存在及其强弱，并以此指导自己的运动方 向，蚂蚁倾向于信息素浓度高的方向移动。由于相等时间内较短路径上的信息量 就遗留得比较多，所以选择较短路径的蚂蚁也随之增多。由此可见经过一段时间 的调整，蚁群能重新找到通往食物源的最短路径，觅食轨迹如图2 1 ( c ) 所示。 由于大量蚂蚁组成的蚁群集体行为表现出了一种信息正反馈现象，即某一路 径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通 过这种信息交流机制来交流信息，并最终沿着最短路径找到食物源的n 引。 6 江苏大擘项士擘 盘论文 酗21 现实生活中蚁群觅食的轨迹图 2 2 基本蚁群算法的机制原理 蚁群算法是人类在长期观察蚁群觅食活动中总结出来的仿生优化算法作为 一种新型智能模拟算法，本算法采用了以下假设o ”： ( 1 ) 蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其所处的局部环 境做出反应，也只对其周围的局部环境产生影响。 ( 2 ) 蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行 为实际上是其基因的适应表现，即蚂蚁是反应型适应性主体。 ( 3 ) 在个体水平上，每只蚂蚁仅根据环境做出独立选择：在群体水平上，单 只蚂蚁的行为是随机的但蚁群可通过自组织过程形成高度有序的群体行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应 阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路 径上经过的蚂蚁越多，遗留下的信息素越多，则该路径越容易被选择；同时由于 信息素在时刻挥发，时间越长，信息量会越小。在协作阶段候选解之间通过信 息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要 对所求问题的每一个方面都有详尽的认识，自组织本质上是蚁群算法机制在没有 外界作用下使系统熵增加的动态过程，体现了从无序到有序的动态演化。 2 3 基本蚁群算法模型的数学描述 由于蚁群算法最初应用于解决t s p 问题，为方便说明算法，这里以t s p 为例介 畸 。簸霉鬻盎1 江苏大学硕士学位论文 绍基本蚁群算法模型1 。 设i l l 是蚁群算法中蚂蚁的总数，n 是城市的个数，用b i ( r ) 表示t 时刻位于城市i 处的蚂蚁数目，则m = b 。( t ) ( 2 1 ) i = l ( f ) 为t 时刻从城市i 到城市j 的路径上的信息量，( 0 ) 2 e o n s t ，表示初始时 各路径上信息素相同且是常量。 为了防止同一只蚂蚁重复访问某一城市，每只蚂蚁k ( k = l ，2 ，m ) 都会背负 一个禁忌表t a b u 。，用来记录k 所走过的城市，每只蚂蚁每走过一个城市都会修改 自己的t a b u 。，同时根据各条路径上的信息量和启发信息来计算状态转移概率， 从而决定下一步要走的路径。用p ：( ，) 表示t 时刻蚂蚁k 在i 处选择到j 的路径的概 率，则 露( ，) =1 再而瓦可 s c a l l o w e d x 0 ， 萄a l l o w e d k 否则 ( 2 2 ) 式中，a l l o w e d k 表示在城市k 处下一步所允许选择的城市，a 表示了遗留信息 对蚂蚁当前选择的影响，p 表示了启发信息对蚂蚁当前选择的影响n 刳。 1 ( ，) 为启发函数，其表达式为r i o ( t ) 2 丁1 ( 2 3 ) ”o 其中z ，表示了两两城市之间的距离，对于蚂蚁k 来说，吒越小，选择从i 到j 的几率越大。从这里也可以看出，c 【过小时，蚂蚁选择路径是主要依赖路径z ，的 大小，这样算法容易陷入局部最优解；若b 过小，则会导致蚂蚁群体陷入纯粹的 随机搜索，这样很难找到最优解。 为了避免残留信息素过多引起的残留信息淹没启发式信息的问题，使蚂蚁能 准确感知路径信息，我们依照自然界中真实蚂蚁的行为，在每只蚂蚁走完一步( 局 部更新) 或者走完所有的城市后( 全局更新) ，对路径上的信息素进行更新n 驯，更 新的规则如下： r , j ( t + 聆) = ( 1 一p ) 幸l ( ，) + a r ( t ) ( 2 4 ) a r ，( ，) 2 a x e ( t ) ( 2 5 ) 8 江苏大学硕士学位论文 其中p 表示路径上信息素挥发的快慢，( 卜p ) 表示了信息素的残留数量，为了 更有效模拟真实蚁群，这罩设p 的取值范围是：p c 【o ，1 ) ，a r , j ( o 表示了本次循环 中路径( i ，j ) 上信息素的增量，( ，) 表示本次循环中蚂蚁k 在路径( i ，j ) 上的信 息素增量，l ( 0 ) 表示初始状态各条路径上的信息素增量为0 。 根据信息素更新策略的不同，d o r i g om 最初提出了三种不同的基本蚁群算法 模型，分别称之为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 模型， 其差值就在于t ( ，) 的求法不同n 2 1 。 在a n t c y c l e 模型中 嘲归 詈若第k 只蚂蚁在本次循环中经过蛳) ( 2 6 ) 【0 否则 式中，q 表示信息素强度，它在一定程度上影响着算法的收敛速度，厶表示 第k 只蚂蚁在本次循环中所走的路径的总长度。 在a n t q u a n t i t y 模型中 苟( ，) ：j 苦若第k 只蚂蚁在t 和t + l 之间经过( i ，j ) ( 2 7 ) 【0 否则 在a n t - d e n sit y 模型中 = 宇黼嚣蚁在诩t + 1 之峪逝场 ( 2 8 ) d o r i g om 提出的这三种模型，区别就在于信息素的更新方式不同，公式( 2 7 ) 和公式( 2 8 ) 中利用的是局部信息，也就是蚂蚁每完成一步就更新路径上的信息 素，而公式( 2 6 ) 中利用的是整体信息，即蚂蚁完成一个迭代操作后更新所有路 径上的信息素。通常，利用a n t c y c l e 模型求解t s p l b 题时性能较好，因此常采用 a n t - c y c l e 作为蚁群算法的基本模型。 2 4 基本蚁群算法的实现 2 4 i 基本蚁群算法实现的步骤 以t s p 问题为例，基本蚁群算法的具体实现步骤如下： ( 1 ) 初始化参数。令时间t = 0 和循环次数n c = 0 ，设置最大循环次数为 9 江苏大学硕士学位论文 ，将m 只蚂蚁置于那个元素( 城市) 上，令有向图上每条：j 2 ( i ，j ) 的初始化信 息量0 ( f ) = c o n s t ，其中c o n s t 表示常数，且每条边上的信息素增量a 毛( ) = 0 。 ( 2 ) 循环次数c 一胁+ 1 ； ( 3 ) 蚂蚁的禁忌表索引号k = 1 ； ( 4 ) 蚂蚁数目k k + l ； ( 5 ) 蚂蚁个体根据状态转移概率公式( 2 2 ) 计算的概率选择下一个城市j 并 前进，j 属于 c t a b u ) ； ( 6 ) 修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市上，并把该城市 移动到该蚂蚁个体的禁忌表中，表示本次迭代中此蚂蚁已经走过了该城市。 ( 7 ) 若集合c 中城市为遍历完，即若k ：n c m “，则循环结束并输出程序 的计算结果，否则清空禁忌表并跳转到( 2 ) 步。 2 4 2 基本蚁群算法实现的流程图 以t s p 为例，基本蚁群算法的程序机构流程如图2 2 所示。 ( = 牙两) 堑西蓟錾 图2 2 基本蚁群算法的程序结构流程图 l o 善 江苏大学硕士学位论文 2 5 基本蚁群算法的系统特性 系统学的基本特点是强调整体性，它可以确定为处于一定关系中并与环境发 生关系的各组成部分的综合体，即系统具有如下三个基本特征阳1 n0 j ：多元性，相 关性和整体性。在自然界中的蚁群中，蚂蚁个体的行为是系统的元素，蚁群中个 体的相互影响体现了系统的相关性，而蚁群可以完成个体完成不了的任务则体现 了系统的完整性，显示出系统整体大于部分之和的整体突出原理。作为对蚁群觅 食行为抽象的蚁群算法，如果把算法也看成一个整体，那么我们会发现它也具备 了系统的特征，采用多只蚂蚁的求解结果会明显优于单只蚂蚁的求解结果，不具 有加和性，整体大于部分之和，所以基本蚁群算法也是一个系统。 如果把基本蚁群算法作为一个系统来研究，那么它就具有如下的系统学特征 1 l 】： ( 1 ) 分布式计算。在蚁群系统中，每只人工蚂蚁在问题的解空间上同时独立 地构造问题的解，而整个算法的最终解不会由于某只蚂蚁的缺陷受到太大影响。 所有的仿生优化算法都可以看做按照一定的规则在问题解空间搜索最优解的过 程，所以搜索解的初始选址会直接关系到算法求解结果的优劣，而蚁群算法把人 工蚂蚁均匀分布在求解空间的点上独立求解，使得算法有较强的全局搜索能力， 也增加了算法的可靠性。 ( 2 ) 自组织性。自组织性是指在没有外界作用干预下系统熵增加的过程( 即系 统从无序到有序的的进化过程) ，基本蚁群算法体现了这一过程，初始状态下人 工蚂蚁无顺序的求解，但是经过一段时间的进化，越来越趋近于最优解。自组织 大大增强了算法的鲁棒性。 ( 3 ) 正反馈性。系统的正反馈性指的是现在的行为会作为未来行为的影响因 素。在自然界中的蚂蚁能够最终找到最短路径，直接依赖于最短路径上的信息素 的累积，而同时本只蚂蚁会继续在这条路径上遗留更多的信息素以影响其他蚂蚁 的行为，所以信息素的累积是个正反馈的过程。 2 6 基本蚁群算法的复杂度 2 6 1 基本蚁群算法的时间复杂度 设有n 个城市的t s p 问题，m 为算法采用的蚂蚁数目，最大的循环次数为性， 江苏大学硕士学位论文 则根据2 4 1 中算法步骤的描述，可以逐步求出算法的时间复杂度n 3 儿1 钔。如表2 1 所示。 表2 1 基本蚁群算法的时间复杂度分析 步骤操作过程时间复杂度 ( 1 )初始化n 个城市的距离和放置m 个蚂蚁o ( n 2 + m 、 ( 2 )设置m 个蚂蚁的禁忌表 o ( m ) ( 3 )m 只蚂蚁单独构造解o ( n 2 m ) ( 4 )信息素轨迹浓度的更新o ( n 2 ) ( 5 ) 判断是否满足终卜条件 o ( n c m 。) 当城市规模足够大( 即n 足够大) 时，由于基本蚁群算法中的m 只蚂蚁要完全遍 历r 1 个城市，经过的迭代次数是n c ，则整个计算过程的时间复杂度为 t ( n ) = o ( n c m 。木n 2 木m ) 2 6 2 基本蚁群算法的空间复杂度 还是以n 个城市规模的t s p 问题问题为例，算法中采用的蚂蚁数目为m ，则系 统所需的内存开销如表2 2 所示 表2 2 基本蚁群算法所需要的空间开销 步骤内存开销空间复杂度 ( 1 ) 用t a o 【n 】【n 】记录n 个城市见两两间信息素强度 o ( n 2 ) ( 2 ) 用t a b u m n 记录m 只蚂蚁背负的禁忌表 o ( m 幸n ) ( 3 ) 用d i s t a n c e n n 记录n 个城市两两见的距离信息 o ( n 2 ) ( 4 ) 用s o l u t i o n m 来记录本次迭代中每只蚂蚁所搜索路 o ( m ) 径的k 度 ( 5 ) 用b e s t r o u t e n 米记录最终最终最优解 o ( n ) 通过对基本蚁群算法各个步骤中空间复杂度的分析，可知其整个程序运行期 间的空间开销复杂度为 s ( n ) = 0 ( n 2 ) + 0 ( m 木n ) 2 7 基本蚁群算法的缺点 蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很多 观点都来源于真实蚁群。真实蚂蚁在初始觅食时，总是以蚁穴为起始点，向四周 随机选择路径，从而增加寻找食物的范围啪1 。当某个蚂蚁找到食物源后，会在蚁 穴与食物源之间留下信息素，引导蚁群逐渐向信息素浓度高的方向移动，表现出 一种信息正反馈现象，最终找到一条从蚁穴到食物源的最短路径。但是基于仿生 学的计算机模拟程序在运行时总是会出如下现的问题： ( 1 ) 程序能很快的得到结果，但很显然不是最优值，甚至结果和已知最优解 1 2 江苏大学硕士学位论文 相差甚远。 ( 2 ) 程序运行较长时间仍然未得到任何优化结果。 以上出现的这两种情况就是我们经常所说的陷入局部最优解和收敛速度慢。 经过对基本蚁群算法的分析，我们找到导致这种情况几种原因： a ) 初始化的时候预置的路径信息影响了蚂蚁的路径选择。 蚂蚁觅食可分为两个阶段：开始觅食时，以蚁穴为起始点，向四周随机发散， 以增加搜索食物的范围。当找到食物源后，会在蚁穴与食物源之间留下信息素， 引导蚁群逐渐向信息素浓度高的方向移动，表现出一种信息正反馈现象，最终找 到一条从蚁穴到食物源的最短路径。 但是我们在程序设计中，往往首先就把各条路径上的信息设置为常量，在蚁 群算法中，首先将蚂蚁随机置于n 个顶点( 城市) 上，令每条路径( i ，j ) 上的初始 信息量r ，( o ) = c ( c 为常数) ，蚂蚁根据各条路径上的信息量及路径的启发信息来 计算状态转移概率，而状态转移概率由公式( 2 2 ) 决定，即r , j ( o ) 和r , j ( t ) 的乘积来 确定，而此时r , j ( 0 ) 为常数，那么实际上由r , j ( t ) 来决定状态转移概率，又因为 仍肜) = _ 1，且嚷为相邻两个城市之间的即离，t g 就是在初始状态下蚂蚁仅仅 q l ， 根据两两城市间的距离来选择下一个城市。由于两点之间距离的信息在蚂蚁开始 搜索时的作用，导致蚂蚁初始搜索空间的减小，容易陷入局部最优。 那么这种情况就是我们在上面看到的第( 1 ) 种情况，程序过早的陷入了局部 最优解。 b ) 为了增大程序的搜索空间，基本蚁群算法在实现时采取的路径选择方式 为轮盘赌，这样就就会忽略了信息素在蚂蚁个体路径选择时的积极作用，也就淡 化了其他蚂蚁在构造解的过程中所发现的解，从而是程序陷入盲目的随即搜索， 耗费了很多的c p u 时间，收敛速度变慢。 江苏大学硕士学位论文 第三章基于遗传学的蚁群算法 根据上一章对基本蚁群算法缺点的分析，本章提出了基于遗传学的蚁群算 法。首先介绍了基于遗传学的蚁群算法的原理，然后介绍了算法模型和算法实现 的具体步骤。分析了参数的设置对算法求解性能的影响。最后，作者开发出了基 于v c 6 0m f c 的单文档应用程序并进行了仿真实验，验证了改进算法的性能。 3 1 基于遗传学的蚁群算法( g 蚁群算法) 的原理 上一章我们详细分析了基本蚁群算法在求解组合优化问题时存在的问题，基 本蚁群算法中，路径信息的正反馈机制能强化所找到的性能较好的解，但是却容 易陷入停滞状态；另一方面，路径的随机选择策略在一定程度上降低了陷入停滞 状态的可能，却又会导致盲目的随机搜索。 作者在深入研究遗传算法的基础上，发现遗传算法的交叉变异操作理论上能 解决这一矛盾，提出了基于遗传学的蚁群算法一蚁群算法。其核心思想就是在 每一次迭代搜索后，都把当前解和最优解进行交叉变异，这样既能搜索更大的解 空间，又能使系统陷入局部最优后跳出停滞状态。 本文提出的对蚁群算法的改进，主要围绕提高收敛速度和全局搜索能力。针 对蚁群算法自身的先天不足，引入了遗传算法的遗传操作，以改进算法的局部最 优搜索能力，同时避免陷入随机搜索情况的出现，提高算法的效率。 3 2 基于遗传学的蚁群算法的实现 3 2 1g 蚁群算法实现的步骤 g 一蚁群算法的基本思想是在以蚁群算法为主体的基础上引入遗传算法的思 想，目的是让蚁群算法经过迭代产生遗传算法所需的初始种群数据，提高种群数 据的多样性。然后，遗传算法经过选择、交叉和变异操作，为蚁群算法模块提供 反馈数据，防止陷入，早熟收敛n 7 m 利。这罩仍然以求解t s p 问题为例来介绍g 一蚁 群算法，实现的具体步骤如下： ( 1 ) 参数的初始化： ( 2 ) 迭代次数n c n c + l ： ( 3 ) 将m 只蚂蚁随机置于n 个城市： 1 4 江苏大学硕士学位论文 ( 4 ) 蚂蚁所走过的步数s t e p = 1 ： ( 5 ) 蚂蚁的标识号k = 1 ： ( 6 ) 对于每只蚂蚁，按转移概率选择下一城市，并修改路径信息。 ( 7 ) 执行s t e p s t e p + 1 ，若蚂蚁遍历完所有城市，即s t e p = n ，则把 得到的当前结果交给遗传算法模块处理，否则跳转到( 5 ) 。 ( 8 ) 对从遗传算法模块得到的解进行验证，看是否满足结束条件，若满足， 则退出系统，输出结果。否则转到( 2 ) 。 在上述步骤( 7 ) 中，蚁群算法处理得到的初始种群数据交给遗传