（信号与信息处理专业论文）基于蚁群算法的物流配送路径优化研究与应用.pdf

西华大学硕士学位论文 摘要 随着经济全球化的趋势增强和科技的迅猛发展使物流业得到了发展，致使车辆增 多，最终导致了环境问题的出现。要推进经济的可持续发展，就需节能减排，最终进入 “低消耗、低污染、低排放”的全新时代。为了减少气体排放量，节约成本，就需要从 交通运输环节做优化，优化的重点即是配送车辆的路径优化。这既能实现物流配送公司 利益的增加，又能使气体排放量减少，污染降低，得到双赢，对国家实现可持续发展具 有重要意义。 奉课题为“基于蚁群算法的物流配送路径优化研究与应用”。首先，介绍路径优化 的几种智能算法的原理与求解过程。然后，阐述基本蚁群算法的原理与求解t s p 问题的 框图，由_ 丁解决实际问题时，基本蚁群算法有不足之处，再提出能克服其缺点的改进算 法，并对改进算法进行比较。最后，采用较好的改进算法来设计路径优化系统，从路径 优化系统中能得到配送车辆的路线，最终达到节能减排的目的。 本文主要从以下几个方面展开具体的研究工作： ( 1 ) 路径优化的智能方法原理与比较：主要介绍了智能算法的基本原理、框图与 运行框架，l ：对智能算法进行比较，为后面提出的蚁群算法作好铺垫。 ( 2 ) 基本蚁群算法：介绍蚁群算法的原理，求解t s p 问题的流程框图，求解实际 问题时出现在不足，引出了改进蚁群算法：自适应蚁群算法和最大最小蚁群算法，并用 这两种算法对t s p 问题作比较，得出最大最小蚁群算法较好的结果。 ( 3 ) 路径优化系统研究：采用最大最小蚁群算法设计路径优化系统，首先用 l a t l a b 的g u i 来设计界面，在仿真界面上能够清楚得出路线的走向；最后采用v i s u a lc + + 来设 计一个软件，从设计的软件中可以求出v r p 问题的路线走向。 结果表明，该路径优化系统能清楚的给出配送车辆的配送路线，最少的配送车辆数， 且能够在实际应用当中突现其较重要的部分，最终能够实现节能减排，可持续发展的目 的。 关键词：节能减排；物流配送路径优化；蚁群算法；改进蚁群算法；路径优化系统 基丁蚁群算法的物流配送路径优化研究j 应用 ab s t r a c t i h ed e v e i o p m e n to f 。l o g i s t i c si n d u s t 呵m a d eb ye n h a n c e m e n t so f 。t h et r e n do fe c o n o m i c g l o b a l i z a t i o na n dr a p i dd e v e l o p m e n to f s c i e n c ea n dt e c h n o l o g yl e a dt oi n c r e a s i n gv e c h i c l e sa n d t h ee m e r g e n c eo fe n v i r o n m e n t a lp r o b l e m sf i n a l i y e n e r g ys a v i n ga n de m i s s i o nr e d u c t i o ni s i n d i s p e n s a b l et op r o m o t et h es u s t a i n a b l ee c o n o m i cd e v e l o p m e n ta n de n t e ran e we r ao fl o w c o n s u m p t i o n ，l o wp o l l u t i o na n di o we m i s s i o n s i no r d e rt or e d u c eg a se m i s s i o n sa n ds a v ec o s t ， o p t i m i z a t i o no nt r a n s p o r t a t i o ni sn e e d e d ，a n dt h ep o i n ti sd i s t r i b u t i o nv e h i c i ep a t h o p t i m i z a t i o n t h i sc a nn o to n l ya c h i e v et h ei n c r e a s eo fl o g i s t i c se n t e r p r s e si n t e r e s t s ，b u ta l s or e d u c e e m i s s i o n sa n dp o l l u t i o nt og e taw i n w i ns i t u a t i o na n di sv i t a li m p o r t a n tt oa c h i e v es u s t a i n a b l e d e v e l o p m e n to ft h ec o u n t r y t h et o p i ci st h er e s e a r c ha n da p p l i c a t i o no fl o g i s t i c sd i s t r i b u t i o np a t ho p t i m i z a t i o nb a s e d o na n tc o l o n ya l g o r i t h m f i r s t l y ，i n t r o d u c ep “n c i p l e sa n ds o l u t i o n so fs e v e r a ii n t e l l i g e n t a l g o r i t h m s ，s e c o n d i y ，d e s c r i b ep r i n c i p i eo fb a s i ca n tc o l o n ya i g o r i t h ma n db l o c kd i a g r a mo f s o l v i n gt s pp r o b l e m s ，t h i r d l y ，p r o p o s et h ei m p r o v e da i g o r i t h mt oo v e r c o m et h es h o r t c o m i n g s o ft r a d i t i o n a la i g o “t h ms o l v i n gp r a c t i c a lp r o b l e m s ，f i n a l l y ，t a k eb e t t e ri m p r o v e da l g o r i t h mt o d e s i g nv i c h c l eo p t i m i z a t i o ns y s t e ma n dg e td e l i v e 眄v i c h c l er o u t ef r o mi tt or e a l i z et h et a 唱e to f e n e r g ys a v i n g i nt h i sd i s s e r t a t i o n ，s p e c i f i cr e s e a r c hw o f ki sc a r r i e do u tm a i n l y 疗o mt h ef o l i o w i n g a s p e c t s ： ( 1 ) c o m p a r i s o na n dp r i n c i p l eo f i n t e l l i g e n tm e t h o do f r o u t eo p t i m i z a t i o n ：b a s i cp r i n c i p i e s b l o c kd i a g r a m sa n do p e r a t i n gf r a m e 、v o r ko f i n t e i i i g e n ta l g o r i t h ma r ei n t r o d u c e da n dc o m p a r e d ， w h i c hm a k e st h ep r e p a r a t i o nf o r t h ea l g o r i t h mp r o p o s e dl a t e r ( 2 ) b a s i ca n tc o i o n ya l g o r i t h m ：p r i n c i p l e s ，f l o wd i a 黟a mo fs o i v i n gt s pp r o b l e m sa n d s h o r t a g ef o rs o i v i n gp r a c t i c a lp r o b l e m so fb a s i ca l g o r i t h ma r ei n t r o d u c e da n di m p r o v e d a i g o “t h m a d a p t i v e a n t c o l o n ya l g o r t h m a n dm a x m i na n t c o i o n ya l g o r i t h m i s p r o p o s e d c o m p a r i s o no ft h e s et w oa i g o r i t h m sf o rt s pp r o b l e mi sm a d ea n dc o n c l u d e st h a t m a x - mi na n tc o l o n ya i g o r i t h mh a sab e t t e rp e 晌m a n c e ( 3 ) r e s e a r c ho nr o u t eo p t i m i z a t i o n ：m a x m i na n tc o l o n ya l g o r i t h mi st a k e nt od e s i g nr o u t e o p t i m i z a t i o ns y s t e m f i r s t ，d e s i g ni n t e r f a c ew i t hm a t l a b sg u la n do b t a i nr o u t e sd i r e c t i o n 腼ms i m u l a t i o ni n t e a c e ，f i 舱l i y ，d e s i g ns o 胁a r ew i t hv i s u a lc + + a n ds o l v er o u t ed i r e c t i o no f v r p p r o b l e mf 沁mi t t h er e s u i t ss h o wt h a tt h er o u t eo p t i m i z a t i o ns y s t e mc a ng i v e st h ed e l i v e 眄r o u t ea n dt h e m i n i m u mn u m b e r so f v i h i c i e s ，a n dr c f l e c t st h ei m p o r t a n tp a r to f p r a c t i c a la p p i i c a t i o nt oa c h i e v e t h ep u r p o s eo f e n e r g ys a v i n ga n de m i s s i o nr e d u c t i o na n ds u s t a i n a b l ed e v e l o p m e n t 。 i i 西华大学硕士学位论文 k e yw o i d s ：e n e r g ys a v i n ga n de m j s s i o n sr e d u c t i o n j o p t l m i z a t i o no ni o g i s t i c sd e i v e r yr o u t e ； a n tc o i o n ya 1 9 0 r i t h m ；l m p r o v e da n tc 0 1 0 n ya 1 9 0 r i t h m ；r 0 u t e0 p t i m i z a t i o ns y s t e m i i i 西华大学硕士学位论文 1 绪论 随着车辆的增多，气体排放也增加，污染也日益严重，而现代物流又是经济的重要 组成部分。要使经济与环境可持续发展，就需要降低资源的消耗。而在物流配送过程中， 要降低资源消耗，就得从配送路径上着手，这是可持续发展的主要依据和最终目标。 1 1研究目的及意义 随着经济全球化的趋势增强和科技的迅猛发展，世界各国经济发展面临着前所未有 的机遇和挑战。物流是提高劳动生产率、降低资源消耗的“第三利润源泉”，在国民经 济与社会发展中发挥着重要作用，发展同时，全球性的环境问题也日益突出。推进节能 减排，实现可持续发展，成为我国转变经济增长方式的内在要求。2 0 0 9 年在哥本哈根国 际气候会议上，中国政府向世界承诺，到2 0 2 0 年单位g d p 碳排放比2 0 0 5 年减少4 0 一4 5 ，并作为约束性指标纳入国民经济和社会发展中长期规划【l 】。“低碳革命”正在 兴起，人类也将因此进入“低能耗、低污染、低排放”为基础的全新时代。据有关部门 测算，每年物流业的油品消耗占全社会油品消耗总量的1 3 【l 】，其中消耗量较多的运输 行业如表1 所示。 表1 1我国运输行业每年的油品消耗量 t a b 1 1 c h i n a s 缸1 m s p o r t a t i o ni n d u s t r ) r sa n n u a lo i lc o n s u m p t i o n 卡车铁路船舶飞机 消耗量( 吨) 1 4 l0 4 5o 5 52 2 从上表可以看出，节能减排的目标对物流业的发展有很大影响，有数据显示，货物 配送费用占物流活动费用的5 0 左右，即要发展低碳物流，就得从交通运输环节做优化。 作为优化的重点，车辆路径问题( v e l l i c l er d u t 洫gp r o b l 锄，冲) 是物流配送路径优化 的关键点，问题被提出后得到各学科专家的广泛关注，且各国学者也对其进行了多领域 的研究工作，并取得相应的成果。 车辆路径问题是组合优化问题，也属于n p h 砌问题，也就是说，在计算时间内 无法获得问题的最优解。正是由于这个原因，在解决大规模的实际应用问题时，就得采 用近似的方法来求在一个相对较短的时问内获得近似最优解。解决此类问题，也有多种 算法，其中包括：禁忌搜索算法、模拟退火算法、遗传算法、粒子群算法、人工神经网 络算法等，并且这些算法在一些领域也得到相当好的应用，但都有缺陷存在。 基于蚁群算法的物流配送路径优化研究与应用 蚁群算法是意大利学者m a r c od 耐g o ( 及其导师c o l o n l i ) 于1 9 9 1 年在其博士论文 中提出，该算法的提出引起了学者的关注，该算法采用了正反馈并行自催化机制，有较 强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点，在许多复杂组合优 化问题方面已体现出其优异性能和巨大发展潜力。物流业的快速发展，环境保护的呼声 正日益增强，对货物配送的车辆路径优化已突显其重要性。本文所设计的路径优化系统 可以在配送货物之前把路线进行归划，此系统可广泛用于物流配送公司、邮局、快递公 司、银行资金配送等，从而达到节约配送成本，减少污染排放，促进人与社会和谐发展 的目的。 1 2 国内外研究现状及发展趋势 1 2 1国内外研究现状 蚁群算法最早是由意大利学者m a r c od o r i g o ( 及其导师c 0 1 0 r n i ) 于1 9 9 1 年在其 博士论文中提出，且早期的研究成果都是一些小型的研讨会及其会议录上所发表的，世 界各地对此了解并不多。如：1 9 9 4 年c o l o r n i 等人的“a n ts y s t e mf o rj o b s h o p s c h e d u l i n g ”发表在比利时运筹学学报第1 期上心3 ；1 9 9 6 年c 0 1 0 r n i 及d o r i g o 等 人在i e e e 系统、人、控制论汇刊第1 期发表了“a n ts y s t e m ：o p t i m i z a t i o nb ya c o l o n yo fc o o p e r a t i n ga g e n t s 川2 3 等，此后还得到一系列的报道，如n e ws c ie n t i s t ( 1 9 9 8 ) 、b b cn e w s ( 2 0 0 0 ) 。蚁群算法的发展得到了一些公司的注意，也已经在实际应 用中得到了应用，如e u r o b i o s ( w w w e u r o b i o s c o m ) 最早采用a c 0 算法于不同调度问题 的应用；a n t o p t i m a ( w w w a n t o p t i 吼c o m ) 对a c 0 的实际应用发展也起着非常重要的推 动作用，做出了成功产品包括：( 1 ) d y v o i l ，是对一个不统一的车队燃油进行管理和 优化，首次被瑞士的p i n ap e t r o l i 所使用；( 2 ) a n t r o u t e ，用以解决m i g r o s 的数百 辆车辆的调度问题，m i g r o s 是瑞士最主要的一个连锁超市集团。b i o s g r o u p 也为法国公 司a i rl i q u i d e 开发了另一个车辆调度系统。 在近几十年里，国外对物流配送车辆路径优化问题作了大量深入的研究，而在国内， 对此方面的研究在2 0 世纪9 0 年代才逐渐兴起，与国外相比，相对落后。在车辆路径问 题也有一些成果，如西南交通大学的李军、郭耀煌在车辆优化调度的基础理论及其各类 问题上作了系统的研究曲吲；李大为等把t s p 的最近距离启发式作为基础，并通过对评价 函数的设置来处理带有时间窗约束的简单v r p 问题 吲；蔡延光等采用模拟退火法求解了 满载车辆路径优化问题睁川。总体来说，我国目前对车辆路径问题的理论研究还相对薄 弱，需作进步研究。 2 西华大学硕士学位论文 1 2 2 发展前景 随着研究的深入，a c o 的性能也不断提高，我们对理论上的研究在不断加深的时 候，仍有许多领域还处于研究的起步阶段，有待人们的努力探索。 对解决组合优化问题上，有儿个方面的发展，包括： ( 1 ) 动态优化问题。在求解问题过程中，它的实例数据，如目标函数值、决策参 数、约束条件等都有可能变化，换句话说，就是问题的一些特征是随着时间而变化的； ( 2 ) 随机优化问题。对于此类问题，由于不确定性、噪声、近似性等其他因素， 只能得到目标函数值、决策参数值、约束条件的概率信息； ( 3 ) 多目标优化问题。在现实生活中，许多应用经常需要对多个且常相互冲突的 目标进行评估，可使用一个多目标函数作为评估解质量的标准，选择最佳折中的解； ( 4 ) 并行化。在求解现实中的优化问题时，需要相当长的计算时问，实现算法的 并行化，是一种值得期待的做法。 ( 5 ) 算法的融合。根据问题的不同，融合策略也存在很人差异，因此在现有成果 的基础上继续深入研究很有必要，努力探索蚁群算法与一些新兴的、目前影响不大的仿 生优化算法的融合，并能应用于实际问题的求解。 实际复杂问题的求解的准确度要求越来越高，由此可知，蚁群算法的改进与融合也 突现其在实际应用中的重要性，使运输路径得到优化，最终达到加快送货速度、降低运 营成本及减少污染，促进人与自然的和谐发展有较大影响。 1 3 本论文的主要工作 本论文以c v r p 问题和蚁群算法为研究内容，针对物流车辆路径优化问题的复杂性 和条件的约束性等特点，对蚁群算法提出了改进，利用算法的改进并设计了车辆路线的 优化系统，从系统中可以容易发现车辆路线走向，从而使运输速度加快、运输成本得到 减少等作用。 本文的主要研究工作包括： 第一章绪论。阐述了本论文的研究目的及意义，并随着实际问题的出现，国内外 对物流配送问题的研究越来越突出，并指m 其国内外研究王见状及发展趋势，说明本文主 要是解决c v r p 问题。 第二章智能优化算法的介绍。本章中要从禁忌搜索算法，模拟退火算法，遗传算 法，粒子群优化算法及人工神经网络算法5 种算法，从这5 种算法的基本原理、流程图、 及其优、缺点可以简单了解其解决组合优化问题的不足之处。 第三章基本蚁群算法介绍。本章主要从t s p 问题和v r p 问题来介绍。介绍用蚁群 算法来解决t s p 问题的基本流程和数学模型：v r p 问题的分类，而本文主要着手c v r p 基于蚁群算法的物流配送路径优化研究1j 应用 问题的研究，也介绍了用蚁群算法解决c v r p 问题的数学模型和其的求解思想，最后提 出蚁群算法求解组合优化问题的不足之处，引出第四章的内容。 第四章改进蚁群算法介绍。本章主要介绍了两种组合蚁群算法：自适应蚁群算法 和最大最小蚁群算法，这两种算法都能克服基本蚁群算法的不足，并介绍了这两种算法 对于基本蚁群算法的改进之处。最后利用这两种算法对t s p 问题做了仿真，得出最人最 小蚁群算法较好，并利用m a t l a b 中的g u i 设计了路径优化的界面，从界面上可以清 晰看出路线的走向和最短路径的长度。 第五章静态车辆路径优化软件的实现。本章主要介绍了路径优化设计的总体设计 及组成部分，该系统主要任务是生成一个文本文件，此文件里包含了配送点的横纵坐标 及车辆自身的约束条件和客户需求量的限制，用路径分配载入此文件，进行路线的分配， 得出路线走向及车辆的使用数。 第六章总结与展望。总结本文的主要内容，并提出不足之处及改进的展望。 4 西华大学硕士学位论文 2 智能优化算法介绍 用于解决物流车辆路径问题的智能算法很多，比如禁忌搜索算法、模拟退火算法、 遗传算法、粒子群优化算法等，也有多篇文章用此类算法进行仿真，但都有不足之处。 蚁群算法利用并行计算机制，且易于与其他方法结合，具有较强的鲁棒性等优点，能克 服其他智能算法一些不足的地方。本章首先介绍智能优化算法，为下一章蚁群算法的概 念、算法的思想、描述及其求解路径优化问题的相关步骤，蚁群算法的优缺点，并对蚁 群算法的复杂度及性能评价的相关指标进行分析的介绍作铺垫。 2 1 智能优化算法 2 1 1 禁忌搜索算法 禁忌搜索算法( t a b us e a r c h ，t s ) 最早于1 9 8 6 年由g l o v e r 提出1 ，随后经过学者 的研究，形成了一套完整的算法。其工作原理是利用记忆存储并系统化的使用，来指引 搜索的过程。其记忆存储包括短期记忆和长期记忆n2 1 ，短期记忆是把当前解的邻域限制 到一个子集中，邻域包含这个子集；而长期记忆是通过引入另外的解来扩充邻域。 禁忌搜索在每一步的搜索都使用局部搜索，到达过的局部最优点用一张禁忌表记录 下来，在以后的搜索中，有选择的或禁止搜索这些局部最优点n3 1 。用局部搜索，如果新 生成的解比当前的解差，也会让原来的路径尽量移动到一个邻近的路径解中来做出最好 的移动，若差的解被生成，此算法将选择差解中的最好解。由于局部搜索可能返回到先 前已经访问过的解，为了防止这个过程，或都说为了避免环路的出现，t s 可以使最近访 问过的解显式保存下来或禁止算法移回那些解。然而，这种做法会阻碍算法向着有吸引 力的，没有访问过的解移动。为了避免这种不理想的情况出现，最常用的方法是使用一 个渴望标准( a s p i r a t i o nc r i t e r i o n ) 来覆盖某些移动的禁忌状态，使某些向比目前访 问过的最好解更好的解移动。使用短期记忆是t s 在搜索过程中最广泛的应用特征，但 是短期记忆又使得禁忌表是弱禁忌，即这些禁忌在一定的时间后将失效，最后达到全局 最优，其优缺点如表2 2 所示。 当前，t s 是最广泛使用的元启发式算法之一，并且其应用相当成功，在各种领域不 同问题的求解上也取得了优异的结果。而通常算法的高效性是源于其对参数和不同的实 现选择做了相当多的精细调整而得到的，所以就产生了算法的改进，例如活性t s ( r e a c t i v et s ) ，这些改进算法都在t s 的参数设定方面尝试，使得其有更强的鲁棒性 1 2 】 基于蚁群算法的物流配送路径优化研究与应用 在实际问题求解过程中，搜索过程使用短期记忆是t s 算法最广泛的应用特征，这 种只依赖短期记忆的t s 算法被称为简单禁忌搜索( s i m p l et a b us e a r c h ) 算法。简单t s 算法的算法框架如图2 1 所示。 图2 1 简单t s 算法的高层伪代码 f i g 2 1 t sa l g o 订也n l sh i g h l e v e lp s e u d oc o d e 由图中显示，有以下解释： 函数g e i l e r a t e i n i t i a l s o l u t i o n ，用来生成初始解： 函数i i l i t i a l i z e m e m o 叫s t m 曲h e s ，在t s 算法运行过程中用来初始化所有的存储记忆 结构： 函数g c i l 删e a d m i s s i b l e s o l u t i o n s ，用来决定邻近解的子集，子集中的解不处于禁 忌状态，或者虽然处于禁忌状态但满足渴望标准： 函数s e l e c t b e s t s o l u t i o n ，选择最好的解，向最好的解移动； 函数u p d a t e m e m o r y s 缸1 l c n 】r e s ，更新存储记忆结构。 2 1 2 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 最早是由m e t r o p 0 1 i s 于1 9 5 3 年提出的， 是局部搜索算法的扩展，且k i r k p a t r i c k 等于1 9 8 3 年将模拟退火算法成功地应用于组 合优化问题n 射，特别是n p 组合优化问题 1 5 1 。求解优化问题，模拟退火算法是基于一般 优化问题与物理中固体物质退火过程有相似性，在对固体物质退火处理时，经常先把它 6 西华大学硕士学位论文 的温度上升到使其粒子能自由运动，再随着温度的下降，温度下降的速度保持足够慢， 如果速度足够慢，最后系统会达到自身的最低能量状态( 基态) ，这个基态相似于能量 函数的全局最小点。针对组合优化问题也是类似过程，其迭代过程是“生成新解一判断 一接受o r 舍弃”，且迭代过程使用了随机接受准则一一m e t r o p o l i s ，用此来接受恶化 解，使恶化解的概率逐渐趋于o ，让模拟退火算法有可能跳出局部极值区域，并尽可能 找到全局最优解。 由于模拟退火算法采用了上述准则，所以成为了全局寻优算法。该准则应用于模拟 退火算法中的优点是：中间解以一定的接受概率避免落入局部极小点，最后在退火温度 的控制下找到最优解。如果没有该准则，模拟退火算法就谈不上全局寻优，最多只能算 是一种局部搜索算法，在实际应用中并不能找到真正的最优解。 传统的模拟退火算法流程图如图2 2 所示，其具体原理己在多部文献n 6 。1 7 3 中已经出 现。 一薹王壑登篁鲨塑望鎏型堡垡些婴窒皇窒旦 图2 2 模拟退火算法流程图 f i g 2 2s i i i l u l a t c d 撇e a l i l l ga l g o r i t l l l l lf l o wc h a n 由图2 可见，内部包含内循环和外循环。内循环是在同一温度下经多次扰动生成不 同的模型状态，按照m e 仃o p o l i s 准则选择新模型，因此是把模型扰动的次数作为控制的； 而外循环包含了当温度降低时，模拟退火算法迭代次数的增加与算法停止的条件，因此 西华大学硕士学位论文 是把迭代次数作为控制。s a 在理论上算是一种全局最优算法，但在实际应用中也有其 缺点，如表2 2 所示。 2 1 3遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是由美国m i c h i g a n 大学的j o h nh o l l a n d n 8 3 教 授于1 9 7 5 ( 7 0 年代) 年提出的，他把大自然优胜劣汰的进化思想应用于组合优化及机 器学习等问题中。6 0 年代是遗传算法研究的起步阶段，遗传算法相对简单，并没有用于 求解特定类型的问题；7 0 年代是遗传算法的发展探索阶段，用其来解决两类问题：( 1 ) 设计出特定问题的求解系统；( 2 ) 理解这些系统是怎么求解问题的，并且发现采用的 遗传算子对于算法的运行结果有很大的影响，经过这一阶段的探索，为遗传算法的发展 奠定了良好的基础。8 0 年代，遗传算法的优化得到了不断的改进和研究，并且发现其缺 点，相应提出了许多方法来改进。9 0 年代遗传算法的研究和应用进一步深入n 。1 ，遗传算 法的优缺点如表2 2 所示。 由于遗传算法简单易行，广泛应用于各个领域，并且也有相当多的文献说明该算法 的优缺点，如：r a d 0 1 p h 在文献乜中证明了一般的遗传算法没有收敛性，在每次保存最 优个体才收敛：p e r e y 在文献雎中针对一类特殊的遗传算法，给出了其收敛的充要条件； q i 和p a l m i e r i 在文献心幻中证明算法在群体容量无限大时是收敛的口3 3 等等。 遗传算法的原理是从初始种群出发，用选择策略在当前种群中选择个体，其中的选 择策略是基于适应值比例的，其后用杂交和变异来使下一代种群产生，像这样一代代进 行下去，一直到期望的终止条件为止。遗传算法对旅行商问题( t s p ) 而言，杂交算法 的常用表示方法一般是把染色体表示成一个排列，里面包含所有的城市，即长度为n 的 整数向量( i ，i ：，i 。) ，而整数向量中的每个整数正好出现一次。用这种表示方法 很有可能不是传统的杂交算子所产生的向量，这样可能会出现没有意义的路径。因些， 必须保持t s p 的杂交算子编码的有效性。基本的形式有基于次序的杂交、基于位置的杂 交、部分映射杂交、循环杂交等妲制。变异算法在遗传算法中起着双重作用，一方面它在 群体中保持并提供多样性，这样可以使其他的算子一直起作用，另一方面它自身也可以 当作为一个搜索算子。变异在单个染色体上起作用，基本形式有基于位置的变异、基于 次序的变异、打乱次序的变异等。 遗传算法的主要步骤如下所示： ( 1 ) 编码。g a 在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结 构数据，这些串结构数据的不同组合便构成了不同的点。 ( 2 ) 初始群体的生成。随机产生n 个初始串结构数据，每个串结构数据称为一个个 体，n 个个体构成了一个群体。g a 以这n 个串结构数据作为初始点开始迭代。如设输 9 基于蚁群算法的物流配送路径优化研究与应用 入需求重量集n ( g ) = ( g l ，& ，& ) 和体积集n ( v ) = ( v 1 ，v 2 ，v 1 ) ，运 输车的载重量为g ，体积为v ，初始车辆数为m ； ( 3 ) 适应性值评估检测。适应性函数表明个体或解的优劣性。对于不同的问题，适 应性函数的定义方式也不同。令v m g = 0 ，g m g = 0 ，其中v m g 和g m g 分别表示车辆m 已 装载的货物总体积和总重量； ( 4 ) 选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父 代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性 强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。 ( 5 ) 交换。交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一 代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 ( 6 ) 变异。变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随 机地改变串结构数据中某个串的值。同生物界一样，g a 中变异发生的概率很低，通常取 值在0 0 0 1 o 0 1 陋5 1 。变异为新个体的产生提供了机会。 2 1 4 粒子群优化算法 粒子群优化算法( p a 】m c l es w a mo p t i m i z a t i o n ，p s o ) 是由美国的k e 如e d y 和e 1 b e r h a n 受鸟群觅食的启发于1 9 9 5 年提出的，两位分别是社会心理学博士和电子工程学博士。 粒子群优化算法也是起源于对一种生物系统一社会系统的模拟。最初设想是模拟鸟群觅 食，更确切的是模拟由简单个体组成的群落与环境以及个体之间的互动行为。 粒子群优化算法跟其他演化算法有相似之处，如都是基于群体迭代，但也有不相同 的地方，如该算法没有交叉、变异和复制等算子，而是把群体中的每个个体当成是一种 没有质量和体积的粒子( p a r t i c l e ) 乜引。粒子在搜索空间中以一定的速度飞行，其位置 变化是以一个个体成功地超过其他个体的社会心理意向为基础的，因此，群中粒子的变 化受到其邻近粒子( 个体) 经验或知识的影响，由此可见，粒子群优化算法是一种共生 合作的算法。 由于该算法对复杂非线性问题具有较强的寻优能力和简单通用、鲁棒性强等显著特 点，引起了不同研究领域的研究人员的研究，在短短几年的时间内，粒子群优化算法已 经获得了很大的发展，广泛用于函数优化、车间调度等组合优化问题，并发表了很多关 于该算法的文献。如t r e l e a 在文献眩刀中对算法的参数选择和收敛性做了一定的分析； z h i h u ac u i 在文献口8 1 中提出了双层粒子群算法的全局收敛问题。由于该算法也有缺点， 也有文献提出改进或混合算法，如文献1 提出了将粒子群算法与模拟退火算法结合应用 于函数优化过程中；文献m 3 提出了将粒子群与蚁群算法的融合等。 粒子群优化算法的基本流程图如图2 3 所示： 1 0 西华大学硕士学位论文 图2 3 粒子群优化算法流程图 f i g 2 3 p a n i c l es w a 哪o p t i m i z a t i o na l g o r i t h mn o wc h a n 粒子群优化算法有其优点，也有其缺点，如下所示，和其他算法的优缺点比较如 表2 2 所示。 优点： ( 1 ) 粒子群优化算法原理简单，较易实现； ( 2 ) 该算法的通用性较强，不依赖问题信息； ( 3 ) 各粒子间协同搜索，并且搜索策略是由个体局部信息、群体全局信息进行指 导的： 基于蚁群算法的物流配送路径优化研究与应用 ( 4 ) 由于粒子群优化算法是群体搜索，且具有记忆功能，所以能使个体和种群的 最优信息得以保留。 缺点： ( 1 ) 该算法的搜索性能对参数的依赖性比较强； ( 2 ) 局部搜索能力较差，极易陷入局部最优，且搜索精度不高； ( 3 ) 由于该算法易陷入局部最优( 即局部极小解) ，所以此算法不能保证能完全 得到全局最优解； ( 4 ) 该算法的理论有待完善，尤其在算法的具体应用设计中缺少实用性的指导原 则。 2 1 5 神经网络算法 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 的起源，目前说法不一。一般 认为，其起源可追溯到1 9 4 3 年由w a r r e nm c c u l l o c h 和w a l t e rp i t t s 发表的论文删， 文献3 3 根据已知的神经细胞生物过程原理，构造了一个简单的人工神经元模型，后来就 被称为m p 模型。 人工神经网络是模拟生物神经系统的一类人工智能简化系统，这个简化系统包括组 织结构、处理方式和系统功能。该算法使用数学理论和计算机模拟的方法在生物神经细 胞层次上模拟脑结构、脑信息处理方式和脑功能。神经网络的基本组成单元为神经元， 其一般由输入( 感知) 器、加权求和( 信息汇聚) 器、传递( 信息传输) 器和输出( 响 应) 器构成。其示意图如图2 4 所示。 输 图2 4 神经元模型示意图 输 出 西华大学硕士学位论文 f i g 2 4 n e u r o nm o d e ld i a 鲫l 图2 4 显示为单个神经元模型，当大量神经元广泛互连组成人工神经网络时，就能 对复杂信息进行存储和处理。由于人工神经网络是一种具有大量连接并行分布式处理 器，使得它能通过学习解决模式识别、感知和在复杂环境中做出决策等实际问题4 1 。 人工神经网络在科研、生产和生活中产生了普遍而巨大的影响，表2 1 给出了对神 经网络发展有重要影响的神经网络。 表2 1 对神经网络发展有重要影响的神经网络 t a b l e 2 1n e u a l ln e 似o i ( k sh a v eam a j o ri m p a c to n 廿1 ed e v e l o p m e n to fn e u r a ln e m o r k 名称提出者诞生年 典型应用领域弱点特点 f r a n k 文字识别，声音不能识别复 最早的神经 p e r c 印n o n ( 感 r o s e i l b l a t t 1 9 5 7 识别，声纳信号 杂字形，对字 网络，已很少 知机) ( 康奈尔大识别，学习记忆 的大小、平移 应用，有学习 学) 问题研究和倾斜敏感 能力，只能时 行线性分类 a d a l i i l e ( 自适雷达天线控制， 学习能力较 应线性单元) b e m a r d 自适应回波抵 要求输入输 强，较早开始 和m a d a l i i l e ( 多 w i d r o w ( 斯 1 9 6 0 1 9 6 2 消，适应性调制 出之间为线 商业应用， 个a d a l i n e 的组 坦福大学) 解调，电话线中 性关系 m a d a l i l l e 是 合网络)适应性补偿等 a d a l i l l e 的功 能扩展 a v a l a n c h e ( 雪 s d r o s s b e r g连续语音识别， 不易改变运 崩网) ( 波士顿大 1 9 6 7 机器人手臂运动速度和插 学) 动的教学指令入运动 类似于 a v a l a l l c h e 网 c e r e l l a t r o n ( 小 d m a r r ( 麻省 控制机器人的需要复杂的 络，能调各 1 9 6 9 1 9 8 2 脑自动机) 理工学院)手臂运动控制输入 各种指令序 列，按需要 缓慢地插入 动作 基于蚁群算法的物流配送路径优化研究与应用 p w e i b o s ( 哈 佛大学) 语音识别，工业需要大量输多层前馈网 b a c k d a 、，i d 过程控制，贷款入输出数络，采用最小 p r 叩a g a t i o n ( 误 r 啪e m a n ( 期 1 9 7 4 1 9 8 5 信用评估，股票据，训练时间 均方差学习 差反传网络) 坦福大学) j 锄e s 预测，自适应控长，易陷入局方式，是应用 m c c l e l l a i l d 制等部极小最广泛的网 ( 斯坦福大 络 学) a d a p t i v e g 。c a 印e n t e r模式识别领域， 受平移、旋转可以对任意 r e s o n a c e 锄ds 擅长识别复杂 及尺度的影多和任意复 n e o 巧( 自适应 觚s s b e r g ( 波 1 9 7 乒1 9 9 0 模式或未知的 响。系统比较杂的二维模 共振理论 士顿大学) 模式 复杂，难以用式进行自组 a r t ) 硬件实现织学习 具有最小均 b r a i ns t a t e i i laj 锄e s 解释概念形成，只能作一次 方差的单层 b o x ( 盒中脑 a n d e r s o n ( 布 1 9 7 7 自联想网络， 分类和知识处性决策，无重 类似于双向 b s b 网络)朗大学) 理复性共振 联想记忆，可 对片段输入 补全 多层结构化 字符识别网 n e o c o g n i t i o n f 1 1 k u s h i m ak 需要大量加 福岛邦彦( 日 1 9 7 8 1 9 8 4 手写字母识别 络，与输入模 ( 新认知机) 工单元和联 式的大小、平 本广播协会) 系 移和旋转无 关，能识别复 杂字形 s e l f - o r g a i l i z i i l g t u e v o 语音识别，机器 对输入样本 f c a n l r em a p ( 自 k o n h o n 铋( 芬 1 9 8 0 人控制，工业过 模式类型数 自组织聚类， 组织特征映射兰赫尔辛基 程控制，图像压 需预先知道 映射样本空 网络) 技术大学) 缩，专家系统等间的分布 1 4 西华大学硕士学位论文 j o h nh 0 p f i e l d 求解t s p 问题，无学习能力， 单层自联想 h o p 6 e l d 网络 1 9 8 2 线性规划，联想连接要对称， 网络，可从有 ( 加州理工 缺损或有噪 学院) 记忆和用于辨权值要预先 声输入中恢 识 给定 复完整信息 b o l t 黜a n 玻尔兹曼机一种采用随 m a c h i l l e ( 玻尔 j h i n t o n ( 多 兹曼机) 伦多大学) t 1 9 8 5 1 9 8 6 图像、声纳和雷 训练时间长，机学习算法 c a u c h y s e j n o w s h ( 霍达等模式识别 柯西机在某的网络，可训 些统计分布练时实现全 m a c h i n e ( 柯西 布金斯大学) 下产生噪声局最优 机) b i d i r e c t i o n a l a s s o c i i a t i v eb a a a r tk