（系统工程专业论文）物流配送车辆路径智能优化方法研究.pdf

中文摘要 随着我国工业化步伐的不断加快，作为工商业企业支柱之一的物流也越来越 受到重视，尤其是近些年来第三方物流公司的蓬勃兴起对物流管理理论与技术的 发展提出了较高的要求。运输是物流的基本内容之一，在物流作业中扮演着重要 的角色，运输成本也是物流成本的主要的组成部分之一，因此物流运输规划的好 坏与否将直接关系到企业物流成本的高低。于是作为物流管理的重要组成部分的 物流运输的车辆路径理论在近些年来逐渐成为学术界的研究热点。 本文分为两大部分，第一部分是静态车辆路径问题条件下调度算法的研究， 该部分主要在静态路径条件下研究三种人工智能算法，即免疫算法、粒子群算法 和蚁群算法。通过研究分析这三种算法的运作机理，结合求解s o l o m o n 算例得出 三种算法应用于不同类型车辆路径问题时所表现出的性能，总结出在何种条件下 采用何种算法可以达到最佳效果。最后从遗传算法的角度进一步解释这三种算法 的运作的根本机理。 第二部分提出了一个动态车辆路径问题的新模型，原有动态车辆路径问题的 模型假定了车辆通过单一某路段的时间服从均值和方差为固定数值的正态分布， 这显然不符合实际情况。新模型对该假定条件予以放宽，即假定该正态分布随着 车辆到达该路口时刻的不同而不同，并且结合了随机需求的情况。本文针对该问 题构建了随机机会约束规划模型，并设计了遗传算法求解该模型，最后给出了一 个算例。 关键词：物流 动态车辆路径问题免疫算法粒子群算法蚁群 算法 a b s t r a c t a so u rc o u n t r y sp a c e st o w a r d si n d u s t r i a l i z a t i o ns p e e du p ，l o g i s t i c s ， w h i c hi so n eo ft h ep i l l a r so fi n d u s t r i a la n dc o m m e r c i a le n t e r p r i s e s i s g a i n i n gm o r ea n dm o r ea t t e n t i o n s e s p e c i a l l yi nr e c e n ty e a r s ，t h et h r i v i n g o ft h et h i r d p a r t l o g i s t i c sc o m p a n i e sc a l l f o r l o g i s t i c st h e o r i e s a n d t e c h n o l o g i e so fh i g hs t a n d a r d s a so n eo ft h eb a s i cp a r t so fl o g i s t i c s ， t r a n s p o r t a t i o n i s p l a y i n g a n i m p o r t a n t r o l ei n l o g i s t i c so p e r a t i o n t r a n s p o r t a t i o n a c c o u n t sf o ral a r g ep o r t i o no fl o g i s t i c sc o s t s o ，t h e v e h i c l es c h e d u l i n gt h e o r y , w h i c hi sa l li m p o r t a n tp a r to fl o g i s t i c s m a n a g e m e n t ，h a sb e,come ah o tt o p i co ft h es c h o l a rf i e l d t h i sp a d e ri sc o m p o s e do ft w os e c t i o n s t h ef i r s tp a r td e a l sw i t ht h e s c h e d u l i n ga l g o r i t h m so ft h es t a t i cv e h i c l es c h e d u l i n gp r o b l e m s t h i s s e c t i o nm a i n l yr e s e a r c h e st h r e ea l g o r i t h m sw h i c ha r ei m m u n ea l g o r i t h m ， p a r t i c l es w a r ma l g o r i t h ma n da n t sa l g o r i t h mw h i c ha r ea b o u tv e h i c l e r o u t i n gp r o b l e m si na s t a t i cs t a t ea n dw o r ko u tt h ep e r f o r m a n c eq u a l i t i e s o ft h ed i f f e r e n ta l g o r i t h m sa p p l i e dt od i f f e r e n tp r o b l e m st h r o u g h a n a l y z i n gt h em e c h a n i c so ft h ea l g o r i t h m sa n ds o l v i n gt h es o l o m o n s i n s t a n c e s a n dt h e n s u m m a r i z ew h i c hk i n do fa l g o r i t h ms h o u l db eu s e dt o s o l v ec e r t a i np r o b l e mi no r d e rt og e tt h em o s ts a t i s f i e ds o l u t i o n a tl a s t t h er o o tm e c h a n i c so ft h ea l g o r i t h m sa r ei n t e r p r e t e df r o mt h ea n g l eo f g e n e t i ca l g o r i t h m t h es e c o n ds e c t i o np r o p o s e dan e wd y n a m i cv e h i c l er o u t i n gp r o b l e m t h eh y p o t h e s i so ft h eo r i g i n a lo n ei st h a tt h et i m ev e h i c l e st a k et op a s s ar o a di ss u b je c t e dt on o r m a ld i s t r i b u t i o nw i t hc o n s t a n tm e a nv a l u e sa n d v a r i a n c e s h o w e v e ri ta p p a r e n t l yd o e sn o tm e e tt h er e a ls i t u a t i o n t h en e w m o d e lf o r m san e wh y p o t h e s i s t h a tt h en o r m a ld i s t r i b u t i o nv a r i e s a c c o r d i n gt o t h et i m ew h e nv e h i c l e sg e tt ot h er o a d ，a n ds t o c h a s t i c d e m a n di sc o m b i n e d a i m e da tt h i sp r o b l e m ，t h i sp a p e rb u i l tas t o c h a s t i c c h a n c ec o n s t r a i n e dp r o g r a m m i n gm o d e la n dd e s i g n e dag e n e t i ca l g o r i t h m t os o l v et h i sp r o b l e m ，a n da ni n s t a n c ei sg i v e n k e yw o r d s ：l o g i s t i c s ，d y n a m i cv e h i c l es c h e d u l i n gp r o b l e m ，i m m u n e a l g o r i t h m ，p a r t i c l es w a r ma l g o r i t h m ，a n ta l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤聋盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：弓冻岩签字日期：2 7 年 f 月彩日 学位论文版权使用授权书 本学位论文作者完全了解丕鲞叁茎有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 导师签名：讴田黜 签字日期：j 力7 年7 月字日 签字日期：眵哆年月日 第一章绪论 第一章绪论 随着新世纪的到来，电子商务的蓬勃发展以及中国加入w t o ，市场竞争进 一步加剧，企业要保有和争得市场，不仅要在产品的质量和功能上下功夫，更重 要的还是在优质服务上面下功夫。车辆路径问题( v r p ) 的研究成果，不仅可以帮 助企业提高服务水平，为顾客提供准时、安全、舒适的服务，解决电子商务中“速 递”这一瓶颈约束，而且有助于企业节约运输成本，改善车辆运输效率，缩短产 品的生产周期，加速资金周转，实现资源的合理配置，汲取“第三利润源泉的财 富”。 1 1 车辆路径问题的概念 车辆路径问题( 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 年首次提出的1 1 | ，该问题一经问世很快引起运筹学、应用数学、组合数 学、网络分析、图论、计算机应用数学等学科的专家与运输计划制定者和管理者 的极大重视，他们进行了大量的理论研究及实验分析，取得了很大的进展。 车辆路径问题一般定义为：对一系列发货点或收货点，组织适当的行车路线， 使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、发送量、交发 货时间、车辆容量限制、行程里程限制、时间限制等) 下，达到一定的目标( 如 路程最短、费用最小、时间尽量少、使用车辆尽量少等) 。 1 2 车辆路径问题的分类 根据研究重点的不同，v r p 有多种分类方式。如按任务特征分类，有装货问 题、卸货问题及装卸混合问题：按任务性质分类，有对弧服务问题( o n 中国邮递员 问题) 和对点服务问题( 如旅行商问题) 以及混合服务问题( 0 n 校车路线安排问 题1 ；按车辆载货状况分类，有满载问题和非满载问题；按车场数目分类，有单车 场问题和多车场问题；按车辆类型分类，有单车型问题和多车型问题；按车辆对 车场的所属关系分类，有车辆开放问题( 车辆可不返回车场) 和车辆封闭问题( 车 辆必须返回车场) ；按已知信息的特征分类，有确定性v r p 和不确定性v r p ， 其中不确定性v r p 可进一步分为随机v r p ( s v r p ) 和模糊v r p ( f v r p ) ；按约束 第一章绪论 条件分类，有c v r p ( 带能力约束) 、d v r p ( 带时间距离约束) 和v r p t w ( 带时间窗 口) ；按需求是否可切分分类，又可分为可切分的v r p 和不可切分的v r p 。按优化 目标数来分类，有单目标问题和多目标问题。根据冲是否和其它优化问题相结 合分为单纯性v r p 和复合性v r p 其中复合性v r p 又分为库存路径问题0 r p ) ，定位 路径问题( l r p ) 等。 1 3 确定性v r p 在过去的几十年对v r p 的研究中，绝大多数的研究工作都集中于确定性 v r p ，因此对于该类问题的研究已经日趋成熟。下面主要从模型和算法两个角度 来介绍确定性v r p 的研究成果。 1 3 1 确定性v r p 的模型综述 迄今为止确定性v r p 的类型一般分为如下几种： 1 ) 单车场非满载有容量约束问题。该问题可描述为考虑货物需求量、发送量和 车辆容量三种约束的条件下运输车辆的路径优化问题。它可以描述为：物流配送 渠道有1 个市场、刀个送货点组成，送货的车辆从车场出发到送货点送货，每个 送货点货物需求量一定，每辆车限定容量一定，每辆车完成送货任务之后，返回 车场。费用函数为总路程数，目标为使总路程最小。该问题为v r p 的最基本的问 题，是进行深入研究的基础。 2 ) 单车场非满载有容量和时间窗约束的问题。可描述为一个配送中心有若干可 供调动的车辆，每一个送货点都有时间窗限制，对一项运输业务，调用哪几种型 号的车辆、选择什么路径可达到最小的费用。时间窗分为软时间窗和硬时间窗。 所谓软时间窗是指配送点允许配送车辆在时间窗以外的范围内送达货物，但同时 必须给以一定的处罚。硬时间窗是指不允许配送车辆在时间窗以外的范围内送达 货物。 3 ) 多车场非满载问题。在现实中，集约化的发展使多个配送中心、多个货场综 合实行配送优化成为可能，即有多个车场可发出和接收车辆，各个车场协调调派 车辆到货场完成配送任务，可以大大节省整体配送费用。在现有文献中，几乎所 有的多车场问题都转化为单车场来处理。 4 ) 非满载集送一体化车辆路径问题。如果一些货物运输的每r 一个客户都有自己 的送货点，要求车辆在一定的集货点装货后运至一定的送货点卸货，即所有的任 务不是纯装或纯卸的，而是既有装义有卸，即为集货和送货体化的车辆路径问 题。 第一章绪论 5 ) 多车场开放式车辆路径问题。车辆路径问题按车辆对车场的所属关系分，可 以分为车场封闭问题和车场开放问题。车场封闭问题的特点是发车车场和回车车 场必须样，而车辆开放问题则车辆可以不返回其发出车场。 6 ) 满载车辆路径问题。当货主的货物量不小于车辆容量时，执行每项任务需要 的车辆可能不只一辆，车辆为完成任务，需满载运行。 7 ) 复杂情况下的车辆路径。有学者把许多约束条件如不同的车型指标、路况信 息、时间窗容量、发车时间等都考虑了进来【2 】。 1 3 2 确定性v r p 的算法综述 在研究v r p 的论文中，绝大多数都是研究探讨寻找合适的算法来解决这些问 题，迄今为止，所涌现出的算法和理论已经有十几种，随着时间的推移，算法的 功能越来越强大，可解决的问题越来越复杂。总的来说，基本上可以分为精确算 法、传统启发式算法和智能算法几大类。 1 ) 精确算法 精确算法是指可以求出最优解的算法，精确算法主要有：分枝定界法、割平 面法、网络流算法、动态规划方法、在研究的初期，基本上都是采用这些算法， 但是由于随着问题规模的增大，运用精确算法的计算量将呈指数增长，因此其实 际应用范围很有限。 2 ) 传统的启发式算法 由于v r p 问题是n p h a r d 难题，运用高效的精确算法求解的可能性并不大， 所以寻找近似算法是必要和现实的，为此后来专家们主要是把精力花在构造高质 量的传统启发式算法上。 ( 1 ) c l a r k e - w r i g h t 算法。该算法是i 妇c l a r k e 和w r i g h t 提出的1 3 】 用来解决车 辆数不固定的v r p 。该算法最初按所需访问的点数n 1 ( 不含出发点) 生成同样 数量的路径，计算合并任意两条路径后可节省的成本量s o = c i l + c l ，c 巧。然 后对可节省的成本量进行排序。最后根据排序结果以及可行性条件，对路径进行 归并( 这里的归并是指：去掉分别位于原来两条路径中的弧( f ，1 ) 和( 1 ，_ ) ，用( ，) 代替) ，直到无法找到更好的解。 ( 2 ) s w e e p 算法。该算法是由g i l l e t t 等人提出的【4 】。即先计算出所要访问的 点的极坐标，并按角度大小排序。然后在满足可行性条件的前提下，按角度大小归 并到不同的子路径中，最后再根据t s p 的优化算法对所得到的子路径进行优化。 ( 3 ) 两阶段算法。它主要面向c v r p 和d v r p 。该算法的求解过程分为两个 阶段：第一阶段按最小路径的原则形成初始解，然后用k 2 0 p t 算法对所得的各了 路径分别进行优化。第- 阶段是在各子路径问进行点的交换，以减小总行程然后 第一章绪论 用k 2 0 p t 算法对点交换后的子路径进行优化。该算法的优点是：在计算过程中， 考虑了所需要访问的点数量增加的情况。 3 ) 人工智能算法 进入2 0 世纪8 0 年代，一些新颖的优化算法逐一问世，这些算法通过模拟或揭 示自然现象得到发展，其思想涉及到数学、物理、生物进化、人工智能等各方面， 为解决复杂问题提供了新的思路和手段。近年来使用人工智能算法来求解v r p 问题已经成为主流。 ( 1 ) 禁忌搜索算法 5 ( t a b us e a r c h ) 。该算法的思想是对局部邻域搜索的一种扩 展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。该算法通过引入 一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免 一些被禁忌的优良状态，进而保证多样化的有效搜索，最终实现全局优化。 g e n d r e a u 等人最先将该方法应用于v r p 。大量的研究结果表明，禁忌搜索算法 的搜索速度快，局部“爬山能力强”，但是其对初始解具有比较强的依赖性， 一个差的初始解会降低算法的收敛速度。 ( 2 ) 模拟退火算法 6 ( s i m u l a t e da n n e a l i n g ) 。模拟退火算法的思想最早是由 m e t r o p l i s 等在1 9 5 3 年提出，该算法是基于m e n t ec a r l o 迭代求解策略的一种随机寻 优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的 相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳 特性在解空间的中随机群求目标函数的全局最优解。研究结果表明，该算法在求 解送货点较少的v r p 是能够以较高的概率得到最优解，当送货点增多的时候优化 效果急剧下降，当达至l j 2 0 个送货点时，优化效果十分有限。 ( 3 ) 遗传算法1 7 1 ( g a ) 。j l a w r e n c e 最先将该方法用于v r p 的研究，并可有效 求解带时间窗口的v r p 。大量的研究成果表明，遗传算法在处理v r p 方面表现出 了良好的性能，因此遗传算法已经成为研究和应用v r p 的最普遍的算法。但是仍 然摆脱不了易陷入局部最优点的弱点。 ( 4 ) 免疫算法o a ) 、粒子群算法( p s o ) 、蚁群算法。这几种算法是2 0 世纪9 0 年代出现的新兴算法，本文将研究上述三种算法在v r p 中的应用。 1 4 不确定性v r p 1 9 9 2 年，m a l a n d r a k i 弄l i d a s k i n 提出了时间依赖的车辆路径问题【8 】，即两结点 间的运行成本( 时间) 不仪依赖于它们之间的距离还依赖于出发时间，其定义可 以描述为：在车辆运行路网的路段运行成本( 时间) 随出发时间变化或依概率随 机变化的情况下，车场安排车辆和运输路线以满足系统要达到的目标。该定义强 第一章绪论 调了网络的动态性，符合实际交通网络的特点，同时对需求特点、车型、有无服 务时间窗等其他因素作了限制，有效地扩展了动态网络v r p 的范围。 1 4 1 不确定性v r p 的宏观特性 不确定婶具有一系列的宏观特征，主要包括： 1 ) 不能完全确定安排车辆路线时网络运行成本( 时间) 。在以往的v r p 研究中， 运行网络的信息是静态的，在制定和执行路线中不存在因为交通状况变化而调 整路线的情况；但在动态网络中，路段运行速度、行程时间等受交通流量、天气、 突发事故等的影响经常发生变化，且这些变化事先无法确切得知。 2 ) 突出强调时间特性。在确定性网络的v r p 中，本身并不具有时间性，服务时 间窗等属于外在时间因素；但在不确定性网络v r p 中，网络的时间依赖性和不确 定性是系统固有的特性，即使最简单的旅行商问题也要充分考虑发车时间、访问 顺序、离开客户的时间等与时间有关的因素以及一些依时间而变化的随机因素， 在有时间窗要求的动态网络中，要综合考虑网络的时间依赖性与客户要求的服务 时间窗，时间显得更重要。 3 ) 问题及其解决方法均比较复杂，甚至无可行解存在。由于时间依赖和随机性问 题太复杂，精确算法显然不能适用，由于上面提到的该问题的微观特征，也不能 直接应用一些本身具有插入、交换等操作的启发式算法，必须经过较多的改进。 由于其时间要求特别严格，往往一个问题不能找到满足各个约束条件的最优解 甚至可行解，尤其是在时间窗要求比较严格的情况下。 1 4 2 不确定性v r p 的模型综述 目前来说，对于不确定v r p 的研究还处于发展阶段，已经形成了如下几类模 型： 1 ) 时间依赖v r p , 且p t d v r p 。在这种类型问题中，网络的行程时间严格依赖于路 段的出发时间，是对现实网络动态性的高度假设。目前动态网络v r p 的研究主 要集中在这种网络类型上，一般时间依赖函数处理为分段函数或是单调函数。从 目前对t d v r p 研究内容的时间层次分析，将t d v r p 研究可以进一步分为三 类： ( 1 ) 只考虑网络时间依赖性的t d v r p 。由于网络的时间依赖性是t d v r p 的固 有特性，因此，这是最简单的问题。在该问题的研究中，般不考虑时间窗和动 态随机需求的情况。 ( 2 ) 有时间窗约束或动态随机需求特点的t d v r p 。动态随机需求由于随着时 间的推移而产生，不能在初始时刻确定，所以在此将其认为是需求出现方面的时 第一章绪论 间要求，客户的时间窗要求被认为是服务方面的时间要求，二者其一与时间依赖 网络结合形成两种时间层次交叉的t d v r p 。该问题复杂度明显增加。 ( 3 ) 动态随机需求且有时间窗约束的t d v r p 。该问题是t d v r p 领域复杂性最 高的问题，三个时间层次上的因素都要考虑，且相互影响。目前只有j o o j u n g 对该 类问题做了较多研究1 9 】。另p l i c h o u a 等对动态需求情况也略有涉及f 1 0 】。 2 ) 概率网络v r p 。网络运行成本( 时间) 以离散或连续概率发生变化。在这种网络 中可以用期望运行成本( 时间) 代替路径运行成本( 时间) ，再进行问题的求解，比 较简单。 3 ) 时间依赖且依概率变化网络下的冲。网络行程时间是一离散或连续时间的 随机过程，非常接近实际的交通网络，但也十分复杂。 本文在第三章将研究的是时间依赖且依概率变化并带有时间窗以及动态随 机需求的情况，该模型向着反映现实的方向又迈出了一步，具有一定的实际意义。 1 5 复合性v r p 目前，国外一些学者开始着手研究对于配送和设施定位的整合优化问题，即 定位路线问题( l r p ) 以及对于配送和库存策略的整合优化问题，即库存路径问题 o r e ) ，并取得了一些进展，开创了冲的新的研究方向。 1 6 我国对于v r p 的研究状况 根据所能掌握的资料，国内最先对v r p 进行系统研究的是西南交通大学的郭 耀煌教授，他及其学生从1 9 8 9 年起对多车场、多车型等类型的问题进行了研究， 并出版了国内v r p 研究领域的第一部专著车辆优化调度1 1 1 | 。后来西南交通大 学承担了物流调度问题研究的国家自然科学基金项目，结合国内外学者近年来在 该领域的研究成果做出了大量的研究工作，并由李军教授出版了另一部专著物 流配送车辆优化调度理论与方法1 1 2 】，该著作成为国内学者研究物流配送问题的 首选参考文献。可见西南交通大学在国内的物流配送领域的研究一直走在前列。 近年来，随着“物流热”的升温，国内学者对v r p 的研究开始重视起来。但大多 数文献都是对vr p 的模型和算法进行研究。如文献【l 副采用遗传算法求解了有无 时间窗的v r p ，文献i2 j 研究了复杂条件下车辆路径问题。但总地来说，我国在车 辆路径问题上的研究起步较晚，和国外相比差距较大，在动态车辆路径问题的研 究方面刚刚起步而在定位路线问题和库存路径问题领域上的研究还是空白。 第一章绪论 1 7 本文研究内容 1 ) 智能算法优化静态车辆路径问题。前人在对使用免疫、粒子群、蚁群人工智 能算法解决优化v r p 的研究成果，通常仅仅局限于研究单个算法优化问题时所展 现的性能和效果，或是仅将其与传统算法相比较，本文除了研究上述内容之外， 对三种算法的性能和效果做了横向比较，得出在优化何种问题时采用何种算法最 佳的结论，并研究了算法运作的基本原理，探究了不同的算法运行机理中存在的 共同点和特异性，并由此解释了算法的性能特征。 2 ) 一类动态车辆路径问题的建模与算法。以前对动态车辆路径问题的研究仅仅 局限于分别考虑时间依赖和概率网络的情况，而这样会同实际情形出入较大，为 了接近实际情况，本文综合的研究了时间依赖和概率网络的情况，并参考了随机 需求的因素，使得模型更贴近真实情况，并设计出求解该问题的算法。 第二章智能算法摹本理论 第二章智能算法基本理论 本文所涉及的智能算法包括：免疫算法、粒子群算法、蚁群算法 2 1 从遗传算法到免疫算法 遗传算法( g a ) 是基于适者生存的一种高度并行的、随机的、和自适应的 优化算法。它将问题的求解表示成“抗体”的适者生存的过程，通过一代代的进 化最终收敛到“最适应环境”的个体。该算法鲁棒性强，适应性好，已在各工程 领域得到了广泛的应用，相比较传统优化算法显示出强大的优势。尽管遗传算法 在优化设计等领域取得很大成功，但也存在着严重不足，如早熟现象与欺骗问题、 不能很好保持个体的多样性等，从而影响了其在一些优化设计中的正确性与有效 性，而免疫算法( i a ) 则能很好地避免类似问题。 2 1 1 免疫算法的生物学基础 众所周知，免疫是生物体对病菌病毒的特异性生理反应，由具有免疫功能的 器官、组织、细胞、免疫效应分子及基因等组成，当生物体受到外界病毒( 抗原) 的攻击时，免疫系统会检测是否遇到过该类病毒，如果曾经遇到过，免疫系统会 释放出专门针对该病毒的淋巴细胞( 抗体) 来消灭它。如果该类病毒对生物体来 说是新病毒，免疫系统会在和该病毒艰苦的交战过程中训练出该类病毒的抗体并 用它消灭该类病毒，今后该细胞就会永远保存下来，以后类似病毒再来侵犯，该 抗体会直接将其消灭。 2 1 2 免疫算法的机理 免疫算法的机制由遗传机制、抑制机制和促进机制组成，其中遗传机制为主 体机制，抑制机制和促进机制为辅助机制，三个机制相互协同运作共同实现了该 算法良好的优化性能。在遗传算法的运行过程中，染色体往往会聚集到一个局部 最优点的邻域内，造成该邻域内染色体浓度较高，多样性降低，陷入局部最优解， 阻碍着算法向更优解处搜索，这样会在一定程度上影响算法的全局搜索能力，甚 至得不到全局最优解。免疫算法中的“抑制机制”却较好地解决了这个问题，若 在某处邻域内聚集了较多的抗体并超过一一定限度，“抑制机制”就会开始作用， 第二章智能算法基本理论 抑制该邻域之内的抗体，直到全部消失。并把邻域内最优抗体所记录到“记忆池” 中，以后该邻域内一旦再出现抗体，则由“记忆池”中的m 负责消灭它。这一点 正如人体免疫系统中抗体的产生以及抗体消灭抗原的过程样。“促进机制”则 执行相反的功能，当抗体中出现较为优秀的个体而该个体邻域内抗体较少时，促 进机制就会“加速开发”该邻域，即在该邻域内产生一些抗体以加速在该邻域内 的搜索，尽早发现更优秀的抗体。 r 、 抗 体 群 图2 1 免疫算法原理 的多样性和浓度 口椭体+ 赫局黻牌赫鳎最懈 图2 - 2 “促进机制”与“抑制机制”示意图解 解的多样性和解的浓度是免疫算法中的一个非常重要的概念，解的多样性从 直观上来说就是解形式上的丰富性，一般用信息熵概念指标来描述解的多样性。 如图所示个抗体： 123sm 抗体， 叵皿 抗体t 互口 抗体n 巨口 图2 - 3 抗体示意图 每位可供选择的字母表中共有s 个字母：| i 。，k ：， 息熵为 ( ) = 击姜，( ) 其中， k ，则这个抗体的信 ( 2 1 ) 日( ) = 一p pl o g p f ( 2 2 ) ，= i h ，( ) 为盯个抗体第，位的信息熵，p ，为刀个抗体中的第位为字母| j ，的概率。 当抗体间的差异越大时，信息熵的值也就越大，解的多样性也就越丰富。 抗体间的亲和力：用于表明两抗体之间的相似度抗体v 和抗体w 间的相似度 为： 第二章智能算法基本理论 施w 2 丽1 ( 2 - 3 ) 抗原与抗体的亲和力：用于表明抗体对抗原的识别程度，其计算方法与抗体 之间的亲和力的计算相同。 从本质上来说，一个抗体的浓度表示其他的抗体有多大的程度携带着该抗体 的信息。抗体集合的浓度越高，表示该抗体集合的多样性越小，在解空间上抗体 的分散程度越低。抗体v 的浓度表示为 c 1 ，= 去口c 。( 2 - 4 、) c v2 面乙口c 一 一 1 6 c ，。 6 c 。，t h r e s h o m ，其中旷jo 舭咖掰 其中t h r e s h o l d 为设定的抗体相似度阈值，6 为抗体之间的相似度。 2 1 3 免疫算法的运行步骤 1 ) 编码，同遗传算法相同，将问题的解用一种码来表示，从而将问题的状态空 间与i a 码空间对应。 2 ) 产生初始抗体，初始抗体产生的好坏也会影响到算法的收敛速度以及解的质 量，因此制定一个良好的初始抗体产生策略也很重要。 3 ) 计算抗体浓度。按照抗体浓度计算公式计算出各抗体的浓度。 4 ) 计算抗体适应度。建立一套合适的抗体适应度评价体系并按照该评价体系计 算适应度。 5 ) 抑制浓度最高且高于阈值的抗体，促进亲浓比高于阈值的抗体。 6 ) 选择、交叉、变异。 7 ) 若满足终止条件则终止，否则转3 。 2 1 4 免疫算法的特点 1 ) 识别功能：免疫系统通过相似度的检测可以识别抗原。 2 ) 学习与优化：抗体的产生是免疫系统学习的功能，也是一个优化的功能。 3 ) 联想记忆：免疫系统消灭新抗原后，将所得抗体植入记忆细胞，当与该抗原 相似的抗原再次入侵肌体时，免疫系统能够产生更快速、更强烈的二次应答，免 疫记忆是一种联想记忆。 4 ) 并行的分布系统：免疫网络中的淋巴细胞分布于全身，根据周围的环境自适 应地确定自身的行为，整个免疫系统是一个没有中心控制的并行的分布自治系 统。 5 ) 信息共享性：遗传算法只体现了个体对环境的适应关系对个体选择的影响， 第一二章智能算法基本理论 而免疫算法还包括个体之间的相互作用对个体选择的影响，利用的信息更加丰 富，智能性更加突出。 2 2 粒子群算法的基本理论 2 2 1 粒子群优化算法的概念 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 算法是一种基于群智能 方法的演化计算技术。同遗传算法类似，是一种基于群体的优化工具。粒子群优 化算法最早是由k e n n e d y 和e b e r h e r t 受到人工生命的研究结果启发于1 9 9 5 年提出 的，它的基本概念源于对鸟群捕食行为的研究1 。设想这样一个场景：一群鸟在 随机搜寻食物。在这个区域里只有一块食物。所有的鸟都不知道食物在哪里。但 是它们知道当前的位置距离食物还有多远。那么找到食物的最优策略是什么呢。 最简单有效的就是搜寻目前距离食物最近的鸟的周围区域。粒子群优化算法从这 种模型中得到启示并用于解决优化问题。粒子群优化算法中，每个优化问题的潜 在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个被优化的 函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒 子们就追随当前的最优粒子在解空间中搜索。粒子群优化算法初始化为一群随机 粒子( 随机解) 。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两 个“极值”来更新自己。第一个就是每一个粒子在迭代的过程中其自身所找到的 最优解。这个解称为个体极值。另一个极值是整个种群目前找到的最优解。这个 极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻 居，那么在所有邻居中的极值就是局部极值。 2 2 2 粒子群优化算法处理连续优化问题 假设在一个d 维的目标搜索空间中，有m 个粒子组成一个群落，其中第i 个 粒子表示一个d 维向量x ，= ( x 舯x ，x 仍) ，i = 1 ，2 ，m ，即第，个粒子在d 为 空间的位置为x ，。换言之，每个粒子的位置就是一个潜在的解。将x ，代入一个目 标函数就可以计算出其适应值，根据适应值的大小来衡量x 的优劣。第i 个粒子 的“飞翔”速度也是一个d 维的向量，记为1 ，= ( v n ，v ，d ) ，i = 1 ，2 ，m ， 记第，个粒子迄今为止搜索到的最优位置为p b e s t ，= ( p b e s t ，l ，p b e s t ，2 ，p b e s t ，) ) ， 整个粒子群迄今为止搜索到最优位置为驴e s t = ( g b e s t l ，g b e s t 2 ，g b e s t d ) 。 k e n n e d y 和e b e r h e r t 最早采用下列公式对粒子进行操作： v ，= w v ，j + q r a n d ( p b e s t 耐一，) + c 2 r a n d ( g b e s t d 一一d )( 2 5 ) 第二章智能算法基本理论 x “= x 耐+ v 耐 ( 2 6 ) 其中，i = l ，2 ，i t i ，d = 1 ，2 ，d ，学习因子c l 和c 2 是非负常数；r a n d 是 介于【0 ，l 】之间的随机数，w 为介于 0 ，1 之间的数。v 耐【- 1 ，一，y 一】：v 一是 常数，由用户设定。 如图所示，式( 2 - 5 ) 表示第f 个粒子的位移量，其中第一项表示为维持原来 搜索方向的分量，w 为调整系数；第二项是向着当前自身最优解的方向去搜索的 速度分量，c 为调整系数；第三项是向着当前全局最优解的方向去搜索的速度分 量，c ，为调整系数。三个速度叠加便得到新的速度向量。式( 2 - 6 ) 表示第i 个 粒子经过调整后的位置。 2 2 3 粒子群优化算法处理组合优化问题 粒子群优化算法在处理组合优化问题上要复杂一些。把每个初始解的各分量 的数值组成一个集合k ，连续优化问题中，粒子的位置是体现在位置向量分量的 数值上，粒子位置的改变实际上是对各分量的数值进行增减，在迭代的过程中集 合k 是不断改变的。但是在组合优化中集合k 代表配送点序号，该集合是不能 改变的。因此，在处理这类问题中，不能直接套用上面的公式，而是应该利用粒 子群优化算法的思想，设计出一个新的算法体系来。 下面对处理组合优化问题的粒子群算法进行重定义： 1 ) 用s 表示离散的解空间，该解空间往往是有限的。 2 ) 粒子的位置三仍然用一个向量表示，由各分量的数值所组成的集合k 在迭代 过程中是不变的。各分量数值顺序决定粒子的位置。 3 ) 粒子的速度矿用序偶来表示，m i 表示该序偶向量的长度。 v = ( ( i k ，女) ) ，七个p 。若该粒子下一步迭代的速度为v = ( ( 1 ，3 ) ，( 2 ，4 ) ) ，则 表示该速度序偶向量所作用的位置向量的第一分量与第三分量交换，第二分量与 第四分量交换， v i i = 2 。一v 表示以相反的方向执行v ，一v = ( ( i k ，j ；) ) ， 七 - - 一( ( 1 、似+ i ，j l ，m ) ) ，k 个| ，l ，如上，一v = ( ( 2 ，4 ) ，( 1 ，3 ) ) 。 下面对公式中的符号操作进行重定义： 1 ) 位置一位置一速度( 一_ y ) 。两个位置向量用减号连接得出的结果为速 度，表明从后一个位置一步到达前一个位置所需要的速度。在公式( 2 5 ) q ，第二 项和第三项括号中的运算就属于这种情况。 2 ) 常数速度一速度( c v v ) ，c 为常数。常数与速度序偶向量相乘仍为速 度。 ( 1 ) 当( = o ，c v ：痧。 ( 2 ) 当c ( o ，1 ，c v = ( ( ，。) ) ，k 个p 盯，其中叫 为不大于c | i v l l 的整数。 第二章智能算法基本理论 ( 3 ) 当c ( 1 ，) ，分解c = k + c ，其中k 为正整数，c ( 0 ，1 。c f = c 矿。 3 ) 速度+ 速度一速度( y + v v ) ，两个速度序偶之和仍为速度序偶，新得到的 序偶为原序偶的简单合并，并且新序偶的深度不大于原序偶的深度之和。公式 ( 2 5 ) 中的三项之和便属于此类别。 4 ) 位置+ 速度一位置( 三+ 矿一) ，位置与速度之和为位置，该式也称为位移式。 表示一个粒子从一个位置以某种速度移动到另一个位置。公式( 2 6 ) 中的两项之和 便属于此类别。 2 2 4 粒子群优化算法的一些特点 1 ) 基本p s o 算法最初是处理连续优化问题，其收敛速度一般比较快。 2 ) 与遗传算法和免疫算法类似，该算法也是基于群的多点搜索且粒子之间的信 息共享。 3 ) 式( 2 5 ) 的第一项对应多样化( d i v e r s i f i c a t i o n ) 的特点，第二项、第三项对 应于搜索过程的集中化( i n t e n s i f i c a t i o n ) 特点，因此这个方法在多样化和集 中化之间建立均衡。 4 ) 由于该算法主要围绕两个公式进行迭代，因此程序实现比较容易并且代码量 比较小。 2 3 蚁群算法 蚁群算法是由意大利学者m a r c od o r i g o 于1 9 9 1 年提出的一种全新的模拟进 化算法n 5 6 m 引，它是一种通用的启发式算法，可以解决不同的组合优化问题。 m d o r i g o 等人首次提出该方法时充分利用了蚁群搜索食物的过程与著名的旅行 商问题( t s p ) 之间的相似性，通过人工模拟蚂蚁搜索食物的过程( 即通过个体之间 的信息交流与相互协作最终找到从蚁穴到食物源的最短路径) 来求解t s p 问题。 2 3 1 蚁群算法生物学基础 蚁群算法的生物学基础可大致描述如下：像蚂蚁这类群居昆虫，虽然视觉极 其微弱，却能找到由蚁穴到食物源的最短路径。仿生学家们经过大量细致的观察 研究发现，生物世界中的蚂蚁在搜索食物时，能在其走过的路径上释放一种信息 素，使得在一定范围内的其他蚂蚁能够察觉到并影响其搜索行为。蚂蚁个体之间 是通过一种称之为外激素( p h e r o m o n e ) 的通讯介质来相互传递信息的，从而能相 互协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该 第二章智能算法基本理论 物质，而且在运动的过程中，能够感知路径上这种物质的存在及其强度，蚂蚁倾 向于朝着外激素强度高的方向移动。因此，由大量蚂蚁组成的蚁群( a n tc o l o n y ) 的集体行为便表现出一种信息正反馈的现象。当某路径上经过的蚂蚁越多时，留 在相应路径上信息素的迹( t r a i l ) 也越多，以致信息素的强度增大，后来的蚂蚁选 择该路径的概率也就越高，从而进一步增加该路径的信息素强度，这样的选择过 程被称为蚂蚁的自催化行为( a u t o c a t a l y t i cb e h a v i o r ) 。蚂蚁个体之间就是通过这种 信息的交流达到快速搜索食物的目的。 2 3 2 蚁群算法的原理 蚁群算法是在结合着求解旅行商问题( t s p ) 提出的使用m 只蚂蚁来优化一 t s p 问题，在f 时刻有6 艇) ( 法1 ，2 ，玎) 只蚂蚁位于城市f ，那么显然聊= b 形) ， 每一只蚂蚁都是一个独立的智能体，它们具有如下特征： 1 ) 每只蚂蚁根据概率选择下一步到达的城市，该概率由残留在该城市和下一城 市之间的信息素强度以及之间的距离构成的函数表示。 2 ) 每只蚂蚁下一步所到达的城市只局限于该蚂蚁还未访问过的城市。 3 ) 每只蚂蚁完成一次遍历之后在其所走过的路径上撒下相同数量的信息素。 蚂蚁必须依据转移概率公式选择下一个到达点，该公式为 相_ je 黑裂如黟a l l o w e d k p 7 ) p = 。吼 r 脚刚” ( 2 7 ) 1 0 否则 其中r ，为“可视度常量”，令7 7 ，2 两个城市越远，相互之间的“可 视度”越差。 r ，( f ) 为f 时刻路径( f ，) 上的信息素强度，由于每一只蚂蚁都要在t 时刻确定 下一步走向哪里，即该蚂蚁在t + l 时刻在哪个点。因此