（计算机软件与理论专业论文）基于蚁群优化的供应链调度算法研究——物流调度算法研究.pdf

摘要 摘要 随着市场经济的发展，信息化、智能化技术的提高，供应链管理技术也得 到了飞速的发展。物流过程是供应链管理过程的子过程，物流过程中的物件分 配调度是供应链调度的一部分，同时也是物流过程中最重要的组成部分、核心 问题，优化物流过程中的物件分配调度对于提高企业的经济效益和社会效益具 有重要意义。供应链物流过程中的物件分配调度问题是一个组合优化问题，目 前解决该问题的方法比较简单，并有其各自的局限性，而新型的仿生算法 蚁群算法，具有正反馈性、鲁棒性、并行计算、协同性等特点，非常适合于解 决该调度问题，并顺应算法向智能化、仿生化发展的趋势。 本文研究了蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 在t s p 问题中的应 用，深入研究分析了改进的蚁群算法。通过对物流过程的分析，建立物流过程 的模型，深入分析问题的特点，将蚁群算法应用到物流调度领域中，建立适合 于蚁群算法的调度模型，提出了基于蚁群优化的物流调度算法，实现供应链物 流过程中物件的动态分配，并进行仿真研究以评价所提出方法的有效性。 本文针对蚁群算法早熟停滞、收敛速度慢等不足，提出了针对物流调度问 题的改进策略。仿真结果表明，使用改进的蚁群优化策略测试不同的订单组合， 能得到一个优化解决方案，该方案能使尽可能多的定单按时交付，同时也能将 订单的延迟减小，提高了算法的运算效率。 最后，本文还根据物流调度问题开发了一个相应的模拟仿真系统，表明基 于蚁群优化的物流调度算法具有一定的实用价值。 关键词：供应链；物流过程；调度；蚁群算法 a b s t r a c t a b s t r a c t w i t hd e v e l o p m e n to fm a r k e te c o n o m ya n di m p r o v e m e n to ft h ei n f o r m a t i o n i z a t i o n , i n t e l l i g e n tt e c h n o l o g y , t h em a n a g e m e n tt e c h n i q u e o f s u p p l i e d c h a i ng o tt h e d e v e l o p m e n ta th i g hs p e e d i ns u p p l yc h a i nm a n a g e m e n t ，l o g i s t i c sc a n b ed e f i n e da s t h es u b p r o c e s so ft h es u p p l yc h a i np r o c e s s t h es c h e d u l i n go ft h ec o m p o n e n t a s s i g n m e n t i st h ek e yi s s u ei n l o g i s t i c sp r o c e s s e s t h eo p t i m i z a t i o n o ft h e s c h e d u l i n gl o g i s t i c ss i g n i f i c a n t l yi m p r o v e s e c o n o m i ca n ds o c i a lb e n e f i t so f e n t e r p r i s e t h es c h e d u l i n go fl o g i s t i cp r o c e s si sac o m b i n a t i o no p t i m i z a t i o np r o b l e m r e c e n t l y , t h ea p p r o a c h e st h a ts o l v e dt h i sp r o b l e mc a nb ea p p l i e di ns i m p l i c i t y , b u tt h e s e m e t h o d sh a v es o m el i m i t a t i o n a san o v e ls 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 m , a n t c o l o n yo p t i m i z a t i o n ( a c o ) h a sm a n ym e r i t sa sp o s i t i v ef e e d b a c k , r o b u s t , p a r a l l e l c o m p u t e ，c o o r d i n a t i o n , s oi t i sv e r ys u i t a b l et os o l v es c h e d u l i n gp r o b l e ma n da c c o r d s w i t ht h et e n d e n c yt h a tt h e a l g o r i t h m e v o l v e si n t oi n t e l l i g e n ta n ds i m u l a t e d e v o l u t i o n a r y t h ep a p e rh a ss t u d i e dt h ea p p l i c a t i o no ft h ea n tc o l o n yo p t i m i z a t i o n a tt h e t r a v e l i n gs a l e s m a np r o b l e m sa n dh a sf u r t h e ri n v e s t i g a t e d t h ei m p r o v e dt h ea n t c o l o n yo p t i m i z a t i o n a f t e rt h ea n a l y s i so ft h el o g i s t i c sp r o c e s s ，i th a sb u i l tt h em o d e l o ft h el o g i s t i c ss c h e d u l i n g b yt h ea n a l y z e dt h ec h a r a c t e ro ft h ep r o b l e m , t h ea n t c o l o n ya l g o r i t h m h a s a p p l i e d i ns c h e d u l i n go ft h el o g i s t i c sp r o c e s s e s i th a s e s t a b l i s h e dt h es c h e d u l i n gm o d e lo fa n tc o l o n ya l g o r i t h m i th a sp r e s e n t e dt h e s c h e d u l i n ga l g o r i t h mo fl o g i s t i cs c h e d u l i n gb a s e do na n tc o l o n i e st h a th a so p t i m i z e d t h ed y n a m i ca s s i g n m e n to fi t e m st oo r d e r s e m p i r i c a ls t u d ys h o w st h ee f f i c i e n c yo f p r o p o s e da l g o r i t h m t oo v e r c o m et h ed e f a u l to fs t a g n a t i o na n dc o n v e r g e n c es p e e ds l o w , a ni m p r o v e d a c o s t r a t e g yi sp r e s e n t t h es i m u l a t i o nr e s u l ts h o w st h a ta l lo p t i m i z a t i o ns o l u t i o nc a l l b eo b t a i n e df r o ma p p l y i n gt h ei m p r o v e do p t i m i z a t i o ns t r a t e g yo fa n tc o l o n i e st ot e s t d i f f e r e n to r d e rc o m b i n a t i o n t h i ss o l u t i o ni m p r o v et h ee f f i c i e n c yo fa l g o r i t h mb y d e l i v e r i n gm o r eo r d e r so nt i m ea n dr e d u c i n gt h ed e l a yo f o r d e r s f i n a l l y , a c c o r d i n gt ot h el o g i s t i cs c h e d u l i n g ，t h es y s t e mo fs i m u l a t i o nh a sb e e n e s t a b l i s h e d i ts h o w st h a tt h el o g i s t i cs c h e d u l i n ga l g o r i t h mw i l lb e o fs o m e w h a t s i g n i f i c a n c e k e y w o r d s ：s u p p l yc h a i n ；l o g i s t i cp r o c e s s ；s c h e d u l i n g ；a n tc o l o n ya l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：- - s 需。月日期：厶耐7 7 关于论文使用授权的说明 本学位论文作者完全了解津南大学有关保留，使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 第一章绪论 第一章绪论 1 1 研究背景及研究意义 供应链管理是近年来在国内外逐渐受到重视的一种新的管理理念与模式。 供应链管理的研究最早是从物流管理开始的，起初人们并没有把它和企业的整 体联系起来，主要是进行供应链管理的局部性研究，如研究多级库存的控制问 题、物资供应的问题，其中较多的是关于分销运作的问题。随着经济全球化和 知识经济时代的到来，以及全球制造的出现，供应链在制造业管理中得到普遍 应用。我们生活在政治经济国际化和动态化的时代，面对的市场竞争日益激烈、 用户需求的不确定性和个性化增加、高新技术迅猛发展、产品寿命周期的缩短 和产品结构越来越复杂的环境，企业管理如何适应新的竞争环境，已成为广大 管理理论及实际工作者关注的焦点。 目前工业社会制造业商的特征是制造业商的产品中大多数部件是从别的 公司里买来的，生产线不再是工厂里的一系列传统的机器，而是由供应商、仓 库、分配中心等组成的一个世界范围内的网络，这些网络称之为供应链。供应 链的一个最主要的特征就是能够对市场的变化做出快速的反应。供应链管理 出现的时间虽不长，但是已经引起了人们的广泛关注。特别是国际上一些著名 的企业如惠普公司、i b m 公司、戴尔计算机公司等在供应链的实践中取得的成 就，更使人坚信供应链是进入2 1 世纪后企业适应全球竞争的一个有效途径，因 而吸引了很多学者和企业界人士对供应链管理进行研究和实践。 物流过程作为供应链管理的子过程，用以解决生产点和消费点之间的计划 编制、处理和货物存储控制等问题。在过去，货物生产、存储然后根据需求分 发。现在，许多公司不再需要做货物的存贮工作，而是使用集中的快速货物流 转系统，快速货物流转系统能够在有限的存储空间( 如航空港，海港等) 中很 容易的存贮货物心3 。供应商将货物运送到快速货物流转中心，存贮，然后交付 给有需求的客户。因此，物流过程的物件分配问题是一个调度问题。 近年来，利用蚁群优化解决物流调度中的组合优化问题是一个新的热点。 蚁群算法( a c o ) 是最新发展的一种带有智能行为的仿生优化算法，它具有较 强的鲁棒性、优良的分布式计算机制、易于与其它方法相结合等优点。在物流 过程中的一个关键环节就是资源分配，即物件的分配调度问题，对于物流中心 来说，如何得到一个合理的最佳组合能够既要保证按时交付的订单最多，同时 还要保证物流存储- 1 ，转中心所剩资源最少，如何对物流中心已有的物件进行分 江南大学硕士学位论文 配，并且使得需要按时交付的订单数目达到最优；所以必需寻找性能很好而且 时间复杂度相对较低的优化算法，然而，物件的分配调度问题是n p 难问题，通 常方法很难较好而且较快地接近全局最优。 如果物流过程中的物件分配方案不合理，会产生一系列的问题，如服务质 量下降，不能满足客户的要求；大量不合理的物件分配的出现会加大快速货物 流转中心的空间，增加额外的成本。优化物流过程中的物件分配调度问题可以 减少物件的存储量，加快订单的交付时间，这样既减少了大量的投资资金，降 低了成本，又增加了客户的最大满意度，增强了供应链的灵活性。最主要的一 点就是能够确保客户的最大满意度，货物交付及时，同时也将存储最小化了。 因此，优化物流过程的物件分配调度问题是一项非常关键的工作。优化物 件分配可以减少货物在快速物流中转中心的停留时间，节约了成本费用，加速 了物件的流转，增加了客户的满意度，提高了企业的经济效益和服务质量，减 少了快速物流中转中心的空间。 1 2 研究现状 1 2 1 物流调度的研究现状 在调度理论中，供应链物流过程中的物件调度问题是近几年才出现的。无 论是国外还是国内，供应链调度问题一直都是一个非常活跃的研究领域。供应 链物流过程中的物件调度问题由j m s o u s a 3 等人在2 0 0 2 年的i e e e 国际学术 会议上提出。由于供应链物流过程中的物件调度问题是近几年才提出来的，所 以到目前为止对该问题的研究主要有文献 4 - 7 等。 目前，国内外组合优化领域的理论已经相当成熟，许多理论已经被应用到 各个领域，在调度理论中，调度问题通常与资源的缺乏超时行为的最佳分配问 题有关口3 。在过去的十年里，研究了大量的方法来解决调度问题，通常这些问 题都是属于n p 难问题：分派规则阳1 ，瓶颈启发式方法阴1 ，局部搜索方法或元启 发式方法n 0 1 。p i n e d o 1 提出了一种最新的调度技术，主要用于车间调度问题， 但是这个方法对于一般的调度来说也是适用的。现在，元启发式被认为是最强 大的调度技术，其中主要的一个是进化类比，如遗传算法n 2 1 3 1 。然而，有许多 其它的启发式算法已经被成功的使用到了调度问题中，如模拟退火，禁忌搜索 或蚁群优化等。由于供应链物流过程中的物件调度问题是近来才出现的，所以 目前解决这个问题所使用的几种方法( 如：预分配策略( p a ) ，基于f i f s 的调 度规则等) 操作使用都比较简单，但是在处理复杂的供应链优化问题中显示出 了其局限性；而收敛性和稳定性较高的组合优化卫e 论和方法尤其足近期 现的 第一章绪论 一些新的优化理论和方法还没有利用计算机实现。因此，在物流调度中利用计 算机进行组合优化在国外尤其是国内是一个比较新的研究领域和发展方向。 1 2 2 蚁群算法的研究现状 1 9 9 1 年意大利学者d o f i g om 等人n 4 儿1 5 1 在首届欧洲人工生命会议上提出了蚁 群算法。1 9 9 6 年d o f i g om 等人在文献 1 6 中系统地阐述了蚁群算法的基本原理 和数学模型，还将其与遗传算法、禁忌搜索算法n7 l 、模拟退火算法n 鲫n 训、爬山法 等进行了仿真实验比较，并把单纯地解决对称旅行商问题( s y m m e t r i c t r a v d i n g s a l e s m a np r o b l e ms t s p ) 拓展到解决非对称旅行商问题( a s y m m e t r i c t r a v e l i n g s m e s m a np r o b l e ma t s p ) 、指派问题( 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 ) 以及车 间作业调度问题( 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 ) ，且对蚁群算法中初始化参数 对其性能的影响作了初步探讨；之后引起了全世界许多国家研究者的关注，其应 用领域得到了迅速拓宽。 l mg a m b a r d e l l a 、e dt a i l l a r d 和md o f i g o 他们将混合蚁群算法和局部搜索算 法用于二次指派问题，称为h a s q a p ( a h y b r i da n tc o l o n y s y s t e mc o u p l e dw i t ha l o c ms e a r c h ，a p p l i e dt ot h eq u a d r a t i ca s s ig n m e n tp r o b l e m ) 不像传统的蚁群算法用 信息迹的信息构造全部的解，h a s q a p 用信息迹的信息对q a p 的解进行修改。 h a s q a p 与其他一些能最好的解决q a p 的算法进行分析和比较：两种版本的 列表搜索( 也就是r o b u s t 和r e a c t i v e 列表搜索算法) 、混合遗传算法和模拟退火 算法。实验结果显示，h a s q a p 和混合遗传算法由于它们发现好的解的结构的 能力，在真实世界、不规则和结构化的问题中表现得最好。而对于随机、规则 和非结构化的问题，h a s q a p 则表现较差。 目前人们对蚁群算法的研究己由当初单一的t s p 领域渗透到了多个应用领 域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范 围内研究逐渐拓展到了连续域范围内研究，而且在蚁群算法的硬件实现上取得 了突破性进展，同时在蚁群算法的模型改进及与其它仿生优化算法的融合方面 也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未 有的勃勃生机。 1 3 本文的研究工作和安排 本文旨在基本蚁群算法原理的基础上提出一种适用于供应链物流过程中的 物件分配调度优化方案。通过研究基本蚁群算法的优势与不足，建立相应物件 分配调度模型，针对蚁群算法在优化物件调度存在的不足，提出了相应得改进 江南人学硕十学何论文 措施，将其改进的蚁群算法应用到解决物流过程中的物件调度问题中。另外， 通过实验测试，从实验角度论证算法的可行性，测试蚁群算法在解决物件分配 调度问题时的性能；最后分析了物流调度优化系统的必要性，开发了物流调度 模拟仿真系统。 本文的结构如下安排： 第一章主要提出课题的来源，介绍了课题的背景及其意义，分析了物流调 度问题的研究现状。 第二章对物流过程中的物件调度问题进行了分析，描述，提出问题，给出 了物流过程的生灭过程模型；简单介绍了目前用于解决物流调度问题的算法。 第三章详细介绍了蚁群算法。论述了蚁群算法的基本原理、算法模型，并 对算法的特点，参数进行了分析，最后简单阐述了几种改进的蚁群算法。 第四章主要给出了供应链物流过程中的物件分配调度问题的定义以及数学 模型，运用基本蚁群算法对该问题进行求解，并通过仿真算例分析了存在的不 足。 第五章提出了蚁群算法的改进策略：路径的选择策略，信息素的更新策略， 挥发系数p 的自适应调整策略；并对蚁群算法进行了描述；与f i f s 、f d f s 以 及基本蚁群算法在物流过程中的物件分配调度求解问题上进行了分析比较；最 后给出了物流调度的仿真系统。 第六章对本文进行了小结，总结了论文的主要工作以及有待改进之处，并 对进一步的研究工作进行了展望。 第二章物流调度问题分析 第二章物流调度问题分析 2 1 物流过程的描述 物流过程中的物件调度分配问题是供应链调度问题中的子问题心。供应链 物流过程一般有订单到达、物件请求、物件到达和物件分配调度、订单交付等 五个部分组成m 引，如图2 1 所示。 图2 - 1 基本物流过程示意图 f i g 2 1g e n e r a lr e p r e s e n t a t i o no fal o g i s t i cp r o c e s s ( 1 ) 订单到达 客户对物件的种类需求信息称为一个订单哆；订单到达是指客户对物件的 需求信息到达物流调度中心，通常将商品看作是物件的集合。每天物流调度中 心都有一个由1 1 1 个需要交付的订单所组成的列表o ( o s d ，其e e j = l ，j 聊) 。每一 江南大学硕十学位论文 个订单由一个或多个不同的条目组成，每一个条目通常叫做条件白。当订单被 提交到系统的时候，必须包含被客户要求的交付日期等基本信息。此外，系统 还应该提供一个交付日期。 ( 2 ) 物件请求 物件请求是指根据物流中心所接收的订单信息将客户对物件的需求进行分 类，然后把这种需求提供给不同的供应商。即向供应商提供一张购买单，购买 单包括所需物件的类型c ，及其数量g ，、需要的日期等信息，以便于供应商能够按 时按需交付物件。 ( 3 ) 物件到达 物件到达是指供应商根据购买单提出的需求将准备好的物件信息反馈到物 流中心。物件交付到物流中心还需要一些时间，这个时间叫做供应商延迟；当 物件提交到物流中心后，物流中心修改存货单，其中存货单上记录了它所能提 供的物件以及其数量等基本信息。 ( 4 ) 物件分配调度 物件调度分配在物流过程中起着决策性的作用，即物流中心把所有的物件 都分配到相应的客户并实施运送。但通常某些订单所需的物件并不会同时得到 满足，因此，订单就必须等待所需的物件都到达为止。所有需要等待的订单形 成一个表，叫做订单表。因为每个订单要求的交付时间一般都不同，而它们所 需的物件又是在不同时刻得到满足的，所以决策进程必须决定哪一个订单将被 交付，并考虑订单所需的物件是否已得到满足，同时还需检查存货单，并将它 与订单表进行比较，最后经优化做出决策。 ( 5 ) 订单交付 在物件分配调度决策过程中选择出的需要交付的定单后，通过转运中心， 将这些订单交付给相应的客户。 在物流过程中的一个关键环节就是资源分配，即物件的调度分配问题；物 件的调度分配问题是一个组合优化问题，如何对物流中心已有的物件进行分配， 并且使得需要按时交付的订单数目达到最优? 物流过程的物件调度分配可看成 是一个多维背包问题( m u l t i p l ek n a p s a c kp r o b l e mm k s ) 的特例乜钔，这个i 口- j 题属 于n p 难问题陋射。 2 2 问题的模型 2 2 1 供应链物流过程可以作为一个生灭过程模型 6 第二章物流调度问题分析 供应链物流过程中订单的到达和订单的处理呈指数分布，由此生成的随机 过程可以看作是一个马尔可夫过程凹6 3 的模型，或者是一个生灭过程的模型啦”。 通常生灭过程可以分为两个过程：生长过程和消亡过程。生长过程是指某时间 段内新订单到达的过程，消亡过程是指被处理的订单随着时间的消逝不断减少。 在某时间段t 内系统中新到达的订单数目呈离散型的概率分布，因此生长 过程可以用泊松分布来描述 。p ( 工，2 t ) ：哗e - 2 t ( 2 1 ) 彳! 这里，z 是一个随机变量( 指物流过程中的订单数目) ，参数m 是指在某时 间间隔t 内事件发生的概率。 消亡过程可以用指数分布来描述 p ( t ，t o ，z ) = p 一“一 ( 2 2 ) 其中，i l 是消亡率，t 是随机变量。指数分布表明尽可能使订单在时间间隔 a t - - - t t o 内完成。变量t 不具有记忆性，即系统中交付的订单数与系统中还有多 少订单无关。 2 2 2 问题的模型 设物流中心有r 1 种类型的物件，m 个未分配到物件需要等待交付的订单， 定义该问题的标志符号如下： ( 1 ) c = c ，c 2 ，c 玎) - 川流中心物件i 的种类集合； ( 2 ) q = q l ，q 2 ，q n 卜一物流中心当前库存中物件i 数量集合； ( 3 ) d = d ，o 加，o m 系统中的客户订单j 的集合； ( 4 ) 9 i 厂客户订单i 需要物件j 的数量； ( 5 ) 尺广订单j 到达系统的时间； ( 6 ) d 厂客户对订单j 的需求交付r 期； 西是物件到达物流中心后分配给订单j 的时间，所有的调度分配时间不能 超过时间d 。 物件调度分配问题包含下面的组成部分： ( 1 ) 订单q 由物件类型及其所需要的数量组成； ( 2 ) 符合条件的订单所需要的物件的数量不能超出库存中物件的数量； ( 3 ) 使得系统中订单的延迟数目达到撮少。 整个问题的解的总费用为： 江南大学硕士学位论文 ( 丁) = ：。i 乃 ( 2 3 ) 2 3 物流调度问题解决算法 供应链物流过程中的物件调度问题是近几年才提出的，到目前为止，研究 者给出的算法主要有预分配( p a ) 算法，先到先服务( f i f s ) 算法和先需要先服务 ( f d f s ) 瞳剐算法，蚁群算法等。 ( 1 ) 预分配 在供应链物流调度过程中，通常考虑使用预分配( p a ) 策略，预分配具有 简单、安全、快速等特点。在预分配策略中，当物件从供应商到达物流中心时， 就分配给相应的订单。如果订单所需的物件并没有同时到达物流中心，那么其 它的物件就必须暂存在那旱直到所缺的物件都到达为止，以便订单的物件能够 一起被发送。该策略并不能够有效地处理一些突来的变化，如订单的延迟或客 户所需物件数量的改变，因为分配任务是在订单一进入系统就已经完成了的。 这是一种静态调度策略。静态法不会受到物流中心的影响，它完全取决于外部 变量。 ( 2 ) 先到先服务( f i f s ) 和先需要先服务( f d f s ) 【2 8 】 先到先服务( f i f s ) 和先需要先服务( f d f s ) 属于动态分配策略；动态分 配是基于订单间物件的交换实现的。物流中心所有的物件都储存在一起，同时 订单表将按一定的策略排序列表顶端的订单将最先被系统分析。如果订单需要 的物件都得到满足，那么将交付该订单。否则，该订单就会留在订单表中，同 时处理下一个订单。对先到先服务( f i f s ) ，其列表的排序方法是根据订单的到 达日期进行的，最先进入系统的订单将最先得到服务。这种排序策略的不足在 于，订单到达得早，那么它也被交付得早，也许它被要求的交付日期还没到。 另一方面，有些订单被要求的交付时间早，但因为它们进入系统的时间太晚而 被延迟。先需要先服务( f d f s ) 策略是按照订单被要求交付的时间来排序，这种 策略能解决f i f s 所带来的问题，也可以与优先级列表相结合使用。 ( 3 ) 蚁群算法 蚁群优化算法是受到自然界的蚁群觅食行为的启发而提出的，是一种用于 求解组合优化问题的新型仿生进化算法，该算法首先由意大利学者m d o r i g o 6 3 等人提出，最初的蚁群优化算法称之为蚁群系统( a n ts y s t e m ，a s ) 引。蚁群优化 算法在许多相当困难的组合优化问题的求解中体现了极强的寻优能力和较好的 性质。在后续章节中将详细介绍和分析蚁群算法。 第二章物流调度问题分析 2 4 本章小结 本章首先对基本的物流过程进行了分析、描述，指出物流过程中的物件分 配调度问题是一个组合优化问题；然后给出了物流过程的生灭过程模型和物流 调度问题的模型；最后，对目前解决物流过程中的物件调度问题的算法进行了 简单的介绍说明。 江南大学硕十学位论文 第三章蚁群算法( a n tc o l o n ya l g o r i t h m ) 蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 是2 0 世纪9 0 年代才提出的一种新 的仿生进化算法，最初由意大利学者d o r i g om 等人受自然界中蚂蚁搜索食物行 为启发于1 9 9 1 年首先提出的1 4 】【3 0 】【3 1 1 ，作为一种新的启发式优化算法，对解决 这类问题表现出了较好的效果。它具有较强的鲁棒性、优良的分布式计算机制、 易于与其他方法相结合等优点【”】【1 6 】。 3 1 蚁群算法的背景介绍 蚂蚁算法是受到自然界中的蚂蚁行为的启发而提出的，是一种用于求解组 合优化问题的新型仿生进化算法。最初蚂蚁算法的思想来自蚂蚁寻找食物的行 为，像蚂蚁、蜜蜂等群居昆虫，虽然单个昆虫的行为及其简单，但是由单个简 单的个体所组成的群体却表现出极其复杂的行为。真实的蚂蚁在没有视觉的情 况下，能够找到从食物源到蚁巢的最短路径；同时，他们能适应环境的改变， 例如，当原最短路径中出现故障物时能够重新发现一条新的最短路径。究其原 因是因为蚂蚁个体之间是通过一种称为信息素( p h e r o m o n e ) 【3 2 j 的物质进行信 息传递的。蚂蚁在运动过程中，能够在它所经过的路径上留下该物质，而且蚂 蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方 向，蚂蚁倾向于朝该信息素浓度高的方向移动。因此，由大量蚂蚁组成的蚁群 的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后 来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流进行路 径的最优选择从而达到搜索食物的目的。 3 2 蚁群算法的生物模型儿蚓 蚁群算法主要是基于对蚂蚁觅食行为的研究，模拟真实蚂蚁的真实写作过 程。真实的蚂蚁在觅食过程中能够通过相互协作找到食物源和蚁巢之间的最短 路径阻5 3 引。在现实生活中，我们总可以观察到大量蚂蚁在蚁巢与食物源之间形 成近乎直线的路径，而不是曲线或者圆等其他形状，如图3 1 ( a ) 所示。蚂蚁群 体不仅能完成复杂的任务，而且还能适应环境的变化，如在蚁群运动路线上突 然出现障碍物时，一开始各只蚂蚁分布是均匀的，不管路径长短，蚂蚁总是先 按同等概率选择各条路径，如图3 1 ( b ) 所示。蚂蚁在运动过程中，能够在其经 过的路径上留下信息素，而且能感知这种物质的存在及其强度，并以此指导自 己运动的方向，蚂蚁倾向于信息素浓度i ：吾的方向移动。4 1 1 等时| 1 l j 内较短路径，j 二 第三章蚁群算法( a n tc o l o n ya l g o r i t h m 的信息量就遗留的比较多，则选择较短路径的蚂蚁也随之增多，如图3 - 1 ( c ) 所 示。不难看出，由于大量蚂蚁组成的蚁群集体行为表现出了一种信息证反馈现 象，即某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁 个体之间就是通过这种信息交流机制来搜索食物，并最终沿着最短路径行进， 如图3 - 1 ( d ) 所示。 常嚣= h 麓赣 等# 图3 1 现实中蚁群寻找食物的过程 f i g3 - it h ep r o c e s so f a n t f i n d f o o d i n t a l e - l i f e 蚂蚁觅食寻找路径的过程中涉及到以下机制： ( 1 ) 选择机制。路径上的信息素的浓度越大，选择的概率越大。 ( 2 ) 信息素更新机制。路径上的信息素随着蚂蚁的经过而增加，随着时州 的流逝而减少。 ( 3 ) 协峒机制。蚂蚁_ z | 1 l j 通过信息豢这种川接通讯方式束进行通信和协作。 啪 忡 撤忡 卅畔 絮 摭忡 靠 集， 江南大学硕士学位论文 3 3 蚁群算法原理口7 蚁群算法最初随机的选择搜索路径，随着对解空间的“了解”，搜索变得有 规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜索空间的“了解” 是通过观察蚁群觅食活动中建立的机制而得到的，由蚂蚁觅食的过程可以看出， 其协作方式的本质是：信息素浓度越大的路径，被选中的概率越大，即路径 概率选择机制；路径越短，它上面的信息素浓度增加得也越快，即信息素更 新机制；蚂蚁之间通过信息素进行通信，即协同工作机制。 为了进一步说明蚂蚁群体的路径搜索原理和机制，下面我们引用 m d o r i g o n 4 儿1 5 3 叩呤剐等所举的例子来具体说明蚁群系统的原理。如图3 2 假设蚂蚁 在食物源a 和巢穴e 之间运动，每单位时间内爬行单位距离，图中d 为距离，且每 单位时间内各有3 0 只蚂蚁从巢穴和食物源出发( 图3 2 ( a ) ) 。假设t = 0 时，有 3 0 只蚂蚁在点b 和点d ( 图3 - 2 ( b ) ) 。由于此时路上无信息素，蚂蚁就以相同的 概率走两条路中的一条，因而在点b 和点d 各有1 5 只蚂蚁选择往c ，其余1 5 只选 择往f 。t = 1 时，经过c 的路径被3 0 只蚂蚁爬过，而路径b f 和d f 只被1 5 只蚂蚁 f 5 c 5 ( a ) 各有3 0 只蚂蚁准备离开b 和d( b ) 各有1 5 只蚂蚁选择c 和f ( c ) 2 0 只蚂蚁选择c ，1 0 至选择f 图3 - 2 蚁群算法原理 f i g3 - 2t h et h e o r yo f a n tc o l o n ya l g o r i t h m 爬过，从而b c d 上的信息素踪迹的浓度是b f d 的2 倍。此时，又有3 0 只蚂蚁离开 b 和d ，于是有2 0 只蚂蚁选择往c ，另外1 0 蚂蚁选择往f ，这样更多的信息素被 留在更短的路径b c d 上。这样一来，较短路径b c d 上的信息素踪迹变的更浓， 越来越多的蚂蚁选择这条短路径。整个选路过程如此往复，即实现了随机选择 到自适应行为的过程。 第三章蚁群算法( a n tc o l o n ya g o r i t h m ) 3 4 基本蚁群算法模型 m d o r i g o 等学者提出的第一个蚁群优化( a c o ) 算法是a s ( a n ts y s t e m ) 算法n5 1 ，并用其对旅行商问题( t s p ) 进行求解。下面将以t s p 问题来具体阐 述a s 算法的基本模型。 3 4 1t s p 问题描述 旅行商问题是研究最为广泛的组合优化问题，它是最早被证明的n p 完全 问题之一。旅行商问题是指一个旅行推销员，要到1 3 个城市去推销产品( 包括 他所在的城市) ，每个城市能且只能访问一次，然后返回出发点。从一个城市到 另外一个城市需要一定的旅行费用，应该如何选择访问的路线，才能使总的旅 行费用最低。 定义3 1 ( t s p 问题) ：给定1 1 个城市的集合 v i ，屹，h ) 及城市之间旅行的 花费西( j 对确，j 对囟，f 习) 。t s p 问题是指找到一条经过每个城市一次 且回到起点的花费最小的回路，其数学模型如下： m i n d u 石盯 ( 3 1 ) 其中勃= e 嚣卵艳挎成脯路径 t s p 的简单形象描述是：给定n 个城市，有一个旅行商从某城市出发，访问 各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。 t s p 虽然是个求最短环路的问题，但是在现实生活中，很多问题都可以归结为 t s p 问题【3 9 】。 3 4 2 蚁群算法的数学模型0 6 id 4 1 1 1 6 1 1 3 5 l 设b i ( t ) 表示t 时刻位于元素i 的蚂蚁数目，以f ) 为t 时刻路径( i j ) 上的信 息量，1 1 表示t s p 规模，m 为蚁群中蚂蚁的总数目，则m ；罗b i ( f ) ； 百 r = f ，船) l q ，c ，c c 是t 时刻c 中元素( 城市) 两两连接萄上残留信息量的集合。 在初始时刻各条路径上信息量相等，并设r i i ( 0 ) = c o n s t 。 蚂蚁k ( k = l ，2 ，m ) 在运动过程中，根据各条路径上的信息量决定其转移方 向。这里用禁忌表t a b u k ( k = l ，2 ，m ) 来记录蚂蚁k 当前所走过的城市，集合随 着t a b u 进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及 路径的启发信息来计算状态转移概率。p f ，( t ) 表示在t 时刻蚂蚁k 由元素( 城市) i 转移到元素( 城市) j 的状态转移概率 江南大学硕士学位论文 尸t r y ( f ) =：圭兰!龋萄口zz。wpd。 。3 2 ， s c a l i o w e d k 0 ，否则 其中，a l l o w e d k = c - t a b u 七 表示蚂蚁k 下一步允许选择的城市；a 为信息启 发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂 蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径， 蚂蚁之间协作性越强；口为期望启发式因子，表示能见度的相对重要性，反映 了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则 该状态转移概率越接近于贪心规则；即盯( f ) 为启发函数，其表达式如下 ，、 1 t 乒f 2 瓦 ( 3 3 ) 其中，西表示相邻两个城市之f b l 的距离。对蚂蚁k 而言，如越小，则r u ( 力 越大，呶，) 也就越大。显然，该启发函数表示蚂蚁从元素( 城市) i 转移到元 素( 城市) j 的期望程度。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一 步或者完成对所有n 个城市的遍历( 也即一个循环结束) 后，要对残留信息进 行更新处理。t + n 时刻在路径( i ，j ) 上的信息量可按如下规则进行调整 气( f + 刀) = ( 1 一p ) ( f ) + z a z 0 ( t ) ( 3 4 ) 厶( f ) = f 扩( f ) ( 3 5 ) 其中，p 表示信息素挥发系数，则j p 表示信息素残留因子，为了防止信息 的无限积累，p 的取值范围为：pc o , 1 ) ；乃( f ) 表示本次循环中路径( i ，j ) 上的信息素增量，初始时刻( o ) = 0 ，f 盯( f ) 表示第k 只蚂蚁在本次循环中留 在路径( i ，i ) 上的信息量。 根据信息素更新策略的不同，在a s 算法中提出了三种信息素更新的算法。 在蚁周模型( a n t c y c l es y s t e m ) 中： ) = 悟薯誉只蚂蚁在本次循环中经趴厶户 6 ) 在蚁密模型( a n t d e n s i t ys y s t e m ) 中： f 。扣) = 彳孑薯翥k 只蚂蚁在t 和”1 之间经过g ，p ( 3 7 ) 1 4 第二章蚁群算法( a n tc o l o n ya l g o r it h m ) 在蚁量模型中( a n t - q u a n t i t ys y s t e m ) 中： k ：善若第k 只蚂蚁在t 和t + 1 之间经过a ，j ()i ri ( f ) = 如 ( 3 8 ) 10 否则 其中，q 表示信息素强度，它在一定程度上影响算法的收敛速度；l k 表示 第k 只蚂蚁在本次循环中所走路径的总长度。 3 5 蚁群算法的算法分析 3 5 1 蚁群算法的特点 蚁群算法作为一种新兴的仿真优化算法有其自身的特点，与以往其他的模 拟进化算法，蚁群算法具有如下几种优点： ( 1 ) 自组织。在系统论中，自组织和他组织是组织的两个基本分类，其区 别在于组织力或者组织指令是来自于系统的内部还是系统的外部。如果组织指 令来自于系统内部是自组织，组织指令来自外部的是他组织。如果系统在获得 空间、时间或者能力结构的过程中，没有外界的特定干预，我们便说系统是自 组织的。简单来说，即在没有外界作用的情况下，系统从无序向有序的进化过 程。蚂蚁算法充分体现了这一过程，在算法初期，单只蚂蚁无序地寻找解，经 过一定时间的算法演化，蚂蚁越来越趋向于寻找到接近最优解的一些解，这就 是一个从无序到有序的过程 4 0 】。 ( 2 ) 分布式计算。蚁群算法本质上是一种并行的算法，每只蚂蚁搜索的过 程相对独立，仅通过信息激素进行相互的通信。蚂蚁算法可以看成是一个分布 式的多智能体系统，具有本质并行性，它在问题空间的多点同时开始进行独立 的进行解搜索，易于并行实现，也增加了算法的可靠性口3 。 ( 3 ) 正反馈【4 0 1 。从蚂蚁觅食的过程中可以看出，蚂蚁最终能够找到最短 的路径，其主要原因就在于在最短路径上信息素的不断堆积，信息素堆积正是 一个正反馈的过程。蚁群算法在初始时刻各条路径上分布着相同的信息素，随 着算法的不断进行，各个路径上的信息素浓度会有所差异，算法采用的正反馈 是在较优的路径上蚂蚁会留下较多的信息素，而更多的信息素又会吸引更多的 蚂蚁，最终引导整个系统向最优解的方向进化。 ( 4 ) 鲁棒性。蚁群算法的鲁棒性很强，因为蚁群算法对初始解的要求并不 高，初始的信息素分布要求也不高，而且在计算过程中，蚁群算法不需要人工 进行调整。 江南大学硕七学位论文 ( 5 ) 易与其它方法结合。蚁群算法可以容易地与多种其它启发式算法相结 合，以