（计算机应用技术专业论文）基于免疫遗传算法的车间调度问题研究.pdf

基于免疫遗传算法的车间调度问题研究 中文摘要 中文摘要 车间调度问题是被许多专家学者广泛关注的焦点问题，遗传算法是目前解决该问 题常用的优化算法，本文在对提高遗传算法的优化效率等方面进行研究的基础上，提 出一种改进的免疫遗传算法，并将此算法应用到了金属加工车间求解调度问题中。本 文的研究主要包括以下四个方面： ( 1 ) 针对车间调度问题描述、车间调度目标等存在问题，研究将遗传算法应用 于车间调度问题中。实验表明，遗传算法应用在车间调度问题中比其它算法更有优越 性。 ( 2 ) 针对基本免疫算法在解决多目标优化上存在的问题，在基于信息熵的人工 免疫算法的基础上引入小生境技术，提出改进的免疫遗传算法。通过多峰函数优化证 明，改进的算法有更好的收敛速度和全局搜索能力。 ( 3 ) 通过对一个金属加工车间进行数学模型分析、设计优化函数，将改进的算 法应用到实际车间调度参数设计中。实验表明，该算法是可行和高效的。 ( 4 ) 基于改进的免疫遗传算法，设计实现了金属加工车间调度系统仿真平台。 实验结果表明，改进算法比传统算法得到更优的调度解。 关键词：遗传算法，免疫遗传算法，多目标优化，车间作业调度 作者：杨道文 指导老师：刘全( 教授) a b s t r a c t j o b - s h o ps c h e d u l i n gp r o b l e mi st h ew i d e s p r e a dc o n c e r n e dp r o b l e mb ym a n ye x p e l s a n ds c h o l a r s g e n e t i ca l g o r i t h mi st h ec o m m o n l yu s e do p t i m i z a t i o na l g o r i t h mt os o l v et h i s p r o b l e m b a s e do nt h es t u d yo fe n h a n c i n gt h eo p t i m i z i n ge f f i c i e n c yo fg e n e t i ca l g o r i t h m ， t h i sp a p e rp r o p o s e da ni m p r o v e di m m u n eg e n e t i ca l g o r i t h m a n dt h i si m p r o v e da l g o r i t h m w i l lb ea p p l i e dt os o l v i n gs c h e d u l i n gp r o b l e m so fam e t a lp r o c e s s i n gw o r k s h o p t h i s p a p e r i n c l u d e st h ef o l l o w i n gf o u ra s p e c t s ： i f o rt h ej o b s h o ps c h e d u l i n gp r o b l e md e s c r i p t i o na n dj o b - s h o ps c h e d u l i n gp r o b l e m s ， g e n e t i ca l g o r i t h mi sa p p l i e dt oj o b - s h o ps c h e d u l i n gp r o b l e m s e x p e r i m e n t a lr e s u l t ss h o w t h a tg e n e t i ca l g o r i t h m sa p p l i e dt oj o b - s h o ps c h e d u l i n gp r o b l e m sa r em o r ea d v a n t a g e st h a n o t h e ra l g o r i t h m s i i f o rb a s i ci m l t l u n ea l g o r i t h mi ns o l v i n gm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s ， p r o p o s ea ni m p r o v e di m m u n eg e n e t i ca l g o r i t h mb a s e do ni n f o r m a t i o ne n t r o p ya r t i f i c i a l i m m u n ea l g o r i t h ma n di n t r o d u c t i o no fn i c h et e c h n o l o g y t h r o u g hm u l t i m o d a lf u n c t i o n o p t i m i z a t i o ns h o w st h a tt h ei m p r o v e da l g o r i t h mh a sb e t t e rc o n v e r g e n c es p e e da n dg l o b a l s e a r c hc a p a b i l i t i e s n 1 t h r o u g ha n a l y s i sm a t h e m a t i c a lm o d e ld e s i g no p t i m i z a t i o nf u n c t i o nf o ram e t a l p r o c e s s i n gw o r k s h o p ，t h ei m p r o v e da l g o r i t h mi sa p p l i e dt od e s i g nt h ep a r a m e t e ro ft h e a c t u a lj o b - s h o ps c h e d u l i n g e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mi sf e a s i b l ea n de f f i c i e n t i v b a s e do nt h ei m p r o v e di n m l u n eg e n e t i ca l g o r i t h m , d e s i g n sa n di m p l e m e n t sam e t a l p r o c e s s i n gs h o ps c h e d u l i n gs y s t e ms i m u l a t i o np l a t f o r m t h ee x p e r i m e n t a lr e s u l t ss h o w t h a t , t h ei m p r o v e da l g o r i t h mi sb e t t e rt h a nt h et r a d i t i o n a lm e t h o di ng e t t i n gs c h e d u l e r s o l u t i o n k e y w o r d s ：g e n e t i ca l g o r i t h m ，i m m u n eg e n e t i ca l g o r i t h m ，m u l t i - o b j e c t i v eo p t i m i z a t i o n , j o b - s h o ps c h e d u l i n gp r o b l e m w r i t t e nb y ：y a n gd a o w e n s u p e r v i s e db y ：l i uq u a n 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：勃亟耋 日期：型盟。包f 垦 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：杨豇 导师签名： 日期：掣! ! 垒笪 基于免疫遗传算法的车问调度问题研究第一章引言 第一章引言 1 1 研究背景及研究意义 1 1 1 研究背景 随着世界进入信息化时代，制造业所处的环境不断改变，大多数企业的生产模式 已由过去的大批量生产转化为单件小批生产，市场竞争的日趋激烈，客户需求多样化 的发展，企业上层生产计划管理受市场影响越来越大，明显感到计划跟不上变化。制 造企业面对客户对交货期的苛刻要求，面对更多产品的改型，订单的不断调整，企业 如何运用有限的资源，快速响应客户需求，降低产品的生产成本，保证按时交货，赢 得更多客户，成为制造业在竞争中生存的一个重要条件。 车间调度是制造系统生产管理的核心，生产管理任务顺利实施与完成，最终要靠 合理的车间调度来保证。近2 0 年来，国际生产工程学会曾总结了4 0 种先进的制造模 式，无论哪一种模式都是以优化的生产调度为基础【l 】。车间调度研究的是如何合理配 置加工过程的各种资源，减少零件的加工准备、等待与传送时间，从而提高设备利用 率与生产效率，降低生产成本。车间调度对任务的交货时间、各项生产任务的生产周 期、设备利用率和在制品占用量都有影响。因此，及时准确的车间调度对生产系统的 高效运行有着重要的影响，主要表现在车间调度可以保证：生产计划的有效实施；高 效低耗地使用生产资源；均衡生产，减少在制品的资金占用。总之，车间调度对于提 高产品质量、降低成本、提高效率、快速响应市场需求等生产管理的各个方面都起着 至关重要的作用。所以，车间调度是制造业生产中最活跃和生产系统研究的前沿问题 之一。 在理论研究中，车间调度问题被称为排序问题、资源分配问题、组合优化问题。 由于车间调度具有动态随机性、计算复杂性的特点，至今尚未出现一套系统的方法和 理论。在调度问题的理论研究中，大多数还是集中在针对经典的调度问题设计优化算 法，而经典调度问题与实际相差较大，因此需要探讨建立符合车间实际情况的调度模 型。由于大多调度问题属于一类n p 困难组合问题，因此寻找最优算法几乎是不可能 的。在过去的几十年里，基于实际的及理论上的考虑，不断地激励着人们寻找新的调 l 第一章引言 基于免疫遗传算法的车间调度问题研究 度算法。车间的调度优化工作，因其在提高生产效率，降低生产成本等方面所起的重 要作用，己成为生产领域研究的热点，有效的调度方法与优化技术的研究，对于先进 制造企业的现代化具有重要的理论意义和实用价值。 1 1 2 研究意义 车间生产调度是制造系统的基础，生产调度的优化是先进制造技术和现代管理技 术的核心技术。研究作业车间调度问题，寻求先进的作业车间调度算法，具有较大的 理论意义和实际意义，主要表现在： ( 1 ) 理论意义 目前调度问题的理论研究中，大多数还是集中在针对经典的调度问题设计优化算 法，而经典调度问题与实际相差较大。经典调度问题大多是基于无限能力的，只考虑 了工艺路线和资源独占两类约束，而未考虑能力约束，这样得到的调度方案与实际不 相符，使得许多调度方案不可行，研究有限能力作业车间调度模型，能有效解决经典 作业车间调度问题的缺陷，促进调度理论的发展。同时，调度问题属于n p 难题，遗 传算法因其操作简单，通用性强，且具有隐含并行性和全局解空间搜索能力，为调度 问题的解决提供了方法，但传统遗传算法存在一定的缺陷，将其他算法的优点引入遗 传算法中，能提高遗传算法的性能，使其更好的求解调度问题，得到合理的调度方案， 同时也为其他领域类似问题的解决提供方法借鉴【2 】。 ( 2 ) 实际意义 针对单件小批生产企业生产特点，合理的调度模型和先进的调度算法，使企业能 快速的制定准确的调度方案，合理配置加工过程的各种资源，使零件的加工准备、等 待与传送时间减少，提高设备利用率与生产效率，提高企业准时交货率使企业能够按 时完成计划。 综上所述，对车间生产作业调度问题的理论研究将对调度理论体系的完善与企业 竞争力的提升有着重要的理论与现实意义。 1 2 国内外研究现状 1 2 1 车间作业调度的国内外研究现状 车间作业调度问题是一个传统问题，对它的研究开始于2 0 世纪5 0 年代。早在 2 基于免疫遗传算法的车间调度问题研究第一章引言 1 9 5 4 年，s m j o h n s o n 对两台机床的f l o ws h o p 型调度问题进行了研究【3 】，提出了 n 2 f c m a x 和部分特殊的n 3 f c m a x 问题的求解方法，代表着调度理论研究的开始。 6 0 至7 0 年代，建立了经典调度理论，人们开始了对算法复杂性的研究，多数调度问 题被证明属于n p 完全问题或n p 难问题，难以找到多项式算法，因此人们开始关注 启发式算法。到7 0 年代末，经典调度理论趋向成熟。 由于调度问题是制造系统中最基本、最重要的问题之一，是生产管理的核心问题 和关键技术，因此国内外大量的学者对其进行了广泛的探讨和研究。随着调度理论研 究的深入及各种交叉学科的发展，又涌现出许多新的车间调度的理论和方法。如确定 性最优化方法、基于规则和基于知识的调度方法、仿真调度方法、神经网络优化法、 基于d e d s 的解析模型方法、拉氏松弛法、以及基于模糊数学理论的方法等。近年来， 用模拟退火算法( s i m u l m e da n n e f l i n g ，s a ) 、禁忌搜索算法( t a b us e a r c h ，t s ) 、 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 、免疫蚁群算法( i m m u n ea n tc o l o n y a l g o r i t h m ) 和遗传算法( g e n e t i ca l g o r i t h m ， g a ) 等智能方法解决车间作业调度问 题受到人们的高度关注。 文献 4 】将遗传算法与模拟退火算法结合在一起，对分批作业的调度问题进行了 研究。文献 5 利用遗传算法与模拟退火法相结合的混合遗传算法对分布式车间作业 调度进行了研究。文献 6 j e f f e o a t 和b u l f m 应用模拟退火法解决资源受制约的调度问 题。文献 7 】采用了并行禁忌搜索法以加快搜索进度，提高效率。文献 8 】在求解车间 作业调度问题时，将遗传算法和禁忌搜索法相结合，提出了一种基于禁忌搜索算法和 遗传算法的混合算法。文献 9 】提出了一种基于约束满足的自适应神经网络方法求解 车间作业调度问题。文献【1 0 】对基于免疫蚁群算法的车间作业调度问题进行了研究。 由于各种车间作业调度的算法都存在着不同程度的优缺点，所以近年来人们开始 将各种算法组合起来进行研究，以扬长避短，达到优化调度的目的。文献【1 1 】研究了 遗传算法和禁忌搜索算法及它们的混合策略在车间调度优化问题中的应用现状。文献 【1 2 】研究了基于仿真和遗传算法的车间调度优化方法，并通过实验说明了该集成优化 方法的有效性。文献 1 3 】结合启发式算法和遗传算法的特点，提出了混合优化调度的 方法，建立了多资源约束的车间优化调度模型。 总体上说，经典调度理论仍是调度理论的基石，但智能调度理论已在迅速发展并 趋于成熟。可以预测，在不久的将来，智能调度理论必将取代传统调度理论，二者的 3 第一章引言基于免疫遗传算法的车间调度问题研究 结合也是一种趋势。 1 2 2 遗传算法的国内外研究现状 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是1 9 7 5 年由美国m i c h i g a n 大学的j h o l l a n d 教授等人受生物进化论的启发而提出的。g a 以生物进化过程为背景，模拟生物进化 的步骤，将繁殖、杂交、变异、竞争和选择等概念引入到算法中。通过维持一组可行 解，并通过对可行解的重新组合，改进可行解在多维空间内的移动轨迹或趋向，最终 走向最优解【1 4 1 【1 5 】。它克服了传统优化方法容易陷入局部极值的缺点，是一种全局优 化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因 的作用，有效地利用已有信息来指导搜索有希望优化质量的状态。 遗传算法在调度领域中己经得到了比较广泛的应用，特别是九十年代以来，国内 外学者发表了大量应用遗传算法解决调度问题的文章【l 争1 8 】。几乎每一种调度问题都有 人用遗传算法求解，因此可以认为遗传算法的适用性是比较好的。 遗传算法的有效性一般与其选择的相关参数有关。如文献 1 9 1 q h 设计的f l o ws h o p 得到了满意的效果。文献 2 0 1 q b 用遗传算法研究模糊加工时间单机r t 调度问题，发 现使用不同的遗传因子，算法的有效性也有一定差异。另一方面，不同的迭代次数对 相对于不同的遗传因子得到的结果也不同。文献【2 1 】提出了一种两机成组作业流水车 间优化调度的遗传算法，该遗传算法分两层：一层优化组内作业排序，一层优化组排 序。文献 2 2 】中用遗传算法研究了具有柔性加工路径的作业车间的智能优化调度问 题，提出了一种将遗传算法和分派规则相结合的调度算法，将加工计划与生产调度同 时考虑，避免了加工计划和生产调度相脱节的弊端。文献 2 3 】中设计了一种调度遗传 算法用于任务类型相同的多个项目在多个虚拟车间的调度问题。文献 2 4 1 q b 通过对遗 传算法关键因素的讨论，研究了s f s d s s 设计的优化方法。文献 2 5 用遗传算法研究 了含机器人的作业车间双资源调度优化问题，提出了一种将遗传算法和分派规则相结 合的调度算法，将加工机床和机器人合理地分配给加工任务，使评价指标获得最优。 遗传算法的主要任务和目的，是设法产生或有助于产生优良的个体成员，且这些 成员能够充分表现出解空间中的解，从而使算法效率提高并避免早熟收敛现象。但是， 实际应用遗传算法时，往往出现早熟收敛和收敛性能差等缺点。因为遗传算法是一类 基于“产生+ 测试 方式的迭代搜索算法，尽管算法在一定条件具有全局收敛性，但 4 基于免疫遗传算法的车间调度问题研究第一章引言 算法的交叉、变异、选择等操作一般都是在概率意义下随机进行的，虽然保证了种群 的群体进化，但一定程度上不可避免退化现象的出现。此外，尽管遗传算法具有通用 性的一面，但却忽视了问题特征信息的辅助作用，同时相对固定的遗传操作使得对不 同问题的求解缺少灵活性。大量研究表明，仅仅依赖于以遗传算法为代表的进化算法 在模拟人类智能化处理事务能力方面还远远不足，还需要更深入地挖掘和利用人类的 智能资源，而免疫遗传算法就是将生命科学中免疫的原理与遗传算法相结合来提高算 法的整体性能并有选择、有目的的利用待求解问题中的一些特征信息来抑制优化过程 中退化现象的出现。 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 ) 调度问题，即使得工件尽量按交货期完成，变得越来 越突出。由于市场需求的多样性，多品种、小批量成为一种主流的生产方式。j i t 的 目标是消除一切可以消除的浪费现象，以使得多品种小批量的生产方式下达到低成 本。 从目前的研究来看，车间调度要形成一套系统的方法和理论还有一些困难，因为 大多数研究在建模时对实际环境进行了一些简化，还不能很好地应用于实际生产中。 另外，实际的生产过程是一个动态生产的过程，即实际生产系统中存在着很多不确定 的变化，如加工设备的故障造成的环境变化，变动的市场需求带来的任务变化，以及 任务变化导致的生产目标的变化等。所以，实际的调度应该是动态调度，仅在静态调 度的基础上解决问题很难取得最好的效果。 现有的调度算法大多是在经典调度理论的基础上进行研究的，而经典调度理论与 实际情况有一定的差距，尤其是在目前的柔性车间制造环境下。在实际车间生产调度 中，车间计划与车间调度往往是分层进行的，这可能会产生调度计划在实际调度中不 可行的情况。如何将计划与实际调度结合考虑，以获得总体的优化也是需要考虑的。 在多数调度方案中，对于评价指标的选取通常采用生产周期、平均流动时间等时 间指标。尽管这些指标在一定程度上反映了调度方案的优劣，但他们并不是管理人员 5 第一章引言基于免疫遗传算法的车间调度问题研究 真正关心的问题，如产品的收益、总生产成本、库存费用、工件拖期损失等。而作业 调度的最终目的，应该是选择一个能给车间生产带来最大经济利益的方案。 1 3 本文的研究内容 随着当今世界经济环境变化和用户要求不断的提高，在制造领域存在着一种强烈 的需求：低成本、高质量的提供更加客户个性化的产品。为了满足这个要求，本文在 总结了遗传算法在车间调度中的应用状况之后，提出了一种基于免疫遗传算法的新的 优化算法，并用实际车间数据进行了验证，结果表明该算法在作业车间调度中能有效 地提高调度的效率，加快了进度，不失为一种好的算法。 本文的主要研究内容包括以下几个方面： ( 1 ) 针对车间调度问题描述、车间调度目标等存的在问题，研究了车间调度问题 的分类及发展趋势，并研究了经典遗传算法在车间调度中的应用问题。 ( 2 ) 研究了基本的免疫遗传算法的框架和流程，在分析其在具体操作中一些不足 的基础上，提出了改进的免疫遗传算法，通过对多峰函数进行优化，验证了改进的免 疫遗传算法较之人工免疫算法和遗传算法有着更好的收敛速度和全局搜索能力。 ( 3 ) 将改进的免疫遗传算法应用到实际车间调度参数设计中，仿真实现了金属加 工车间的调度系统。基于改进算法，通过对一个金属加工车间进行了参数分析，建立 数学模型，设计开发了了一个金属加工车间的调度系统。经过试验结果分析得出，改 进的算法比传统算法得到更优的调度解。 1 4 本文的组织结构 本文的研究内容分为以下六章： 第l 章介绍了车间调度问题的历史背景及研究意义。主要阐述了遗传算法应用 在车间调度问题应用现状及存在问题，并给出了本文的研究内容和结构安排。 第2 章主要介绍基础理论。首先介绍了遗传算法基础理论，主要包括遗传算法 的概念及原理、遗传算法的基本操作、遗传算法流程、遗传算法的特点及缺陷。然后 介绍了人工免疫算法，主要包括免疫算法的免疫学原理、免疫算法基本操作及流程。 最后对免疫算法和遗传算法进行比较。 6 基于免疫遗传算法的车间调度问题研究第一章引言 第3 章主要介绍了车间调度问题。首先介绍了车间作业调度问题概述，主要包 括车间调度问题描述、车间调度目标、车间调度问题特点及分类。然后介绍了车间调 度问题的研究方法及研究发展趋势。最后介绍了经典遗传算法在车间调度中的应用问 题。 第4 章在遗传算法和免疫算法的基础上，改进免疫遗传算法。首先总结了前面 的遗传算法和人工免疫算法在处理多目标优化问题方而各自的特点，提出了免疫遗传 算法处理多目标优化问题。然后介绍了基本的免疫遗传算法的框架和流程，在分析其 在具体操作中一些不足的基础上，提出了改进的免疫遗传算法，其在适应度方而采用 n s g a 中的适应度赋值方式，在相似性方而采用抗体间欧式距离方法来计算，并且引 入浓度来调节聚合适应度以及交叉和变异算子，保证了种群的多样性，具有更好的全 局搜索能力，应用记忆细胞保留最优抗体。最后通过对实际的多峰函数进行优化，验 证了改进的免疫遗传算法较之人工免疫算法和遗传算法有着更好的收敛速度和全局 搜索能力。 第5 章本章将所改进的免疫遗传算法应用到实际车间调度问题中，仿真实现了 一个金属加工车间的调度系统。首先对一个金属加工车间进行了参数分析，建立其数 学模型。然后将改进的算法应用到车间调度系统参数中，在v b 6 0 开发环境下，仿真 实现了一个金属加工车间的调度系统。最后经过试验结果分析得出，改进的算法比传 统算法得到更优的调度解。 第6 章对本文工作进行总结和对以后工作的展望。 7 第二章理论基础 基于免疫遗传算法的车间调度问题研究 2 , 1 遗传算法 2 1 1 遗传算法简介 第二章理论基础 根据达尔文的进化论，生物种群从低级、简单的类型逐渐发展成为高级、复杂的 类型。各种生物要生存下去就必须进行生存斗争，具有较强生存能力的生物个体容易 存活下来，并有较多的机会产生后代：具有较低生存能力的个体则被淘汰，或者产生 后代的机会越来越少，直至消亡。这种现象被称之为“物竞天择，适者生存”。这一 关于生物进化的研究结论，已得到广泛的接受和应用。 按照m e n d e l 和m o r g a n 的遗传学理论，遗传物质是作为一种指令密码封装在每 个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某 些特性。生物体所表现出来的外在特征是对其染色体构成的一种体现。生物的进化本 质体现在染色体的改变和改进上，生物体自身形态的变化是染色体结构变化的表现形 式。通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣态的自然选择， 适应值越高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论， 揭示了遗传与变异的基本规律。 自然界的生物进化是一个不断循环的过程。在这一过程中，生物群体不断的完善 和发展。生物进化过程本质上是一个优化过程，在计算科学上具有直接的借鉴意义。 通过计算机模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域，这是遗 传算法( g e n e t i ca l g o r i t h m 简称g a ) 模拟自然进化的计算方法的思想源泉。 遗传算法是借鉴生物界“适者生存”原则的一种优化算法。生命是进化的产物， 其基本特征包括生长、繁殖、新陈代谢和遗传与变异。达尔文用自然选择( n a t u r a l s e l e c t i o n ) 来解释物种的起源和生物的进化，其自然选择学说包括以下三方面陶： ( 1 ) 遗传( h e r e d i t y ) 这是生物的普遍特征，“种瓜得瓜，种豆得豆 ，亲代把生物信息交给子代，子代 按照所得信息而发育、分化，因而子代总是和亲代具有相同或相似的性状。生物具有 了这个特征，物种才能稳定存在。 g 基于免疫遗传算法的车间调度问题研究第二章理论基础 ( 2 ) 变异( v a r i a t i o n ) 亲代和子代之间以及子代的不同个体之间总有些差异，这种现象称为变异。变异 是随机发生的，变异的选择和积累是生命多样性的根源。 ( 3 ) 生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行，其结 果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰， 通过一代代的生存环境的选择作用，物种变异向着一个方向积累，于是性状逐渐和原 先的祖先种不同，演变为新的物种。这种自然选择过程是一个长期的、缓慢的、连续 的过程。 既然遗传算法是基于自然选择的生物进化，是一种模仿生物进化过程的随机方 法。故而在该算法中要用到生物遗传学的知识，下面给出几个在遗传算法中很重要的 基本概念和术语【2 7 】： ( 1 ) 染色体( c h r o m o s o m e ) 遗传物质的主要载体，有多个遗传因子一一基因组成，在算法中为解的编码( 字 符串，向量等) 。 ( 2 ) 基因( g e n e ) d n a 或r n a 长链结构中占有一定位置的基本遗传单位，在算法中为解中每一分 量的特征( 如各分量的值) 。 ( 3 ) 个体( i n d i v i d u a l ) 指染色体带有特征的实体，在算法中为解。 ( 4 ) 适应度( f i m e s s ) 表示某一个体对于环境的适应程度，在算法中为适应函数值。 ( 5 ) 种群( p o p u l a t i o n ) 染色体带有特征的个体的集合，该集合内个体数称为群体的大小，在算法中为选 定的一组解( 其中解的个数为群体的规模) 。 ( 6 ) 复制( r e p r o d u c t i o n ) 细胞在分裂时，遗传物质d n a 通过复制而转移到新产生的细胞中，新的细胞就 继承了旧细胞的基因，在算法中为根据适应函数值选取的一组解。 ( 7 ) 交叉( c r o s s o v e r ) 9 第二章理论基础 基于免疫遗传算法的车间调度问题研究 有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组，亦即在两个 染色体的某一相同位置处d n a 被切断，其前后两串分别交叉组合形成两个新的染色 体。这个过程又称基因重组r e c o m b i n a t i o n ，俗称“杂交 ，在算法中为通过交配原则 产生一组新解的过程。 ( 8 ) 变异( m u t a t i o n ) 在细胞进行复制时可能以很小的概率产生某些复制差错，从而使d n a 发生某种 变异，产生新的染色体，这些新的染色体表现出新的性状，在算法中表现为编码的某 一个分量发生变化的过程。 2 1 2 遗传算法的基本操作 在实际应用中，针对具体问题的遗传算法都有很大程度的改进，但每种遗传算法 的实现都涉及5 个主要因素：个体编码、初始群体的生成、适应度函数、遗传操作和 控制参数的设定口引。这些要素构成了遗传算法的核心内容，下面给以简要介绍。 ( 1 ) 个体编码 用遗传算法求解问题时，是对表示可行解的个体编码实施遗传操作，而非对实际 变量决策，因此必须在目标问题实际表示与遗传算法的染色体位串结构之间建立联 系，即确定编码和解码运算。编码是利用遗传算法求解问题的第一步，它的策略或方 法对于交叉和变异算子的功能和设计有很大影响。 比较常用的有二进制编码、实数编码、符号编码、树编码、自适应编码、乱序编 码等。 d e j o n g 按照遗传算法的模式定理，提出了两条基本的编码评估准则： a ) 有意义积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低 阶的积木块。 b ) 最小字符集编码规则：所定编码应采用最小字符集以使问题得到自然的表示 或描述。 但这些仅是编码方案的一个指导性原则，并不总是适用。因此在处理实际问题时， 仍必须对编码方法、遗传运算方法、解码方法等综合考虑，确定描述最为方便、运算 效率最高的编码方案。 ( 2 ) 初始群体的生成 1 0 基于免疫遗传算法的车间调度问题研究第二章理论基础 遗传操作是对众多个体同时进行的，这众多的个体组成了群体。在遗传算法处理 流程中，继编码设计后的任务是初始群体的设定，并以此为起点一代代进化直到按某 种进化停止准则终止进化过程，由此得到最后一代。 初始群体设计时首先要解决的问题是群体规模大小。根据模式定理，若群体规模 为n ，则遗传操作可从n 个个体中生成和检测n 3 个模式，并不断在此基础上形成和 优化积木块，直到找到最优解。从这个角度讲，应该是群体规模越大，得到最优解的 概率就越高，但是群体规模太大不可避免地会降低遗传算法的速度，而群体规模太小 则会限制遗传算法的搜索空间，引起早熟现象的发生。初始群体如何设定，群体规模 如何，对于遗传算法效能的发挥有着重要的影响。 ( 3 ) 适应度函数 遗传算法在进化搜索中基本上不用外部信息，仅以目标函数即适应度函数为依 据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数 的唯一要求是针对输入可计算出加以比较的非负结果。这一特点使得遗传算法的应用 范围很广。 在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。需要特别强 调的是，适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的 性能。 ( 4 ) 遗传操作 遗传算法中遗传操作包括选择、交叉、变异三个基本遗传算子，它模拟了生物基 因的遗传过程。三个遗传算子的操作都是在随机扰动情况下进行的，但它们都是高效 有向的搜索而不是一般随机搜索方法所进行的无向搜索。 a ) 选择算子 选择算子就是把适应度高的优秀个体直接遗传到下一代或通过交叉产生新的个 体再遗传到下一代，主要目的是为了避免基因的丢失，提高全局收敛性和计算效率。 目前常用的选择算子有适应度比例方法、最佳个体保存方法、排序选择方法、联 赛选择方法等多种。 b ) 交叉算子 在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样，遗传算法 中起核心作用的是遗传操作的交叉算子。交叉是指把两个父代个体的部分结构加以替 1 1 第二章理论基础 基于免疫遗传算法的车间调度问题研究 换重组而生成新个体的操作。交叉算子使遗传算法的搜索能力得以飞跃提高。 实际应用中，交叉算子的设计要综合所研究的问题与个体编码统一考虑。如编码 为二进制编码，可采用单点交叉、多点交叉、一致交叉等多种算子；而编码若为实数 编码，则需要采用点式交叉、离散交叉和多种数值型交叉。 c ) 变异算子 变异算子的基本内容是对群体中个体串的某些基因座上的基因值作变动。遗传算 法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力；二是使遗传算 法可维持群体多样性，以防止出现未成熟收敛现象。遗传算法中，交叉算子因其全局 搜索能力而作为主要算子，变异算子因其局部搜索能力而成为辅助算子。 变异算子可以包括基本变异算子、逆转算子、自适应变异算子、边界值变异算子、 均匀一致变异算子、非均匀一致变异算子和变步长变异算子等多种。 ( 5 ) 控制参数的设定 在遗传算法运行的整个过程中，存在着影响其性能的一组参数。这组参数在初始 阶段和群体进化过程中都需要进行合理的选择和控制，从而使遗传算法以最好的搜索 轨迹达到问题最优解。主要参数包括如下四项： a ) 群体规模n 群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模较小 时，遗传算法的运算速度快，但降低了群体的多样性，易引起遗传算法的早熟现象； 而当群体规模较大时，群体中含有较多模式，改善搜索质量，但又极大地增加了运算 旦 亘0 b ) 交叉概率p 。 交叉是遗传算法中产生新个体的主要方法。交叉概率较大时可增强遗传算法开辟 新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大；相反，交叉概率太低， 遗传算法可能陷入搜索迟钝状态。 c ) 变异概率p m 变异的主要目的是维持解群体的多样性。一般情况下，较低的变异概率可防止群 体中重要的、单一基因的可能丢失，较高的变异概率将使遗传算法趋于纯粹的随机搜 索。 d ) 终止代数g 1 2 基于免疫遗传算法的车间调度问题研究 第二章理论基础 g 是表示遗传算法运行结束的一个参数，当算法运行到第g 代时就会停止，并 将当前群体中的最佳个体作为所求问题的最优解输出。 2 1 3 遗传算法流程 遗传算法采纳了自然进化模型，如选择，交叉，变异等等。标准遗传算法的流程 如图2 1 所示： 图2 1 遗传算法流程图 步骤l ：构造满足约束条件的染色体。由于遗传算法不能直接处理解空间中的解， 所以必须通过编码将解表示成适当的染色体。实际问题的染色体有多种编码方法，染 色体编码方式的选择应尽可能的符合问题约束否则将影响计算效率。 步骤2 ：随机产生初始群体。初始群体是搜索开始时的一组染色体，其数量应适 当选择。 1 3 第二章理论基础基于免疫遗传算法的车间调度问题研究 步骤3 ：计算每个染色体的适应度。适应度是反映染色体优劣的唯一指标，遗传 算法就是要寻得适应度最大的染色体。 步骤4 ：使用复制、交叉和变异算子产生子群体。这二个算子是遗传算法的基本 算子，其中复制体现了优胜劣汰的自然规律，交叉体现了有性繁殖的思想，变异体现 了进化过程中的基因突变。 步骤5 ：若满足终止条件，则输出搜索结果：否则返回步骤3 。 2 1 4 遗传算法特点及缺陷 ( 1 ) 遗传算法的特点 遗传算法是一个利用随机化技术来指导对一个被编码的参数空间进行高效搜索 的方法，遗传算法具有十分顽强的鲁棒性，与传统的搜索方法不同，它采用了许多独 特的方法和技术，归纳起来主要有以下几个方面： 幻遗传算法处理对象不是函数本身，而是对参数进行编码的个体，此编码操作， 使得遗传算法可直接对结构对象进行操作。所谓结构对象泛指集合，序列，矩阵，树， 图，链表等各种一维或二维甚至三维结构形成的对象，这一特点使得遗传算法具有广 泛的应用领域。 ”许多传统搜索算法都是单点搜索算法，对于多峰分布的搜索搜索空间，常常 会陷入局部的某个单峰的优解，而遗传算法是采用同时处理群体中多个个体的方法， 即同时对搜索空间中的多个解进行评估，更形象的说，遗传算法是并行的爬多个峰。 这一特点使得遗传算法具有较好的全局搜索性能和良好的全局收敛性能。减少了陷入 局部最优解的风险，同时这使遗传算法也十分易于并行化处理。 c ) 在标准遗传算法中，基本上不用搜索空间的知识或其它辅助信息，而仅用适 应度函数来评估个体，并在此基础上进行遗传操作，尤其是适应度函数不受连续性和 可微性的约束，而且定义域也可以任意设定，对适应度函数唯一的要求是，对于输入 可计算出用于比较的非负结果，这一特点使得遗传算法应用范围极为广 ( 2 ) 遗传算法存在的问题 众多的应用实践表明了遗传算法是一个性能优良的算法，但是传统的遗传算法有 两个严重的缺点： a ) 容易过早收敛 1 4 基于免疫遗传算法的车间调度问题研究 第二章理论基础 造成这样的原因有两个。其一，在实际的应用当中，在进化群体之中，会有少数 个体的适应度函数值远大于其它个体，这样经过少数迭代后，这些个体的后代就占据 了整个群体，这样，进化过程就提前收敛了。其一，传统的遗传算法，个体间的竞争 只在自了代中进行，而了代与父代之间没有竞争，这样父代中的优良个体有可能丢失， 一些算法直接将父代中的优良个体复制到了代群体中来保存最优解。这样也容易造成 过早收敛。 b ) 在进化后期搜索效率较低 当遗传算法进化至最优解附近时，因为其交叉操作寻优范围较大，很容易跳过最 优解，从而造成后期搜索效率较低。而目交叉操作还有一个致命的弱点，它容易破坏 已经搜索到的最优解，从而降低后期的搜索效率。 这些缺陷都限制了遗传算法更加广泛的应用。因此，研究如何改进遗传算法，采 用合适的算法加快寻优速度和改善寻优质量，无论在理论上还是在实践上都有重要意 义。 2 2 人工免疫算法 2 2 1 生物学免疫原理 免疫是指生物体接触抗原性异物( 如各种微生物、细胞、病毒) 后，能产生一种 特异的生理反应，其作用可排除异物保护机体。它是生物机体的一种生理反应，当抗 原性异物进入生物机体后，生物机体能识别“自己”和“非己 ，并发生特异性的免 疫应答，排除抗原性的非己物质【2 引。 人工免疫算法是根据免疫系统原理特性，抽象出用于工程应用领域的算法。根据 构成系统中各个元素的关系，可以分为基于群体的免疫算法和基于网络的免疫算法。 构成基于群体的免疫算法的元素之间存在间接联系，同时与环境相互作用；基于网络 的免疫算法同免疫模型密切相关，其中部分甚至全体的系统元素都能相互作用。基于 群体的免疫算法依据免疫学不同机制又可以分为3 类，第一类是参照免疫系统抗体和 抗原识别、结合抗体产生过程而抽象出来的一般免疫算法，这是最基本的免疫机制的 算法，目前应用最多；第二类是基于免疫系统中其他特殊机制抽象的算法，如基于克 隆选择原理的克隆选择算法；第三类是与其他计算智能融合产生的新算法，如免疫进 1 5 第二章理论基础基于免疫遗传算法的车间调度问题研究 化算法。如果把实际求解问题的目标函数视为外来入侵的抗原，问题的多个峰值视为 不同的抗原决定簇，免疫响应中产生的抗体视为问题的解，则不同亲和度抗体的进化 与成熟机制就是寻找目标函数多个峰值的过程。 以下是标准人工免疫算法的几个重要元素【3 0 】： ( 1 ) 信息熵 在人工免疫算法中，表征群体多样性的是群体的平均信息熵，群体的平均信息熵 越大，说明群体多样性越大，故又称为基于信息熵的人工免疫算法。抗体基因的信息 熵如图2 2 所示： 0123 j m 抗体- 工工工1 丑 抗体2 抗体n 图2 2 抗体基因的信息熵 其中：设共有n 个抗体，每个抗体用一个位串来表示，在算法设计中规定每个 位串的长度为m ，即表示每个抗体由m 位基因组成。抗体中用来表示基因的可供选 择的字母共有s 个： k l ，k 2 ，k s 。如当抗体采用二进制编码时，则表示可 供选择的抗体基因的字母有两个为： 0 ，1 ) 。则这n 个抗体的信息熵如式2 1 所示： h ( ) - 去善q ( ) ( 2 - 1 ) 其中，h j ( ) = - p 万l o g p 可，q ( ) 为n 个体抗体第j 位的信息熵，乃 为n 个体抗体中第j 位基因为字母k z 的频率。 ( 2 ) 亲和度 亲和度表征免疫细胞与抗原的结合强度，亲和度越高，免疫细胞与抗原的结合力 越强，说明免疫细胞质量越好。亲和度相当于遗传算法中的适应度，它的好坏直接影 响着算法的收敛速度。抗体和抗体之间的亲和力反映抗体的相似程度，当亲和力比较 基于免疫遗传算法的车间调度问题研究第二章理论基础 大时，抗体就越相似，反之，则相似程度较差。采用下列公式计算抗体。抗体u ， v 间的亲合度，也即抗体u 和v 的相似度如式2 2 所示： 1 = 丽 2 2 q w 的取值介于0 和1 之间，等于1 时表明抗体u 和抗体v 是完全相同的，当 q u v 趋于0 时，表明抗体u 与v 之间几乎完全不相似。 其中，k ( 2 ) = 击孝表示两个抗体u 和v 的信息熵，m 表示抗体基因的长 度，抗原和抗体之间的适