（管理科学与工程专业论文）遗传算法在马钢车轮公司排产优化中的应用.pdf

遗传算法在马钢车轮公司排产优化中的应用 摘要 本论文讨论了遗传算法在生产优化过程中的应用，分为钢锭配切和排产优化 两部分。 钢锭配切部分首先简单介绍了马钢公司目前配切情况，并分析了配切问题的 模型；接着讨论了配尺的概念和两种配尺算法；最后总结了常用的配切方法( 运 筹学方法、启发式算法、动态规划法等) ，分析了它们各自的优缺点，并在此基 础上提出了一种编码方法，并用遗传算法对轮箍进行配切。 排产优化部分，介绍了轮箍厂排产现状和存在的问题，讨论了排产问题的难 度所在；分析和比较了目前常用的排产方法( 运筹学方法、基于规则的方法、系 统仿真的方法、基于排序的方法) ；讨论了怎样用遗传算法进行生产排产，并具 体说明了这种遗传算法的编码方法和解码过程。 最后对本论文所介绍的配切和排产算法，用v c + + 进行了编程实现。 关键词：遗传算法装箱问题作业调度问题 t h e a p p l i c a t i o no f g e n e t i ca l g o r i t h mi nw h e e la n d 珂ep l a n to f m as t e e lc o l t d j o b s h o ps c h e d u l i n g0 p t i m i z a t i o n a b s t r a c t t m sp 印e ri sa b o u th o wt oo p t i n l i z ep r o d u c t i o np r o c e s s 、i t l lg e n e t i ca l g o r i t h m ， i ti n c l u d e ss t e e lc u t t i n ga n ds c h e d u l i n go p t i m i z i n g i n t h ep a r to fs t e e lc u n i n g ，w ei n t r o d u c et h en o wc u t t i n gs i t u a t i o no ft h e m a g a i l gc o m p a i l ya i l da j l a l y z e t l ：l em o d e lo ft h ec 毗i n gp r o b l e m ；t h ec o n c 印to f n j l e r - c r e a t i n ga n d 觚om l e r - c r e a t i n gm e t h o da r ea r g u e d ；w ea l s os u m m a r ys o m e c o i m o nm e t h o d so fc u t t i n g ( o p e r a t i o n a lr e s e a r c ha l g o r i t l l m ，h e u r i s t i ca l g o r i t l m l ， d y n 锄i cp r o 伊a n m i n g ，e t c ) ，a i l da n a l y z e 也ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e m ， b a s i n go ni tw ep u tf o r 、眦do n ec o d i n gm e t l l o d ，a n dc u ts t e e l 埘mg e n e t i ca 1 9 0 r i m m i nt l l ep a r to fo p t i m a ls c h e d u l i n g ，w ei n t r o d u c et h ep r e s e n ts i t u a t i o na j l dp r o b l e m o f j o bs c h e d u l i n g ，a i l dt 1 1 ed i 伍c u l t yo fi t ，c o n l p a r ea 1 1 da n a l y z et l l ec o n u n o nm e t h o d s o fi tw ea l s oa 玛u eh o wt os c h e d u l ew i t hg e n e t i ca l g o r i t h m ，a 1 1 di n t e 印r e tt l l ee n c o d e a n dd i s c o e do fi t f i n a j l y ，w ew i t ev cp r o g r 锄st oc u ta n ds c h d u l e k e y w o r d ：g e n e t i ca l g o r i t h m ，b i n p a c k i n gp r o b l e m ，j o b s h o ps c h e d u li n g 图目录 图2 1 轮箍的加工流程图5 图2 2 机器安排6 图2 3 不同产品工艺时间不同6 图3 1 遗传算法流程图9 图4 1 钢锭图一1 8 图5 1 按工件方式甘特图一2 4 图5 2 按机器方式甘特图2 4 图5 3 甘特图2 7 图5 4 遗传算法生成的工件甘特图2 9 图5 5 遗传算法生成的机器甘特图一2 9 图6 1 配尺表3 0 图6 2 自动生成的配尺表3 l 图6 3 定单选择31 图6 4 配尺方案3 2 图6 5 配尺方案选择3 2 挖拍拍勰捣 一 ： 一 一 | | 一 ； 录 一 ： 一 一 一 目 一 一 一 表 较 比 表表的表表工间案器间加时 方机时器工 切工工机加配加加的的同件件序序不工工工工 1 1 2 3 4 禾孓孓孓孓表表表表表 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金月巴王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 桓避签字日期：蝣e 月切日 学位论文版权使用授权书 本学位论文作者完全了解金月巴工些态堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金艘 王业太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 钽咯 签字日期：1 泖拜名月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 钿卜 签字醐川睥6 月7 日 电话： 邮编： 致谢 本人在三年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得到 了我的导师刘心报教授的悉心指导，无论从课程学习、论文选题，还是到收集资 料、论文成稿，都倾注了刘心报老师的心血，由衷感谢刘心报老师在学业指导及 各方面所给予我的关心以及从言传身教中学到的为人品质和道德情操，刘老师广 博的学识、严谨的治学作风、诲人不倦的教育情怀和对事业的忠诚，必将使我终 身受益，并激励我勇往直前。 同时，真诚感谢杨善林校长、刘林老师，炮院王金山老师，他们的教诲为本 文的研究提供了理论基础，并创造了许多必要条件和学习机会；感谢叶强、经怀 明、吴谊胜、方宇、陈继超、蒋甜甜、唐亚伟、刘蓉同学在我课程学习、做课题 和论文撰写期间，给予我的大力帮助。 第一章绪论 1 1 本文的研究背景 本文是在课题“马钢股份有限公司车轮轮箍分公司生产毛坯配切及排产方 案优化模型”的基础上进一步研究的，主要研究模型的建立、求解及实现。 马钢股份有限公司车轮轮箍分公司是我国生产火车整体碾钢车轮和轮箍的 特大型企业，公司坐落在安徽省马鞍山市南麓、闻名遐迩的采石矶畔，始建于 1 9 6 1 年，1 9 6 4 年全面建成投产。本公司经营销售车轮、轮箍环件、轮件、盘件、 锻件六大系列产品，品种规格达2 0 0 0 多种。产品覆盖面涵及铁路机车车辆、机 械、化工、石油、纺织、冶金、矿山、航天、港口、地铁等行业。公司经营销 售6 0 0 一2 0 1 0 m m 直径的铁路机车用轮箍；7 2 4 1 0 9 8m m 直径的铁路客、货车辆、 冶金、矿山、地铁车辆用车轮；6 0 0 2 5 0 0 m m 直径的机械、化工、石油、纺织、 航天等行业用的各种断面环件；5 5 0 - 1 0 0 0 m m 直径的起重、港口用轮件； 1 2 0 4 0 0 m m 直径的锻件。公司除经营销售上述六大类产品外，还可根据客商的 要求，按i s 0 、a a r 、u i c 、b s 、j i s 等标准生产销售各种规格的产品。 由于每次的订单所要求的品种规格都在几百种以上，要把众多种类的待加 工产品进行优化排序，按照生产流程合理分配到各个生产部门，在保证均衡生 产的前提下，使各个部门的设备利用率达到最高，同时使得仓储费用、辅助材 料费用等加工费用达到最低。要做到这一点，仅靠经验是完全不可能的，必须 借助于数学手段，建立适当的数学模型并设计可靠的算法，求出最优方案，才 能较好地解决这个问题。 本文的研究工作主要包括加工毛坯的配切及生产方案的优化两个部分。具 体地说，对2 0 0 0 多种规格的数据进行分析、处理和论证；找出影响该系统的诸 多原因以及这些原因之间的内在联系；分析该系统的内部机理，在此基础上进 行抽象、概括和归纳，进而做出合理的假设并明确变量；确定目标函数，找出 变量之间所要满足的约束条件，进而写出明确的数学模型；在对模型进行详细 分析的基础上，对模型进行合理地简化；制定切实可行的算法，并通过计算机 求出模型的解：利用计算机模拟的方法分析材料的利用率和模型的稳定性：最 后编制成易于操作的计算机软件。 本文给出的配切和排产最优方案可以大大地提高原材料的利用率，降低生 产成本，提高生产效率。同时利用本文的成果可以提高企业的技术含量以及信 息化管理水平，为企业今后进一步的技术改造打下一个良好的基础。 息化管理水平，为企业今后进一步的技术改造打下一个良好的基础。 1 2 国内外研究状况 生产调度理论方法研究是非常复杂的课题，但它的研究对企业提高生产效 率和效益是至关重要的，特别是在当前市场经济时代。 生产调度理论和方法的研究已经有5 0 多年的历史，目前对生产调度理论与 实践的研究受到了广泛的重视，也取得了很快的进展，但是经典调度理论和实 际调度问题之间仍然存在着很大的差距。实践的需求和理论方法研究上的不平 衡促进了生产调度的研究和开发的进展1 2 j 。 生产调度问题的研究，国外要早于国内，而且更多的是基于生产实践，就 一般调度方法而言，就有g a n t t 图法，构造型法，动态规划法，。分支定界法，排 队论法，规则调度法和仿真法等。由于多数调度问题都属于n p 难题，目标解 的搜索涉及解空间的组合爆炸，普通的方法只能处理小规模的问题。而且调度 问题有约束性，非线性，不确定性，大规模性，多目标性等复杂性，于是研究 和发展了统计式全局搜索技术和人工智能的方法，如模拟退火，遗传算法，禁 忌搜索，神经网络方法等优化算法口】i ”。 调度中的大部分问题都属于n p 难题，虽然对它们的研究已有很多年的历 史，但至今还没有形成一套系统的方法和理论，理论研究与实际应用之间还存 在着非常大的差距。尤其随着j i t ( j u s t i n t i m e ) 思想的广泛采用，即使得工件 尽量按交货期完成，变得越来越突出。实际应用中的调度方法能够响应系统的 动态变化，但不能保证得到好的调度：一些理论上的最优化方法能提供最优调 度，但由于其计算的复杂性，并且忽略了很多实际因素，离实际运用还有较大 距离。基于最优化的方法，诸如动态规划算法与分枝定界法等等，由于其大多 数是建立在对可能调度的部分枚举上，因此只能解决小规模的调度问题，距离 实用还有较大距离。 正因为如此，寻找最优方案几乎是不可能的。各种近似、启发式方法，如 基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应 用于实际调度中，但所得的调度解往往不是较优的。在这方面有必要探索更好 的近似最优调度算法，可以考虑增加合理的计算时间代价，提高解的性能。各 种基于统计优化的方法，如模拟退火法、遗传算法等，提供了一种解决调度优 化问题的新途径，但同别的优化算法类似，其也存在着一定程度的差距、一般 来说收敛到最优解很慢，并且对于判断解的最优性也很困难。在这方面也需要 做进一步的研究。 在实际车间调度中，车间计划与车间调度往往是分层进行的，但这可能造 成计划在实际调度中的不可行问题，如何将计划与调度结合考虑，以求总体的 优化也是需要进一步研究的。另外，还有很多有待进一步研究的问题，比如实 际车间调度的多目标性等。调度理论、方法与应用的研究是一项非常艰巨的工 作，目前人们还在进行各种各样的探索性研究工作。 1 3 本文研究的意义 随着企业的不断发展，生产能力日益扩大，产品品种和涉及的生产经营行 业越来越多，当客户订货的品种不断增加、批量不断减少、交货期不断变短时， 快速成长中的制造企业面临的最大威胁不是市场竞争，而是制造企业自己。如 何提高对愈来愈苛刻的客户需求的反应速度? 如何在确保速度的同时保证产品 质量? 如何在保证速度、质量的同时降低产品成本? 成为企业一项艰巨而现实 的项目【1 】。 提高订单反应速度，客户需求不断发生变化，主要表现在：订单不断增加 及个性化需求导致产品品种增加而单笔定单的数量减少；交货期越来越短，企 业恨不得扩大产能，满足供货，趁机迅速占据更多的市场份额，使得全体员工 都在疲于奔命，企业内部组织、规范、流程建设早已无暇顾及；由于过分追求 产能，质量问题开始出现，成本意识逐渐淡薄：更糟糕的是，大量的原材料、 半成品、产成品使库存急剧膨胀，资金周转出现危机。要在生产能力范围内， 要求不断变化的情况下，提高订单的速度【lj 。 提高排产效率、使瓶颈工序得到充分利用：生产计划排程的目的是为车间生 成一个详细的短期生产计划。排产计划( p r o d u c t i o ns c h e d u l e ) 指明了计划范围 内的每一个定单在所需资源上的加工开始时间和结束时间，也即指出了在给定 资源上定单的加工工序。排产计划的计划间隔可以从一天到几周，取决于具体 的工业生产部门。合理的计划长度取决于几个因素：一方面，它至少应当涵盖 与一个定单在生产单元中最大的流动时间相对应的时间间隔；另一方面，计划 间隔受到已知顾客定单或可靠需求预测的可用性限制。很显然，只有当排产计 划适度稳定时，在一个资源上进行定单排产才是有用的。也就是说，它们不应 受不期望事件经常变化的影响( 如定单数量改变或中断) 。 对某些生产类型，生产计划排程需要对瓶颈资源上的任务定单进行排序和 计划；而对另一些生产类型，生产计划排程要能自动地、按时段检查资源组的 能力，看其是否能够在下一个时间段内完成成组加工的一组定单。然后，可以 手工排序这组定单在下一个时间段内的加工次序。 生产计划排程受到上层主生产计划的约束，主生产计划设立了在分散的决 策单位中执行生产计划排程的框架。从主计划中可获得的相应指导包括：使用 超时或加班的数量：在不同时间点上来自供应链上设施物料项的可用性；涉及 来自供应商输入物料的采购协议。 要合理安排各主要工序，体现出相互衔接，充分提高关键工序的利用率。 要均衡安排劳动力，以提高工效和有利于充分有效地利用机械设备，减少机械 设备占用周期。有利于资金流动，降低流动资金占用量，节省资金利息。 对紧急情况的处理：生产过程中随时会出现的各种质量异常、设备异常、 停机待料、停机待物等各种问题。在异常事件发生时，要根据设备的当前状态， 进行设备调度，减小计划，并在可能的情况下，均衡设备负荷。 1 4 本文内容的结构安排 第一章为绪论部分，简单介绍了本文的研究背景、国内外研究状况、和研 究意义。 第二章介绍了排产和配切的关系、排产问题的难度所在、常用的排产方法， 以及目前马钢轮箍厂的排产情况。 第三章介绍了基本遗传算法、遗传算法的实现技术，以及改进遗传算法。 第四章写了配切问题的模型、圆台配尺方法、常用的几种配切算法，并介 绍了怎样甩遗传算法进行配切。 第五章写了怎么用遗传算法进行排产，还介绍了遗传算法的编码和解码算 法。 第六章介绍了配切和排产算法的程序实现方法。 4 第二章排产问题及其现状 2 1 排产问题和轮箍配切的关系 车轮和轮箍加工的主要流程包括：配切、加热、粗轧、成型、校圆、热处 理、等温、精加工等，如图2 1 。 图2l 轮箍的加工流程图 粗 加 工 轮箍配切问题是排产的一个环节，但因为轮箍配切用的是圆台形钢锭，加 上数量少批量多，配切起来比较复杂，如果配切得不好，还会产生很大的浪费， 所以我们把配切问题从整个排产过程中分开来单独讨论。 2 2 排产问题的复杂性 机器安排复杂，由于生产产品数量多工序复杂；每个机器的生产能力、 加工产品类型都各不相同；一台机器同一时间只能加工一个产品，但不同时间 可以加工不同类产品，要合理安排各产品的各工序什么时间在什么机器上加工， 对排产的效率非常重要。要适应安排各产品加工顺序，错开各产品在各机器上 加工时间，减少机器的等待时间，提高机器的使用效率非常重要，当机器和产 品数量很多时就会非常复杂，如图2 2 。 工序1工序2工序3；工序4 图2 2 机器安排 瓶颈工序复杂，生产排产的一个目标就是要找到生产线中的瓶颈工序， 充分利用瓶颈工序上的设备，从而提高整个生产线的效率。但是要在实际生产 排产中找瓶颈工序非常复杂。因为同一条流水线生产不同的产品瓶颈可能不同， 即时生产同一批产品生产顺序不同瓶颈工序也可能不同。如图2 3 ，可能生产产 品1 时机器1 是瓶颈，生产产品2 时机器2 是瓶颈。 机器1 i机器2 产品1 丽r 1 哥 产品2 仁三至三卜正二j 团一 图23 小j 司产晶工艺时间不i 司 加工顺序安排复杂，在实际排产过程中各产品生产顺序的安排也很复杂。 安排得好会节约成本提高效率。如：加热时加热温度接近的产品尽量放在一起， 这样可以减少换产品时的等待时间，也可以节省燃料：轧制时尺寸接近的产品 尽量放在一起，这样可以减少换模具时间。 n p 问题，作业调度问题是一个典型的n p 问题，这类问题在规模比较小 的情况下结果数目不多，可以用穷举法得到最优的结果：而在问题规模不断扩 大，其结果的数目呈爆炸式增长，以致于现代最快的计算机在有限的时间和空 间内无法得到最好的结果。 其它复杂性，生产过程中随时可能会出现各种质量异常、设备异常、停 机待料、停机待物等各种问题。在异常事件发生时，要根据设备的当前状态， 进行设备调整，减小计划，并在可能的情况下，均衡设备负荷。 生产排产常常受到各种人为因素的( 如领导干预，个人关系等) 影响，用 计算机进行排产就不得不考虑到这外界因素的影响，得操作者能手动的干预排 产的过程，修改排产的结果。 6 2 。3 目前常用排产方法 运筹学方法：运筹学方法是将生产调度问题简化为数学规划模型，采用基 于枚举思想的分枝定界法或动态规划算法进行，解决调度最优化或次优化问题， 属于精确方法。这类方法虽然从理论上能求得最优解，但由于其计算复杂性而 难获得真正实用，对于复杂的作业调度问题( 这种纯数学方法有模型抽取困难、 运算量大) 算法难以实现的弱点。 基于规则的方法：对生产加工任务进行调度的最传统方法是使用调度规则， 已有许多调度规则被应用，因其调度规则简单，易于实现，计算复杂度低等原 因，能够用于动态实时调度系统中。多年来一直受到学者的广泛研究，并不断 涌现出新调度规则。常用的优先规则有：交货期最早的工件优先加工、后续队 列中加工时间最短的工件优先进入、当前队列加工时间最短的工件优先加工、 先进入队列的工件优先加工、最后进入队列的工件优先加工、停滞时间与剩余 工序数之比最小的工件优先加工。 系统仿真的方法：基于仿真的方法通过运行仿真模型来收集数据，能对实 际系统进行性能状态等方面的分析，从而能对系统采用合适的控制调度方法。 仿真方法的优点：直观显示系统的状态，参数，及和机器的运行情况；真 实反映系统的特性，避免因调度不当造成损失；找出系统的瓶颈环节，从而 使系统的设计和运行可靠有效。仿真方法的缺点：仿真没有优化能力；应 用仿真进行生产调度费用高；仿真的准确性受编程人员的判断和技巧限制。 基于排序的方法：该类方法是先有可行性加工顺序，然后才确定每个操作 的开工时间，并对这个顺序优化。虽属近似算法，但有时可能达到最优调度。 这类方法包括：局部探索，模拟退火法，遗传算法。它们存在各自的不足，很 多学者采取混合算法来弥补单一方法的不足。 2 4 实际排产情况 马钢股份有限公司车轮轮箍分公司是我国生产火车整体碾钢车轮和轮箍的 特大型企业，规模国内最大，世界第二，每天有大量的生产定单要处理，但生 产排产用的还是手工处理方式，由两个排产员根据每周的生产定单、生产能力、 机器运行情况，按照经验对生产进行人工排产。由于每次的订单所要求的品种 规格都在几百种以上，实际生产中还常常有各种变化，当有异常情况( 设备故 障等) 发生时还要求及时对排产过程进行调整，由人进行手工排产很难达到实 际要求，排产的结果也远远不能达到优化的目的。 目前轮箍厂的排产分为轮箍和车轮两部分，由两个排产人员分别进行排产。 轮箍生产过程由于其生产工艺特点，热轧是整个生产流水线过程的固定瓶 颈，生产工序变化很少，排产过相对很简单，通常的排产就把相似的产品放在 一起加工。但轮箍的配切过程相对比较复杂。 车轮生产排产的配切比较容易而排产很复杂，手工排产不能达到令人满意 的结果，也无法具体排到每个产品的加工情况，只是粗略的下达每周每个机器 的大概任务，再由各个车间具体安排生产时间。具体的排法是： 首先以销售计划作为生产计划的基础，决定每周生产哪些产品，每个产品 生产多少；有些客户临时追加的合同也作为指导生产计划的一个重要因素。 其次把生产工序按车间分成技术开发部、工模具车间、原料车间、轧钢车 间、加工车间、热处理车间等，根据工艺特点，机器性能和以往的经验安排每 个车间每周产品的规格和数量，同时安排好各产品在各工艺间的时间衔接。 召开排产会议，根据各生产车间的实际情况( 如人员、机器状态) ，对排产 结果做局部调整。 投入生产，再根据实际生产中出现情况，异常情况做一些调整。 8 3 1 基本遗传算法 3 1 。l 遗传算法简介 第三章遗传算法及其应用 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应 全局优化概率搜索算法。它最早由美国密执安大学的h 0 1 l a n d 教授提出，起源于 6 0 年代对自然和人工自适应系统的研究。7 0 年代d ej o n g 甚于遗传算法的思想 在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础 上。8 0 年代由g o l d b e r g 进行归纳总结，形成了遗传算法的基本框架”。8 j 。 遗传算法运算过程如图3 1 。 图3 1 遗传算法流程图 遗传算法中最优解的搜索过程模仿生物的进化过程，使用所谓的遗传算子 作用于群体p ( t ) ，进行下述遗传操作、从而得到新一代群体p ( t + 1 ) 。遗传算法的 主要运算过程如下所述。 步骤一：初始化。设置进化代数计数器仁0 ：设置最大进化代数t ；随机生 成m 个个体作为初始群体p ( o ) 。 步骤二：个体评价。计算群体p ( t ) 中各个个体的适应度。 步骤三：选择运算。将选择算予作用于群体。 步骤四：交叉运算。将交叉算子作用于群体。 步骤五：变异运算。将变异算子作用于群体。群体p ( t ) 经过选择、交叉、变 异运算之后得到下一代群体p ( t + 1 ) 。 步骤六：终止条件判断。若t = t ，则以 进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。 三种遗传算子为： 一是选择( s e l e c t i o n ) 根据各个个体的适应度，按照一定的规则或方法，从 第t 代群体p ( t ) 中选择出一些优良的个体遗传到下一代群体p 一1 ) 中。 二是交叉( c r o s s o v e r ) ：将群体p ( t ) 内的各个个体随机搭配成对，对每一对个 体，以某个概率f 称为交叉概率，c m s s o v e rr a t e ) 交换它们之间的部分染色体。 三是变异( m u t a t i o n ) ：对群体p ( t ) 中的每一个个体，以某一概率( 称为变异概 率，m u 诅t i o nr a t e ) 改变某一个或某一些基因座上的基因佰为奠等位基因。 3 1 2 基本遗传算法的描述 针对不同的问题，许多学者设计了许多不同的遗传算法但这些遗传算法都 有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿， 来完成对问题最优解的自适应搜索过程。基于这个共同特点，g o l d b e 昭总结出 了一种统的最基本的遗传算法基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m s 简称s g a ) 。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗 传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和 基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价 值1 卜13 1 。 ( 1 ) 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群 体中的个体，其等位基因是由二值符号集 0 ，l 所组成的。初始群体中各个个 体的基因值可用均匀分布的随机数来生成。如：x = 1 0 0 1 1 1 0 0 1 0 0 0 1 0 i l o l 就可 表示一个个体，该个体的染色体长度是n = 1 8 。 ( 2 ) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当 前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这 里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须 预先确定好由目标函数值到个体适应度之间的转换规则，持别是要预先确定好 当目标函数值为负数时的处理方法。 ( 3 ) 遗传算子。基本遗传算法使用下述三种遗传算子：选择运算使用比例选 择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子或均匀变 异算子。 ( 4 ) 基本遗传算法的运行参数。基本遗传算法有下述4 个运行参数需要提前 设定：m ：群体大小，即群体中所含个体的数量，一般取为2 0 1 0 0 ；t ：遗传运 算的终止进化代数，一般取为1 0 0 5 0 0 ；p 。交叉概率，一般取为o 4 - 0 9 9 ；p 。变 异概率，一般取为o 0 0 0 1 0 1 。 这4 个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目 前尚无合理选择它们的理论依据。在遗传算法的实际应用中。往往需要经过多 次试算后才能确定出这些参数合理的取值大小或取值范围。 3 1 3 基本遗传算法的实现 l 、适应度 在遗传算法中，以个体适应度的大小来确定该个体被遗传到下代群体中 的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大：反之，个 体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比 例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为正确计算不 同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能 是负数。对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个 负号就可将其转化为求目标函数最大值的优化问题【2 0 0 3 1 ， f ( z ) ：j ，( x ) 一c m m矿，( x ) 一c m m o ( 3 1 ) 、7 【 o 矿厂( x ) 一c m 。o 、7 2 、比例选择算子 选择算子的作用是从当前代群体中选择出一些比较优良的个体，并将其复 制到下一代群体中。最常用和最基本的选择算子是比例选择算子。所谓比例选 择算子，是指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小 成正比。比例选择实际上是一种有退还随机选择，也叫做赌盘限o u l e t t ew h e e l ) 选择，因为这种选择方式与赌博中的赔盘操作原理颇为相似，整个赌盘被分为 大小不同的一些扇面，分别对应着价值各不相同的一些赌博物品。当旋转着的 赔盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。虽然赔盘的指 针具体停止在哪一个扇面是无法预测的，但指针指向各个扇面的概率却是可以 估计的，比例选择算子的具体执行过程是： ( 1 ) 先计算出群体中所有个体的适应度的总和。 ( 2 ) 其次计算出每个个体的相对适应度的大小，个体被遗传到下一代群体中 的概率。 ( 3 ) 最后再使用模拟赌盘操作( 即o 到1 之间的随机实数) 来确定各个个体被选 中的次数。 3 、单点交叉算子 单点交叉算子是最常用和最基本的交叉操作算子。单点交叉算子的具体执 行过程如下。 ( 1 ) 对群体中的个体进行两两随机配对。若群体大小为m ，则共有m 2 对相 互配对的个体组。 ( 2 ) 对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。 着染色体的长度为n ，则共有( n - 1 ) 个可能的交叉点位置。 ( 3 ) 对每一对相互配对的个体，依据设定的交叉概率p 。在其交叉点处相互交 换两个个体的部分染色体，从而产生出两个新的个体。 单点交叉运算的示意图如下： 0 1 0 1 0 0 1 0 l o ：110 1 0 1 0 0 1 0 1 0 ：1 0 v 4 、基本位变异算子 基本位变异算子是最简单、摄基本的变异操作算子。对于基本遗传算法中 用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上原有 基因值为o ，则变异操作将该基因值变为1 ；反之，若原有基因值为l ，则变异 操作将其变为o 。 基本位变异算子的具体执行过程是： ( 1 ) 对个体的每一个基因座，依变异概率p 。指定其为变异点。 ( 2 1 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来 代替。从而产生出一个新的个体。 1 0 0 1 1 0 ；1 i o l 0 1 0 ： 1 0 0 1 1 0 ：o 0 1 0 1 0 1 3 2 遗传算法的实现技术 3 2 1 编码方法 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关 键步骤。编码方法除了决定个体的染色体排列形式之外，它还决定了个体从搜 索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉 算予、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决 定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方 法、有可能会使得交叉运算、变异运算等遗传操作可以简单地实现和执行。而 一个差的编码方法，却有可能会使得交叉运算、变异运算等遗传操作难以实现， 也有可能会产生很多在可行解集合内无对应可行解的个体，这些个体经群码处 理后所表示的解称为无效解【i o - 13 1 。 二进制编码：二进制编码方法是遗传算法中最常用的一种编码方法，它使 用的编码符号集是由二进制符号o 和1 所组成的二值符号集 o ，1 ，它所构成的 个体基因型是一个二进制编码符号串。 格雷码：格雷码是这样的一种编码方法，其连续的两个整数所对应的编码值 之间仅仅只有一个码位是不相同的，其余码位都完全相同。 浮点数编码：浮点数编码方法，是指个体的每个基因值用某一范围内的一 个浮点数来表示，个体的编码长度等于其决策变量的个数。因为这种编码方法 使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。 符号编码：符号编码方法是指个体染色体编码串中的基因值取自一个无数 值含义、而只有代码含义的符号集。 3 五2 适应度函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语 来度量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种 将有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对 较少，甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度 量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最代解的优 良程度。适应度较高的个体遗传到下一代的概率就较大：而适应度较低的个体 遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数 ( f i 恤e s sf u i l c 廿o n ) 。 有时在遗传算法运行的不同阶段，还需要对个体的适应度进行适当的扩大 或缩小。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。 目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺 度变换和指数尺度变换。 3 2 3 选择算子、交叉算子、变异算子 1 、选择算子 遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：适应度较高 的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代 群体中的概率较小。 ( 1 ) 比例选择 比例选择方法是一种回放式随机采样的方法。其基本思想是：各个个体被 选中的概率与其适应度大小成正比。由于是随机操作的原因，这种选择方法的 选择误差比较大，有时甚至连适应度较高的个体也选择不上。 设群体大小为m ，个体i 的适应度为f ；则个体i 被选中的概率入为： f n = 音。( i = l ，2 ，m ) f l i l ( 2 ) 最优保存策略 由于选择、交叉、变异等遗传操作的随机性，可能破坏掉当前群体中适应 度最好的个体。使用最优保存策略进化模型来进行优胜劣汰操作。即当前群体 中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体 中经过交叉、变异等遗传操作后所产生的适应度最低的个体。 ( 3 ) 排序选择 排序选择方法的主要思想是：对群体中的所有个体按其适应度大小进行排 序，基于这个排序来分配备每个个体被选中的概率。 2 、交叉算子 单点交叉：单点交叉又称为简单交叉，它是指在个体编码串中只随机设置 一个交叉点，然后在该点相互交换两个配对个体的部分染色体。 双点交叉：双点交叉是指在个体编码串中随机设置了二个交叉点，然后再 进行部分基因交换。将单点交叉和双点交叉的概念加以推广，可得到多点交叉 的概念。 均匀交叉：均匀交叉是指两个配对个体的每一个基因座上的基因都以相同 的交叉概率进行交换，从而形成两个新的个体。均匀交叉实际上可归属于多点 交叉的范围，其具体运算可通过设置屏蔽宇来确定新个体的各个基因如何由哪 一个父代个体来提供。 3 、变异算子 遗传算法中的所谓变异算子，是指将个体染色体编码串中的某些基因座上 的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。 基本位变异：基本位变异操作是指，在个体编码串中以变异概率p 。，随机 指定的某一位或某几位基因座上的基因值作变异运算。 均匀变异：均匀变异操作是指，分别用符合某一范围内均匀分布的随机数， 以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。 均匀变异的具体操作过程是： ( 1 ) 依次指定个体编码串中的每个基因座为变异点。 ( 2 ) 对每一个变异点，以变异概率p 。从对应基因的取值范围内，取一个随机 数来替代原有基因值。 3 2 4 遗传算法运行参数 遗传算法中需要选择的运行参数主要有个体编码串长度l 、群体大小m 、交 叉概率p 。、变异概率p m 、终止代数t 等。这些参数对遗传算法的运行性能影响 较大，需认真选取。 编码串长度l 。使用二进制编码来表示个体时，编码串长度l 的选取与问题 所要求的求解精度有关；使用浮点数编码来表示个体时，编码串长度l 与决策 变量的个数n 相等：使用符号编码来表示个体时，编码串长度l 由问题的编码 方式来确定；另外，也可使用变长度的编码来表示个体。 群体大小m 。群体大小m 表示群体中所含个体的数量。当m 取值较小时， 可提高遗传算法的运算速度，但却降低了群体的多样性，有可能会引起遗传算 法的早熟现象：而当m 取值较大时，又会使得遗传算法的运行效率降低。 交叉概率p 。交叉操作是遗传算法中产生新个体的主要方法，所以交叉概 率一般应取较大值。但若取值过大的话，它又会破坏群体中的优良模式，对进 化运算反而产生不利影响；若取值过小的话，产生新个体的速度又较慢。 变异概率p 。若变异概率取值较大的话，虽然能够产生出较多的新个体， 但也有可能破坏掉很多较好的模式，使得遗传算法的性能近似于随机搜索算法 的性能；若变异概率p 。取值太小的话，则变异操作产生新个体的能力和抑制早 熟现象的能力就会较差。 终止代数t 。终止代数t 是表示遗传算法运行结束条件的一个参数，它表 示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个 体作为所求问题的最优解输出。 3 3 遗传算法的改进 自从1 9 7 5 年j h h o l l a n d 系统地提出遗传算法的完整结构和理论以来。众 多学者一直致力于推动遗传算法的发展。对编码方式、控制参数的确定、选择 方式和交叉机理等进行了深入的探究，引入了动态策略和自适应策略以改善遗 传算法的性能、提出了各种变形的遗传算法4 。1 。 3 3 1 自适应遗传算法 遗传算法的参数中交叉概率p 。相变异概率p m 的选择是影响遗传算法行为 和性能的关键所在，直接影响算法的收敛性，p c 越大，新个体产生的速度就越 快。然而p 。尺过大时遗传模式被破坏的可能性也越大，使得具有高适应度的个 体结构很快就会被破坏；但是如果过小，会使搜索过程缓慢，以至停滞不前。 对于变异概率p m 、如果过小，就不易产生新的个体结构：如果过大，那么遗传 算法就变成了纯粹的随机搜索算法。 针对不同的优化问题，需要反复实验来确定p 。和p m ，这是一件繁琐的工 作，而且很难找到适应于每个问题的最佳值。s 南i v a s 等提出一种自适应遗传算 法( a d a p t i v eg a ，a g a ) ，p 。和p 能够随适应度自动改变。当种群各个体适应度 趋于一致或者趋于局部最优时，使p c 和p m 增加，而当群体适应度比较分散时， 使p 。和p m 减少。同时，对于适应值高于群体平均适应值的个体，对应于较低 的p 。和p 。，使该解得以保存进入下一代：而低于平均适应值的个体，相对应于 较高的p 。和p m 使该解被淘汰掉。因此，自适应的p 。和p 。能够提供相对某个解 的最佳p 。相p m 。自适应遗传算法在保持群体多样性的同时，保证遗传算法的收 敛性。 f 生! 血二：盟r ， e ： 。一厶。“一山” i 屯，厂 z 。 匕= “关乞 睁z ， 。，群体中最大的适应度值； f a 。每代群体的平均适应度值； f 要交叉的两个个体中较大的适应度值； f 一要变异个体的适应度值。 这里，只要设定k l ，k 2 ，k 3 ，k 4 取( o ，1 ) 区间的值，就可以自适应调整了。当适 应度值低于平均适应度值时，说明该个体是性能不好的个体，对它就采用较大 的交叉率和变异率；如果适应度值高于平均适应度值，说明该个体性能优良， 对它就根据其适应度值取相应的交叉率和变异率。可以看出，当适应度值越接 近最大适应度值时，交叉率和变异率就越小；当等于最大适应度值时，交叉率 和变异率的值为零。 这种调整方法对于群体处于进化后期比较合适，但对于进化初期不利，因 为进化初期群体中的较优的个体几乎处于一种不发生变化的状态，而此时的优 良个体不一定是优化的全局最优解，这容易使进化走向局部最优解的可能性增 加。为此，可以做进一步的改进，使群体中最大适应度值的个体的交叉率和变 异率不为零，分别提高到p 。2 ：和p r r l 2 ，这就相应地提高了群体中表现优良的个 体的交叉率和变异率，使得它们不会处于一种近似停滞不前的状态。为了保证 每一代的优良个体不被破坏，采用精英选择策略，使它们直接复制到下一代中。 经过上述改进，p 。和p m 计算表达式如下： 。k 坠掣岛 ：p二。一岛 “叫” l 咒，厂 正。 只：卜与警肛岛p 。，只= 1t 一厶 “叫” ( 3 3 ) l 圪， 正。 可以使r ，= 0 9 ，r 。= 0 6 ，n ，= o 1 ，= o o o l 。 3 3 2 混合遗传算法 梯度法、爬山法、模拟退火法等一些优化算法具有很强的局部搜索能力， 而另一些含有问题相关的启发知识的启发式算法的运行效率也比较高。如果融 合这些优化方法的思想，构成一种新的混合遗传算法，是提高遗传算法运行效 率和求解质量的一个有效手段。目前，混合遗传算法实现方法体现在两个方面， 一是引入局部搜索过程，二是增加编码变换操作过程。在构成混合遗传算法时， d ej o n g 提出下面三个基本原则： ( 1 ) 尽量采用原有算法的编码： ( 2 ) 利用原有算法全局搜索的优点； ( 3 ) 改进遗传算子。 3 3 3 并行遗传算法 伴随着遗传算法应用的深入开展。并行遗传算法及其实现的研究也变得十 分重要。一般来说，遗传算法中适应度的计算最费时间，再加上需要不断产生 新一代。而每一代又有若干个体，所以