（计算机软件与理论专业论文）基于遗传算法的作业车间调度问题研究.pdf

摘要 摘要 作业车间调度问题具有计算复杂性、动态约束性、多目标性等特点， 被证明是典型n p 困难问题，近几年各种智能计算方法被引入到作业调度问 题中，如遗传算法、模拟退火算法、启发式算法等。遗传算法因其对优化 问题的弱依赖型、求解的简单性和鲁棒性、隐含并行性等特点被广泛应用 于作业车间调度，但在解决调度问题时，仍然存在收敛速度慢、精度不高 等问题。 本文首先对调度问题及其描述进行了阐述，分析了基于遗传算法的车 间调度的编码方式、交叉算子、变异操作等算子的特点以及遗传算子对算 法求解精度的影响。 其次，在深入分析基于操作编码的基础上，提出了一种新的基于作业 的交叉算子，并且使用该算予对具有确定加工时间的作业车间调度问题进 行了求解。同时与传统的基于位置交叉算子进行了仿真对比，实验结果证 明新设计的交叉算子能够得到更好的求解精度。 最后，对实际生产中加工时间和交货期都是模糊数的作业车间调度问 题进行了研究。为了求解模糊调度问题，分别用三角模糊数和半梯形模糊 数表示作业的加工时间和交货期，以极大化最小客户满意度为优化指标， 并且在g & t 算法的冲突处理中引入基于优先规则的冲突处理算法。通过大 量实验仿真对比，证明了基于优先规则的冲突处理算法在求解精度方面优 于原算法，并且是可行的，有效的。 关键词遗传算法；作业车间调度；三角模糊数；半梯形模糊数；交叉算子 燕山大学工学硕士学位论文 a b s t r a c t j o bs h o ps c h e d u l i n gp r o b l e m ( j s s p ) ，w h i c hc h a r a c t e r sa si t sc o m p l i c a t e d c a l c u l a t i o n , d y n a m i cm u l t i - r e s t r i c t i o n , a n dm u l t i - o b j e c t i v e ，h a sb e e np r o v e da s n p - h a r dp r o b l e m m a n yi n t e l l i g e n tc o m p u t a t i o nm e t h o d ss u c ha ss i m u l a t e d a n n e a la l g o r i t h m ，g e n e t i ca l g o r i t h m ，h e u r i s t i ca l g o r i t h m ，a l ei n t r o d u c e di n t o j o bs h o ps c h e d u l i n gp r o b l e mi nr e c e n ty e a r s g e n e t i ca l g o r i t h mi sw i d e l yu s e d i nj s s pb e c a u s eo fi t sl e s s d e p e n d e n c yo fo p t i m i z a t i o np r o b l e m , s i m p l i c i t y , r o b u s t n e s sa n di m p l i c i tp a r a l l e l i s m ，b u ti ta l s oh a sp r o b l e mo fs l o wc o n v e r g e n c e a n dl o w p r e c i s i o n f i r s t l y , t h i sp a p e re x p l a i n st h ej s s pa n di t sd e s c r i p t i o na n da n a l y z e st h e e n c o d i n gs t r a t e g y , c r o s s o v e ro p e r a t o ra n dm u t a t i o no p e r a t o ro fg e n e t i c a l g o r i t h mo nj s s ea tt h es a m et i m eg e n e t i co p e r a t o r si n f l u e n c eo ns o l u t i o n p r e c i s i o nh a sb e e ni s l l u s t r a t e d s e c o n d l y ，b a s e do nt h o r o u g hs t u d yt h eo p e r a t i o n - b a s e dr e p r e s e n t a t i o n ，t h i s p a p e rd e s i g n san e wc r o s s o v e rw h i c hi sb a s e do nj o b sa n dn s e st h ea l g o r i t h mt o s o l v et h ej o bs h o ps c h e d u l i n gp r o b l e mw i t l lad e t e r m i n a t i o np r o c e s sp e r i o d t h r o u g ht h ec o m p a r a t i v es i m u l a t i o n s 、j l ，i mp o s i t i o n - b a s e dc r o s s o v e r , t h en e w a l g o r i t h mc a ng e tab e t t e rs o l u t i o n a tl a s t , t h i sp a p e rs t u d i e st h ej s s pw i t hf u z z yp r o c e s s i n gt i m ea n df u z z y d u e d a t e i no r d e rt os o l v et h ef u z z ys c h e d u l i n gp r o b l e m , w eu s eat r i a n g u l a r f u z z yn u m b e rt or e p r e s e n tt h ef u z z yp r o c e s s i n gt i m ea n das e m it r a p e z i af u z z y n u m b e rt or e p r e s e n tt h ef u z z yd u e d a t e ，s e e kt h es c h e d u l i n gt h a tm a x i m i z e st h e m i n i m u mv a l u eo fc u s t o m e rs a t i s f a c t i o na n di n t r o d u c et h ep r i o r i t yr u l e b a s e d a l g o r i t h mt os o l v et h ec o n f l i c to fg & ta l g o r i t h m o u re x t e n s i v es i m u l a t i o n r e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mi sp r i o rt ot h ef o r m e r l ya l g o r i t h m t h e i m p r o v e da l g o r i t h mi sa l s of e a s i b l ea n d v a l i d a b s t r a c t k e y w o r d sg e n e t i ca l g o r i t h m ；j o bs h o ps c h e d u l i n g ；t r i a n g u l a rf u z z yn u m b e r ； s e m it r a p e z i af u z z yn u m b e r ；c r o s s o v e ro p e r a t o r l l i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于遗传算法的作业车 间调度问题研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个 人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人 承担。 ， 作者签字銮番诞日期：2 0 。7 年月7 日 燕山大学硕士学位论文使用授权书 基于遗传算法的作业车间调度问题研究系本人在燕山大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山 大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本 人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向 有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授 权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论 文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密嘭 ( 请在以上相应方框内打“4 ”) 作者签名：攘日期：3 - 叼年月f 日 导师签名：z 笥。支 日期：j ld 0 7 年f 月日导师签名： 形气t 艾 日期：d 0 7 年f 月f y 日 第1 章绪论 第1 章绪论 1 1 本课题的研究背景及意义 敏捷制造作为2 1 世纪企业的先进制造模式，综合了1 i t 、并行工程、 精益生产等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客 满意的产品，是完全面向顾客的。在这种模式下如何进行组织管理，包括 如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行 调度都是面临的主要问题。其中车间作业调度与控制技术是实现生产高效 率、高柔性和高可靠性的关键，有关资料表明，制造过程中9 5 之间的消 耗在非切削过程中i l j 。因此，有效的调度方法与优化技术的研究和应用，已 成为先进制造技术( a m t ) 实践的基础和关键。 那么什么是作业车间调度? 车间调度主要是针对一项可分解的工作( 如 产品制造) ，探讨在尽可能满足约束条件( 如交货期、工艺路线、资源情况) 的前提下，通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其加 工时间及加工的先后顺序，以获得产品制造时间或成本的最优化1 2 。在理论 研究中，车间作业调度问题常被称为排序问题或资源分配问题或组合优化 问题。在过去的几十年里，基于实际的及理论上的考虑，不断地激励着人 们寻找新的调度算法，其中一个重要原因是产品制造界的市场竞争性在不 断提高，好的生产调度能提高资源的利用率和操作管理水平，生产出具有 竞争力的产品。车间的调度优化工作，因其在提高生产效率，降低生产成 本等方面所起的重要作用，正越来越受到学者们的关注，也是本课题的研 究意义所在。 1 2 车间调度问题研究现状 调度问题的研究始于2 0 世纪5 0 年代，j o h n s o n 提出了解决n 2 f c m a x 燕山大学工学硕士学位论文 和部分特殊的“3 f f c m a x 问题的优化算法，代表调度理论研究的开始；6 0 7 0 年代建立了调度理论的主体( 经典调度理论) 并重视调度复杂性的研究。 随着7 0 年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了 许多新的车间调度理论与方法【3 】。 1 2 1车间调度问题的描述、分类及特点 从数学规划的角度看，车间调度可表达为在等式或不等式约束下，对 一个或多个目标函数的优化。现代典型的车间调度问题是将作业均衡地安 排到各处理机上，并合理地安排作业的加工次序和开始时间，使约束条件 被满足，同时优化一些性能指标。 对于车间调度问题，g r a v e 等人进行了分类整理1 4 】，按照不同的分类标 准，可以有以下4 种分类。 ( 1 ) 以复杂程度分类根据加工系统的复杂程度，可分为单机、多台并 行机、f l o ws h o p ( 流水线车间) 和j o bs h o p 。单机调度问题是所有的操作任务 都在单台机器上完成，为此存在任务的优化排队问题；多台并行机的调度 问题更复杂，因而优化问题更突出；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 型的调度问题展开。 ( 2 ) 以性能指标分类分为基于调度费用和调度性能的指标两大类。 ( 3 ) 以生产环境分类根据生产环境的特点可将调度问题分为确定性调 度和随机性调度问题。 ( 4 ) 以作业的加工特点分类可将调度问题分为静态调度和动态调度。 静态调度是指所有待安排加工的工作均处于待加工状态，因而进行一次调 度后，各作业的加工时间被确定，在以后的加工过程中就不再改变；动态 调度是指作业依次进入待加工状态、各种作业不断进入系统接受加工、同 时完成加工的作业又不断离开，还要考虑作业环境中不断出现的动态扰动、 如作业的加工超时、设备的损坏等。因此动态调度要根据系统中作业、设 2 第1 章绪论 备等的状况，不断地进行调度。实际调度的类型往往是j o bs h o p 型，且是 动态的。 1 2 2 车间调度问题的研究方法 在对车间调度问题进行研究的方法上，最初是集中在整数规划、仿真 和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。 随着各种新的相关学科与优化技术的建立与发展，在调度领域也出现了许 多新的优化方法，比如神经网络、模拟退火法、遗传算法、禁忌搜索法等， 使得调度问题的研究方法向多元化方向发展，总结起来，现有调度问题的 研究方法大体上可以分为以下几种类别。 ( 1 ) 基于运筹学( 0 r ) 的方法这种纯数学方法有模型抽取困难，运算量 大、算法难以实现的弱点，仅适合较小规模调度问题【”。 ( 2 ) 基于启发式规则的方法从实用的角度来看，启发式算法因其易于 实现、计算复杂度低等原因，但它们一般不具有全局优化的特点【6 j 。 ( 3 ) 控制理论方法g e r s h w i n 等人从控制理论的角度出发，较全面地阐 述了控制理论方法在制造系统的应用情况1 7 l 。但还没有形成一套有效的调度 模型表达、分析设计的技术，只适合对小规模的系统求解【s j 。 ( 4 ) 基于人工智能( a i ) 的方法在基于知识和规则的调度系统中，常用 的知识表示法有产生式规则、语义网络、框架等；常用的调度技术有生产 规则、探试法搜索、机会主义的推理、仿真和分级式的分解等1 9 】。 ( 5 ) 基于p e t r i 网的方法目前，p e t r i 网用于制造系统调度存在以下问题， 节点语义的单义性，使得所携带的系统信息不够丰富、重用性差，当调度 规则或方法复杂时，建模困难1 1 0 。 ( 6 1 基于仿真的方法由于仿真具有实验的特点，很难从特定的实验中 提炼出一般的规律性，生产调度成本高，仿真结果的价值和可信度严重依 赖仿真模型、仿真方法及仿真实验输入数据，仿真的准确性受程序员判断 能力和技能的限制l i t 。 ( 7 ) 神经网络q n ) 优化法h o p f i e l d 神经网络模型的提出为求解各种有 约束优化问题开辟了一条新途径，用h o p f i e l d 网络解决t s p 问题就是其在 3 燕山大学工学硕士学位论文 组合优化问题中的最成功的应用之- - i t 2 , t 3 。 ( 8 ) 遗传算法( g a ) 优化g o l d b e r 9 1 1 4 j 首次将g a 应用到实际的工程系统 优化当中。由于g a 原理和操作简单，通用性强，不受限制条件的约束， 且具有隐含并行性和全局解空间搜索能力，在机器学习、模式识别、控制 工程、优化等领域，尤其是在生产调度领域得到广泛的应用。 1 9 8 5 年d a v i s 首次将遗传算法用于解决车间作业调度问题 t 5 】，他在使 用g a 求解车间调度问题的研究中取得了近似最优解，并且发表了关于把 g a 成功应用于车间调度问题的论文，充分展示了g a 在解决车间调度问题 中的前景，此后其他学者开始完善并改进传统g a 车间调度的应用方法。 如h o l s a p p l e 、c l y d e w 1 6 l 利用将简单遗传算法与启发式算法结合的混合遗传 算法求解，得到较为满意的结果，王万良、宋毅、吴启迪1 1 7 1 提出了用双染 色体解决车间调度问题，杨晓梅、曾建潮f l8 】分析了j o bs h o p 问题自身的求 解难点和遗传算法的特点，并借鉴生物学的依据，提出了多个体交叉的遗 传算法。 ( 9 ) 组合调度方法由于各种调度算法都不同程度地存在着这样或那样 的优缺点，除了传统组合的启发式规则外，近来人们开始把各种近似算法 的组合应用研究作为热点，以弥补各自的缺点，发挥各自的优势，达到高 度次优化的目标【l 蚰”。目前，各种算法的组合应用己成为解决优化调度问 题很有前途的方法。 ( 1 0 ) 基于模糊数学理论的方法随着模糊数学的发展以及模糊数学规 划思想在调度领域的成功应用，模糊车间调度问题已成为研究的热点。例 如i s h i ih 1 2 2 1 等人首次提出应将交货期视作模糊数，并对开环车间的双机调 度问题和同型机调度问题作了研究，h a r ts 1 2 3 j 等人研究了单机模糊交货期的 调度问题，i s h i b u c h i l 2 4 , 2 5 1h 等人研究了模糊流水作业车间的调度问题，并 对模糊流水作业车间中的模糊加工时间问题做了描述，t s u j i i n m l 2 6 】等人运 用遗传算法求解了j s s p 中的模糊加工时间问题，王玮、汪定伟1 2 7 j 研究了单 件制造业模糊交货期下的准时化生产计划，m u r a t at 【2 驯等人研究了模糊交货 期下的多目标调度问题，a d a m o p u l o sgi 2 9 1 等人用基于邻域搜索的混合方法 研究了具有模糊交货期和可变加工时间的单机调度问题，l a mss 、c a ix 1 3 0 j 4 第1 章绪论 研究了模糊交货期下带有非线性附加惩罚的单机调度问题。 1 2 3 车间调度研究存在的问题 调度领域中的大部分问题都具有n p 问题，虽然对它的研究已有几十年 的历史，但至今尚未形成一套系统的方法和理论，理论研究与实际应用之 间还存在着很大差距。尤其随着j i t ( j u s t - i n - t i m e ) 思想的广泛采用，e t ( e a r l i n e s s t a r d i n e s s ) i 周度问题1 3 1 1 ，即使得作业尽量按交货期完成，变得越来 越突出。实际应用中的调度方法虽然能够响应系统的动态变化，但不能保 证得到好的调度，一些理论上的最优化方法能提供最优调度，但由于其计 算的复杂性，并且忽略了很多实际因素，离实际运用还有较大距离。 由于大多调度问题属于一类n p 困难组合问题，因此寻找具有多项式复 杂性的最优算法几乎是不可能的。各种近似启发式方法、诸如基于规则的 算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用于实 际调度中，但其往往对所得的调度解的次优性不能进行评估。在这方面有 必要探索更好的近似最优调度算法，可以考虑增加合理的计算时间代价， 提高解的次优性。各种基于统计优化的方法、诸如模拟退火法、遗传算法 等，提供了一种解决调度优化问题的新途径，但同别的优化算法类似，其 也存在着一定程度的枚举、一般来说收敛到最优解很慢，并且对于判断解 的最优性也很困难。在这方面也需要做进一步的研究。 在调度问题的理论研究中，大多数还是集中在针对经典的调度问题设 计优化算法 3 2 1 而经典调度问题与实际相差较大，尤其在目前柔性制造环境 下，柔性车间作业调度问题将是一个研究的重点和进一步研究的方向，而 目前对于这方面研究的文献相对来说较少。 1 2 4 车间调度研究的发展趋势 针对上述存在的问题以及车间调度系统的日益复杂性，目前车间调度 问题的研究形成了下列一些策略和研究趋势。 ( 1 ) 并行或分布策略适合不同车间控制结构与高度问题复杂性的实际 需要，不少学者提出并行或分布策略来解决调度问题 3 3 埘】。 5 燕山大学工学硕士学位论文 ( 2 ) 分解与成组策略利用分解生产计划或g t 的调度策略【3 5 1 可以大大 降低问题的复杂性和规模，求得调度问题的较优解，同时优化系统的一些 性能指标。近年来g t 或独立制造岛的应用实践便是一个明显的例证。 ( 3 ) 人机协同策略调度问题的性质、现有研究方法的缺陷以及人类独 特的思维能力决定了人机协同策略的生命力，大量的研究成果表明人机协 同交互的策略可以减少系统的搜索空间，可在有限的时间、背景知识条件 下解决困难的问题。 ( 4 ) 实时或动态重调度策略车间制造过程的随时性、不确定性需要不 断地进行重调度，以处理突发的事件。基于目前的研究，对于动态调度的 具体策略有周期调度、连续调度、事件驱动调度、周期与事件驱动混合调 度、周期与连续调度混合的策略等。 ( 5 ) 生产计划与调度集成策略生产计划与调度的集成研究具有全局优 化的特征，也符合先进制造模式的思想，同时提高了生产系统的柔性。 ( 6 ) 多目标权衡决策实际调度问题是多目标的，且这些目标往往相互 冲突【3 6 】，如何对调度系统的不同目标进行权衡分析，实现多目标调度是车 间调度问题的一个值得研究的方向。 ( 7 ) 异地生产调度策略作为a m 模式的关键技术之一，异地生产调度 已成为近期的研究热点【3 “。国家8 6 3 c i m s 专题也己把此项研究列入重点研 究领域予以支持。 总之，对车间调度领域的研究，随看应用数学理论的进一步发展，必 然朝着集成化、柔性化、多目标化、动态实用化、高度次优化方向进行。 1 3 课题的主要工作 论文土要运用遗传算法求解复杂车间调度问题，研究过程中做了以下4 个方面的工作。 ( 1 ) 对车间调度及遗传算法中存在的问题进行了深入分析与研究。 ( 2 ) 由于遗传算法存在过早收敛以及局部搜索能力不强的问题，本文提 出一种基于作业的交叉算子，并将其运用于作业车间调度问题的求解。 6 第1 章绪论 ( 3 ) 结合实际生产调度中存在问题，对模糊作业车间调度进行了研究。 ( 4 ) 使用基于优先规则的g i f f l e r & t h o m p s o n 算法对模糊作业车间调度问 题进行了求解。 1 4 全文的主要内容及结构安排 第1 章为绪论，阐述了本文研究的意义，描述了车间调度的概念、调 度问题的分类及其特点，介绍了车间调度问题的研究方法和调度策略。 第2 章遗传算法作为后续内容的铺垫，概述了遗传算法的基本原理和 步骤，介绍了遗传算法常用的一些算子，分析了遗传算法的特点，并对遗 传算法的一些理论进行了讨论。 第3 章研究了基于遗传算法的经典车间调度，详细介绍了调度问题的 数学表示形式，分析比较了车间调度遗传算法中的各种编码方式，最后设 计了一种基于作业交叉的遗传算子，通过仿真实验验证了新算法的有效性。 第4 章研究了基于遗传算法的模糊车间调度，介绍了模糊理论的基本 知识，研究了模糊调度的操作和求解中的难点，设计了新的遗传算法来解 决模糊调度问题，仿真实验证明了新算法是可行的。 最后，对全文进行总结，并就进一步的工作进行了分析与展望结论与 展望。 7 燕山大学工学硕士学位论文 2 1 引言 第2 章遗传算法理论基础 遗传算法【3 8 j 9 1 是一种仿生优化算法，它模仿的机制是一切生命与智慧 的产生与进化过程。它通过模拟达尔文“优胜劣汰、适者生存”的原理激 励的结构，通过模拟孟德尔遗传变异理论在迭代过程中保持己有的结构， 同时寻求更好的结构。作为一种随机的优化与搜索方法，遗传算法有鲜明 的特点：遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有 多条，而非单条，因而具有良好的并行性；遗传算法只需利用目标的取值 信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线形的 不连续多峰值函数的优化以及无解析表达式的目标函数的优化，具有很强 的通用性：遗传算法择优机制是一种“软”选择，加上良好的并行性，使 它具有良好的全局优化性和稳健性；遗传算法可行解集是编码化的，因而 具有良好的可操作性和简单性。 2 2 遗传算法的发展与现状 遗传算法的产生归功于美国m i c h i g a n 大学的h o l l a n d 在2 0 世纪6 0 年 代初的开创性工作，其本意是在人工适应系统中设计的一种基于自然演化 原理搜索机制。h o l l a n d 不仅设计了遗传算法的模拟与操作原理，更重要的 是，他运用统计决策理论对遗传算法的搜索机理进行了理论分析，建立了 著名的s c h e m a 定理和隐含并行性( i m p l i c i tp a r a l l e l i s m ) 原理，为遗传算法的 发展奠定了基础。将遗传算法应用于函数优化始于d ej o n g 4 0 1 ，他在其博士 论文中设计了一系列遗传算法的执行策略和性能评价指标，对遗传算法性 能做了大量的分析。d ej o n g 的在线( o n 1 i n e ) 和离线( o f f - l i n e ) 指标仍是目前衡 量遗传算法性能的主要手段，而他精心挑选的5 个实验函数( 称作d ej u n g s 第2 章遗传算法理论基础 f i v e t e s t f u n c t i o n ) 也是目前遗传算法数值实验中用的最多的实验函数。 在h o l l a n d 和d ej o n g 的工作之后，遗传算法经历了一个相对平稳的发 展时期，逐渐被人们所接受和利用。遗传算法的发展高潮开始于2 0 世纪8 0 年代末，而且延续至今，人们对遗传算法兴趣的日益增长有两个背景，其 一是工程领域，特别是人工智能与控制领域，不断涌现出超大规模的非线 形系统，在这些系统的研究中存在着大量的经典优化方法所不能有效求解 的优化问题，诸如神经网络连接权重及网络拓扑结构的优化、模糊系统中 模糊规则的选取及隶属函数的确定、知识库的维护与更新等等，其二遗传 算法本身就是一种模拟自然演化这一学习过程的求解问题方法，他能以独 立的或其他方法相结合的形式用于智能机器学习系统的设计中，经过1 0 年 的努力，遗传算法不论在应用上、算法设计上，还是在理论基础上，均取 得了长足的发展，己成为信息科学、计算机科学、运筹学和应用数学等诸 多科学所共同关注的热点研究领域。 2 3 遗传算法基本概念 由于遗传算法是由生物进化论和生物遗传学机理而产生的直接搜索最 优化方法，故而在这个算法中要用到各种生物进化和遗传学的概念，这些 概念如下。 ( 1 ) 串( s 仃i n g ) 它是个体( i n d i v i d u a l ) 的形式，在算法中为字符串，并且 对应于遗传学中的染色体( c h r o m o s o m e ) 。 ( 2 ) 群体( p o p u l a t i o n ) 个体的集合称为群体，串是群体中的元素。 ( 3 ) 群体大：j 、( p o p u l a t i o ns i z e ) 在群体中个体数量称为群体大小。 【4 ) 基因( o e n e ) 基因是串中的元素，基因用于表示个体的特征。例如 有一个串s = l o l l ，则其中的元素1 ，0 ，l ，1 分别称为基因，它们的值称为 等位基因( a l l e i e s ) 。 ( 5 ) 串结构空间s 在串中，基因任意组合所构成的串的集合就是串结 构空间，基因操作是在串结构空间中进行的，串结构空间对应于遗传学中 的基因型( g c n o t y p c ) 集合。 9 燕山大学工学硕士学位论文 ( 6 ) 参数空间s ，这是串空间在物理系统中的映射，它对应于遗传学中 的表现型( p h e n o t y p e ) 的集合。 ( 7 ) 适应度( f i t n e s s ) 表示某一个体对环境的适应度。 2 4 遗传算法的基本操作 标准遗传算法主要包括三个基本操作即选择操作( s e l e c t i o n ) 、交叉操作 ( c r o s s o v e r ) 和变异操作( m u t a t i o n ) ，适应度尺寸变换和最优保存等策略也可以 视为遗传算法基因选择的一部分，此外，还有许多用的比较少、作用机理 尚不明或没有普遍意义的高级基因操作，这里主要表述一下几个较为常用 的操作。 2 4 1 适应度函数与尺度变换 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e s s f u n c t i o n ) 为依据，利用种群中每个个体的适应度值来进行搜索。因此适应度 函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优 解。一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的 某种映射变换称为适应度的尺度变换( f i t n e s ss c a l i n g ) 。 适应度函数主要是以待求解的目标函数的转化为适应度函数，若目标 函数为最大问题则适应度函数为f i t ( f ( x ) ) = 厂( x ) ，若目标函数为最小问题 则f i t ( f ( x ) ) = 一厂( 石) ，该适应度函数简单直观，但存在两个问题，其一是可 能不能满足常用的轮盘赌选择中的概率非负的要求；其二是某些代求解的 函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平 均性能，影响算法的性能。 在设计遗传算法时，群体的规模一般在几十至几百，与实际物种的规 模相差很远，因此，个体繁殖数量的调节在遗传操作中就显得比较重要。 如果群体中出现了超级个体，即该个体的适应度大大超过群体的平均适应 值，在按照适应值比例选择时，该个体很快就会在群体中占有绝对的比例， 从而导致算法较早地收敛到一个局部最优点，这种现象称为过早收敛。在 1 0 第2 章遗传算法理论基础 这种情况下，应该缩小这个个体的适应度，以降低这些超级个体的竞争力， 防止过早收敛。另一方面，在搜索过程的后期，虽然群体中存在足够的多 样性，但群体的平均适应值可能会接近群体的最优适应值。在这种情况下， 群体中实际上已不存在竞争，从而搜索目标也难以得到改善，出现了停止 现象。在这种情况下，应该放大个体的适应度，以提高个体之间的竞争力。 这种对适应度的缩放调整称为适应度函数的定标( s c a l i n g ) ，自从d e j o n g 引入适应度函数定标以来，定标己成为保持进化过程中竞争水平的重 要技术，目前主要有以下3 种定标法。 ( 1 ) 线性定标设原适应度函数为f ，定标后的适应度函数为厂，则线 性定标采用下式表示，= a f - i - 6 ，式中系数a 和b 可以由多种途径设定，但 要满足两个条件：适应度平均值要等于定标后的适应度平均值；定标后适 应度函数的最大值等于原适应度函数平均值的所指定的倍数。即 二= c 。- ，雌其中，c 。是为得到所期望的最优群体个体的复制数。 ( 2 ) 仃截断仃截断是使用上述线性定标前的一个预处理方法，目的在 于更有效地保证定标后的适应度值不出现负值。相应的表示式如下： f = f 一杪一c o ) 式中，常数c 要适当选择。 ( 3 ) 幂函数定标方式其定义如下厂= f ，式中，幂指数i 与所求的最 优化问题有关，可在算法中修正以获得较好的结果。 2 4 2 选择算子 ( 1 ) 适应度比例方法适应度比例方法是目前遗传算法中最为基本也是 最常用的选择方法，它也叫轮盘赌或蒙特卡罗选择，在该方法中各个个体 的选择概率和其适应度值成比例。设群体大小为r ，其中个体f 的适应度值 f 为，则被选择的概率只= ，乃显然，概率反映了个体的适应度在 ，j 1 1 整个群体中的个体适应度总和中所占的比例，个体适应度越大，其被选择 的概率越高，反之亦然。 ( 2 ) 最佳个体保存方法( e l i t i s tm e t h o d ) 该方法的思想是使群体中适应度 最高的个体不进行配对交叉而直接复制到下一代中。设时刻r ( 第t 代) 时，群 燕山大学工学硕士学位论文 体中口o ) 为最佳个体，又设4 ( f + 1 ) 为新一代群体，若一o + 1 ) 中不存在口( ，) 则把口o ) 作为彳o + 1 ) 的第珂+ 1 个体。 采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和 变异操作破坏，但是这也会导致局部最优个体的遗传基因会急剧增加而使 进化有可能陷于局部最优解，也就是说该方法的全局搜索能力较差，因此 该方法一般都与其他方法结合使用。 ( 3 ) 排名选择方法所谓排名选择方法是在计算每个个体的适应度后， 根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率按序分 配给个体，作为各自的选择概率。根据选择概率的不同，可分为线性排名 选择和非线性排名选择。 线性排名选择是将群体中成员按适应度从好到坏依次排名，并按照式 2 1 所示分配选择概率。 z = 卜篙胁叫，2 ， r ( 2 _ 1 ) 式中口，b 为常数，由于只= 1 ，得b = 2 ( a - 1 ) ，又要求对任意的 f - 1 , 2 ，n 有只0 ，且置置只，所以限定1 口2 ，通常取口= 1 1 。 非线形排名选择是将群体中成员按适应度从好到坏依次排列，并按照 式2 - 2 所示分配选择概率。 只= 【q ( 1 0 一- g q ) ) 。 - ，= 1 ；二。一1 ( 2 - 2 ) 式中口是一个常数，表示最好的个体选择概率。 ( 4 1 期望值方法本算法的基本思想是，首先计算每个个体在下一代生 存得期望数目m = 7 = 玎，：z ，若某个体被选中并且要参与配对和交 叉，则它在下一代中的生存期望数目减去o 5 ，若其不参与配对和交叉，则 该个体的生存期望数目减去1 ；若一个个体的期望值小于0 ，则该个体不参 与选择。 在轮盘赌选择方法中，当个体数不太多时，依据产生的随机数有可能 会出现不正确的反映个体适应度的选择，即存在统计误差。也就是说，适 应度高的个体有可能被淘汰，期望值方法克服了这种误差，d ej o n g 对比了 第2 章遗传算法理论基础 适应度比例选择法、最佳个体保存法和期望值用于函数优化中的性能，结 果采用期望值的遗传算法离线和在线性能都高于采用另外两种方法的遗传 算法性能。 2 4 3 交叉算子 ( 1 ) 单点交叉在个体串中随机设定一个交叉点，实行交叉时，该点前 或后的两个个体的部分结构进行交换，并生成两个新的个休，如图2 - 1 所示。 父体a 1 00 l l i 11_ + 100 100 0 子体c 父体b 。1li 。叶。i lll1 子体。 图2 - 1 单点交叉 f i g 2 - 1s i n g l ep o i n tc r o s s o v e q ( 2 ) 两点交叉两点交叉的操作与单点交叉类似，只是设置了两个交叉 点( 依然是随机设定) 两个交叉点之间的码串相互交换，如图2 2 所示。 ii 父体。1 0 1 1i 1 1 一1 10 11 子体c 父体b00 i 1l 0 l 00 _ + 0o01100 子体d 图2 - 2 两点交叉 f i g 2 - 2t w op o i n t sc r o s s o v e r ( 3 ) 部分算术杂交这种方法通常用于实数编码的情形，设两个父体为 墨= ( 1 ，f l ，v ) ，吨) ，岛= ( v ”，v 1 2 ，堙) ，在两个父代解向量中选一部分 分量，然后生成( 0 ，1 ) 区间的一个随机数口，则后代染色体如式2 3 和式2 4 所示。 s l = 0 f ”，v ，v ! i ，盯2 。+ ( 1 一口) v 刍，口v ：+ ( 1 一口 ：) ( 2 3 ) s ：= ( v 2 ) ，v 1 ，雌，口v ：。+ ( 1 一口) ，：+ ”，钟：+ ( 1 一口弘：) ( 2 川 2 4 4 变异算子 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作 变动。交叉后子代经历的变异，实际上是子代基因按小概率扰动产生的变 化，依据个体编码表示方法的不同，可以有以下两种算法。 燕山大学工学硕士学位论文 ( 1 ) 基本变异算子基本变异算子是指对群体中的个体码串随机挑选一 个或多个基因并对这些基因座的基因值作变动( 依变异概率作变动) ，1 0 ，1 二 值码串中基本变异操作如图2 3 所示。 变异前10 0 1 q 10 + 10j1 l 10 变异后 图2 - 3 基本变异算子 f i g 2 - 3b a s i cm u t a t i o n ( 2 ) 逆转变异算子在个体码串中随机挑选二个逆转点，然后将两个逆 转点间的基因值逆向排序，二值码串的逆转操作如图2 - 4 所示。 变异前1o ol 1 1o 卜10jiq10 变异后 图2 4 逆转变异算子 f i g 2 - 4r e v e r s em u t a t i o n 2 5 本章小结 遗传算法在求解复杂的组合优化问题中表现出非常明显的优势，但也 受到诸如遗传算子选择和种群规模、变异概率、交叉概率等参数确定问题 的影响，为此，本章在介绍遗传算法起源和发展应用现状之后，给出了遗 传算法的详细设计步骤，同时介绍了一些有关遗传算法的理论问题。 1 4 第3 章基于作业交叉g a 的经典车间调度 第3 章基于作业交叉g a 的经典车间调度 3 1 引言 作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ) ，又被称为j s p ，是一 个典型的n p 困难问题，已成为c i m s 领域中研究的重要课题。它的研究不仅 具有重大的现实意义，而且具有深远的理论意义。 r o d a m m e r f a ，j a c k e kb 对j s p 调度方法、复杂性分析和数学规划模型 进行了综述【4 1 , 4 2 1 。解决j s p 调度问题的方法基本上可以分成两大类，即精确 算法和近似算法( j a c k e k1 3 ) 。在精确算法中，分枝定界法是初期解决j s p 调度 问题的最重要方法，其中m c m a h o n g b 提出的改进的分枝定界方法在相当 产的时间内一直是最好的精确的求解方法。 由于实际调度问题的复杂性，精确调度算法难以得到应用，因此，在 实际应用中，往往需要某种近似算法求解调度问题的近似解。优先权规则 调度和启发式算法以及基于局部搜索的算法是最常用的近似算法，a d a m sj 的移动瓶颈启发式算法是解决j s p i h 题的一个比较有效的方法t 3 s 。近几年， 模拟退火算法、禁忌搜索、遗传算法以及基于多智能矩阵的方法相继被应 用于解决j s p 问题。 3 2 调度问题及其描述 调度问题通常指生产过程的作业计划，譬如作业在机器上的加工顺序、 生产批量的划分等。就生产方式而言，调度问题可分为开环车间( o p e ns h o p ) 型和闭环车间型( c l o s e ds h o p ) 至d 1 3 】。 开环调度问题，也称加工排序问题，它本质上只研究作业的加工顺序， 即订单所要求的产品在所有机器上的加工排序，其中订单均来源于顾客， 不考虑库存的设立。 燕山大学工学硕士学位论文 闭环调度问题除了研究作业的加工顺序外，还要涉及各种产品批量大 小的设置值，即在满足生产工艺约束条件下寻找一个调度策略，使得所确 定的生产批量在设定的相应加工顺序下的生产性能指标最优( 或者是次优 解，满足用户需要) ，其中顾客需求的产品均由库存提供，生产任务一般只 能由产品存储策略来决定。 显然，通过比较开环调度贺闭环调度容易发现，闭环调度问题较开环 调度问题复杂。鉴于批量大小与排序之间的耦合性，寻求批量大小和排序 的有效同时处理方案很困难，目前处理闭环问题的常用近似方法是，首先 确定批量大小，然后确定加工顺序。 3 2 1 作业加工数据和特性的描述 调度问题中，通常一个作业一包含一个操作溉l ，q ，j ，每个操作q 的加工时间或需求为p 护若n 。；1 ，则作业，仅包含一个操作d l 。，简记其加 工时间p 。称作业，。的第一个操作可执行的时刻为释放时间或准备时间， 记为，i 。记加工操作d ；，的机器集为p 。f 似”，m 。 ，q 可以在p ，中的任 何一台机器上加工。通常，p 。，仅对应一台机器或者对应所有机器。前者称 为专用机器，后者称为并行机。许多实际生产系统中，各机器可装备相同 或不同的工具，操作可以在任何一台装备合适工具的机器上加工，这就是 生产系统所谓的柔性，该调度通常称为多目的机器调度。若p ，的加工过程 同时占有p ，中所有机器，则该调度称为多处理机任务调度( m u l t i - p r o c e s s o r t a s ks c h e d u l i n g ) 。对于每一作业以，记t 时刻完成以的加工费用函数为，( f ) ， 记计划完成时间或交货期( d u ed a t e ) 为z ，与之相关的权重为嵋。 若同一机器上既没有任意两个时间区间重叠，也没有分配给同一个作 业的任意两个时间区间重叠，并且满足调度问题的一些特殊工艺约束，则 称一个调度为可行调度。进而，称使得调度准则或指标最优的可行调度为 最优调度。 通常，作业加工特性可使用六元组卢= 弘。，皮，j b 3 ，卢。，风，卢。 来表示，b 用来表示加工方式，包括抢占式(