（计算机应用技术专业论文）改进的遗传算法在多目标车间调度中的应用研究.pdf

摘要 摘要 针对以往车间调度系统只能适应某个具体车间环境，且只能得到时间最短，成本最 低，设备负荷平衡等一个目标评价标准的调度方案的缺点，设计并实现通用的多目标车 间调度系统。根据企业的各种实时信息，例如实时库存信息，在制品进度信息，车间生 产能力信息等进行动态综合调控，生成实时性高的车间调度方案；同时可以根据实际需 要选择生产过程中待控制的成本，以使最终的调度方案在满足般评估标准的同时，兼 顾各个目标尽可能达到较优的情况。本系统除了考虑并行的各种约束，还是同时对系统 适用的场合进行改善，现有的研究工作绝大多数要么研究加工的调度，要么研究装配的 调度，很难适合现在混合生产形态类型的制造业。针对上述的问题，不仅需要一个良好 的解决多目标的优化算法，同时还需要一个针对实际的车间调度的产生一个合适的方 案。 本文利用遗传算法可以很好地并行优化多目标问题的特点，提出一种基于偏好的随 机权重的多目标遗传算法，来解决多目标遗传算法很难做出选择的问题。算法利用了随 机权重的简单易用性以及多向搜索的特点，和偏好的引导性，结合这些特点来筛选进化 得到p a r e t o 解。算法克服了随机权重法在搜索方面的盲目性，同时也解决了因完全依 赖偏好信息而带来在计算方面的复杂性，提高了多目标遗传算法在产生p a r e t o 解的性 能。 针对混合生产形态下多目标车间调度的实际情况，本文设计了一种新的适用于混合 生产形态下多目标车间问题的生产方案，并提出了一个可以同时关注多个目标的优化算 法模型，相比传统的多目标优化算法，本设计具有较好的通用性，根据需要来优化多个 目标，因而该模型具有更好的实用性。 本文将开发混合生产形态下的实际车间调度应用平台主要技术进行了介绍，并将研 究的新算法应用到开发的调度平台上。最后通过实际问题进行求解，得到的最终的结果 是可行的和有效的。 关键词：遗传算法；作业车间调度；偏好；多目标 人连交通人学l ：学硕十学何论丈 a b s tr a c t j o bs h 叩s c h e d u l i n gs y s t e mf o rt h ep a s t ，o n l yt oa d a p tt oas p e c i f i cs h o pe n v i r o n m e n ta n d as i n g l eo b j e c t i v eo ft h ee v a l u a t i o nc r i t e r i ao ft h es c h e d u l i n go p t i o n s ，s u c ha so n l yg e t t i n gt h e s h o r t e s tt i m e ，l o w e s tc o s t ，l o a db a l a n c i n ge q u i p m e n te t c d e s i g n e da n dr e a l i z e dac o m m o n m u l t i o b j e c t i v ej o bs h o ps c h e d u l i n gs y s t e m a c c o r d i n gt oav a r i e t yo fr e a l t i m eb u s i n e s s i n f o r m a t i o n , s u c ha sr e a l t i m ei n v e n t o r yi n f o r m a t i o n ，i n - p r o g r e s si n f o r m a t i o n ，p l a n tc a p a c i t y i n f o r m a t i o n ，d y n a m i cc o m p r e h e n s i v ec o n t r o l ，g e n e r a t er e a l t i m e h i g h - s h o ps c h e d u l i n g p r o g r a m s a tt h es a m et i m e ，y o uc a nc h o o s ec o s ta c c o r d i n gt ot h ea c t u a lc o n t r o lo ft h e p r o d u c t i o np r o c e s st om a k et h ef i n a ls c h e d u l i n gp r o g r a m st om e e tt h eg e n e r a la s s e s s m e n t c r i t e r i a ，a n dt a k i n gi n t oa c c o u n tt h ev a r i o u so b j e c t i v e st oa c h i e v ea sm u c ha sp o s s i b l eo n b e t t e rc o n d i t i o n s t h i s s y s t e m ，b e s i d e sc o n s i d e r i n gt h ev a r i o u sc o n s t r a i n t si np a r a l l e l ， s i m u l t a n e o u s l yi m p r o v e ss u i t a b l eo c c a s i o no ft h es y s t e m t h ee x i s t i n gr e s e a r c hw o r ko rs t u d y i sm o s t l yt h es c h e d u l i n gp r o c e s s ，o ra s s e m b l yo ft h es c h e d u l i n gr e s e a r c h ，i ti sd i f f i c u l tf o r p r o d u c t i o np a t t e r n sa r em i x e dt y p e so fm a n u f a c t u r i n gi n d u s t r y t oa d d r e s st h ea b o v ei s s u e s ， r e q u i r e dn o to n l yag o o ds o l u t i o nt om u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m ，b u ta l s oa n a p p r o p r i a t es o l u t i o nf o rap r a c t i c a lw o r k s h o p i nt h i sp a p e r ，ag o o dp a r a l l e l i s mo fg e n e t i ca l g o r i t h m sc a no p t i m i z et h ec h a r a c t e r i s t i c so f m u l t i - o b j e c t i v ep r o b l e mp r o p o s e d ，m u l t i - o b j e c t i v eg e n e t i ca l g o r i t h mb a s e do nr a n d o mw e i g h t p r e f e r e n c ei sp r o p o s e d ，w h i c hs o l v em u l t i o b j e c t i v eg e n e t i ca l g o r i t h mt h a ti sd i f f i c u l tt om a k e ac h o i c e a l g o r i t h mu s e sar a n d o mw e i g h te a s eo fu s e ，a sw e l la sm u l t i s e a r c hf e a t u r e s ，a n d p r e f e r e n c e so ft h el e a d i n gl i g h to ft h ee v o l u t i o no ft h e s ec h a r a c t e r i s t i c st of i l t e rt h es o l u t i o nt o b ep a r e t o a l g o r i t h mo v e r c o m e st h eb l i n d n e s so ft h er a n d o mw e i g h t i n gm e t h o di ns e a r c h ，b u t a l s os o l v e sar e s u l to ft o t a l l yd e p e n d e n to np r e f e r e n c ei n f o r m a t i o nb r o u g h ti nt h ec a l c u l a t i o n o ft h ec o m p l e x i t ya n di m p r o v et h em u l t i o b j e c t i v e g e n e t i ca l g o r i t h mt og e n e r a t ep a r e t o s o l u t i o np e r f o r m a n c e f o rt h em u l t i - o b j e c t i v ej o bs h o ps c h e d u l i n ga c t u a ls i t u a t i o ni nm i x e dp r o d u c t i o np a t t e r n s ， t h i sa r t i c l eh a sd e s i g n e dan e wa p p l i c a t i o nf o rm i x e dp r o d u c t i o np a t t e r n s ，a n dp r e s e n ta o p t i m i z a t i o nm o d e lt h a tc a ns i m u l t a n e o u s l yc o n c e r n e da b o u tm u l t i - t a r g e t c o m p a r e dw i t h t r a d i t i o n a lm u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m ，t h ea l g o r i t h mh a sg o o dv e r s a t i l i t ya n d o p t i m i z en e e d e dm u l t i - t a r g e t ，a n dt h e r e f o r et h em o d e lh a sb e t t e rp r a c t i c a b i l i t y t h i sp a p e ri n t r o d u c e sa p p l i c a t i o np l a t f o r mk e yt e c h n o l o g i e st h a td e v e l o pt h ep a t t e r no f m i x e d p r o d u c t i o nj o bs h o ps c h e d u l i n ga n da p p l i e dt h en e wa l g o r i t h mt os c h e d u l i n gp l a t f o r m i nf i n a l ，t h ef i n a lr e s u l ti sf e a s i b l ea n de f f e c t i v eb yt h ep r a c t i c a lp r o b l e ms o l v i n g k e yw o r d s ：g e n e t i ca l g o r i t h m ；j o b - s h o ps c h e d u l i n g ；p r e f e r e n c e ；m u l t i - o b j e t i v e 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太董塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名：孑队女7 多 日期：卅年，2 月弓日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太蓬銮通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太整銮通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太整銮通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 本人授权太蓬褒通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 、 又。 ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：捩受f 纱 日期：y 口7 年，1 月，日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电子信箱 锄张屏彬 日期：矽矽年肛月弓日 电话： 邮编： 绪论 绪论 一、研究背景及其意义 全球性的竞争给制造业提出了新的挑战。企业要想在激烈的竞争中立于不败之 地，必须以最快的速度、最好的质量、最低的成本和最优的服务来响应市场。车间生产 调度是制造系统的基础，生产调度的优化是先进制造技术和现代管理技术的核心技术。 有关资料表明，制造过程9 5 的时间消耗在非切削过程中，因此制造过程的调度技术， 将在很大程度上影响制造的成本和效率。在制造环境中调度就是对加工过程进行作业计 划，采用高效的调度可以“缩短工期、减少库存、按时交货、提高信誉 。随着客户需 求的个性化，制造系统的调度问题愈来愈受到重视。此外，在企业的生产调度中，多目 标问题在当今是普遍存在。比如，生产者不仅要考虑满足用户的需求，还要考虑自身企 业的经济效益；既要应付突如其来的紧急任务，又要有计划地完成合同订货任务；既要 缩短空闲时间和用户等待时间，又要缩短生产周期；既要减少因为延误时间造成的未完 工时费，还要防止因为提前带来的存储费用等一系列相互联系、相互矛盾的问题。因此， 研究多目标车间调度问题，对促进企业生产管理的现代化，建立现代企业制度，提高我 国企业入世后的竞争力和市场应变能力，迅速打开走向世界的局面都有重要的意义。 二本文主要工作 1 、本文首先介绍多目标车间调度的基本理论。简要地概述了车间调度的问题，并 对车间调度的问题用数学模型进行了描述。本章同时还对车间调度的问题现状进行一些 总结，以及对车间调度存在的问题进行了叙述，探讨了车间调度解决的途径。 2 、其后简介了多目标遗传算法，介绍了多目标遗传算法应用一些相关的概念，对 多目标优化问题的解进行了必要的阐述，对如何寻找一组非劣解过程进行了介绍，并对 当今几种新型的多目标遗传算法进行了简介，另外还对当前的多目标遗传算法的现状进 行讨论。 3 、再在本文给出一种基于偏好的随机权重的多目标处理方法，利用较少的偏好信息 构造了一种新的权值生成方式用于判断最终得到的解的优劣，从而减少了像其他偏好算 法的过多的客观因素的约束和主观因素的不确定性。通过仿真实验表明所提算法能够有 效地依据偏好信息搜索到期望区域内的折中解，并能随着偏好的变化实时地调整搜索的 方向，改变解的范围；与另两种经典的多目标遗传算法的比较结果验证了所提算法具有更 高的求解效率。 4 、本文最后对车间调度系统的设计过程进行了在处理流程方面和主要的功能模块 进行了说明。对各个模块进行了如何设计以及设计的方法进行了阐述，在系统实例运行 人连交通人学t 学硕十学伊论文 中，利用最终完成的系统，通过实验的方式进行验证，将各个模块的主要功能进行了展 示，并给予模块实现的主要技术，并给出实验结果，验证了算法解决实际问题的有效性。 最后将系统利用的数据库表单进行了展示，有利于更好地了解系统的运行机制。 2 第一章多 标车间调度问题的研究 第一章多目标车间调度问题的研究 1 1 多目标车间调度问题概述 车问调度问题就是在时间上合理配置系统的有限资源，以满足特定目标的要求。典 型的车间调度问题包括一个待加工零件集合，每个零件包含一个工序集合，各工序需要 占用机床等生产资源，并且要按照一定的工艺路线进行加工：不同机床加工的工序可以 不同：调度的目的就是为零件合理地分配机床等资源，并合理地安排加工时间，在满足 约束条件的同时，使一些指标最优。 而多目标车间调度是在普通的车间调度的基础上，同时满足多个目标利益。虽然有 时存在多个目标利益的冲突，但是也需尽可能通过权衡来满足多个目标的利益。 1 2 车间调度数学模型 车间调度问题可描述为：在m 台机床和w 个工人的加工系统中，工人的数量w 少于 机床的数量m ，一个工人可操作一台或多台机床，机床的工时费与机床精密度和自动化 程度有关，工人的小时工资率与工人劳动能力和劳动质量有关：有n 个待加工工件，每 个工件有一条或多条工艺路线，每条工艺路线包含一道或多道加工工序，工序的加工顺 序和加工机床是预先确定的。此外，对工件、机床和工人有下面一些约束： ( 1 ) i 序的加工时间是预知的，辅助加工时间被考虑到加工时间内。 ( 2 ) 工序必须连续加工，一旦进行不能中断。 ( 3 ) 一个工件不能同时在两台机床上加工。 ( 4 ) 每台机床一次只能加工一个工件。 ( 5 ) 工人可操作的机床集合是确定的。 ( 6 ) 每个工人一次只能操作一台机床。 ( 7 ) 在零时刻，所有工件都可被加工。 ( 8 ) 任何作业没有抢先加工的优先权。 ( 9 ) 一台机床同时只能由一人操作。 调度的任务是确定机床上工序的加工顺序及操纵机床的工人，使得生产周期和生产 费用最小。 描述的数学模型，采用的符号表示的含义如下表所示： 3 大连交通人学下学硕十学何论文 表1 1 数学符号表 t a b l e1 1t a b l eo fm a t hs i g n 符号含义 o i j h 工件i 第j 条工艺路线的第h 道工序 t i j h工序o i j i l 的加工时间 c i j h 工序o i - 的完工时刻 s i j h工序o i j i l 的开工时刻 w i j i工人加工完工序o i j h 的时刻 n ij 零件i 的第j 条工艺路线的工序总数 a 一个很大的正数。 g生产费用 w 生产周期 取值为1 ，当0 1 1 h 先于，在机床m 上加工 y y h p q * , 取值为0 ，其他情况 取值为1 ，选择工件i 的加工路线j x i j 取值为0 ，其他情况 取值为1 ，工人i 先于工人j 使用机床m z i 取值为0 ，其他情况 根据对调度模型的描述，建立的数学模型如下： 优化目标：m i n g ，w 约束条件： 零件i 的第j 条工艺路线中的最后一道工序，c 如一口( 1 - 嘞) s w 零件i 的第j 条工艺路线中的第一道工序，c t j x + a ( 1 一x 0 ) t , j - 零件i 的第j 条工艺路线中的其它工序， 勺l c 0 ( 一1 ) + 口( 1 一嘞) t _ j h ，v f ，h ，h 一1 在机床m 上加工的两道工序， ( 1 1 ) ( 1 2 ) ( 1 3 ) ( 1 4 ) 一c 胛+ 缈伽唧+ 口( 1 一嘞) + 口( 1 一x m ) t o h ( 1 5 ) c 胛一+ 口1 - y i j h p q s m ) + 口( 1 一嘞) + 口( 1 一) 即 ( 1 6 ) 如果工序o i j h 与t 序o p q m 都在机床k 上加工，并且o i j h 由工人a 加工，o p q m 由 工人b 加工，则这两个工人满足条件： w i h - - w p q m + a z a b k 苫t i j h ( 1 7 ) 4 第一章多 1 标乍矧凋度问题的研究 一+ 口( 1 一z 掀) t e a m ( 1 8 ) 每个零件只能选择一条工艺路线， 莩纠 ( 1 9 ) 零件的每条工艺路线中使用机床m 的工序， 掣；y i j h p q x m 列 ( 1 1 + 莩y y h q p , , 列 m 每一道工序的完工时刻， 0 ( 1 1 2 ) 式( 1 1 ) 给出了优化目标，即同时缩短生产周期和减少生产费用。式( 1 2 ) 是生产周 期的约束。式( 1 3 ) 和( 1 4 ) 保证了工序之间的先后顺序。式( 1 5 ) 和( 1 6 ) 保证了一台机 床不能一起加工两个零件和一个零件不能同时由两个机床加工。式( 1 7 ) 和( 1 8 ) 保证了 一台机床不能同时由两个工人操作和一个工人不能同时操作两合机床。式( 1 1 0 ) 和 ( 1 1 1 ) 保证了在零件一条工艺路线中不能重复使用一台机床。 在上面的数学模型中，总的约束个数和变量个数是零件数量、零件的工艺路线数量 工序数量及工人数量的函数，假设有w 个工人和n 个工件，每个工件有m 条加工路线， 在每条工艺路线中有k 个工序，则总的变量个数e 为： o = n m + m n k + 历2 砌o 一1 ) 2 + k w ( w 一1 ) 2 ( 1 1 3 ) 总的约束条件个数西为： 西一2 m n k + 所2 砌0 1 ) + 刀+ m k n ( n 一1 ) + k w ( w 一1 ) ( 1 1 4 ) 1 3 多目标车间调度问题的研究现状 针对特定利益指标解决生产计划与调度集成优化问题有很多研究，如：文献从集 成化的角度研究了柔性j o bs h o p 计划和调度问题，建立了两层混合整数规划模型，并 用遗传算法求解最佳加工路径，用启发式规则求解调度问题。文献乜1 中详细的描述了遗 传算法在生产计划与调度优化领域的理论和技术。文献b 1 利用遗传算法解决了生产线平 衡问题。文献n 1 利用遗传算法解决了并行多机调度问题。文献3 利用遗传算法解决了作 业车间动态调度问题。文献叩1 研究了一类作业车间的生产计划和调度集成优化问题。文 献n 1 针对汽车装配车间( 流水车间) ，利用禁忌搜索算法与快速调度仿真相结合给出了 三种不同的启发式算法使生产计划和调度同时得到优化。文献1 针对多级串联流水车间 5 大连交通大学t = 学硕十学何论文 给出了一个基于调度仿真的集成生产计划和调度系统，通过在生产计划制定过程中引入 仿真的方法可以给出设备的准确负荷，并通过调节计划求解部分设备的可用负荷最终得 到一个可行调度。 还有最近几年提出的一些较为理想的解决车间调度的算法，如：吴秀丽饽1 提出了一 个基于多目标免疫遗传算法( m o i g a ) 的动态调度优化算法。首先定义了柔性作业车间动 态调度问题，然后采用事件驱动和周期驱动相结合的调度策略，提出了基于m o i g a 的动 态调度优化模型，接着设计了面向交货期性能最优的柔性作业车间调度算法，并讨论了 影响算法复杂度的因素。鞠全勇，朱剑英n 们提出批量生产优化调度策略，建立多目标优化 调度模型，结合多种群粒子群搜索与遗传算法的优点提出具有倾向性粒子群搜索的多种 群混合算法，以提高搜索效率和搜索质。黄敏镁：罗荣桂n 妇提出了柔性资源约束流水车 间调度( f r c f s ) 问题的假设条件，分析了问题求解的复杂性。针对f r c f s 问题的强n p 一难 特性，提出了由基于混合遗传算法的作业调度模块、基于优先规则的工序开始时间决策 模块和基于关键工序的柔性资源分配模块3 部分组成的求解问题的改进算法( m a ) 。王伟 达，刘文剑n 2 1 提出了一个动态调度控制器的设计框架，并详细阐述了它的功能模块和工 作流程。控制器采用基于过程规范语言本体论的工艺规划信息表示和多步骤适应调度策 略，并从知识库中获取规则，使用在线仿真的方式对其进行评价。这些技术的应用保证了 控制器与车间内部其他异构信息系统间有效地传递工艺规划信息，并具有很好的调优能 力。雷德明：吴智铭n 3 1 研究了具有模糊加工时间和模糊交货期的多目标作业车间调度问 题，首先给出了基于模糊优先规则的编码新方式，染色体的每一位表示在g t 算法迭代过 程中，对应机器上发生的某次冲突，根据该基因位对应的优先规则消除。然后设计了基于 个体密集距离的多目标进化算法，该算法利用密集距离进行外部档案维护和适应度赋 值。最后将多目标进化算法应用于模糊作业车间调度问题，以最大化最小一致指标和最 小化模糊最大完成时间，并和其他算法比较。 其中很容易发现多目标调度问题引起了越来越多学者的关注，有不少学者运用偏好 的方法来解决多目标的问题。他们的研究方法有大致有以下三种： 采用先验偏好信息的方法，即在求解问题之前，获取决策者的偏好信息。譬如， c a v a l i e r i 和g a i a r d e l l i 【l 钔先通过调查，得到了综合目标与生产周期和平均延误时间之 间的函数关系，然后按综合目标搜索最优调度。d a g l i 和s i t t i s a t h a n c h a i c u 引用神经 网络把多个目标映射成一个综合指标。由于调度问题非常复杂，取得准确的“先验偏 好信息是很难的，所以得到的结果往往不能反映决策者的真正偏好。 采用后验偏好信息的方法，即直接根据问题的性质和结构求出部分以至全部非劣 解，再由决策者选择一个最满意解。基于这种思想，m u r r a n 7 1 等提出了多目标的遗传算 6 第一章多目标， i 问阔度问题的研究 法，算法可得到多个非劣解。p o n n a m b a l a m 等n 8 1 用该方法研究了作业调度问题，证明了 该算法的有效性。但当非劣解数目较多时，如何从中选择最满意解仍然是个有待决策的 问题。 逐步取得偏好信息的方法。在决策过程中，决策者通过与辅助决策系统对话，来加 深自己的认识，辅助决策系统则根据决策者新的认识重新搜索解空间，对话和搜索过程 不断进行，直到找到最优解。文n 町采用了这种方法。这种方法更符合车间的实际情况。 当然，方法的性能取决于决策者提供局部偏好信息的准确性，不能保证在有限对话次数 内求得满意解。 1 4 车间调度存在的问题及解决途径 在车间调度领域中的大部分问题都具有np 困难特性，虽然对它的研究已有几十年 的历史，但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着很 大差距。实际应用中的调度方法能够响应系统的动态变化，但不能保证得到好的调度：一 些理论上的最优化方法能提供最优调度，但由于其的计算复杂性，并且忽略了很多实际 因素，离实际运用还有较大距离。因此，研究者可以从以下几个方面进行深入的研究恻： ( 1 ) 寻求新的最优算法。基于最优化的方法，诸如动态规划算法与分析定界算法等等， 大多数是建立在对可能调度的部分枚举上，因此只能解决小规模的车间调度问题，距离 实用还有较大距离。大多车间调度问题属于一类np 困难组合问题，寻找具有多项式复 杂性的最优算法几乎是不可能：但因其解的最优性，至今仍激发着学者们进行不断的探 - 察。 ( 2 ) 解决基于统计优化方法的计算时间复杂性问题。各种基于统计优化的方法，诸如 模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途径，但同别的优化算法类 似，也存在着一定程度的枚举，一般来说收敛到最优解很慢，且对于判断解的最优性也很 困难。在这方面也需要做进一步的研究。 ( 3 ) 探索新的近似调度算法，解决次优性的保障及定量评估问题。各种近似启发式方 法，诸如基于规则的算法等，由于能在合理的时间内产生比较满意的调度，因此广泛应用 于实际调度中，但其往往对所得的调度解的次优性不能进行评估。在这方面有必要探索 更好的近似最优调度算法，可以考虑增加合理的计算时间代价，提高解的次优性。 ( 4 ) 探索车间计划与调度问题的集成求解方法。在实际车间调度中，车间计划与车间 调度往往是分层进行的，但这可能造成计划在实际调度中的不可行问题，如何将计划与 调度结合考虑，以求总体的优化也是需要进一步研究的。 7 人连交通入学t ：学硕十学位论文 ( 5 ) 另外，还有很多有待进一步研究的问题，比如实际车间调度的多目标性等。本文 正是利用遗传算法来解决多目标车间调度的问题 1 5 本章小结 本章主要论述了多目标车间调度的基本理论。简要地概述了车间调度的问题，并对 车间调度的问题用数学模型进行了描述。本章同时还对车间调度的问题现状进行一些总 结，以及对车间调度存在的问题进行了叙述，探讨了车间调度解决的途径。 8 第：章多目标遗传算法概述 第二章多目标遗传算法概述 般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优 化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为 代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与 单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优 解集合，集合中元素称为p a r e t o 最优或非支配最优( n o n d o m i n a t e d ) 。所谓p a r e t o 最优就 是，不存在比其中至少个目标好而其它目标不劣的更好的解，也就是不可能通过优化 其中部分目标而其它目标不至劣化。p a r e t o 最优解集中的元素就所有目标而言是彼此不 可比较的。 2 1 多目标遗传算法简介 遗传算法是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者 h o l l a n d 于1 9 7 5 年首先提出来的。它摒弃了传统的搜索方式，模拟自然界生物进化过程， 采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的 一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘 汰的生物进化过程，对群体反复进行基于遗传学的操作例如遗传，交叉和变异等，根据 预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不 断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足 要求的最优解。 遗传算法包含以下的主要处理步骤： 1 、对优化问题的解进行编码。组成编码的元素称为基因。编码的目的主要是用于 优化问题解的表现形式和利于之后遗传算法中的计算。 2 、适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适 应函数确定以后，自然选择规律是以适应度函数值的大小决定概率分布来染色体的生存 淘汰情况。 3 、染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。 遗传算法的步骤如下口羽： l 、选择问题的一个编码；给出一个有n 个染色体的初始群体p o p ( 1 ) ，t = 1 ； 2 、对群体p o p ( t ) q h 的每一个染色体p o p i ( t ) ，计算它的适应函数： f i = f i t n e s s ( p o p i ( t ) ) 3 、若满足停止规则，则算法停止；否则，计算概率： 9 大连交通大学t ：学硕十j 学位论文 p j = 1 l ，f = 1 ，2 ，” 荟 ( 2 1 ) 4 、并从p o p ( t ) 中随机选一些染色体构成一个种群： n e w p o p ( t + 1 ) 一 p 叩j ( f ) ij = l 2 ，。 5 、通过交配，交配概率为p c ，得到有n 个染色体的c r o s s p o p ( t + 1 ) ； 6 、以一个较小的概率p ，使得一个染色体的一个基因发生变异，形成m u t p o p ( t + 1 ) ； t = t + l ，新的群体p o p ( t ) = m u t p o p ( t ) ；返回2 0 遗传算法的优越性可以简单的归结为以下三个方面： 1 、遗传算法适合数值求解那些带有多参数、多变量、多目标和在多区域但连通性 较差的优化问题，通过解析求解或是计算最优解的可能性很小，主要依赖于数值求解。 2 、遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深 入的了解。遗传算法在给问题的决策变量编码后，其计算过程是比较简单的，且可以较 快得到一个满意解。 3 、遗传算法同求解问题的其他启发式算法有较好的兼容性。 遗传算法不同于传统的搜索和优化方法，其主要的特点在于：自组织、自适应和自 学习性。应用遗传算法求解问题时，在编码方案、适应度函数及遗传算子确定后，算法 将利用进化过程中获得的信息自行组织搜索。遗传算法的这种自组织、自适应特征，使 它同时具有能根据环境变化来自动发现环境的特性和规律的能力。自然选择消除了算法 设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不 同特点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结 构化问题。 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。 它的并行性表现在两个方面： 1 、遗传算法是内在并行的，即算法本身非常适合大规模的问题。它适合在目前所 有的并行机或分布式系统上进行并行处理，而且对并行效率没有太大影响； 2 、遗传算法的内含并行性，由于遗传算法采用种群的方式组织搜索，因而可同时 搜索解空间内的多个区域，并相互交流信息。 由于遗传算法的并行性，所以非常适合解决多目标的问题，于是出现了多目标遗传 算法。多目标遗传算法和单目标遗传算法的最大区别就在于选择过程前的适值分配。在 单目标遗传算法中，从单个目标函数值到适应度函数值的映射是很方便的，只要给定的 单个目标函数值达到最大或最小，就达到了最优。而在多目标遗传算法中，为了进行选 1 0 第：章多目标遗传傅法概述 择操作，必需采用一定的算法将向量形式的目标函数值标量化，从而得到每个个体对应 的单个适应度函数值。遗传算法的优化过程利用的唯信息就是适应度函数，其选取将 直接影响算法的收敛速度以及最终能否找到最优解。因此，不同的多目标遗传算法也着 力对这一过程进行研究与改进，以尽可能提高整个算法的搜索效率。 2 2 多目标最优化及p a r e t o 解相关概念 与单目标遗传算法不同，多目标遗传算法必须对解的每个目标上的值进行综合评价， 而往往这些目标有时相互冲突，很难找到在每个目标上的值都是最优的解。所以引入了 p a r e t o 概念，用基于p a r e t o 的概念来求解问题的最优解。 2 2 1 多目标优化问题( m o p ) 的定义 定义1 ：多目标优化( 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 s ) l h q 题可以表述为下面的形式： m i n y = 厂0 ) = 饥= 元 ) ，y 2 一厂2 0 ) ，。以。o ) rt g i o ) s0 ，i = 1 , 2 ，朋 x = o 气，x 2 ，工。) e x ，y 一( y l ，) ，2 ，儿) y 2 2 2 最优解的定义 我们这里所讲的最优( p a r e t oo p t i m a ) ，是由v i l f f c d op a r e t o 在1 8 9 6 年提出的，故称 之为p a r e t o 最优解( p a r e t oo p t i m u ms o l u t i o n ) ，定义如下嘲： 设q 是可行解的集合，i ： 1 ，2 ，k ) 。若对于每一个三q ，或者v 旧( 正 ) l 五 ) ) 或者至少存在一个iei 使得z ) 正o “，则称石为p a r e t o 最优解。 2 2 3p a r e t o 相关概念 l 、p a r e t o 支配：对于向量“= l ，u 2 ，u ) 和，t ( v l ，v 2 ，v i ) 我们称“p a r e t o 支配，( 记作u - 1 ，) ，当且仅当v ；仙2 ，k ：咋s u 且j i o 2 一k ) ：吩s b 。 2 、p a r e t o 非支配：设v 表示向量的集合，对于向量“= 1 ，u 2 ，“t ) v ，u 是p a r e t o 非支配的，当且仅当不存在y y ，使得u - 4 ，。 3 、p a r e t o 不相关：v u ，v g v ，若u 和v 之间不存在支配关系，则称u 和v 不相关或 无关。 4 、p a r e t o 非支配集：设v 表示向量的集合，由v 中所有的p a r e t o 非支配 人连交通大学i ：学硕十学位论文 个体所组成的集合就称作p a r e t o 非支配集。 5 、p a r e t o 最优解集：对于一个给定的多目标最优化问题m o pf ( x ) ，p a r e t o 一 一 一 一一 最优解集( p ) 被定义为：p - 缸qi - 3 x q ：厂o ) - 厂o ) 】。 6 、p a r e t o 边界：对于给定的多目标最优化问题m o pf ( x 1 和p a r e t o 最优解 集p ，p a r e t o 边界( 阡+ ) 被定义为：p f + 暑缸一厂；( ) ，l ( x ) ) l x p 最优解是目标函数的切点，它总是落在搜索区域的边界线( 面) 上。 2 3 多目标优化问题的解 在求解单目标优化问题时，人们寻找的是一个最好的解。在多目标优化问题中，由 于各个目标之间相互矛盾、相互制约，一个目标的改善可能往往是以其它目标的损失为 代价，不可能存在一个使每个目标都达到最优的解，所以多目标优化问题的解往往是一 个非劣解的集合一p a r e t o 解集。 在存在多个p a r e t o 最优解的情况下，如果没有关于问题的进一步的信息，那么很难 说哪个解更可取，所有的p a r e t o 最优解被认为是同等重要的。所以，鉴于理想法，重要 的是找到尽可能多的关于问题的p a r e t o 最优解。因而，可以推论在多目标优化中有两个 目标： ( 1 ) 找到一组尽可能接近p a r e t o 最优域的解。 ( 2 ) 找到一组尽可能不同的解。 第一个目标在任何优化工作中都是必须的。收敛到不接近真正的p a r e t o 最优解集的 一组解是不可取的。只有当解收敛到近似真正的最优解才能保证它们的近似最优这一特 性。 除了收敛到近似最优域，求得的解也必须稀疏地分布在p a r e t o 最优域。只有一组多 样的解，才能确保有一组在多个目标之间的好的协议解。由于多目标进化算法需要处理 两个空间一决策变量空间和目标空间，所以解( 个体) 之间的多样性能在这两个空间定 义。例如，如果两个个体在决策变量空间的欧拉距离大，那么就说它们在决策变量空间 互异。同样，如果两个个体在目标空间的欧拉距离大，那么就说它们在目标空间互异。 尽管对于大多数问题，在一个空间的多样性常常意味着在另一个空间的多样性，但是并 不是对于所有问题都成立。对于此类复杂的非线性问题，找到在要求的空间有好的多样 性分布的一组解也是一项重要的任务。 1 2 第：章多目标遗传饽法概述 2 4 用于查找一组非劣解的过程 下面介绍得到非劣解的过程，首先介绍一种较慢的方法，然后介绍一种更有效且更 快的方法n3 1 。 方法一：种群中的每个解i 都要与该种群中的所有其它的解进行比较，看解i 是否劣 于种群中的其它的任意一个解。如果发现解i 劣于任意一个解，那么，解i 不可能属于 非劣组。对解i 作一个标记以表明它不属于非劣组：如果没有发现优于解i 的解，那么解 i 属于非劣组。下面的步骤描述了在一组给定的种群大小为n 的解p 中辨识非劣组的过 程。 第一步：设解计数器i = l ，建一个空的非劣组p ； 第二步：对于p 中的一个不同于i 的解j ，将它与解i 进行比较，看它是否优于解i 。 若否，则跳到第四步； 第三步：如果p 中还有没参与比较的解，则j = j + l 且跳到第二步：否则，设置 p = p u 料 第四步：i = i + 1 ，如果i s n ，则跳到第二步：否则，终止且得出非劣组p 。 方法二：种群中的每一个解都要与一个部分填充的种群进行比较来实现优劣分组。辨 识非劣组的过程如图所示。图2 1 中 - 表示占优于，_ y 来表示； 2 、u 比v 差，或者对u 的偏好小于v ，用h _ - 与_ - v 尊y 一 - 、一 、一具有传递性，即u ，一 - 1 - 3 2 ，但是同样可以得到2 7 4 ，3 7 4 ，这就 丸，将这 种关系与得到的线性优胜关系一一对应； 在生成的线性优胜关系的时候，可能存在同等重要的目标函数，即存在某些偏 好关系g ，一q z 。若存在g j 吼关系，再生成一个对应关系正数九一丑； 如果其中存在某个目标函数吼与其他的目标函数有不确定关系，就再随机生成 一个随机正数九，作为该目标函数对应的正数； 如果通过3