（计算机应用技术专业论文）面向蚁群算法的车间调度问题研究.pdf

哈尔滨娌工大学t 学坝i ：学位论文 面向蚁群算法的车间 调度问题研究 摘要 车间调度是一个典型的n p 难问题，理论上已经证明想在多项式时问内 对这类问题找到全局最优解是不可能的。蚁群算法是近年来兴起的种寻 优算法，特别在解决组合优化问题中被越来越多的人所采用。本文应用蚁群 算法求解两个车间调度问题，提出建立蚂蚁初始点的概率优先权分布方法， 利用蚁群算法的正反馈和并行搜索特点提高解的质量和稳定性。 1 通过对基本蚁群算法的实现过程和j o b s h o p 调度问题的分析和研 究，给出了求解j o b s h o p 调度问题的析取图模型，并给出了详细的a c a 蚁 群算法求解j o b s h o p 调度问题的算法描述，然后通过对2 8 个b e n c h m a r k 实 例进行模拟。试验结果表明：蚁群算法可以有效地求解车间调度问题：对于 个别实例可以达到最优解：蚁群算法的平均性能优于遗传算法。 2 通过对摹本蚁群算法的实现过程和流水调度问题进行研究，给出了 求解流水调度问题的解构造图，提出了两种蚁群算法来求解以总流程时川最 小为目标的流水调度问题一f a c a 蚁群算法和p a c a 蚁群算法，分别给出了 f a c a 蚁群算法和p a c a 蚁群算法的参数初始化方式、相对应的信息素更新 方法和概率分布规则，并提出了局部搜索模式，最后进行模拟试验，对这两 种算法进行比较，试验结果表明：对于较大规模的问题，p a c a 蚁群算法要 优于f a c a 蚁群算法，而对于较小规模的问题，f a c a 蚁群算法优于p a c a 蚁群算法。平均来说，p a c a 蚁群算法的性能优于f a c a 蚁群算法。 关键词车间调度；m a k e s p a n ；蚁群算法；启发式算法 哈尔滨埋1 大学：学倾l 。学位论文 r e s e a r c ho na na n tc o l o n y a l g o r i t h mf o rj o bs h o p s c h e d u l i n gp r o b l e m a b s t r a c t t h ej o b s h o ps c h e d u l i n gp r o b l e mi san p - h a r dt h ef a c tt h a ti ti si m p o s s i b l e t of i n dt h eg l o b a lo p t i m u mi np o l y n o m i a lc o m p l e x i t yh a sb e e np r o v e da n t c o l o n ya l g o r i t h m ( a c a ) ，w h i c hi sa no p t i m i z a t i o ns e a r c h i n gt e c h n i q u e ，h a sb e e n w i d e l yn o t i c e dd u r i n gr e c e n ty e a r s ，a na n tc o l o n ya l g o r i t h m ( a c af o rs h o r t ) i s p r o p o s e d f o rt w o j o b - s h o ps c h e d u l i n gp r o b l e m ap r o b a b i l i t yp r i o r i t y i s i n t r o d u c e df o rt h ei n i t i a ld i s t r i b u t i o no fa n t s m o r e o v e r ，q u a l i t ya n dr o b u s t n e s so f s o l u t i o n sa r ei m p r o v e db yt h en a t u r eo f f e e d b a c ka n dp a r a l l e lp a r a d i g mo f a c a 1 t h r o u g ht h ea n a l y s i sa n ds t u d y i n go fa n tc o l o n ya l g o r i t h ma n dj o b s h o p s c h e d u l i n gp r o b l e m ，ad i s j u n c t i v eg r a p hi si n t r o d u c e d t h ed e t a i ld e s c r i p t i o no f t h ep r o p o s e da c aa l g o r i t h mi sd e s c r i b e d l a s t ，a c aa n dg aa r er u no n2 8 i n s t a n c e sw i t hd i f f e r e n ts i z e s e x p e r i m e n t a lr e s u l t ss h o wt h a ta c a c a ne f f i c i e n t l y s o l v ej o b - s h o ps c h e d u l i n gp r o b l e ma n dc a no b t a i nt h eo p t i m u m so ns o m e i n s t a n c e sa sw e l l ，a c ao u t p e r f o r m sg ai np e r f o r m a n c eo na v e r a g e 2 t h r o u g ht h ea n a l y s i sa n ds t u d y i n go fa n tc o l o n ya l g o r i t h ma n df l o w s h o ps c h e d u l i n gp r o b l e m ，ac o n s t r u c t i o ng r a p hi s i n t r o d u c e d t w oa n tc o l o n y a l g o r i t h m s ( f a c aa n dp a c a ) a r ep r o p o s e da n da n a l y z e df o rs o l v i n gt h ef l o w s h o p s c h e d u l i n gp r o b l e mw i t ht h eo b j e c t i v eo fm i n i m i z i n gt h e f l o w t i m e l h e i n i t i a l i z a t i o no fp a r a m e t e r sa n du p d a t i n go ft r a i li n t e n s i t i e sa n dp r o b a b i l i t yi s d e s c r i b e dr e s p e c t i v e l ya n dan e w l yl o c a ls e a r c ht e c h n i q u ei sp r o p o s e dl a s ti st h e e x p e r i m e n ta n dt h ec o m p a r i s o ns h o w st h a tt h ep a c ap e r f o r m sb e t t e rt h a nt h e f a c ai nt h ec a s eo fr e l a t i v e l yl a r g e - s i z e dp r o b l e m st h a ni nt h ec a s eo fr e l a t i v e l y s m a l l s i z e dp r o b l e m s a sw e l l ，p a c ao u t p e r f o r m sf a c ai np e r f o r m a n c eo n a v e r a g e 【i 哈尔滨理工人学工学硕士学位论文 k e y w o r d sj o b s h o ps c h e d u l i n g ；m a k e s p a n ；a n tc o l o n ya l g o r i t h m ；h e u r i s t i c s i i i 哈尔滨理工大学工学硕士学位论文 第1 章绪论 车间调度问题是交通运输、科研、服务行业以及各种企业生产中普遍遇到 的问题，也是调度领域和f m s 中人们广泛注意的问题。它最早是在机器制造 业中提出来的，但事实上它在编制作业计划、企业管理、交通运输、航空航 天、医疗卫生等各个领域都有广泛的应用。因此，车问调度问题中的任务、机 器、资源都应理解为抽象的概念，可以代表及其广泛的具体对象。与生产计划 相比，车间调度一般是在线实时的，对快速高效运行要求更高。 车间调度问题应用如此广泛，以至于在应用数学、计算机科学、运筹学、 人工智能以及工程科学等领域，大量新的文献不断涌现。由此可见调度研究的 重要性。随着现代制造业中车间调度问题的复杂性和重要性的提高，迫切需要 研究有效地车间调度方法。随着现代制造业的发展，小批量、多类型的、有不 同完工时间和产品要求的产品需求逐渐取代大批量单类型的产品制造计划。在 这种情况下，如何利用现有的资源( 加工能力) ，满足被加工任务所需的各种约 束( d r l 工次序、所需机器) ，使所有的任务能尽量按时完成( 性能指标最小) ，就 成为一个十分现实和迫切的问题。由于理论上已经证明车间调度问题属于典型 的n p 难问题，不可能在多项式复杂度的时间算法内找到最优解。有越柬越多 的人开展了对该问题的研究，产生了许多方法，并随着对各类调度问题研究的 深入及各种交叉学科的发展，出现了许多新的车间调度理论和方法，并取得了 许多研究成果。 1 1 车间调度问题及其传统研究方法 1 1 1 车间调度问题 1 9 5 4 年，j o h n s o n 研究了两台机床的流水车间调度问题。这标志着调度理 论研究的开始。由于调度问题的理论价值和实用意义，在后来的5 0 年中，有 2 0 0 0 0 多篇关于调度问题的文献发表，其中包括m u t h 着【l t h o m p s o n c o n w a y ， r i n n o o y ，c o f f m a n ，f r e n c h ， m o r t o n ，b l a e w i c 2 ，c h r e t i e n n ee ta l 等八篇专 著。 总的说来，车间调度问题的实质就是在时间上合理配置系统的有限资源， 以满足特定目标的要求。典型的车闽调度问题包括一个待加工零件集合，每个 哈尔滨理工大学t 学撷b 学位论义 零件包含一个工序集合，各工序需要占用机床等生产资源，并且要按照一定的 工艺路线进行加工：不同机床加工的工序可以不同；调度的目的就是为零件合 理地分配机床等资源，并合理地安排加工时问，在满足约束条件的同时，使一 些指标最优。 1 1 2 车间调度问题的分类 生产调度系统的分类方法很多，主要有以下几种： 1根据加工系统的复杂度，可分为单机、多台并行机、f l o ws h o p 和i o b s h o p 。 2 单机调度问题是所有的操作任务都在单台机器上完成，为此存在任务 的优化排队问题：多台并行机的调度问题更复杂，因而优化问题更突出；f l o w s h o p 型问题假设所有作业都在同样的设备上加工，并有一致的加工操作和加工 顺序；j o bs h o p 是最一般的调度类型、并不限制作业的操作的加j = 设备，并允 许一个作业加工具有不同的加工路径。 3 根据性能指标，分为基于调度费用和调度性能的指标两大类。 4 根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问 题。 5 根据作业的加工特点，可将调度问题分为静态调度和动态调度。 静态调度是指所有待安排加工的工作均处于待加工状态，因而进行一次调 度后、各作业的加工被确定、在以后的加工过程中就不再改变；动态调度是指 作业依次进入待加工状态、各种作业不断进入系统接受加工、同时完成加工的 作业又不断离开，还要考虑作业环境中不断出现的动态扰动、如作业的加工超 时、设备的损坏等。因此动态调度要根据系统中作业、设备等的状况，不断地 进行调度。实际调度的类型往往是j o bs h o p 型，且是动态的。 车间调度问题有以下几个特点： 1 计算复杂性大部分车间调度问题具有n p h a r d 特性，因而计算复杂度 高。动态随机性制造系统的加工环境是不断变化的，在运行过程中会遇到多 种随机干扰，故生产调度过程是一个动态的随机过程。 2 多目标性实际的车间调度问题是多目标的，并且这些目标之间往往会 发生冲突。 3 多约束性车间调度受到多种加工资源的制约如加：亡机床、操作工人、 运输小车、刀具以及其它辅助生产工具等。 哈尔滨理t 大学1 学颂一 一学位论文 车侧调度问题的优化目标是评价调度方案优劣的标准，常见的调度指标 自： 1反映调度成本的指标调度中发生的费用有：启动成本、换线成本、加 工费用、i a ；b n 班费用、过期赔偿费用、在线库存费用、调度管理费用等。由 于调度净现值指标能综合反映上述费用，所以得到了广泛应h = j 。 2 反映调度性能的指标包括：生产周期、平均流动时间、机床利用率、 工人利用率等。 3 反映用户要求的指标包括：最大拖期时问、平均拖期时间、拖期零件 的数量等。 1 1 ，3 车间调度问题的研究状况 1 1 31 车间调度的研究进展自从车问调度问题在2 0 世纪5 0 年代被，j ：始广泛 研究以米，经过几十年的发展，产生了许多车问调度问题的类型和求解方法 2 1 ，对于车间调度问题，根据需求的产生来源，可分为丌环车间和闭环车间； 根据加工系统的复杂性，可分为单机、多台并行机、f l o ws h o p 和j o bs h o p ；根 据性能指标，可分为基于调度费用和调度性能的指标两大类。根据生产环境的 特点，也可以将调度问题分为确定性调度和随机性调度问题。根据作业的加工 特点，也可以将调度问题分为静态调度和动态调度。实际中，车问调度的类型 往往是j o bs h o p 型，且是动态的。目前研究比较多的是作业车刚调度( j o bs h o p ) 问题【3 】【4 1 和流水车间调度( f l o ws h o p ) l h 日题【”，并随着对各类调度问题研究的深入 及各种交叉学科的发展，出现了许多新的车间调度理论f 6 1 【7 】( 8 1 和方法【9 】。早期关 于流水车间调度问题，只局限于调整时间顺序依赖于两台机器中的一台，一种 动态规划方法，可用于求解大约1 5 个工件下这一。问题的最小化最大流程时制 ( m a k e s p a n ) 。当调整时间分离且顺序依赖所有m 台机器时，且有无限大存储空 闯存储已处理过的文件时，数学规划方法和建立在图搜索规则之上呻3 的隐枚举 方法可被修改用来解决问题。这些均是流水车阳j 调度问题的一些最优算法。这 些算法的计算时i 刨即使在中等规模时已经非常大。因此人们转向对高效、有效 的启发式方法的研究。姜思杰，马玉林】针对具有路径柔性的j o bs h o p 调度问 题，以调度长度极小化为优化目标，提出新的动态优化调度算法将优化分配算 法、可行优化调度算法和故障调度算法有机的集成起来，能够在系统设备出现 异常时迅速产生最优或次优调度。但是启发式方法虽然能在较短时间内找到解 但解的质量往往不高，随着计算机运算速度的快速提高，元启发式算法越来越 哈匀 滨理工大学工学硕士学位论文 受到人们的关注。车间调度问题的研究方法向着多元化的方向发展。目前关于 车间调度问题的研究主要分为两大类：启发式方法和元启发式方法。 1 启发式方法“”1 ( 1 ) 数学规划法、( 2 ) 组合优化法、( 3 ) 规则调 度、( 4 ) 人工智能技术等。 ( 1 1 数学规划法有线性规划( l i n e a rp r o g r a m m i n g ) 方法、非线性规划( n o i l l i n e a rp r o g r a m m i n g ) 法、动态规j i l l ( d y n a m i c a lp r o g r a m m i n g ) 法、拉格朗日乘子 法等等，在这些算法中，线性规划法作为一种精确调度方法，是较成熟的方法 之一，但很多问题都不能以简单的线性关系精确表达，且变量多为整数，因此 他的使用受到很大限制。 ( 2 1 组合优化方法包括分支定界法( b r a n c ha n db o u n d ) t ”j 、割平面法等。 其中较常用的是分支定界法，它的效率与定界的方法以及搜索空间的结构密切 相关，如果能合理地这些因素，可将其用于中小规模问题的求解。由于调度问 题地复杂性，对于n p 难题，上述算法的计算时间随规模的增大而呈指数增 长。s a t i ns c e ta l t ”1 和p o r t sc n e ta l 1 提出了改进的分支定界法，其不同点 主要在于分析规则、定界机制和上界的产生三方面的差异。这类方法虽然从理 论上能求得最优解，但由于其计算复杂性和搜索效率低下，难以解决大规模的 调度问题。 ( 3 ) 规则调度”是指在一般的调度算法基础上引入有效的调度规则，以寻 找近忧解。p a n w a l ks e ta l l ”1 总结了1 1 3 条规则，并将它们分为了三类：简单 规则、复合规则、启发式规则。这一方法可以大大缩短寻优过程，具有很强的 使用价值。在选用调度规则时，人们必须对实际情况做具体分析和必要的仿真 实验后，才。可以适当选用。 ( 4 ) 人工智能方法。2 1 利用知识表达技术把人的知识包括进去，同时使用各 种搜索技术以求给调度问题一个令人满意的解。它把调度过程描述成一个在满 足约束的解空间中搜索的过程。人工智能方法如专家系统的研制，为调度问题 指明了一条通向应用的途径。但是具有只是难于表达和难于获取等缺点。 2 元启发式方法。”( 1 ) 模拟退火法、( 2 ) 禁忌搜索法、( 3 ) 遗传算法、( 4 ) 神 经网络算法、f 5 1 蚁群算法。 ( 1 ) 模拟退火法( s i m u l a t e da n n e a l i n g ) 模拟退火法( s a ) i o l 将组合优化问题 与传统力学问题的热平衡问题类比，它模仿了晶体结晶的冷却过程，在较高温 度瓦下，系统状态为s ，能量( 即目标函数) 为e ，选择s 的一个邻域s 。，如果 e ) n 和m n 条件下更具一般性j o b s h o p 问题的研究。 2 需要对局部搜索算法的限制条件以及加强收敛性和计算速度的进一步 研究。 3 大规模问题作为限制性j o bs h o p 最优化问题仍然是一个挑战，虽然启 发式算法能较好解决大规模问题，但应从理论上更深入研究其收敛性及其有限 时阳j 性问题。 4 实际的生产环境是动态的，具有变化的结构和目标，还存在调度的中 断。如果用离线的调度指导生产过程，使等待时间和在制品量增加，设备利用 率、产品质量及批处理性能降低。因此对交互式调度( i n t e r a c t i v es c h e d u l i n g ) 矛f 在线调度的研究是今后的研究方向。 5 寻求新的数学工具和分析方法，建立j o bs h o p 算法复杂性、收敛性的 分析研究理论，对算法的收敛速度和优化度进行估计。 竺竺篓竺三尘兰三兰丝兰堡丝兰 1 2 蚁群算法及其研究状况 1 2 1 蚁群算法 自然界中的蚂蚁是以外激素( p h e r o m o n e ) 为媒介进行信息传递的，从而蚂蚁 个体能相互协作，完成复杂的任务。蚂蚁在行动中，会在它们经过的地方留下 外激素。同一蚁群中后到的蚂蚁能够感知到这些外激素的存在及其强度，并以 此来指引自己的行动方向，具体表现在选择外激素强度大的路径的概率要高 些。这样，后到的蚂蚁同样留下外激素，对原有的外激素进行加强，如此循环 下去。蚁群的行为便表现出一种信息正反馈现象：某一路径上经过的蚂蚁越 多，则后到者选择该路径的概率就越大。由于在一定的时间内，越短的路径会 被越多的蚂蚁访问，因而该路径所沉积的外激素就越多，在下一“时间段内，后 到的蚂蚁选中该路径的概率就越大，这个过程会一直持续到大多数蚂蚁都走最 短的那条路径，蚂蚁个体之间就是通过这种信息的交流达到搜索食物源的目 的。基本蚁群算法的原理就是人工模拟蚂蚁的上述食物搜索过程来求解组合优 化问题，蚁群算法具有如下优点：( 1 ) 较强的鲁棒性：对基本蚁群算法稍加修 改，便可以应用于其它问题：( 2 ) 分布式计算：蚁群算法是一种基于种群的进化 算法，具有真正的并行性，易于实现并行；( 3 ) 易于与其它算法相结合：蚁群算 法很容易与多种启发式算法结合，以改善算法的性能。众多研究已经证明蚁群 算法具有很强的发现较优解的能力，这是因为该算法不仅利用了f 反馈原理在 一定程度上可以加快进化过程，而且是一种本质并行的算法，不同个体之间不 断进行信息交流和传递，从而能够相互协作，有利于发现较好解。 1 2 2 蚁群算法的研究现状 蚁群算法自提出以来，以t s p 问题为测试基准，与其他一些常用启发式方 法做了一系列的比较，用于检验的是若干典型的对称型和非对称型t s p 问题 ( 取自t s p l i b ) ，先后采用了模拟退火( s a ) 、遗传算法( g a ) 、神经网络仆i n ) ( 如 弹性网法、自组织映射法等) 、进化规j i j ( e p ) 、遗传退火法、插入法、禁忌搜索 法( t s ) 、边交换法( 2 o p t 、3 - o p t 等) 等多种算法进行求解，除了l i n k e m i g h a n 的局部改进法外，优于其他所有方法。 在t s p 问题之后，接着求解的就是经典的二次分配问题( q a p ) ，测试数据 堕查堡矍三查兰苫兰丝兰堡兰兰 ! 柬自倒库q a p l i b ，其结果也相当令人满意。随后，工件排序问题、图着色问 题、大规模集成电路、通信网负载平衡、序列订货问题( 即有结点访问顺序限 制的t s p 问题) 等，相继得到测试、求解和应用。 在蚁群算法问世不久，人们就开始对其设计了各种改进措施。首先是将蚁 群算法与q 学习算法结合而成的a n t q 算法，其中利用了多个人工蚁群的协 同效应。其后，m a x m i n 蚁群系统在求解t s p 中获得了更好的效果，这种改 进型蚁群算法对轨迹强度f 。设景了上下限f 。和f m m ，运行时，仅对一个蚂 蚁实施m a x m i n 法则，并且轨迹强度初始时设为f 。在此基础上，又提 出了带有局部改进策略的m a x m i n 蚁群算法，其主要步骤可叙述成： 1 信息素轨迹和参数初始化； 2 当停机条件不满足时，执行 ( 1 ) 对每个人工蚂蚁构造一个解； ( 2 ) 选择实施局部改进的人工蚂蚁； ( 3 ) 更新信息素轨迹，其中，所有的f 。限定在f 。m ，f 。中。 3 返回最佳值。 一般而言，局部改进方法与初始解有关，求解时往往涉及到初始化问题， 而蚁群算法在一些组合优化难题上与其他启发式算法相比尽管更具竞争力，但 比之个别精致的局部改进算法仍相形见绌，于是，将蚁群算法与局部改进法相 结合可使两者的优越性进一步发挥。 此外，用蚁群算法的思想来改善遗传算法的实验结果也已公布，这方面的 工作似乎还有更多的探索余地。 蚁群算法至今仍处于萌芽时期，不管是理论还是应用都尚未成熟，表l 。l 给出了蚁群算法与其他一些常见元启发式算法的研究概况。 表1 1 一些常见的元启发式算法的研究概况 t a b l e1 】o v e r v i e wo f s o m em e t a - h e u r l s t i ca l g o r i t h m s 模拟退火禁忌搜索神经网络遗传算法蚁群算法 理论 v 仿真实验 可 软件包 v 复杂性 v 表示已有成熟的结果表示已有相当一部分结果，v 表示仪有少鼙结果，表示未开 发 堕竺堡些三查兰三兰堡兰兰堡篓兰 1 2 3 蚁群算法的发展方向 在2 0 世纪9 0 年代，意大利学者m d o r i g o ，vm a n i e z z o ，a c o l o m i 等人 从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻找路径的行为，提出了 一种全新的模拟进化算法：蚁群算法( a n tc o l o n ya l g o r i t h m ) ，并用该方法求解 t s p 问题、分配问题、j o bs h o p 调度问题，取得了一系列较好的实验结果。 1 9 9 9 年，吴庆洪1 4 8 1 等提出了具有变异特征的蚁群算法。其核心思想是为了克服 蚁群算法收敛较慢的问题，采用逆转变异方式，随机地进行变异，以增大进化 时所需的信息量。这种变异机制充分利用了2 一交换法简洁高效的特点，因而具 有较快的收敛速度。将前述a c s 算法与具有变异特征的蚁群算法结合起来考 察，恰巧对应了开始介绍的同本学者a k i h i d eh i u r a 4 9 1 等人用一个多智能体模 型( m u l t i a g e n ts y s t e m ) 进行仿真，即智能体( a g e n t ) 协作行为的形成是基于两个条 件：智能体( a g e n t ) 无规律、随机地注意信息素的存在( 即有时利用已知信息， 有时进行探索，对应a c s 算法) ；智能体( a g e n t ) 覆盖整个搜索空间( 即尽可能 增大信息量，对应具有变异特征的蚁群算法) 。具有变异特征的蚁群算法是在遗 传算法中变异算子的启发下产生的。意大利学者f a b i o ，a b a a t t i s t a 等人也受遗 传算法的启发提出蚁群算法和遗传算法相结合的一条思路。鉴于在蚁群算法中 参数盘，( 分别对应信息素和能见度对决策的权重) 和p ( 对应蚂蚁在一个周期中 留下的信息素量) 的选择对算法的性能有很大影响，可以将a ，p 和p 看成代表 蚂蚁翅型特征的染色g 中的三段代码。在g 中，g 。和g8 将a ，编码为实 数，g 。将q 编码为整数。然后将此染色体通过遗传算予交由一个进化过程处 理。这样就把蚁群系统的协作效应与遗传算法的进化效应相结合。此外，德国 学者t h o m a s s t t i t z l e 与h o l g e r h o o s 5 0 1 提出的另种改进的蚁群算法“最大最小 蚁群系统”( m a x， 也是一种较好的通用优化算法。在_ m i n a n ts y s t e m m m a s ) 解t s p 与a t s p 时，m m a s 的性能与a c s 相当，在平均路径长度上还优于 a c s 。两者的共同点是在算法的每次迭代中只允许表现最好的蚂蚁更新路径上 的迹：其不同之处主要在于如何防止过早的停滞现象( s t a g n a t i o n ) 。m m a s 限定 了痕迹浓度允许值的上下限，并且采用了平滑机制( t r a i ls m o o t l l i n g m e c h a n i s m ) 。m m a s 在算法启动时将所有支路上的痕迹浓度初始化为最大值 f 每次迭代后，按挥发系数p 降低痕迹浓度，只有最佳路径上的支路才允许 增加其浓度，并保持在高水平上。但是只采用最大最小痕迹浓度的限制还不足 以在较长的运行时i 目里消除停滞现象，因此采用了平滑机制：痕迹浓度的增加 j 下比于r 。和当前浓度r ( r ，j ) 之差。对此算法的进一步扩展是加入局部搜索， 竺丝篁些三查兰三兰堡。：! 兰丝篁兰 目的是一方面提高算法性能，能在搜索初期获得高质量的解，更直接地引导学 习机制；另一方面，使m m a s 为后续的局部搜索阶段构造好的初始解，以便 找到接近最优的解。 蚁群算法是一种新型的模拟进化算法，虽研究时间不长，已显示出求解复杂 优化问题方面的优势，其应用前景非常广泛。例如交通网络中的最佳路径选择 问题，电信网络中的流量负载分配问题等等都可以应用该算法来解决。但是蚁群 算法还不像其它的启发式算法那样已形成系统的分析方法和具有坚实的数学基 础。参数的选择更多的是依靠实验和经验，没有定理来确定。而且它的计算时间 偏长。这些都表明其在理论和实践方面尚有许多问题需要更深入的研究与解 决。 1 3 课题来源及论文主要研究内容 1 3 1 课题来源 本课题来源于黑龙江省自然科学基金( f 0 2 0 7 ) 、哈尔滨市青年基金 ( 2 0 0 2 a f q x j 0 3 3 ) 、黑龙江省教育厅科学研究( 1 0 5 3 1 0 5 6 ) 。 1 3 2 主要研究内容 本课题研究的目的是针对求解n p 难的车间调度存在的问题，通过深入研 究问题的性质，提出蚁群算法的求解方法，利用蚁群算法的f 反馈和并行搜索 特点提高解的质量和稳定性。 车间调度可以定义为若干个任务在一些机器上进行加工，如何按时日j 对机 器和物力等资源进行安排，使选定的目标函数【1 4 【3 5 1 达到最优。它最早是在机器 制造业中提出来的，但事实上它在编制作业计划、企业管理、交通运输、航空 航天、医疗卫生等各个领域都有广泛的应用。因此，车间调度问题中的任务、 机器、资源都应理解为抽象的概念，可以代表及其广泛的具体对象。与生产计 划相比，车间调度一般是在线实时的，对快速高效运行要求更高。 车i 刚调度问题应用如此广泛，以至于在应用数学、计算机科学、运筹学、 人工智能以及工程科学等领域，大量新的文献不断涌现。由此可见调度研究的 重要性。随着现代制造业中车间调度问题的复杂性和重要性的提高，迫切需要 研究有效地车间调度方法。车问调度问题一直是调度领域和f m s 中人们广泛 堕查鎏矍三查兰三兰堡圭耋堡篓圣 注意的问题。随着现代制造业的发展，小批量、多类型的、有不同完工时间和 产品要求的产品需求逐渐取代大批量单类型的产品制造计划。在这种情况下， 如何利用现有的资源( 加工能力) ，满足被加工任务所需的各种约束( 加工次序、 所需机器) ，使所有的任务能尽量按时完成( 性能指标最小) ，就成为一个十分现 实和迫切的问题。研究车间调度的理论和方法，对于提高工作效率和经济效 益，有着重要的现实意义和理论意义。 主要研究内容： 1 蚁群算法求解i o b s h o p 调度问题。包括i o b s h o p 调度问题的模型，蚁 群算法参数初始值的确定和概率选择方法等。 2 蚁群算法求解流水调度问题。包括流水调度问题的解构造图，蚁群算 法参数初始值的确定，信息素更新方式和概率选择方法等。 1 4 论文结构 第1 章绪论。介绍了车间调度问题及其传统研究方法，给出了车间调度问 题的分类及研究现状；然后介绍蚁群算法及其研究现状，简单阐述蚁群算法的 发展和研究现状；最后说明了课题来源及论文主要研究内容。 第2 章蚁群算法。概述了蚁群算法的发展现状、基本原理及步骤，分析了 蚁群算法的特点，并对蚁群算法的一些理论进行了讨论。 第3 章j o b s h o p 调度问题的蚁群算法求解。描述了 o b s h o p 调度问题，总 结了一些已有的启发式算法，在分析了基本蚁群算法的基础上，提出了面向 j o b s h o p 调度的a c a 蚁群算法：通过模拟试验，比较蚁群算法和遗传算法的 性能。 第4 章流水调度的蚁群算法求解。描述了流水调度问题，给出了解构造 图，总结了求解流水调度问题的f a c a 蚁群算法和p a c a 蚁群算法，通过模拟 试验证明其有效性。 结论。对本文的工作进行总结，并对进一步研究方向作了展望。 1 1 f 尔滨理工大学工学硕士学位论文 2 1 引言 第2 章蚁群算法参数初始化 在2 0 世纪9 0 年代，意大利学者m d o r i g o ，v m a n i e z z o ， a c o l o r n i 等 人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻径的行为，提出了一 种全新的模拟进化算法：蚁群算法( a n tc o l o n ya l g o r i t h m ) 。基本蚁群算法的原理 就是人工模拟蚂蚁的上述食物搜索过程来求解组合优化问题。1 9 9 9 年，吴庆洪 等提出了具有变异特征的蚁群算法。其核心思想是为了克服蚁群算法收敛较慢 的问题，采用逆转变异方式，随机地进行变异，以增大进化时所需的信息量。 这种变异机制充分利用了2 交换法简洁高效的特点，因而具有较快的收敛速 度。德国学者t h o m a s s t t i t z l e 与h o l g e rh o o s 提出的另一种改进的蚁群算法 “摄大最小蚁群系统”( m a xm i na n ts y s t e m ，m m a s ) 也是一种较好的通用优 化算法。众多研究已经证明蚁群算法具有很强的发现较优解的能力，这是因为 该算法不仅利用了正反馈原理在一定程度上可以加快进化过程，而且是一种本 质并行的算法，不同个体之间不断进行信息交流和传递，从而能够相互协作， 有利于发现较好解。蚁群算法是种新型的模拟进化算法，已显示出求解复杂 优化问题方面的优势，其应用前景非常广泛。 2 2 蚁群算法的原理 2 2 1 蚁群算法的物理学背景 蚁群算法( a n tc o l o n ya l g o r i t h m s ) 是受到人们对自然界中真实的蚁群集体 行为的研究成果的启发，而提出的一种基于种群的模拟进化算法，属于随机搜 索算法，由意大利学者m d o r i g o 等人首先提出，m d o r i g o 等人首次提出该方 法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题( t s p ) 之间的相似 性，通过人工模拟蚂蚁搜索食物的过程( 即：通过个体之间的信息交流与相互 协作最终找到从蚁穴到食物源的最短路径) 来求解t s p ，为了区别于真实蚂蚁 的群体系统，我们亦称这种算法为“人工蚁群算法”。我们通常所说的“蚁群 算法”就是指“人工蚁群算法”。 哈尔滨理工大学工学硕一l 学位论文 i f 如m d o r i g o 等人在关于蚁群算法的第一篇文章中指出的：蚁群中的蚂 蚁以“外激素”( p h e r o m o n e ) 为媒介的间接的异步的联系方式是蚁群算法的最大 特点。蚂蚁在行动( 寻找食物或者寻找回巢的路径) 中，会在它们经过的地方留 下一些化学物质( 我们称之为“外激素”) 。这些物质能被同一蚁群中的后来的 蚂蚁感受到，并作为一埽十信号影响后到者的行动( 具体表现在后到的蚂蚁选择 有这些物质的路径的可能性，比选择没有这些物质的可能性大得多) ，而后到 者留下的外激素会对原有的外激素进行加强，并如此循环下去。这样，经过蚂 蚁越多的路径，在后到蚂蚁的选择中的可能性就越大( 因为残留的外激素浓度 越大的缘故) 。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而 积累的外激素也就越多，在下一个时间内被其它的蚂蚁选中的可能性也越大。 这个过程会一直持续到所有的蚂蚁都走到最短的那一条路径为止。如图2 1 所 示： 图2 1 真实蚁群寻找食物的方法 f i g 2 - 1 a ne x a m p l ew i t hr e a la n t s 若以从a 点到e 点的蚂蚁为例进行说明，对于从e 点到a 点的蚂蚁而言 过程基本是一样的。由于路径b h d 比b c d 要短，因此选择b h d 路径的一只 蚂蚁要比选择b c d 的一只蚂蚁早到达d 点。此时，从d 点向b 点看，指向路 径d h b 的外激素浓度要比指向路径d c b 的外激素的浓度大。因此，从下一刻 开始，从e 点经d 点达到a 的蚂蚁选择d h b 路径比选择d c b 路径的可能性 大得多。从而使路径b h d ( 或d h b ) 上外激素浓度与路径b c d ( 或d c b ) 上外激 素浓度的差变大。而外激素浓度差变大的结果是选择路径b h d ( 或d h b ) 路径 的蚂蚁进一步增加，这又导致外激素浓度差进一步加大。最后的结果是，很快 所有的蚂蚁都选择较短的路径。 i一 堕堑堡些三奎兰三耋塑圭兰堡篁塞 2 2 2 蚁群算法的原理 蚁群算法吸收了真实蚁群行为的典型特征：一是能察觉小范围区域内状 况，判断出是否有食物或其他同类的信息素轨迹：二是能释放自己的信息素； 三是所遗留的信息素数量会随时间而逐步减少。人工蚁群和真实蚁群的相似在 于，两者优先选择的都是含“外激素”浓度较大的路径；两者在两种情况卜， 较短的路径上都能聚集比较多的外激素；两者的工作单元( 蚂蚁) 都是通过在其 所经过的路径上留下一定信息的方法进行间接的信息传递。 而“人工蚁群算法”同真实蚁群的活动不同在于以下几点： 1 人工蚁群具有记忆功能，它能够记忆已经走过的节点。 2 人工蚁群在选择下一条路经的时候并不是盲目的，而是按一定的算法 规律有意识的寻找最短路径( 如在t s p 问题中，可以预先指导下一个目标的距 离) 。 3 人工蚁群处在一个离散时间的环境中。 如图2 2 说明蚁群是如何找到最优路径的。 h 5 h ab ) 在时间t = 0 时，路径 曲标明距离的初始化图 鬈譬糍蒜卷磊僦 概率选择h 点或c 点 h c ) 在时间t = 1 时在较 短的边上有较多的外激 素，更多的蚂蚁将会选择 较短路径 例2 - 2 蚁群寻找虽优路径的过程 f i g 2 2a ne x a m p l ew i t ha r t i f i c i a la n t s 在图2 2a ) 中，从a 到e ( 或者从e 到a ) 有两条路径( a b c d e 和 a b h d e ) ，其中b 到h 、d 到h 的距离为1 ，b 到c 和d 到c 的距离为 o5 。下面分别考虑在时刻f o ，1 时，蚁群的运动情况。如图2 2b ) ，在时刻 t = 0 ，设有3 0 只蚂蚁从a 运动到b 。此时路径b h 、b c 上没有外激素( 蚂蚁 留下的信息量) ，故蚂蚁将以相同的概率向b c 、b h 运动，于是各有1 5 只蚂 堕垒堡型三查兰三兰堡圭兰竺篁兰 蚁分别选择路径b h 和b c 。在真实蚁群中，外激素的数量会随时间的 流逝而蒸发掉一部分，为说明方便，此处假设：所有蚂蚁运动的速度相 等；外激素蒸发量与时间成正比例，即路径上外激素的剩余量与路径的长 度成反比；蚂蚁选路的概率与所选路上外激素的数量成f 比。因为路径 b h d 的长度是路径b c d 的2 倍，当b 点的蚂蚁到达d 点后，路径b c d 上 的外激素是b h d 上的2 倍。如图2 2c 1 ，在时刻t = l 另有3 0 只蚂蚁从a 到达b 。因为路径b c 上的外激素量是b h 上的2 倍，根据蚂蚁选路的特 点，将会有2 0 只蚂蚁选择b c ，而只有1 0 只蚂蚁选择b h 。以此类推，当 t = 2 ，3 ，4 时，将会有更多的蚂蚁选择路径b c d 。经过较长时间运动后，蚁 群最终会沿着最优路径a b c d e 运动。 在自然界中，蚁群的这种寻找最短路径的过程表现为一种f 反馈的过 程，与人工蚁群的寻优算法极为一致。如果我们把具备了简单功能的工作单 元视为“蚂蚁”，那么上述寻找路径的过程可以用于解释人工蚁群的寻优过 程，蚁群总是选择外激素浓度高的路径。 2 3 蚁群算法的实现 2 3 1 蚁群算法的参数设定 本节以t s p 蚁群算法求解为例，说明其思想和实现。t s p 是组合优化 领域中的一个著名的经典难题，迄今尚未彻底解决，现已被归入n p 一完备的 问题类。其一般提法为：有一旅行推销员欲往n 个城市推销货物，从城市1 出发，经过其余各城市至少一次，然后回到城市1 ，问应选择怎样的行走路 线，才能使总行程最短( 各城市间距离d ，为己知) 。 在蚁群算法实施的步骤中，用到的变量和常数有： 埘为蚂蚁个数： 7 口为边( f ，) 的能见度( v i s i b i l i t y ) ，即l d f ； a z ；为蚂蚁k 于边( j ，j ) 上留下来的单位长度轨迹信息素数量； ： 0 q 化，若。j 在最优路孳去； ( 2 1 ) ” l其他： ” 其中，l 。为目标函数值。 各参数的含义如下： 1 6 喻尔滨理工大学工学硕十学位论文 口为残留信息的相对重要程度( “o ) ； 口为期望值的重要程度( 0 ) ； p 为残留信息的保留部分，( o p 1 ) ，可将1 一p 理解为残留信息的蒸发 部分； o 为体现蚂蚁所留轨迹数量的一个常数。 设将m 只蚂蚁放入到n 个城市中，那么每一只蚂蚁根据一定的依据选 择下一个它尚未访问的城市；同时在完成一步或者一个循环后，更新所有路 径上的残留信息浓度。选择下一个城市的依据主要是两点：f 。( f ) t 时刻连 接城市i 和城市j 的路径上残留信息的浓度，即出算法本身提供的信息； _ ，一由城市i 转移到城市j 的启发信息，该启发信息是由要解决的问题给出 的，由一定的算法实现。那么，t 时刻在城市i 的蚂蚁k 选择目标城市i 的 概率是： 膨( f ) 赫豫 p ：， 式中： 埘一所有尚未访问的城市；劈( f ) 一t 时刻蚂蚁由i 城到j 城的概率。 在每一只蚂蚁完成对所有n 个城市的访问后，新的信息量由下式确定： f 。( f + ) 2 p 勺o ) + 露 ( 2 3 ) 为了满足蚂蚁访问所有n 个城市的约束条件，为每只蚂蚁定义了一个数 据结构t a b u 数组，用来记载t 时刻蚂蚁已经访问的各个城市，并禁止在下 一次循环之前再次访问这些城市。当一次循环结束后，用l a b u 数组计算当 前解( 即，蚂蚁所走路径的距离) 。然后在f 一次循环之前，t