（计算机软件与理论专业论文）遗传算法及其在生产调度中的应用.pdf

山东大学硕士学位论文 摘要 遗传算法是一种模拟生物进化过程的随机搜索算法，其自组织、自适应、 自学习和种群进化能力使其适合于大规模复杂优化问题。它将问题的求解表 示成“染色体”的适者生存过程，通过种群的一代代不断进化，包括复制、 交叉和变异等操作，最终收敛到“最适应环境”的个体，从而求得问题的最 优解或者满意解。随着计算机技术的发展，遗传算法越来越受到人们的重视， 并在机器学习，模式识别、神经网络、优化控制、组合优化等领域得到了成 功的应用。 生产调度问题几乎在现实环境中，特别是在工业工程领域无所不在。许 多制造工业提出的调度问题从本质上讲非常复杂，难以用传统优化方法求解。 因此，调度问题成为遗传算法领域里的一个热门话题。原因是该问题表现出 约束组合优化问题的所有特征，并且成为测试新算法思想的范例。 本文将介绍遗传算法在生产调度方面的应用，并结合一个模型，提出我 们的共生进化遗传算法通过大量的试验，说明算法的可行性和有效性。 本文第一部分分别介绍了遗传算法和生产调度理论。第一节介绍了遗传 算法的生物学基础，并描述了遗传算法的一般框架。指出了和传统优化方法 相比遗传算法具有的独特优点。总结了遗传算法在基础理论研究、算法设计 和应用领域的研究情况。第二节介绍了生产调度理论的产生、发展、分类和 已有的解决调度问题的方法，指出各种方法的优点缺点。 第二部分提出了本文需要解决的问题：优化调度，使得工件的最大完成 时间( m a k e s p a n ) 最小。首先给出一种表达柔性生产调度的模型，这个模型能 方便的表示工序间的相互关系。针对加工计划和j o b s h o p 调度问题紧密结合 的特点，我们基于生物共生进化的思想，结合传统的启发式算法，提出了一 个共生进化遗传算法框架。对加工计划部分，个体编码采用机器序列和选择 序列的符号串编码：遗传算子采用简单的单点交叉和单点变异。对j o b s h o p 调度部分，个体编码是基于所有工序的排列串，采用基于排列的交叉和变异 算子，并利用结合g i f f l e r & t h o m p s o n 算法的过程进行解码，以生成最终的 山东大学硕士学位论文 调度结果。 由于遗传算法理论分析上的困难，以及生产调度问题的复杂性，我们采 用试验的方法来验证算法的有效性。通过和已有结果进行对比，我们的算法 在解的质量上有了一定程度的提高，并且在程序运行时间上也是可以接受的。 最后，提出了应用遗传算法求解生产调度问题需要进一步解决的问题 关键词 遗传算法生产调度加工计划共生进化 山东大学硕士学位论文 a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sas t o c h a s t i cs e a r c ht e c h n i q u ew h i c hs i m u l a t e st h e p r o c e s so fb i o l o g i ce v o l u t i o n g ai sf i tf o rt h el a r g e s c a l e ，c o m p l i c a t e d o p t i m i z e dp r o b l e m sb e c a u s eo ft h ea b i l i t i e so fs e l f - o r g a n i z e d ，s e l f - a d a p t i v e ， s e l f - s t u d ya n dp o p u l a t i o n se v o l u t i o n g ae x p r e s s e st h es o l u t i o nt op r o b l e m sa s t h ep r o c e s so fs u r v i v a lo ft h ef i t t e s t b yt h ee v o l u t i o n a r yp r o c e s s e s ，i n c l u d i n g r e p r o d u c t i o n ，c r o s s o v e ra n dm u t a t i o n ，g ac o n v e r g e n c e st ot h ei n d i v i d u a lt h a t b e s tf i t t e s tt h ec i r c u m s t a n c ea n dt h u sf i n d st h eo p t i m a ls o l u t i o no rs a t i s f y i n g s o l u t i o n w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , g aa t t r a c t sm o r ea n d m o r ea t t e n t i o na n dg e n e t i ca l g o r i t h m sh a v es u c c e s s f u l l y a p p l i e dt om a n y f i e l d ss u c ha sm a c h i n el e a r n i n g ，p a t t e r nr e c o g n i t i o n ，n e u r a ln e t w o r k ，o p t i m a l c o n t r o la n dc o m b i n a t o r i a lo p t i m i z a t i o n p r o d u c t i o ns c h e d u l i n ge x i s t se v e r y w h e r ei nt h er e a lw o r d ，e s p e c i a l l yi nt h e f i e l do fi n d u s t r ya n de n g i n e e r i n g t h ep r o d u c t i o ns c h e d u l i n gp r o b l e m s p u t f o r w a r db ym a n u f a c t u r i n ga r ee s s e n t i a l l ye x t r a o r d i n a r yc o m p l e x i t ya n dt h e s ea r e d i f f i c u l tt os o l v eb yt r a d i t i o n a lo p t i m i z e dm e t h o d s s c h e d u l i n gp r o b l e m sw h i c h r e p r e s e n ta l lt h ec h a r a c t e r i s t i c so fc o n s t r a i n e dc o m b i n a t o r i a lo p t i m i z a t i o nh a v e b e c o m ea p o pt h e m e i nt h ed o m a i no fg e n e t i c a l g o r i t h m s a n da l s o e x e m p l i f i c a t i o n so f t e s t i n gt h ei d e ao f n e wa l g o r i t h m s i nt h i sp a p e rw ei n t r o d u c et h es c h e d u l i n gp r o b l e m su s i n gg e n e t i ca l g o r i t h m w cp r e s e n tas y m b i o t i cg e n e t i ca l g o r i t h mc o m b i n e dw i t hm o d e l sa n dv e r i f yt h e f e a s i b i l i t ya n de f f i c a c yt h r o u 曲l a r g en u m b e r so fe x p e r i m e n t s t h ef i r s ts e c t i o ng i v e st h eo v e r v i e wo fg e n e t i ca l g o r i t h ma n ds c h e d u l i n g t h e o r yr e s p e c t i v e l y t h eb i o l o g i c a lf o u n d a t i o na n dag e n e r a lf r a m e w o r ko fg ai s g i v e n t h ee x c e l l e n e e so fg ac o m p a r ew i t ho t h e rt r a d i t i o n a lm e t h o d s a r e p o i n t e do u t t h eb a s i cp r i n c i p l e ss t u d y , t h ea l g o r i t h m sd e s i g na n dt h ea p p l i c a t i o n f i e l d so fg a sa r es u m m a r i z e d t h e n ，t h eo r i g i n ，d e v e l o p m e n t ，c l a s s i f i c a t i o no f i i i 山东大学硕士学位论文 s c h e d u l i n gp r o b l e m sa n dt h ee x i s t i n gt e c h n i q u e sa n dr e s p e c t i v e l ya d v a n t a g e sa n d d i s a d v a n t a g e sa r ei n t r o d u c e d t h ep r o b l e mt ob es o l v e di nt h i sp a p e ri sp r e s e n t e di nt h es e c o n ds e c t i o n a m o d e lw h i c hc o u l dc o n v e n i e n t l yd e s c r i b et h er e l a t i o n sb e t w e e no p e r a t i o n si nt h e f l e x i b l ej o b s h o ps c h e d u l i n gi sa d o p t e d f o rp r o c e s sp l a n n i n ga n dj o b s h o p s c h e d u l i n ga r eh i g h l yr e l a t e dw i t he a c ho t h e r , w ep u tf o r w a r daf r a m e w o r ko f s y m b i o t i cg e n e t i ca l g o r i t h mb a s e do nt h ei d e ao fc o e v o l u t i o na n dh y b r i d e dw i t ha h e u r i s t i ca p p r o a c h f o rt h ep a r to f p r o c e s s e sp l a n n i n g ，w ea d o p tt h es t r i n gc o d i n g b a s e do nt h em a c h i n ea n ds e l e c t i o ns e q u e n c e a st ot h eg e n e t i co p e r a t o r s ，t h e s i n g l e p o i n tc r o s s o v e ra n ds i n g l em u t a t i o na r ea d o p t e d f o rt h ep a r to fj o b s h o p s c h e d u l i n g ，c r o s s o v e ra n dm u t a t i o no p e r a t o r sa l eb a s e do nt h es e q u e n c e t h e c o d i n gi sb a s e do nt h es e q u e n c eo fa l lo p e r a t i o n so fa l lj o b sa n dt h ed e c o d i n g h y b r i d e dw i t hg i f f i e r & t h o m p s o na l g o r i t h mg e n e r a t e st h ef i n a lr e s u l t w ev e r i f yt h ef e a s i b i l i t ya n de f f i c a c yo ft h ep r o p o s e da l g o r i t h mb yl o t so f e x p e r i m e n t sf o rt h ed i f f i c u l t yo ft h e o r e t i ca n a l y s i sa n dt h ec o m p l e x i t yo ft h e j o b s h o ps c h e d u l i n gp r o b l e m t h ea l g o r i t h mw ep r o p o s e dg e t st h eb e t t e rr e s u l t a n dt h er u n n i n gt i m ei sa c c e p t a b l e af u r t h e rr e s e a r c hi s s u ei sd i s c u s s e da b o u ts o l v i n gt h es c h e d u l i n gp r o b l e m u s i n gg e n e t i ca l g o r i t h m k e y w o r d s g e n e t i ca l g o r i t h m s c h e d u l i n g p r o c e s sp l a n n i n gc o e v o l u t i o n i v 山东大学硕士学位论文 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 杏弓毡 日期：2 堕墨! 生：堕 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留 或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：壅兰塾导师签名 山东大学硕士学位论文 1 前言 自1 9 6 0 年以来，人们对于模拟生物进化以及由此开发的针对复杂优化问 题的有效算法产生了浓厚兴趣。当前在该领域中常常引用的术语就是进化计 算。它包括以下一些主要算法：遗传算法( 由j o h nh o l l a n d 开发【1 】) ，进化策 略( 由r e c h e n b e r g l 2 】和s c h w e f e l l 3 】开发) ，进化规划( 由f o g e l 等人开发f 4 1 ) 和遗传程序设计( 由k o z a 开发【5 】) 。当然还存在若干将上述算法的各种特点 加以结合而形成的混和算法。作为强有力且应用广泛的随机搜索和优化方法， 遗传算法可能是当今影响最广泛的进化计算方法之一，本文将着重介绍遗传 算法在加工计划和生产调度问题中的应用。 在过去的几十年中，人们对调度问题进行了大量的研究工作从上世纪 5 0 年代起，调度问题的研究就受到应用数学、运筹学、工程技术等领域科研 工作者的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划、 动态规划以及决策分析方法，研究并解决了一系列有代表意义的调度和优化 问题。但是，人们普遍把c o n w a y , m a x w e l l 和m i l l e r 三人有关调度的研究工 作【6 】作为调度理论研究的正式开始，他们3 人也被人们称为调度理论的奠基 人。此后3 0 多年的调度理论和应用研究都受到他们的影响。2 0 世纪7 0 年代， 人们开始注意并重视调度复杂性问题的研究，提出了用于研究算法有效性和 问题难度的计算复杂性理论【7 】，许多调度问题被证明为n p 完全问题。 2 0 世纪7 0 年代后期，经典调度理论取得了重要进展，并且作为一门应 用数学学科已经基本成熟，但是实际调度问题与经典调度问题还有相当距离。 人们经常会问到这样的问题：“调度理论的研究成果有多少已经应用到实际调 度问题中，比如敏捷制造、实时系统、c 4 i 、空中管制、自适应容错和机器人 等领域中的调度问题”，这是一个很难回答的问题，因为调度研究的分类常常 是模糊不清的，并且某些调度研究是在很具体的层次上，通用价值很小。有 关调度理论没有在实践中大规模应用的原因有很多说法，一种比较有说服性 的说法是这样的：现有的调度理论和方法对于解决实际调度问题仍然是不够 的，需要重新考虑和进一步扩展恻。当然，严重阻碍经典调度理论研究取得 第1 负 山东大学硕士学位论文 重大进展和突破的关键还是调度问题的n p 性质，实际调度问题往往都是非 常复杂的，没有确定的物理和自然规律可循，因此是非常难解的，并且大多 是没有精确解的。因此，仅仅依靠经典调度理论中基于解析优化的技术和方 法，试图解决属于n p 完全问题的实际调度问题，不可避免地会遇到难以逾 越的障碍。因此，从2 0 世纪8 0 年代初开始，人们就直在尝试并致力于解 决实际调度问题，调度研究由理论研究转向应用研究阶段。在这样的历史背 景下，应用人工智能、计算智能和实时智能的研究成果，解决实际调度问题 的智能调度方法就走上了历史舞台从大量的文献所反映的情况看，智能调 度方法是解决实际调度问题最有效的途径和最有前途的调度方法之一。同时， 基于反馈控制的实时调度算法也初步显示了解决实际调度问题的强大威力， 尽管目前还处于研究的初步阶段，但是随着研究的不断深入和应用的开展， 相信会取得重大的突破性进展因此。可以说。智能调度方法和基于反馈控 制的实时调度理论和方法为解决实际调度问题展示了光明的前景 本文共分四个部分，第一部分主要说明遗传算法的生物学背景及其发展 历史和特点、生产调度的发展历史和研究现状；第二部分主要介绍了对一类 调度模型应用共生遗传算法进行优化，详细叙述了问题的模型和遗传算子的 构造及共生遗传算法框架；第三部分对一组实例运行我们的程序，通过运行 结果说明算法的可行性；第四部分为文章的结束语，总结了本文所做的工作 和下一步应当做的工作 1 1 遗传算法及其研究现状 1 i 1 遗传算法的生物学基础 生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异生命是 进化的产物。现代的生物是在长期进化过程中发展起来的。达尔文( 1 8 5 8 年) 用自然选择来解释物种的起源和生物进化，其自然选择学说包括以 下三个方面： 第2 贞 山东大学硕士学位论文 ( 1 ) 遗传，这是生物的普遍特征。“种瓜得瓜，种豆得豆”，亲代 把生物信息交给子代，子代按照所得信息而发育、分化，因而子代总是 和亲代具有相同或者相似的性状。生物有了这个特征，物种才能稳定存 在。 ( 2 ) 变异，亲代和子代之间以及子代的不同个体之间总有些差异。 这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样 性的根源。 ( 3 ) 生存斗争与适者生存，自然选择来自繁殖过剩和生存斗争。 由于弱肉强食的生存斗争不断进行，其结果是适者生存，具有适应性变 异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的 生存环境的选择作用，物种变异被定向着一个方向积累，于是性状逐渐 和原先的祖先不同，演变为新的物种这种自然选择过程是一个长期的、 缓慢的、连续的过程。 达尔文的进化理论是生物学史上的个重要里程碑，它解释了自然 选择作用下生物的渐变式进化1 8 8 8 年孟德尔发表了“植物杂交试验” 的论文，他提出的遗传学的两个基本规律一一分离律和自由组合律，奠 定了现代遗传学的基础。w a t e rs s u t t o n 发现染色体的行为与基因的 遗传因子行为是平行的，因此提出遗传因子是位于染色体上的。美国遗 传学家t h l o r g a n 进一步确立了染色体的遗传学说，认为遗传性状 是由基因决定的，染色体的变化必然在遗传性状上有所反映。生物的性 状往往不是简单地决定于单个基因，而是不同基因相互作用的结果，基 因表达要求一定的环境条件，同一基因型在不同的环境条件下可以产生 不同的表现型。2 0 世纪2 0 年代以来，随着遗传学的发展，一些科学家 用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论，他 们通过精确地研究种群基因频率由一代到下一代的变化，来阐述自然选 择是如何起作用的，形成现代综合进化论。种群遗传学是以种群为单位 而不是以个体为单位的遗传学，是研究种群中基因的组成及其变化的生 物学。生物的进化实际上是种群的进化，个体总要消亡，但种群则继续 保留，每一代个体基因型的改变会影响种群基因库的组成。而种群基因 第3 贞 山东大学硕士学位论文 库组成的变化就是这一物种的进化，没有所谓的生存斗争问题，单是个 体繁殖机会的差异也能造成后代遗传组成的改变，自然选择也能够进 行。综合进化论对达尔文式的进化给予了新的更加精确的解释。 生物进化非常复杂i 现有的进化理论所不能解释的问题比已经解释 的问题还要多。除了达尔文的渐变进化外，人们又提出了很多新的非达 尔文式进化理论，如木村资生的分子进化中性理论、g o l d s c h m i d t 的跳 跃进化、n e 1 d r e d g e 的间断平衡进化等。随着生物学的前沿领域一一 生物物理、分子生物学和生物化学的发展，关于生物进化的理论仍在发 展之中，但是以自然选择为核心的进化理论比其他学说的影响广泛而深 远，它仍然是各种生物进化理论的一个重要基础。 1 1 2 遗传算法的简单框架 1 9 7 5 年，美国密歇根大学的心理学教授、电子工程学与计算机科 学教授j o h nh o l l a n d 和他的同事与学生共同研究了具有开创意义的遗 传算法理论和方法。遗传算法是一种借鉴生物界自然选择和进化机制发 展起来的高度并行，随机、自适应搜索算法遗传算法基于自然选择的 生物进化，是一种模仿生物进化过程的随机方法，它是从代表问题可能 潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目 的个体组成。每个个体实际上是染色体带有特征的实体染色体作为遗 传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某 种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染 色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现 从表现型到基因型的映射即编码工作。初代种群产生以后，按照适者生 存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代， 根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传 算子进行组合交叉和变异，产生出代表新的解集的种群这个过程将导 致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群 中的最优个体经过解码，可以作为问题的近似最优解 第4 负 山东大学硕士学位论文 一般认为，遗传算法由5 个基本组成部分( 由m i c h a l e w i c z 归纳) ： 1 问题的解的遗传表示 2 创建解的初始种群的方法 3 根据个体适应值对其进行优劣判定的评价函数 4 用来改变复制过程中产生的子个体遗传组成的遗传算子 5 遗传算法的参数 遗传算法维持由一群个体组成的种群p ( t ) ( t 代表遗传代数) 。每 一个体均代表问题的一个潜在的解。每一个体都被评价优劣并得到其适 应值。某些个体要经历称作遗传操作的随机变换，由此产生新的个体 主要有两种变换方法：变异的方法是将一个个体改变从而获得新的个 体；杂交的方法是将两个个体的有关部分组合起来形成新的个体新产 生的个体( 称作后代o f f s p r i n g ，c ( t ) ) 继续被评价优劣从父代种群 和子代种群中选择比较优秀的个体就形成了新的种群。在若干代以后， 算法收敛到一个最优个体，该个体很有可能代表着问题的最优或次优 解遗传算法的一般结构可以描述如下： 遗传算法过程 b e g i n t ：= 0 初始化p ( t ) 评价p ( t ) w h i l e ( 终止条件不满足) d o b e g i n 重组p ( t ) 以产生c ( t ) 评价c ( t ) 从p ( t ) 和c ( t ) 中选择p ( t + i ) t ：2t+l e n d e n d 关于搜索策略存在两种重要方案：深度搜索最优解和广度搜索解空 第5 页 山东大学硕士学位论文 间遗传算法提供了一种在复杂解空间上进行有向随机搜索的方法遗 传算子原则上进行的是盲目搜索；选择算子则有可能将遗传搜索的方向 引导到解空间的理想区域中。针对特定现实世界中问题开发的遗传算法 需要注意这样一条普遍原则，即要在对解空间进行深度搜索和广度搜索 中维持很好的平衡。 1 1 3 遗传算法的特点 相对于其他优化算法，遗传算法的主要优点是： ( 1 ) 以优化变量的遗传编码为运算、搜索对象。传统的优化算法 往往直接利用优化变量的实际值本身进行优化计算，但是遗传算法不是 直接以原优化变量的值，而是以优化变量的某种形式的遗传编码为运算 对象。这种对优化变量的编码处理方式使得我们在优化计算过程中可以 借鉴生物学中染色体和基因等概念，可以模仿自然界中生物进化机制与 遗传变异原理，也使得我们可以方便地应用遗传、进化等操作算子另 外，对一些非数值概念或很难用数值概念而只能用代码的优化问题( 这 类问题称为非数值优化问题) ，遗传算法的这种处理方式显示其独特的 优越性。 ( 2 ) 只应用适应值信息，而不一定需要应用目标函数的具体值及 其他辅助信息。传统优化算法不仅依赖于直接应用目标函数的具体值， 而且也往往需要应用目标函数的导数值等其他一些辅助信息来确定搜 索方向。而遗传算法通常仅仅使用目标函数变换来的适应值指导搜索。 注意到，评价个体的适应度可以不依赖于目标函数的恰好估值( 例如只 知道排序关系) ，这使得遗传算法不仅可以方便地应用于那些有目标函 数的但是很难求导数，或者导数根本不存在的优化问题( 特别地，组合 优化问题与非光滑优化问题) ，而且更重要地，可应用于那些目标函数 无明确表达或者有表达但不可精确估值的优化问题。 ( 3 ) 非单点操作。使用群体搜索策略传统优化算法往往是从解 空间中的一个初始点出发的单点迭代，从而形成解空间中的一条轨迹。 第6 贝 山东大学硕士学位论文 单个点所提供的搜索信息毕竟不多，因而搜索效率不高，有时甚至使得 搜索过程陷于局部极值而停滞不前。遗传算法是从由多个个体所组成的 初始种群的种群空间中的迭代过程，从而形成个体空间中的多条轨迹， 其搜索过程的每一步利用了种群中各个体所提供的信息。这些信息可以 避免一些不必要搜索的点或者区域，从而既提高了搜索效率，也更大程 度上避免了陷于局部极值另外，遗传算法的群体搜索机制使其具有自 然的并行性，从而适宜于在当代或未来以分布、并行为特征的智能计算 机上发挥潜能。 ( 4 ) 使用概率搜索机制。很多传统优化算法使用的是确定性的搜 索方法，一个搜索点到另外一个搜索点的转移有确定的转移关系，这种 确定性使得算法的搜索具有定向性，从而很难达到问题的全局最优解， 而且数值稳定性不好。遗传算法在计算的各个步骤使用概率转移规则， 因而是一类导向的随机搜索技术特别是，其选择、繁殖( 交叉、变异 等) 操作都是以一种概率的方式进行的，采用的是“软”选择与“让步 策略”，它能以一定概率接收不一定好的个体，从而大大提高了算法跳 出局部极值陷阱的能力另外，概率搜索机制的一个自然优点是相应算 法的稳健性，遗传算法同样具备。 以上优点决定了遗传算法的适用范围应该是复杂、困难的全局优化 问题，而不是通常的数值优化问题。一个优化问题称为是复杂的，通常 指它具有下述特征之一： 一 ( 1 ) 目标函数没有明确解析表达，如非数值优化问题； ( 2 ) 目标函数虽有明确表达，但不可能恰好估值，如大部分最优 控制问题、金融优化问题) ； ( 3 ) 目标函数有极多的峰值，如d n a 计算、组合优化问题； ( 4 ) 多目标问题。 另一方面，我们必须注意到，一个通用而又较少依赖于目标函数值 与其他辅助信息的算法不可能比专用且充分利用目标函数及相关辅助 信息的算法更为有效，而当一个问题有某些辅助信息可供利用时，舍弃 应用本来可供应用的新奇而去应用与这些信息无关的算法也不是一个 第7 页 山东大学硕士学位论文 聪明的选择。所以遗传算法一般说并不适宜于应用到通常的数值优化问 题( 例如连续可微的数学规划问题) 。 1 1 4 遗传算法的研究情况 遗传算法的理论基础研究主要集中于对搜索机理、收敛性、收敛速 度、复杂性、有效性，能解性等基本理论问题的探索，其目的在于从理 论上阐明遗传算法的工作原理与性态，从而为遗传算法技术的发展、比 较与应用提供理论依据。7 h o l l a n d 教授本人提出了模式定理，以及由此所派生的积木块假设 与隐含并行性分析。模式定理、积木块假设与隐含并行性一起构成遗 传算法所谓的模式理论这一理论长期被接收为遗传算法的基本理论， 特别地，模式定理与积木块假设常被用于解释遗传算法的搜索机制，而 隐含并行性被用以解释遗传算法的有效性然而遗憾的是，除模式定理 外，模式理论中的大部分结论都未得到阉割的数学证明，而且在一定意 义上也是似是而非的陈述。所以，用以解释遗传算法的搜索机制与有效 性，模式理论难以令人信服，由此引出的大量有关遗传算法欺骗问题的 研究从一个侧面说明了这一点而徐宗本等人关于遗传算法搜索能力的 研究，建立在严密的数学理论之基础上，而且它不仅清晰的刻画了各个 遗传算子的搜索能力，也刻画了各个遗传算子的合作机制。关于遗传算 法的收敛性研究，研究方法和所用的数学工具可分为4 类n 们1 ：马尔 可夫链模型、v o s e l i e p i n s 模型，公理化模型与连续( 积分算子) 模 型。关于遗传算法的有效性与能解性的研究，目前尚无理论结果 在遗传算法设计方面，h o l l a n d 教授最初应用生物遗传和进化的思 想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在 研究和设计人工自适应系统时，可以借鉴生物机制，以群体的方式进行 自适应搜索；他的思想被他的学生b a g i e y ( 1 9 6 7 年) 在其博士论文中 具体化和系统首次提出了“遗传算法一一词，并发展了复制、交叉、变 异、显性等遗传算子，在个体编码上使用了双倍体的类生物编码方式。 第8 页 山东大学硕士学位论文 1 9 7 5 年，d el o n g 首次将遗传算法应用于函数优化，并建立起了目前为 人们所熟悉的遗传算法工作框架。此后，以优化问题为背景，遗传算法 的各种改进与推广层出不穷，最典型的例如：g o l d b e r g 等的混乱遗传 算法“”，s c h r a u d o l p h 和b e l e w 的动态参数编码遗传算法】，e s h e i m a a 和s c h a f f e r 的实编码遗传算法“”，d a v i s 的混合遗传算法1 ，p o t t e r 和d ej o n g 的合作共存演化遗传算法“”，m a t h i a s 和w h i t l e y 的6 编码 遗传算法“”，t s u z s u i 的分岔遗传算法“耵等等。这些改进与推广的遗传 算法或从模拟特定的生物进化机制，或从改进现有遗传算法性态的意义 上发展和丰富了遗传算法的执行策略。 从开拓遗传算法的应用领域角度，近年来人们特别注重发展对于多 目标优化，多态优化与各种组合问题的遗传算法执行策略。基于对种群 小生境进化的模拟和采用适应值共享策略，g o l d b e r g 、r i c h a r d s o n 和一 d e b 等发展了一系列有效的多目标优化问题遗传算法n ”。这些算法已经 充分显示出较传统多目标优化算法的优越性与有效性。对于这种各样的 组合问题，如t s p 问题，m d r 问题，最大独立集问题等等，通过耦合与 问题相关的启发式信息，已经发展出非常有效的混和遗传算法执行策 略。 对本文将要解决的生产调度问题，在很多情况下所建立起来的数学 模型难以精确求解，甚至模型的建立本身就是一件困难的事情。即使经 过一些简化之后可以求解，也会因简化太多而使得求解结果与实际相差 甚远。由于可采用符号编码，而且不一定必须使用恰好的目标函数估值， 遗传算法也称为解决复杂调度问题的有效工具。 1 2 生产调度及其研究现状 在过去几十年间，人们主要从应用数学的角度来研究调度问题，调 度问题通常被定义为“分配一组资源来执行一组任务”，也就是“排序”。 在生产调度中，就可以这样来描述调度问题1 ：“在某一时间期限内分 配一组机器来执行生产订单任务”针对当前先进制造模式，可以把生 第9 贞 山东大学硕士学位论文 产调度定义得更详细一些：“生产调度是针对一项可分解的生产任务， 探讨在尽可能满足约束条件( 如交货期、工艺线路和资源情况等) 的前 提下，通过下达生产指令，安排其组成部分( 操作) 使用哪些资源、其 加工时间及加工顺序，以获得生产任务执行时间或成本的最优化”。 1 2 1 生产调度的分类 生产调度问题的分类方法很多，主要有以下几种： ( 1 ) 根据加工系统的复杂度，生产调度可分为单机调度、j o b - s h o p 调度、f l o w - s h o p 调度、多机器并行加工调度等几个基本类型。单机调 度是指所有的操作任务都在台机器上完成，需要对任务进行优化排 队；j o b - s h o p 调度是最一般的调度类型，它是指由m 个不同的机器加 工1 1 个有特定加工路线( 顺序) 的工件，不同工件的工序间没有顺序约 束，工序加工不能中断；f l o w - s h o p 调度假设所有工件都在相同的设备 上加工，并有一致的加工操作和加工顺序；多机器并行加工调度是指多 台机器并行加工工件，而且并行加工的机器和工件都是类似的而实际 的调度问题通常是上述几种调度类型的组合 ( 2 ) 根据优化准则，可以分为基于代价和性能的调度两大类代 价包括为了实现调度方案所消耗的各种费用和所造成的损失，如运行费 用、运输费用、存储费用和延期交货损失等性能主要包括设备利用率、 最大完成时间、拖延加工任务的百分比等虽然在理论分析上，大部分 只注意调度的性能，但在实际生产中，通常要综合考虑代价和性能两方 面因素 ( 3 ) 根据生产环境的特点，可将调度分为确定性调度和随机性调 度。前者是指加工时间和其他参数是已知的、确定的量；而后者的加工 时间和有关参数是随机的变量。 ( 4 ) 根据加工任务或被加工工件的特征，可将调度分为静态调度 和动态调度。静态调度是指所有待安排加工的工件均处于待加工状态， 因而进行一次调度后，各作业的加工被确定，在以后的加工过程中就不 第】o 贞 山东大学硕士学位论文 再改变；动态调度是指作业依次进入待加工状态，各种作业不断进入系 统接受加工，同时完成加工的作业又不断离开，还要考虑作业环境中不 断出现的不可预测的动态扰动，如作业的加工超时、设备的损坏等。 实际的生产调度问题往往是由j o b - s h o p 和f 1 0 w s h o p 型等基本调 度类型组合而成，基于代价且是随机的、动态的。下文将详细描述本文 将解决的问题模型。 1 2 2 生产调度方法介绍 在对调度问题进行研究的方法上，最初是集中在数学规划、仿真和 简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的调度 问题。随着各种新的相关学科与优化技术的建立与发展，在调度领域出 现了许多新的优化方法，比如基于人工智能、计算智能和实时智能的各 种调度方法，这些方法已经成为调度方法的主流 ( 1 ) 数学规划方法 数学规划方法是一种运筹学方法，它将生产调度问题简化为数学规 划模型，采用整数规划、动态规划以及决策分析，等方法来解决调度最优 化或近似优化问题，也称为优化调度方法。生产调度中广泛使用的是混 合整数线性规划和混合整数非线性规划方法。数学规划方法的优点是任 务分配和排序的全局性比较好，所有的选择同时进行，因此可以保证求 解凸和非凸闯题的全局优化。但是，数学规划方法是种精确求解方法， 它需要对调度问题进行统一的建模，任何参数的变化会使得算法的重用 性很差，因此，对于复杂多变的生产调度来说，单一的数学规划模型不 能覆盖所有的因素，存在求解空间大和计算困难等问题。 ( 2 ) 启发式搜索方法 启发式搜索方法最初是作为人工智能中问题求解程序的搜索器而 被开发出来的。启发式搜索方法依靠任务无关信息来简化搜索过程，在 很多情况下，问题求解可视为系统化地构造或查找解答的过程。启发式 搜索方法的优点是利用了面向特定问蹶的知识和经验。因而可以产生好 第页 山东大学硕士学位论文 的解决方案，求解时间也可以接受。启发式搜索方法的缺点是用来评估 解决方案的质量手段还较少，如何提高搜索效率并减少内存使用以解决 规模较大的问题，还需要进一步探索。 ( 3 ) 系统仿真方法 基于仿真的方法不单纯追求系统的数学模型，它侧重于对系统中运 行的逻辑关系的描述，而且与数学规划采用全局的而且经常是简化的视 图相比，它对所有分配、排序和时间选择决策的结果提供局部的分析， 通过分析能够对生产调度方案进行比较评价，并选择效果最优的生产调 度方法和系统动态参数系统仿真方法经常与其他方法结合使用。由于 生产系统的复杂性，很难用一个精确的解析模型来进行描述和分析，而 通过运行仿真模型来收集数据，则能对实际系统进行性能和状态等方面 的分析，从而能对系统采用合适的控制调度方法之所以把仿真方法与 其他方法结合使用，是因为纯仿真方法有以下局限性：应用仿真方法进 行生产调度的费用很高，不仅在于产生调度的计算时间上，而且在于设 计、建立和运行仿真模型上；仿真的准确性受人员的判断和技巧的限制， 甚至很高精度的仿真模型也无法保证通过实验总能找到最优或次优的 调度。 ( 4 ) 智能调度专家系统 专家系统在2 0 世纪8 0 年代早期和中期非常流行，它在许多领域也 得到了应用。如果要建立一个专家系统，首先需要构建相关的知识库， 就是从知识源获取知识然后以数字化形式存储它们，在调度问题中，知 识源一般指的是人类专家和模拟数据调度专家系统主要的优点有：在 决策过程中，它既可以使用定量的知识，又可以使用定性的知识：它能 够产生比简单的分配规则复杂得多的启发式规则然而，调度专家系统 也有其不可克服的缺点：构建和验证系统比较耗费时间；难以维护和升 级；求解结果可能会严重偏离最优解或次优解；知识获取和推理速度存 在瓶颈。 ( 5 ) 约束规划 。约束规划是一种旨在应用限制变量选取顺序和变量赋值顺序来减 第1 2 贝 山东大学硕士学位论文 少搜索空间有效大小的方法。当一个值赋给一个变量时，产生的不一致 性就消除了消除不一致性的过程称做一致性检测，而消除以前做的工 作称做回溯。约束规划可以用来实施柔性的和有效的调度系统，因为它 把各种不同的算法包装成传播器，使得可以对可重用的求解器进行规 划。约束规划不局限于一定的约束集合，因为它使用了一个纯声明的模 型，每一个传播器定义问题的一个独立视图但是这一方法的求解代价 比较大，而且由于考虑了多种约束，求解难度很大。 ( 6 ) 基于多代理系统m a s 的方法 专家系统很难用来解决大规模的复杂的实际调度问题，因为它们的 知识和问题求解能力是有限的。为了解决这些复杂问题，研究人员使用 “分而治之”的方法来开发分布式调度系统，这需要一种分解调度问题 的技术以及能够协作求解整个问题的相关的知识系统的集合。这些可以 通过多代理系统( m u l t i _ a g e n ts y s t e m ，m a s ) 来实现。m a s 是一种从问 题的局部概念模型出发，通过由底向上的方式形成的一种分布式人工智 能系统，该系统的基本单元是相对独立的代理，各个代理之间的关系类 似于社会系统中不同利益实体之间的关系，即有协作，又可能有竞争甚 至冲突因此，m a s 研究的是一组在逻辑上或物理上分离的代理之间行 为的协调，包括它们对知识、目标、技巧和规划等通过彼此之间的联合 共同完成比较复杂的任务。不仅可以处理单一目标的问题，也可以处理 多目标问题。由于m a s 在问题求解方面的潜力，它很适合于复杂生产调 度与制造系统优化问题的研究。m a s 技术可以弥补调度理论的不足，可 以增强调度理论在实际应用中的灵活性；m a s 可以和其他各种生产控制 技术如企业资源计划( e n t e r p r i s er e s o u r c e sp l a n n i n g ) 、最优生产技 术( o p t i m iz e d p r o d u c t i o n t e c h n o l o g y ) 和制造执行系统 ( m a n u f a c t u r i n ge