（模式识别与智能系统专业论文）基于混合遗传算法的硬质合金刀具生产车间调度研究.pdf

基于混合遗传算法的硬质合金刀具生产车间调度研究 基于混合遗传算法的硬质合金刀具生产车间调度研究 摘要 车间调度问题既是制造系统实际生产的重要问题，也是理论研究 的难点之一，具有很大的实用意义和理论价值。 目前硬质合金刀具生产企业在车间级还是采用传统的手工排产 方法，排产周期长、效率低，无法适应市场的短周期、按时交货和提 高生产效率的复杂需求，频繁调整生产计划，往往使整个生产陷入混 乱和“救火状态。如何解决硬质合金刀具企业在生产过程中车间生 产调度存在的瓶颈问题，提升硬质合金刀具生产企业的生产效率和产 品质量，是本课题研究的关键。 本文从硬质合金刀具生产的工艺特点出发，对企业的生产环境、 过程及特点进行了分析，构思了硬质合金刀具生产制造信息系统的构 架，建立了一种适合硬质合金刀具生产车间调度状况的双层调度体系 模型，上层调度体系负责由控制中心下达到各车间生产任务的部署， 下层车间级的调度为各具体生产环节的执行。重点针对下层的车间调 度进行研究，并以模具车间的生产加工为例，建立了基于生产周期一 交货期双目标的车间调度数学优化模型。 针对硬质合金刀具生产车间调度问题的特性，应用混合遗传算法 对所建立的车间调度模型进行求解。本文提出了一种阶段进化的自适 应混合遗传算法，并对算法的基本理论进行了研究，详细分析了算 基于混合遗传算法的硬质合金刀具生产车间调度研究 法的设计过程，针对车间的实际情况，对传统的基于工序的编码方法 进行了改进。运用m a t l a b 编程对算例进行了仿真，通过双目标调 度优化结果和单目标调度优化结果的比较和阶段进化的混合遗传算 法同标准遗传算法和自适应遗传算法的比较，显示了本文阶段进化的 混合遗传算法调度模型的优越性。最后对车间调度理论进行了进一步 的探讨，首先分析了车间动态调度的策略，采用变周期的周期性再调 度和事件驱动相结合的再调度方法，并给出了几种典型关键事件发生 时的处理方法，然后分析了多目标优化的调度问题，采用基于层次分 析法的多目标权值的确定方法，为多目标动态调度问题的求解奠定了 基础。 关键字：硬质合金刀具，阶段进化，混合遗传算法，车间调度 基于混合遗传算法的硬质合金刀具生产车间调度研究 r e s e a r c ho nj o b - s h o ps c h e d u l i n gp r o b l e mo ft h ec e m e n t e d c a r b i d et o o lw o r k s h o pb a s e do nh y b r i dg e n e t i c a l g o r i t h m 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 m sa r en o to n l ya l li m p o r t a n ti s s u ei n p r a c t i c a lp r o d u c t i o no fm a n u f a c t u r i n gs y s t e mb u ta l s o o n eo ft h e d i f f i c u l t i e so ft h e o r e t i cr e s e a r c h i th a sl a r g ep r a c t i c a ls i g n i f i c a n c ea n d t h e o r e t i c a lv a l u e c u r r e n t l y , t h em a n u f a c t u r i n ge n t e r p r i s e so fc e m e n t e dc a r b i d et o o l a l s oa d o p tt h et r a d i t i o n a lm a n u a ls c h e d u l i n gm e t h o d si nt h e i rw o r k s h o p t h i ss c h e d u l i n gh a sal o n gc y c l eb u tl o we f f i c i e n c y t h e s ec a n ta d a p tt o t h ec o m p l e xd e m a n d so fm a r k e t ，s u c ha ss h o r tc y c l e ，d e l i v e r yo nt i m ea n d t h ei m p r o v e m e n to ft h ep r o d u c t i o n se f f i c i e n c y f r e q u e n ta d j u s t m e n t so f p r o d u c t i o np l a no f t e np u tt h ew h o l ep r o d u c t i o ni n t oc h a o sa n dt h e u r g e n c y h o wt o r e s o l v et h eb o t t l e n e c k sp r o b l e m so ft h ejo b - s h o p s c h e d u l i n gi nt h ep r o d u c t i o n sp r o c e s sa n dt oi n c r e a s et h ep r o d u c t i o n s e f f i c i e n c ya n dp r o d u c t sq u a l i t yf o rt h ee n t e r p r i s e so fc a r b i d et o o li st h e k e y t ot h i sr e s e a r c h i i i 基于混合遗传算法的硬质合金刀具生产车间调度研究 t h ep a p e ra n a l y s e st h ee n v i r o n m e n ta n dc h a r a c t e r i s t i c so ft h e p r o d u c t i o na r o u n dt h ec h a r a c t e r i s t i c so ft e c l m i c si nt h ep r o c e s so fc a r b i d e t o o l sp r o d u c t i o na n dm a k e sap r e l i m i n a r ys k e t c ho ft h es t r u c t u r eo f i n f o r m a t i o nm a n u f a c t u r i n gs y s t e mo fc a r b i d et o o l sp r o d u c t i o n o nb a s e o ft h a t ，t h e p a p e re s t a b l i s h e s at w o l e v e l s c h e d u l i n gs y s t e mm o d e l s u i t a b l ef o rt h ej o b s h o ps c h e d u l i n gs t a t u so fc a r b i d et o o l sp r o d u c t i o n t h eu p p e rs c h e d u l i n gs y s t e mt a k e sc h a r g eo ft h ed e p l o y m e n to ft h e p r o d u c t i o nt a s kf r o mt h ec o n t r o lc e n t r et oe v e r yw o r k s h o p t h el o w e ri s f o rt h ei m p l e m e n t a t i o no ft h ei d i o g r a p h i cp r o d u c t i o n t h ep a p e rf o c u s e s o nt h el a t t e ra n de s t a b l i s h e st h em a t h e m a t i c a lo p t i m i z a t i o nm o d e lo ft h e j o b - s h o ps c h e d u l i n ga tt h eb a s eo fp r o d u c t i o n sc y c l ea n dd e l i v e r yo nt h e e x a m p l eo ft h em a n u f a c t u r i n gp l a n t sp r o d u c t i o no fm o l d s a i m i n ga t c h a r a c t e r i s t i co fc a r b i d et o o l s p r o d u c t i o ns c h e d u l i n g p r o b l e m s ，t h ep a p e rs o l v e st h ee s t a b l i s h e dj o b - s h o ps c h e d u l i n gm o d e l u s i n gt h eh y b r i dg e n e t i ca l g o r i t h ma c c o r d i n g l y t h ep a p e rp r e s e n t sa s t a g g e r e de v o l u t i o no ft h es e l f - a d a p t e dh y b r i dg e n e t i ca l g o r i t h ma n d a n a l y z e sd e s i g np r o c e s so ft h ea l g o r i t h md e t a i l e d l y i nv i e wo ft h ea c t u a l s i t u a t i o nw o r k s h o p ，t h et r a d i t i o n a lm e t h o do fc o d i n gb a s e do nt h e p r o c e s s e si si m p r o v e d t h ee x a m p l ei ss i m u l a t e db ym a t l a ba n dt h e c o m p a r a t i v er e s u l t s ，b yc o m p a r i n gd o u b l e o b j e c t i v es c h e d u l i n g 丽t h s i n g l e o b j e c t i v es c h e d u l i n ga n dc o m p a r i n gt h es t a g g e r e de v o l u t i o no f h y b r i dg e n e t i ca l g o r i t h mw i t hs t a n d e r dg e n e t i ca l g o r i t h ma n ds e l f - a d a p t e d i v 基于混合遗传算法的硬质合金刀具生产车间调度研究 g e n e t i ca l g o r i t h m , s h o wt h a tt h es c h e d u l i n gm o d e lb a s e do ns t a g g e r e d e v o l u t i o no fh y b r i dg e n e t i cc a l lg e ts a t i s f y i n gr e s u l t s f i n a l l y , f u r t h e r d i s c u s s i o ni sm a d ea b o u tt h ew o r k s h o p s d y n a m i cs c h e d u l i n ga n d 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 a tf i r s t ，w ea n a l y z et h ed y n a m i cs c h e d u l i n g s t r a t e g ya n da d o p tt h er e - s c h e d u l i n gm e t h o dt h a tp e r i o d i cr e s c h e d u l i n g o fv a r i a b l ec y c l ea n de v e n t d r i v e na lei n t e g r a t e d t h e nt h ep a p e rg i v e s s e v e r a lt y p i c a lw a y st os o l v et h ec r i t i c a l i s s u e s ，a n da n a l y z et h e s c h e d u l i n gp r o b l e mo fm u l t i o b j e c t i v eo p t i m i z a t i o n t h em e t h o do f c o n f i r m i n gt h em u l t i o b j e c t i v ew e i g h ti sb a s e do nt h ea n a l y t i ch i e r a r c h y p r o c e s s i te s t a b l i s h e st h ef o u n d a t i o nf o rt h e s o l v i n gp r o b l e mo f m u l t i o b j e c t i v ed y n a m i cs c h e d u l i n g k e yw o r d s ：c e m e n t e dc a r b i d et o o l s ，s t a g g e r e de v o l u t i o n a r y , ah y b r i d 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 v 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位 论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除 文中已明确注明和引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对 所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者签名：撕甲绷侈 日期：年月 日 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密口。 学位论文作者签名：榔p 翔a 侈 日期：年月日 指导教师签名：方参雩 日期： 0 8 璃月 c a ( 2 3 ) 基于混合遗传算法的硬质合金刀具生产车间调度研究 其中，i = 1 , 2 ，露五，老= 1 , 2 册，m 是一个很大的正数，指示系数 。= l l 莩机筘!先于机器k加工工件i(2-4)l 口掀= 0 ，非上述情况 ( 2 ) 机器约束，表示各个工件在同一机床上加工的先后顺序。 一c 髓+ m 0 一) ( 2 - 5 ) 其中，f ，j = 1 , 2 ，刀，k = 1 , 2 ，m ，m 是一个很大的正数，指示变量 = 1 孽 芝1 耋三工佑在机器k 上加工 ( 2 6 ) 毋一10 ，非上述情况 。u 7 于是，问题变为一个可行的调度，也就是决定各作业在机器上何时加工，使 其满足工艺约束，并使目标函数最小化。 2 3 3 应用算例 对于硬质合金刀具生产的模具车间的某实例。在模具车间有车床、铣床、钻 床、镗床、磨床各一台，已知四个模具的生产工艺，加工工时和交货期如表2 1 所示。 表2 - 1 加工数据 模具工序名称( 加工时间)交货期 l2345 ( d i ) j l 车( 6 )钻( 8 )镗( 6 )磨( 4 ) 2 5 3 2 车( 3 )镗( 7 )钻( 5 )铣( 5 )磨( 4 ) 5 0 j 3铣( 8 )钻( 4 )镗( 8 ) 磨( 5 ) 5 0 j 4 车( 6 )铣( 8 )车( 4 )镗( 8 )磨( 6 ) 9 0 其中，假设加工设备：m 1 车床，m 2 钻床，m 3 镗床，m 瑚床，m 5 一磨床。 我们针对模具车间给出如下定义： 定义2 1 ：用仇表示模具f 的第道工序。 定义2 2 ：机器顺序阵厶，j 吖( f ，) 表示加工模具f 的第歹道工序的机器号。 j u ( f ，幸) 表示模具f 的所有操作按优先顺序加工的各机器号的排列。 定义2 3 ：加工时间阵，r ，j r ( f ，- ，) 表示模具f 的第道工序的加工时间。 基于混合遗传算法的硬质合金刀具生产车间调度研究 由上述定义和加工数据表可得： 机器顺序阵j u = l235o 13245 42 3 5 0 14l3 5 ，加工时间阵厶= 68 640 3 7 5 54 848 5o 68486 定义2 4 ：生产周期，对于给定的一个调度方案，设模具f 的加工完毕时间为 ，那么我们定义其生产周期为： c 雌= m a x ( c l ，g ，q ) ( 2 7 ) 定义2 5 ：完工拖后时间，对于给定的一个调度方案，设d 。模具i 的交货期， 那么我们定义其完成的拖后时间为： t d i = m a x ( c i d f ) ，0 j ( 2 - 8 ) 即若模具提前交货或按期交货，取拖后时间为0 ，否则取拖后时间为模具完 工时间与合同交货期之差。 由上述的分析可知，本文的目标函数为： 石= m i n = m i n m a x ( c l ，c 2 ，e ) ) ( 2 9 ) 左= m i n z t d t = m i n m a ) 【 ( q q ) ，0 ( 2 1 0 ) i = lf = l 经过上述转化后，就可以编写相应的算法进行优化求解，求解方法将在第三、 第四两章详细阐述。 2 4 小结 本章结合硬质合金刀具的生产工艺对硬质合金刀具生产企业的生产环境、生 产过程及生产特点进行了分析，构思了硬质合金刀具生产制造信息系统的构架， 为建立车间调度模型打下了基础。然后针对硬质合金刀具的车间调度问题进行了 深入地分析，设计了双层调度体系，并建立了基于生产周期一交货期的双目标的 数学优化调度模型，对本模型的求解是后续章节调度算法研究的重点。 基于混合遗传算法的硬质合金刀具生产车间调度研究 第三章混合遗传算法的研究 算法混合的思想是提高g a 搜索效率和质量的有效手段，如在g a 中嵌入局 部搜索方法则能改善其局部搜索能力，嵌入基于知识的启发式算法则能够将一些 问题相关的信息融入到 3 a 的全局搜索中，进而增强t 3 a 的整体搜索潜力。本章 首先概述了遗传算法和模拟退火算法的基本理论，然后在其基础上将自适应遗传 算法和模拟退火算法进行了融合，在基于黄金分割的思想上提出了阶段进化的混 合遗传算法，并给混合遗传算法加上了一个记忆器，保证了在群体进化的过程中 始终都能保持最优解的存在。 3 1 混合遗传算法概述 亚启发式( m e t a - h e u r i s t i c ) 随机搜索算法 2 3 1 ，如模拟退火、遗传算法、禁忌 搜索、进化规划、进化策略、混沌搜索和蚁群系统等，以其高效的优化性能、无 需问题特殊信息等优点，受到各领域广泛的关注和应用，并成为解决n p - h a r d 问 题的有力工具。尽管它们的收敛性在理论上得到了研究，但与实际应用尚存在差 距，当问题的规模和复杂度增加时，单一算法的优化能力大为削减，要确定合适 的算法参数也是非常困难的。由于优化算法的多样性，对具体问题应用何种算法 往往取决于研究人员的经验和爱好。探讨各种算法的适用域是一项庞大而困难的 工作，而基于自然机理提出新的优化算法也并非易事。鉴于这种现状，算法混合 的思想已成为提高算法优化性能的一个重要而有效的途径，其出发点是使单一算 法互相取长补短，产生更好的优化能力和效率。 遗传算法擅长全局搜索但搜索速度慢，梯度法、爬山法、模拟退火算法等一 些优化算法具有很强的局部搜索能力，擅长微调但常会陷入局部最优解。许多专 家已经详细研究了将遗传算法和局部搜索启发方法相结合从而解决优化问题的 想法，并提出了许多结合方法。一种最常见的混合遗传算法是将局部搜索方法插 入到遗传算法主循环中重组和选择部分之间。在这种混合算法中，遗传算法主要 进行种群中的全局广度搜索，而局部搜索启发方法则进行染色体中的局部深度搜 基于混合遗传算法的硬质合金刀具生产车间调度研究 索。由于遗传算法和传统启发方法的互补特性，混合式方法的效果通常比任意一 种都要好。混合的方式可以有许多种【冽，如下所示： ( 1 ) 两阶段方式：将启发式方法结合初始化以产生性能良好的初始种群。 采用这种方法以后，带有最优性方法的混合遗传算法可以保证不比传统启发式方 法的结果差。 ( 2 ) 嵌入方式：将启发式方法结合到评价函数中，用来将染色体解码为调 度。 ( 3 ) 嵌套方式：将局部搜索启发式方法作为遗传算法基本循环的插件，让 其与变异算子和杂交算予一同工作，以执行快速的局部搜寻，从而在对后代进行 评价之前对其进行改进。 在构成混合遗传算法时，d ej o n g ：i ：2 4 1 提出以下三个基本原则： ( 1 ) 尽量采用原有算法的编码； ( 2 ) 利用原有算法全局搜索的优点； ( 3 ) 改进遗传算子。 近年来，混合遗传算法的研究在国际上受到广泛的重视。d a v i s 2 5 1 对g a 提 出了“h y b r i d i z ew h e r ep o s s i b l e ，d i m o p o u l o s 【2 6 】等则认为混合算法的研究无疑是 一个新的发展趋向。 3 2 遗传算法的基本理论 遗传算法( g a ) 是j h o l l a n d 2 7 】于1 9 7 5 年受生物进化论的启发而提出的。g a 的提出在一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表 示、信息处理和解决组合爆炸等所方面遇到的困难，其自组织、自适应、自学习 和群体进化能力使其适合于大规模复杂优化问题。g a 是一种通用的优化算法， 其编码技术和遗传操作比较简单，优化不受限制性条件的约束，而其两个最大的 显著特点则是隐含并行性和全局解空间搜索。目前，随着计算机技术的发展， g a 越来越得到人们的重视，并在模式识别、图像处理、机器学习、神经网络、 优化控制、组合优化、遗传学等领域得到了成功应用，尤其在生产调度领域。 基于混合遗传算法的硬质合金刀具生产车间调度研究 3 2 1 遗传算法的基本流程 通常，把遗传算法( g a ) 、进化规划( e p ) 、进化策略( e s ) 和遗传编程( g p ) 统称 为进化计算( e c ) ，其中g a 着重强调基因层次的进化。遗传算法在整个进化过程 中的遗传操作是随机性的，但它所呈现出的特性并不是完全随机搜索，它能有效 地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代地不断 进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉 及的五大要素：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设 计和控制参数的设定。 我们通常采用的遗传算法的工作流程和结构形式是g o l d b e r g 在天然气管道 的控制优化应用中首先提出来的【2 引，一般称为规范遗传算法或者标准遗传算法 ( s g a ) 。在g a 的应用过程中，人们往往结合问题的特征和领域知识对s g a 进 行各种改变，形成了各种各样的具体的g a ，使得g a 具备求解不同类型优化问 题的能力，以及具备强大的全局搜索能力。 遗传算法的主要处理步骤是，首先对优化问题的解进行编码，编码的目的主 要是使优化问题解的表现形式适合于遗传算法中的遗传运算；第二是适应度函数 的构造和应用。适应度函数基本上依据优化问题的目标函数而定，当适应度函数 确定以后，自然选择规律是以适应度函数值的大小决定的概率分布来确定哪些染 色体适应生存，哪些被淘汰，生存下来的染色体组成种群，形成一个可以繁殖下 一代的群体；第三是染色体的组合( 交叉) ，父代的遗传基因结合是通过父代染 色体之间的交叉并到达下一代个体的。子代的产生是一个生殖过程，它产生了一 个新解；最后是变异，新解产生过程中可能发生基因变异，变异使某些解的编码 发生变化，使问题的解具有更大的遍历性。遗传算法的基本处理流程如图3 1 所 示。 2 8 基于混合遗传算法的硬质合金刀具生产车间调度研究 图3 - 1 标准遗传算法流程图 由图3 1 可以看出，标准遗传算法的基本步骤如下： s t e pl ：按照编策略生成初始种群p ( 0 ) ，令k - - 0 。确定遗传策略，包括选择 群体的大小n ，选择、交叉、变异方法以及确定交叉和变异概率等遗传参数； s t e p2 ：评价p ( k ) 中各个体的适配值； s t e p3 ：判断算法收敛准则是否满足，或者是否已完成预定的迭代次数，若 满足则执行s t e p 5 ，否则继续执行以下步骤； s t e p4 ：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一 代群体；返回s t e p 2 。 s t e p5 ：将进化终止种群中的最优个体作为最终解。 s t e p6 ：结束。 3 2 2 遗传算法的参数与操作 ( 1 ) 遗传编码 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键 步骤。编码就是将问题的解用一种码来表示，从而将问题的状态空间与遗传算法 的码空间相对应，这很大程度上依赖于问题的性质，并将影响遗传操作的设计。 遗传算法的编码技术必须考虑“染色体”的完备性、健全性、非冗余性以及合法 性与有效性。d ej o n g 依据模式定理，提出了较为客观明确的编码评估准则：有 基于混合遗传算法的硬质合金刀具生产车间调度研究 意义建筑模块编码规则即编码应当易于生成所求问题相关的短距和低阶的积木 块；最小字符集编码规则即编码应采用最小字符集以使问题得到自然、简单的表 示和描述。 最基本最简单的编码方法为二进制编码( 0 - 1 串编码方法) ，具有编码、解码 操作简单易行，交叉、变异等遗传操作便于实现，符合最小字符集编码原则和便 于利用模式定理对算法进行理论分析等优点，二进制编码主要用于数值运算， 而对于g a 在实际问题中的应用，特别是在工业工程领域中的应用，这种编码方 法很难直接描述出问题的性质。 近年来，出现了各种非o 1 串的编码方法。例如符号编码方法和浮点数编码 方法。解决了二进制编码算法精度和存储量的影响，同时便于优化中引入问题的 相关信息，直接在解的表现型上进行遗传操作，目前在复杂优化问题中得到广泛 应用，并取得了较好效果。 ( 2 ) 初始群体的产生 为了满足遗传算法的群体型操作的需要，必须为遗传操作准备一个由若干初 始解组成的初始群体。一般来说，产生初始种群的方法通常有两种【2 9 】：一种是 完全随机的方法产生，适合于对问题的解无任何先验知识的情况；另一种是由某 些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中随机选取样 本。在车间调度问题中，产生初始种群的方法即属于后者。 ( 3 ) 适应度函数 遗传算法将问题空间表示为染色体位串空间，为了执行适者生存的原则，必 须对个体位串的适应性进行评价。因此，适应度函数( f i t n e s sf u n c t i o n ) 就构成 了个体的生存环境。适应度函数的设计主要应满足以下条件：单值、连续、非负、 最大化；合理、一致性；计算量小；通用性强。适应度函数总是非负的，而目标 函数可能有正有负，因此需要在目标函数与适应度函数之间进行变换。常用的尺 度变换方法有三种：线性尺度变换、乘幂尺度变换和指数尺度变换。 如果适应度函数设计不当，有可能造成以下两种问题也称为遗传算法的欺骗 问题的出现：在遗传进化的初期，通常会产生一些超常的个体，若按比例选择 法，这些超常个体会因竞争力突出而控制选择过程，影响算法的全局优化性能； 在遗传进化的后期，即算法接近收敛是，由于种群中个体适应度差异较小时， 基于混合遗传算法的硬质合金刀具生产车间调度研究 继续优化的潜能降低，可能获得某个局部最优解。所以适应度函数的设计是遗传 算法设计的一个重要方面。 ( 4 ) 算法参数 种群数目：决定算法优化性能和效率的因素之一。通常，种群太d , n 不能提 供足够的采样点，以至算法性能很差，甚至得不到问题的可行解；种群太大时尽 管可增加优化信息以阻止早熟收敛的发生，但无疑会增加计算量，从而使收敛时 间太长。当然，在优化过程中种群数目是允许变化的。 交叉概率p 。：用于控制交叉操作的频率。交叉概率太大时，种群中串的更 新很快，进而会使高适配值的个体很快被破坏掉；概率太小时，交叉操作很少进 行，从而会使搜索停滞不前。 变异概率p 。：用于加大种群的多样性。变异概率太小则无法产生新个体， 变异概率太大时则使g a 成为随机搜索。 ( 5 ) 遗传操作 遗传操作是用一定的算子( o p e r a t o r ) 对原来的种群进行变化以产生新的个 体，常用的遗传算子主要有以下几种： 选择算子 选择算予有时也称为复制算子( r e p r o d u c t i o no p e r a t o r ) ，其作用是避免有效基 因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效 率。常用的选择算子有比例选择( 也称轮盘赌) 、基于排名的选择和锦标赛选择 等。 轮盘赌方法基本思想是各个个体被选中的概率和其适应值成正比。设群体大 小为m ，个体i 的适应值为z ，个体被选中的概率只可以表示为： j l f = z ( 3 1 ) k = l 基于排名的选择方法是将所有个体按适应度大小排列，然后用某个线性或非 线性函数对排好序的所有个体作映射，但要保证适应值大的个体被选择的概率相 对较大。锦标赛选择方法首先随机选择群体的一个子集，从子集中找出最好的一 个个体进入交配池，重复这个步骤直至整个交配池被填满。 无论是选择，还是交叉与变异，都具有很大的随机性，这种随机性有可能破 基于混合遗传算法的硬质合金刀具生产车间调度研究 坏当前最好的个体，并对g a 的收敛性与运行效率产生不利的影响。所以不管采 取何种选择算子，精英保留策略一般是必不可少的。其具体操作过程为： 步骤l ：选择当前群体中适应值最高和最低的个体； 步骤2 ：如果当前群体中的最优个体优于迄今为止的最好个体，则用当前最 佳个体替换迄今最优个体； 步骤3 ：用迄今为止的最好个体替换当前群体的最差个体。 精英保留策可以视为选择算子的一部分，它是算法收敛性的一个重要保证条件。 交叉算子 交义算子( c r o s s o v e ro p e r a t o r ) 是把两个父代个体的部分结构加以替换重组而 生成新个体的操作。交叉算子是遗传算法中起核心作用的基因操作，其作用在于 将原有的优良基因传给下一代个体，并生成包含更复杂基因结构的新个体。常用 的交叉算子有：一点交叉、二点交叉、多点交叉和一致交叉等形式。组合优化中 的置换编码g a 通常采用部分映射交叉、次序交叉、循环交叉、基于位置的交叉 等操作。 变异算子 变异算子( m u t a t i o no p e r a t o r ) 也是遗传算法中常用的基因操作，其基本实现 是对选中的父代染色体中的一位或几位基因进行突变。变异本身是一种随机算 法，但与选择和交叉算子结合后，能够避免由于选择和交叉运算而造成的某些信 息丢失，保证遗传算法的有效性。其主要作用有两个，一是改善遗传算法的局部 搜索能力，二是维持种群的多样性，防止出现早熟现象。变异的具体操作是，对 种群中任一个个体，随机产生一个实数p ，0 p 1 ，如果p 大于事先定义的变 异概率的阀值p m ，就对该个体进行变异。组合优化中的置换编码g a 通常采用 互换变异( s w a p ) 、逆序变异( i n v ) 和插入变异( i n s ) 等。 3 2 3 遗传算法的特点 遗传算法既是一种自然进化系统的计算模型，也是一种通用的求解优化问 题的适应性搜索方法。目前，人们最关注和普遍使用的遗传算法是其后一种性质。 从整体上讲，遗传算法是进化算法中产生最早、影响最大、应用也比较广泛的一 个研究方向和领域，它不仅包含了进化算法的基本形式和全部优点，同时还具有 3 2 基于混合遗传算法的硬质合金刀具生产车间调度研究 若干独特的性能【3 0 1 ： ( 1 ) 在求解问题时，遗传算法对问题参数编码成“染色体后进行进化操 作，而不是针对参数本身，这使得遗传算法不受函数约束条件的限制，如连续性 和可导性等。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常 复杂的优化函数求解问题。 ( 2 ) 遗传算法的搜索过程是从问题解的一个集合开始的，若遗传算法在每 一代对群体规模为n 的个体进行操作，实际处理了大约o ( n 3 ) 个模式，具有很高 的并行性，因而具有显著的搜索效率，大大减少了陷入局部最优解的可能性。 ( 3 ) 遗传算法具有全局搜索能力，在所求解问题为非连续、多峰以及有噪 声的情况下，能够以很大的概率收敛到最优解或满意解。 ( 4 ) 遗传算法使用的遗传操作均是随机操作，同时遗传算法根据个体适配 值信息进行搜索，而无需其他信息。 ( 5 ) 对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应 于其他问题，或者加入特定问题的领域知识，或者结合已有算法，能够较好地解 决一类复杂问题，因而具有较好的普适性和易扩充性。 ( 6 ) 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 遗传算法的优越性主要表现在： ( 1 ) 算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，从而 能够提高效率且不易陷入局部最小。 ( 2 ) 算法具有固有的并行性，通过对种群的遗传处理可处理大量的模式， 并且容易并行实现。 遗传算法的缺点： ( 1 ) 在有限的搜索空间内，遗传算法不能保证每次执行都能收敛到相同解。 许多数学方法，如动态规划法，从相同的起始点开始无论执行多少次，必定都会 收敛到相同的最终解，但遗传算法则无法百分百保证其收敛性。 ( 2 ) 由于超级个体的存在，往往导致遗传种群缺乏多样性而过早的收敛。 如果为避免过早收敛采取减小选择压或加大变异概率又会导致收敛太慢，甚至无 法收敛，从而使遗传算法搜索效率低下。 遗传算法的求解时间受其染色体字符串的维度大小影响很大；遗传算法的 3 3 基于混合遗传算法的硬质合金刀具生产车间调度研究 求解时间随染色体字符串位数的增加成指数增加；因此，以遗传算法求解问题时， 编码方式的设计原则是以尽量降低染色体字符串的位数为主。 3 3 模拟退火算法的基本理论 3 3 1 模拟退火算法的基本流程 模拟退火算法( s i m u l a t e da n n e a l i n g , 简称s a ) 的思想最早是由m e t r o p o l i s 等( 1 9 5 3 ) 提出的，1 9 8 3 年k i r k p a t r i c k 等将其用于组合优化。s a 算法是基于 m o n t ec a r l o 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物 质的退火过程与一般组合优化问题之间的相似性，将优化问题比拟成一个物理系 统，将优化问题的目标函数厂( 工) 比拟为物理系统的能量e ( x ) 。模拟退火方法从 某一较高的初始温度t 。 0 开始，伴随温度的不断下降，结合概率突跳特性在解 空间中通过邻域函数进行随机搜索，最终得到全局最优。模拟退火算法采用 m e t r o p o l i s 接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在 多项式时间里给出一个近似最优解。模拟退火算法的基本处理流程如图3 2 所示。 图3 - 2 模拟退火算法流程图 由上图可以看出，模拟退火算法的基本步骤如下： s t e p1 ：给定初 g t = ，随机产生初始状态s = s o ，令k = 0 ，最优解j = s 率； s t e p2 ：若算法终止条件满足则结束搜索并输出最优解s ，否则继续以下 基于混合遗传算法的硬质合金刀具生产车间调度研究 步骤； s t e p3 ：在当前解s 的邻域n ( s ) 中产生邻域解，； s t e p4 - 保优，若f ( s ) r a n d o m o , 1 】，ns = ，f ( s ) = f ( s ) ，其中 a f = f ( s ) 一厂( j ) ，即以m e t r o p o l i s 接受准则接受新状态； s t e p6 ：若抽样稳定准则满足则转s t e p 7 ，否则转s t e p 3 ； s t e p7 ：降温，即令t m = 2 t f ，名( 0 ，1 ) ，并令i = i + l ，再转s t e p 2 。 3 3 2 模拟退火算法的参数与操作 上面的退火算法的流程中，关键的是新状态产生函数，新状态接受函数，抽 样稳定准则，退温函数，退火结束准则( 简称三函数两准则) 是直接影响优化结 果的主要环节，此外，初温的选择对s a 算法的性能也有很大的影响。 ( 1 ) m e t r o p o l i s 接受准则【3 l 】( 状态接受函数) 在模拟退火策略中采用了m e t r o p o l i s 准则，即以概率接受新状态。1 9 5 3 年， m e t r o p o l i s 等提出重要性的采样法。他们用下述方法产生固体的状态序列：先以 给定以粒子相对位置表征的初始状态i 作为固体的当前状态，设该状态的能量是 e 。然后用扰动装置使随机选取的某个粒子的位移随机地产生一微小变化，得 到一个新的状态j ，设新状态的能量是e ，。如果e ， e ，则考虑到热运动的影响，该新状态是否“重要”状态 要依据固体处于该状态的几率来判断。固体处于状态i 和j 的几率的比值等于相 应b o l t z m a n n 因子的比值，即 ，= d 警) ( 3 2 ) r 是个小于1 的数，k 为b o l t z m a n n 常数，用随机数发生器产生一个 0 ， 1 区间的随机数善，若， 孝，则新状态歹作为重要状态，否则舍去。若新状态j 是重要状态，就以歹取代i 成为当前状态，否则仍以f 为当前状态。再重复以上新 状态的产生过程。当这种过程多次重复，即经过大量迁移后，系统趋子能量较低 的平衡态，固体状态的概率分布趋于b o l t z m a n n 概率分布。 3 5 基于混合遗传算法的硬质合金刀具生产车间调度研究 由式3 2 可知，高温下可接受与当前状态能差较大的新状态作为重要状态， 而在低温下只能接受与当前状态能差较小的新状态为中要状态。这与不同温度下 热运动的影响完全一致。在温度趋于零时，就不能接受任何e ， 马的新状态歹 了。这种接受新状态的准则成为m e t r o p o l i s 准则，相应的算法成为m e t r o p o l i s 算 法【3 2 1 。 ( 2 ) 状态产生函数 设计状态产生函数( 邻域函数) 的出发点应该是尽可能保证产生的候选解遍 布全部解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选 解产生的概率分布。前者决定由当前解产生候选解的方式，后者决定在当前解产 生的候选解中选择不同状态的概率。候选解由当前解的邻域函数决定，可以取互 换，插入，逆序等操作产生，然后根据概率分布方式选取新的解，概率可以取均 匀分布、正态分布、高斯分布、柯西分布等。 ( 3 ) 初始温度的确定 初始温度t 。、控制参数衰减函数、内循环终止准则和外循环终止准则通常被 称为退火过程的冷却进度表( c o o l i n gs c h e d u l e ) 。 从理论上来说，起始温度t 。应保证平稳分布中每一个状态的概率相等，也就 是使m e 的p o l i s 准则：e x p 4 生) l ，由此可以推出f 。很大，例如取：0 9 ， 9 0 则在蜕= 1 0 0 时，t o 9 4 9 。经验法则要求算法进程在合理时间里搜索尽可能大 的解空间范围，只有足够大的靠值才能满足这个要求。 初温越大，获得高质量解的几率越大，但花费的计算时间将增加初温的确定 应折衷考虑优化质量和优化效率，常用方法包括： 均匀抽样一组状态，以各状态目标值的方差为初温。 随机产生一组状态，确定两两状态间的最大目标值差l 影麟l 然后依据差 值，利用一定的函数确定初温。譬如，t o = 一眦1 n p ，其中p ，为初始接受概 率。若取p ，接近1 ，且初始随机产生的状态能够一定程度上表征整个状态空间时， 算法将以几乎等同的概率接受任意状态，完全不受极小解的限制。 利用经验公式给出。 ( 4 ) 内循环终止准则，即抽样稳定准则，常用的抽样稳定准则包括：检验 基于混合遗传算法的硬质合金刀具生产车间调度研究 目标函数的均值是否稳定；连续若干步的目标值变化较d , i 按一定的步数抽样。 ( 5 ) 控制参数衰减函数，一个常用的控制参数衰减函数是t m = a t ，其中 五是一个接近1 的常数