（模式识别与智能系统专业论文）汽车钣金件加工智能排程方法研究与系统设计.pdf

硕士学位论文汽车钣金件加工智能排程方法研究与系统设计 摘要 随着现代市场经济的发展，用户个性化需求越来越多，市场变化越来越快， 企业竞争也越来越激烈。原有的人工生产流程控制越来越不能适应现代制造企业 的市场发展。现代制造企业需要根据现有的资源的具体情况和各种约束条件，针 对用户个性化需求来制定高效的生产计划，以提高生产效率。 对某汽车配件公司的生产加工流程的现实情况进行了全面的分析，该企业目 前主要是通过人工控制、手工完成生产排程计划，存在着资源浪费、生产计划兑 现率低和生产周期长等问题。现有生产排程已经不能适应多变的市场发展，不利 于企业长远发展，需要尽快改进。 针对该企业在实际生产过程中存在的与排程相关的诸多问题，本文进行详细 研究和系统分析，提出了生产智能排程系统的具体解决方案，并给出了实现方法。 首先，对本课题的背景、缘由、现状等进行了概括描述，分析了国内外对于生产 智能排程的研究现状。其次，对汽车零件加工企业的钣金车间智能预排程系统整 体思路、模块设计和流程等进行了描述并提出了两种物理模型：由任务管道组成 的通量模型和基于工序体的三维空间模型：选取了智能优化算法中的遗传算法， 并按照传统遗传算法中编码、初始化、遗传算子设计及适应度函数设计的方法， 设计了遗传算法的应用流程，在遗传算子中将交叉算子改换为交换算子、变异算 子改换为分裂算子和合并算子，从而扩大了可行解空间。最后，对智能排程模块 具体实现进行设计和开发。 通过本文研究的生产智能排程系统方案，可以有效地降低生产管理人员的作 业强度，提高生产效率：可以实时地管控生产流程、有效降低生产加工成本，从 而为制造企业产生更大的经济效益。 关键词：生产智能排程空间表达分裂式遗传算法 硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fam o d e mm a r k e te c o n o m y , c u s t o m e r sd e m a n dm o r e a n dm o r cp e r s o n a l i z e d , f a s t e ra n df a s t e rt om a r k e tc h a n g e s ，b u s i n e s sc o m p e t i t i o ni s i n c r e a s i n g l yf i e r c e t h eo r i g i n a lm a n u a lp r o d u c t i o np r o c e s sc o n t r o li si n c r e a s i n g l y c a nn o tm e e tt h em a r k e td e v e l o p m e n to fm o d e mm a n u f a c t u r i n ge n t e r p r i s e s m o d e m m a n u f a c t u r i n ge n t e r p r i s e st ot h ea v a i l a b i l i t yo fr e s o u r c e s ，t h es p e c i f i cc i r c u m s t a n c e s a n dav a r i e t yo fc o n s t r a i n t s ，f o rt h ei n d i v i d u a ln e e d so fc u s t o m e r st od e v e l o p e f f i c i e n tp r o d u c t i o np l a n si no r d e rt oi m p r o v ep r o d u c t i o ne f f i c i e n c y t h ep r o d u c t i o na n dp r o c e s s i n gf l o wo ft h er e a l i t i e so ft h ee n t e r p r i s ei sn o w m a i n l yt h r o u g hm a n u a lc o n t r o l ，m a n u a lc o m p l e t i o no ft h ep r o d u c t i o np r o c e s sp l a n , t h e r ei saw a s t eo fr c s o i i i c 圮s ，p r o d u c t i o np l a n n i n ga n di r r o d u e t i o nt oh o n o rt h el o w r a t eo fl o n gc y c l ea n ds oo n t h ec u r r e n tp r o d u c t i o ns c h e d u l eh a sb e e nu n a b l et o m e e t c h a n g i n gm a r k e td e v e l o p m e n t s ，i sn o t c o n d u c i v et ot h e i r l o n g - t e r m d e v e l o p m e n ta n di m p r o v e m e n ta ss o o na sp o s s i b l e a g a i n s tt h ee n t e r p r i s e si nt h ea c t u a lp r o d u c t i o ns c h e d u l i n gp r o c e s se x i s t sm a n y p r o b l e m sr e l a t e dt ot h i sa r t i c l et oc o n d u c tad e t a i l e ds t u d y a n ds y s t e m a t i ca n a l y s i st o t h ep r o d u c t i o no fi n t e l l i g e n ts c h e d u l i n gs y s t e m , s p e c i f i cs o l u t i o n s ，a n dg i v e st h e r e a l i z a t i o nm e t h o d f i r s t , t h eb a e k g r o t m do ft h i si s s u e , c a t u s c , s t a t u se t c o ft h e g e n e r a ld e s c r i p t i o n , a n a l y s i so fd o m e s t i ca n df o r e i g ni n t e l l i g e n c ef o rp r o d u c t i o n s c h e d u l i n gr e v i e w e d s e c o n d l y , p r o c e s s i n ge n t e r p r i s e so fa u t op a r t ss h e e tm e t a ls h o p s m a r tp r e - s e h e d u l i n gs y s t e m 鹊aw h o l el i n eo ft h o u g h t , s u c h 豳m o d u l ed e s i g na n d p r o c e s sw c r cd e s c r i b e d ；p r o p o s e dt w op h y s i c a lm o d e l s ：f r o mt h et a s ko fp i p e s f o r m i n gt h ef l u xm o d e la n dp r o c e s s - b a s e dt h r e e - d i m e n s i o n a lb o d ym o d e l ；i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h ms e l e c t e di nt h eg e n e t i ca l g o r i t h m , a n da c c o r d i n gt ot h e t r a d i t i o n a lg e n e t i ca l g o r i t h mc o d i n g , i n i t i a l i z a t i o n , g e n e t i co p e r a t o rd e s i g na n dt h e d e s i g no ff i t n e s sf u n c t i o n , t h ed e s i g no fg e n e t i ca l g o r i t h ma p p l i c a t i o np r o c e s sw i l lb e a tt h eg e n e t i co p e r a t o rc r o s s o v e rs u bc h a n g ef o rt h ee x c h a n g eo p e r a t o r , m u t a t i o n o p e r a t o rc h a n g i n gt h eo p e r a t o rs p l i t t i n ga n dm e r g i n go p e r a t o r , t h u se x p a n d i n gt h e f e a s i b l es o l u t i o ns p a c e f i n a l l y , t h ec o n c r e t er e a l i z a t i o no fi n t e l l i g e n ts c h e d u l i n g m o d u l ei sd e s i g n e d t h r o u g ht h i sp a p e r , t h ep r o d u c t i o no fi n t e l l i g e n ts c h e d u l i n gs y s t e ms o l u t i o n s w h i c hc a ne f f e c t i v e l yr e d u c et h ep r o d u c t i o na n dm a n a g e m e n tp e r s o n n e l ，o p e r a t i o n a l s t r e n g t h , i m p r o v ep r o d u c t i o ne t f i e i e n e y ；, c a nb er e a l - t i m ec o n t r o lo fp r o d u c t i o n p r o c e s s e s ，r e d u c ep r o c e s s i n gc o s t so fp r o d u c t i o n , s o 嬲t om a n u f a c t u r i n ge n t e r p r i s e s 硕士学位论文 汽车钣金件加工智能排程方法研究与系统设计 h a v eag r e a t e re c o n o m i cb e n e f i t s k e yw o r d s ：i n t e l l i g e n tp r o d u c t i o ns c h e d u l i n g , f l u xm o d e l sa n ds p a t i a le x p r e s s i o n , s p l i tg e n e t i ca l g o r i t h m m 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名： t p i ( 4 ) i = 1 将一批生产任务分解成的若干种待加工零件任务，并用任务通道图来表示， 这样为后面进行任务通道的操作进行打下了模型基础。 根据表3 - 1 建立1 0 个零件的任务通道图，其中红色通道表示瓶颈通道。 2 1 3 钮盘忭加r 智能* 挫数 横! 研究+ 学位论文 年7 1 目卞 3 2 车间作业排程的三维模型 幽33 任务通道豳 3 2 1 工序捧程三要素与三维模型的关系 本文研究通过将零件工序任务进行分解、排列、重组，最终得到设备的任 务安排。排列= 三要素是零件，设各和时口j ，这旱的三要素也就是工序的三要素， 即工序是指零件p 在设备e 上加工时b jt 。 图34 是排程三要素的空间表达，其中p 轴表示零件类型，e 轴表示设备 类型，t 表示n 件零件加工总时间。工序三要素则由一个长方体的二条边来表 示，这样的长方体称为工序体。模型向pt 甲面进行投影，可以得到零件任务 一维图；若将该模型向et 平而若将该进行投影，可以得到设备任务维图。 为了便于剐察，将各t 序根据l 方向进行分层，同一层次的工序体j j 不同颜色 表示相同颇色的l i f t ：体的总和称为工序层。 。司卧。u甘 重 。雨。可 。冒 n 卫 碰十学位论文 汽乍钮案件加j 馏能排程打法研究5 系统设 3 2 2 模型优化策略 幽34 零件设备时间的空删表选 定义：将空闯模型被平面n ( t 上z ) 横截的剖面叫做圈层。 在实际生产r | 1 ，由于在某一时间段内同一零件只能在一台设各上加工，同 设备只能加工一种零件。在t 轴的负方向上加一个重力，则由于重力的作用， 下游空问的同一图层上零件集p 和设备集e 具有一对应关系。而上游空间的 同圈层上p 的子集和e 的子集具有一一对应关系。 当。批任务确定后，所有工序体就确定了，将工序体按照零件工芭顺序排 放到具有重力场的空日j 中，排放原则按照各罔层零件集i ，和设备集e 的对应关 系使得总图层的厚度最小。 p - t 周的表达方式如图3 - 5 所示图中不同颜色表示相应的工序。前面已 经说明，工序集和设备集是一对应的，即0 = 已( p r ) 。因此这里共用八种工序 和对应的八种设备。考虑到同种设备会有多台。如果多台设备具有相同的工作 步骤，则可以将它们当成一台设备来考虑，同时将该设备的加工能力提高。 工序体在空问模型中体现实际上是长和宽均为零，高不为零的一维模型， 各工序离散分布丁三维宅问。由此可知工序体模型中具有4 个参数，即零件p 、 设备e 、起始时恻t s 。，、加工时问，。 3 钮盘什加j 智能持w 数学模型w 究顺+ 学位论文 * 口”* 口* # 口碾m _ 口# 口_ 固m 圈3 - 5 零 牛任务图 图3 5 是空间模型的pt 投影图，其空间模型在t = 0 5 处的p - e 投影圈36 。 该图满足了设备集与零件集一一对应关系。且由于零件集元素个数大于酷各集 零件个数，所以零件9 和1 0 没有对应设备。圈中的阴影部分表示某零件在相应 设备下加t ，由此正在工作设备数_ 与设备总数m 之比为设备利用率 r = n m 。r 表示衡最某一时刻设备利用率。 鞠 鞲 一 圈 瞄 幽36t = 05 处的pe 投影l 划培 设( f ) 和m ( f ) 为时问t 的两数，q ( f ) = n ( t ) m ( r ) 则t 时间内的设备平 均- 吁用率为： 肿 =m 碰 学位论 汽乍饭金件加i 智能掉程打沾研究与系统设“ 当任务下达后，可以将其分解成以工序体为最小单元的工序体群。工序群 的空问分布体现了排程方式。设f 。为设备i 已安排工序的虽大床尾时问t 这样 在将工序体排放的空阳】模型中的约束条件就是8 。，m a x ( t s 。n + ，n 。，t 。) 。根 据以上的分析，得到车削生产排程三维优化模型为： 3 2 3 优化流程 ( ，) ， e ( p ，) e ( p ) 日p “( q ) p “( e ，) ( f ) “h n “( 8 - + ，“) ( 6 ) t s m a x ( t s ，i + ，悱l ，t h ) f = m a x ( f 】 上式给出了空间模型的约束条件和目标函数，为排程系统的实现提供丁工 序体摆放方法。按照以上方法将表3 - l 的任务转化为以下pt 图， 削37 实例d t 削 以 实例只包括l o 种不同的零件，为了能够反应工艺在时间上的趋势，将 同种工序体中心依次连接得到设备任务曲线图，其中虚线表示负斜率或离散工 序。 p ，i 7 5 | 3 2 3 题2 件加i 璀能排程散学模型研究删+ # 位论文 蚓38 设备任务折线h 从国38 中我们可以看到绝大部分设备曲线都包台在剪板设备眭线与翻边 设备曲线内形成个喇叭口，即工序实体。随着工艺编号后移，设备任务曲线的 斜率减小。卜图中，所有零件在加工时都需要的工序在可以形成连续设各任务 曲线。 周39l ：序分柿犀域削 第一条连续任务曲线和晶后条连续任务曲线中包括若干离散设备曲线，且 这些曲线平均斜率介于以上_ 二者之f b j 。可以看出，斜率越大，相对来蜕总时自j 越小。这就是我们排程优化的日的。也可以认为图3 - 9 中阴影形状是优化的对 象。 33 本章小结 本章通过某汽车配件公司的调研，将生产车怕j 任务进行精简，以陔企业某 钣会年问0 9 年某月的个1 0 种零件的实际生产任务为任务实例。根据汽车配 件均为冲压件的加工工艺特点，提出了两种数学模型抽任务管道组成的通 量模型和基于工序体的三维宅削模型。在三维模型中用三个坐标分别表示零件， 设备与时间的关系，根据不同平面的投影得到零件任务图和设备任务图，从而 p i 9 a 7 6 s 4 3 2 硕士学位论文汽车钣金件加工智能捧程方法研究与系统设计 描述了在任意时刻设备的利用率的表达方式，并给出了优化的目标函数，为第 四章优化算法的实现提供了数学模型表达。 4 钣金件加工智能捧程优化算法研究硕士学位论文 4 钣金件加工智能排程优化方法研究 4 1 排程优化问题的求解方法 4 1 1 运筹学方法 运筹学方法是一种基于分析的、实验的和定量的科学分析方法，也是实现计 划工作的较为全面的分析方法之一。该方法可用于研究在特定的物质条件已经确 定了的情况下，为达到特定目的，如何统筹兼顾活动中所有的各个环节、各个部 分之间的关系，来选择最佳方案，做出整体合理的安排，以取得最好的效果的方 法之一1 射。 运筹学方法应用于汽车钣金件加工的生产排程问题中，就是将钣金件生产排 程问题简化为特定的数学模型，采用分枝定界法或基于枚举思想的动态规划算法 来合理解决生产排程的最优化问题。运筹学方法属于精确方法范畴，很多学者分 别提出了不同的分枝定界法n 铂，各种界定法的不同点主要在于分析的规则、定界 的机制以及上界的产生这三方面存在一定的差异。 运筹学方法运用在本课题中也存在着一些不足之处n 5 1 ： ( 1 ) 运筹学方法最终要得到是问题的最优解，然而从汽车钣金件生产实践的 角度来看，因为决策目标常常有许多个，而且各个不同的钣金件间的加工工序有 可能会存在着相似冲突之处，所以最终解决方案只能是一种折衷。通过运筹学方 法排程得出的只是一个靠经验和直觉所得出的相对比较近似的好一些的方案，这 其实不是生产管理者所需要的最佳方案。 ( 2 ) 运筹学方法是一种纯数学方法，虽然理论上是可以求得最优解，但由于 此种数学计算方法的复杂性致使它不能在制造生产实践中获得真正的应用。对于 很复杂的一些问题如多目标的汽车钣金件加工就存在着一些先天性的弱点：大量 的不同类型的汽车钣金件造成其数学模型抽取困难、运算量大、算法难等等。而 实际生产环境中的排程是动态的，有众多变化的，所以运筹学方法是无法解决生 产过程中的动态排程问题，也就无法快速响应多变的市场需求。 4 1 2 派工方法 派工方法在本研究课题中是指从需要经过多道加工工序的大批量的汽车钣 金件中，按某个原则选出某一个批量进行优先加工，而这种特定的选取方法就称 为派工方法。派工方法是将汽车钣金件的生产排程问题简化成单机的排序问题， 生产排程的决策流程由各台加工机器分别来执行，当某一台机器出现空闲的时 硕士学位论文 汽车钣金件加工智能排程方法研究与系统设计 候，系统就会根据派工方法从等候的待加工的钣金件中挑选出一个工件来进行加 工。 派工方法比较适合于简单的派工问题，生产排程过程中也常以简单准则进行 工作流程的排序，而对于较为复杂的生产管理和排程问题，无法求得最佳的方案。 本课题中涉及到的简单派工法则有：处理时间最短、处理时间最长、剩余工序加 工时间最短、剩余工序加工时间最长、下道工序加工时间最长、交付期最早、剩 余工序数最少、剩余工序数最多等等n 即。 派工方法是基于某个规则的，其规则相对简单，所以该方法的优点是计算速 度很快、容易被人理解、掌握和使用。 派工方法运用在本课题中也存在着一些明显的缺点n 7 】： ( 1 ) 由于其汽车钣金件生产过程中的排程决策是由各台加工机器单独来决 定，所以也就无法兼顾其它加工机器的综合需求，以致其局部即某台加工设备或 某个类型钣金件可以实现最佳排程，但可能会导致整批产品的生产的时间和加工 设备综合使用率无法得到协调和平衡。 ( 2 ) 派工法则的通用性问题也会在汽车钣金件的生产过程中存在，在同一个 生产流程中的不同的派工法则之间有可能还会存在相互矛盾的现象。 ( 3 ) 派工法则有时只能达到部分目标，所以在多目标大批量的多类型汽车钣 金件需要加工的情况下难以判断其算法的优劣性。因此，在面临具体问题时，如 何确定派工的具体应用法则也是一个十分困难的事情，需要设计者具有较丰富的 工作和实践经验。 4 1 3 仿真方法 所谓系统仿真在本课题研究中就是满足特定的系统分析目的如交货期、设备 综合使用率和生产总时间，在考虑系统的各个要素相互关系的基础上，建立起熊 够描述各个结构或生产行为过程的逻辑关系、数量关系的仿真模型，根据这些仿 真模型在计算机中进行多次生产排程试验和定量分析，以便获得最终正确排程决 策所需要的各种信息n 町。 系统仿真的基本方法就是建立生产排程系统的结构化模型、量化分析模型， 并且将这些模型转换为适合在计算机上进行编程的仿真模型，然后对这些已建立 好的模型进行仿真实验。通过利用各种仿真语言在计算机中实现对生产排程真实 系统的虚拟仿真实验，从而研究钣金生产车间各个系统管理模块的结构、功能和 生产行为之间的动态关系。 仿真方法已不再一味追求生产排程系统的数学模型，而是侧重对系统中的各 种钣金件加工工序逻辑关系之间的描述，能够有效地对各种生产排程方案进行比 4 钣金件加工智能排程优化算法研究硕士学位论文 较和评价，同时分析生产智能排程模块各个动态性能指标，并智能地选择系统的 各种动态结构参数。 因为汽车零件生产制造系统涉及到的零件品种繁多，工序也较为复杂，很难 用精确的数学模型来描述和分析。而是通过计算机运行仿真模型来收集各种静态 和动态数据，能够对实际生产排程系统进行性能、状态等多方面的具体分析，从 而选取合适的基于交货期、设备综合使用率和生产总时间的排程控制方法。 仿真方法最早仅用来对排程启发式规则及分派规则进行测试，通过将简单的 优先权规则和启发式规则进行组合，发现其两者组合优于单独的优先权规则。这 样，仿真方法逐渐发展成为对现实的生产车间进行排程的仿真工具。通过仿真方 法，可以动态地展现钣金生产车间的具体状态，分析在不同的生产排程方法下的 各种系统性能指标，并通过设计者已有知识和实践工作经验来选择合适的生产排 程方法，从而改善生产排程性能。 仿真方法运用在本课题中也存在着以下不足n 帕： ( 1 ) 由于此方法鉴于其实验性很强，所以对生产智能预排程的理论研究很难 作出贡献。 ( 2 ) 通过仿真方法进行钣金车间生产智能预排程时，在完成虚拟排程的时间 计算上及其虚拟模型设计方面的费用都比较高。 ( 3 ) 仿真方法其准确性和精确性受编程人员本身的判断和其编程技巧的影响 较大，很难找到最优的排程方法。 4 1 - 4 智能优化算法 系统智能优化方法在现代经济的各个领域中得到了很广泛的应用。最优化理 论的研究领域也一直十分活跃，涌现了一系列最优化理论、方法和实际应用。 目前，人们涉及和研究的实际生产智能排程系统规模越来越大，相应的约束 条件也越来越多，具体生产智能排程系统功能也越来越强大，各种实用的复杂的 系统呈现出多准则、非线性、不确定、不可微等特征，致使实际系统的建模难度 增加。相应的逐步探求较大规模计算、具有智能特征的问题求解方法越来越成为 相关学科的重要研究方向啪1 。计算智能便是在此种情况下出现的一个前沿学科， 它是运筹学、人工智能、自动控制理论、计算数学等多种学科交叉并相互渗透的 学科，其典型分支主要包括进化计算、神经计算与模糊逻辑等。 智能优化算法作为计算智能的很重要研究内容之一，主要包括以下算法如遗 传算法、模拟退火算法、蚁群算法、人工神经网络方法、禁忌搜索算法等曙。这 些智能优化算法的共同特点是从任一解出发，按照某种机制和规则，在整个求解 硕士学位论文汽车钣金件加工智能捶程方法研究与系统设计 空间以一定的概率探索最优解的可能。由于智能优化算法可以把搜索空间扩展到 整个问题空间，因而比运筹学、派工方法和仿真方法具有全局优化性能。 本课题主要采用遗传算法进行智能优化，下面重点对遗传算法进行介绍和分 析。 遗传算法( g e n e t i ca l g o r i t h m s ) 是由美国的j h o l l a n d 陴1 教授于1 9 7 5 年首先 提出的，它是一类借鉴生物界的自然选择和自然遗传机制的随机化搜索算法。 遗传算法主要是模拟大自然生物界自然选择和自然遗传过程中发生的各种 繁殖、交叉和基因突变现象，在每一次迭代过程中都只保留一组候选解，并按照 某种指标从中选取相对较优的个体，利用选择、交叉和变异遗传算子对这些选取 出的较优个体进行组合，从而产生新一代的候选解群，多次重复此过程，直到得 到满足某种收敛指标的最优解为止嘲。 遗传算法作为现代智能计算方法中最为快捷、简便且容错性较强的算法之 一，与传统的搜索方法相比，它在各类结构对象和各种领域的优化过程中显示出 明显的优势之处。遗传算法主要特点有如下几点： ( 1 ) 遗传算法的搜索过程不直接作用在某个指定的变量上，而是作用在进行 了编码的个体即搜索对象为编码，可以直接对编码进行操作，不存在数学上的求 导和函数连续性的限定； ( 2 ) 遗传算法具有内在的隐并行性以致其搜索速度较快，具有更好的全局性 寻优能力从而降低了陷入局部最优解的可能性，采用同时处理群体中多个个体的 方法使其易于并行化； ( 3 ) 采用选择、交叉和变异遗传算子概率化的寻优方法，可以自动获取和优 化的搜索空间，遗传算法对搜索空间没有任何特殊要求且能够自适应地调整搜索 方向。 遗传算法的这些很好的特点，使得它已成为现代智能计算中关键技术之一。 同时遗传算法作为应用广泛的随机搜索和优化方法，也逐渐成为当今影响力较大 的进化计算方法之一。在现代经济发展过程中，遗传算法已经被广泛地应用于工 业工程领域的优化问题、自适应控制和生产智能排程等领域。 遗传算法是模拟达尔文的遗传选择、自然淘汰的生物进化过程来进行计算模 型，其思想源于生物遗传学和适者生存的自然规律。遗传算法是以一种群体中的 所有个体为研究对象，利用随机化技术对群体进行编码，之后对该编码参数空间 进行高效率地搜索。选择、交叉和变异构成了遗传算法的基本操作，参数编码、 初始种群的设定、自适应度函数设计、遗传操作设计、控制参数条件设定这五个 步骤也就组成了遗传算法的核心内容。 3 l 4 钣金件加工智能捧程优化算法研究硕士学位论文 遗传算法主要通过借鉴生物进化的一些特征完成优化，它的一些主要的进化 特征体现在以下几个方面： ( 1 ) 生物学中碱基对应遗传算法中的编码，进化发生在对编码的操作上，一 切的优化问题都是通过对编码的操作来实现的。 ( 2 ) 自然选择规则决定了哪些染色体产生超过平均数的后代即自然选择产生 优秀个体。在遗传算法中，通过优化问题目标而科学地构造自适应度函数，最终 产生最优解。 ( 3 ) 染色体结合使得双亲基因得到结合和遗传，这样产生的子女可以保持双 亲的基本特征。 ( 4 ) 染色体结合除了遗传和继承，随机的变异可能会给子代带来新的与父代 的不同特征。 适者生存的自然规律使得最具有生存能力的染色体得以生存的最大可能性。 优化问题的求解过程也就是从众多解中选出最优的解。 在遗传算法要用到各种进化和遗传学的概念： ( 1 ) 串( s t r i n g ) ：对应于生物遗传学中的染色体( c h r o m o s o m e ) ，属于个体 ( i n d i v i d u a l ) 的形式，在算法中为字符串。 ( 2 ) 群体( p o p u l a t i o n ) ：串可作为构成群体的元素，所有个体的集合称之为 群体。 ( 3 ) 基因( g e n e ) ：是串中的元素，可用于个体的特征表示。 ( 4 ) 串结构空间：应用于遗传学中的基因型集合。在串中，基因的任意组合 可以构成串的集合。所有对基因操作均是在串结构空间中完成的。 ( 5 ) 参数空间：在本课题研究中是指串空间在真实的生产智能排程物理系统 中的映射。 ( 6 ) 适应度：用来衡量群体中各个个体的适应程度，在优化计算中表示解有 可能达到最优解的优秀程度。 一般认为，遗传算法有5 个基本组成部分啮1 ： ( 1 ) 问题解的遗传编码表示。 ( 2 ) 对创建解的种群进行初始化。 ( 3 ) 计算个体适应度值从而对评价函数进行优劣判断。 ( 4 ) 遗传算子操作。 ( 5 ) 通过判断收敛条件是否满足，输出最优解。 图4 - 1 列出了经典遗传算法的基本操作流程汹瑚1 ： 硕士学位论文汽车钣金件加工智能排程方法研究与系统设计 图4 - 1 遗传算法基本流程 从以上遗传算法基本流程框图中可以看出，遗传算法是一种对种群型的操 作，其所有操作对象都是基于种群中个体。 遗传算法的具体求解步骤如下： ( 1 ) 编码及初始种群的生成。 遗传算法对问题的求解空间是通过作用于对编码的操作，所以对编码的选择 机制体现了使用该算法的效率及质量。 ( 2 ) 适应度函数计算。 遗传算法主要根据适应度函数来控制种群的更新，因些适应度函数能够将个 体的优劣性得到充分的体现。合理的适应度函数可以加快进化过程。 ( 3 ) 确定终止条件。 遗传算法的结束是通过判断终止条件来实现的，所以终止条件应该在优化效 率和质量上作出合理的平衡。如果终止准则成立，输出优化结果：如果准则不成 立，则继续进行以下遗传操作。 3 3 4 钣金件加工智能排程优化算法研究硕士学位论文 ( 4 ) 选择。 选择操作是遗传算法的关键，充分体现了大自然生物进化过程中适者生存的 思想。选择操作与适应度函数有关与编码方式无关，其目的是为了从当前群体中 选出较为优良的个体即适应生存环境的较优的个体，将有机会作为父代繁殖更多 后代，从而使群体的优良性得以遗传。通过该过程可以实现寻优对目标函数值进 行改善。 ( 5 ) 交叉。 交叉操作是遗传算法的核心，该操作是由两个父代通过某种方式进行部分基 因交换产生新一代的个体，新的个体组合了其父辈个体的特性。 ( 6 ) 变异。 同生物界一样，遗传算法中发生变异操作的概率较低。变异操作克服了交叉 操作产生的后代个体适应度函数值没有达到最优的缺陷，可以对交叉操作产生的 后代个体进行变异操作，也就是以较小概率地改变个体编码的值或位置。当然变 异也为新的个体产生提供了机会，也是产生新个体的辅助算法。 求解在具有资源受限的约束条件下生产排程问题时采用遗传算法，因为它具 有对复杂问题的求解能力，它可以完成实现将排程方案一代到另一代的选优、进 化，所以将遗传算法应用于汽车钣金件生产排程项目调度中是十分可行的。 本文研究的生产智能排程问题就是在考虑交货期、设备综合使用率和生产总 时间等因素的情况下解决对生产任务进行排序问题，当生产任务和数量达到一定 程度时，此流程还是相当复杂的，所以仅通过枚举等简单方式是很难求得最优解 的。本文将每个生产排程方案用一条染色体来表示，为了达到工期最短的次优解， 优秀的染色体即优秀排程方案会不断复制产生出更优秀的新方案，最终不断向最 优解进行逼近。 4 2 遗传算法应用 遗传算法继承了生物进化的自然规则，是一种随机化搜索方法。将汽车钣金 件加工排程问题的求解过程变成生物“染色体刀适者生存的过程。求问题的最优 解过程，事实上就是“染色体打群的一代代不断进化的过程，而进化过程又包含 了选择、交叉、变异等遗传过程。本节针对于某生产车间排程具体问题应用遗传 算法进行排程优化设计。 硕士学位论文 汽车钣金件加工智能捧程方法研究与系统设计 4 2 i 编码及个体初始化 对“染色体扫进行编码是遗传算法的第一步。遗传算法是针对编码进行操作 的，在对“染色体 进行编码时，要考虑“染色体本身的有效性和合法性。编 码的目的是实现了将需要求解问题的状态与遗传算法的代码进行一一对应。 针对一个具体问题，设计一种完美的编码方案一直是遗传算法的应用难点 之一，也是遗传算法的一个重要研究方向。可以说目前还没有一套既严密又完 整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，d e j 0 n g 曾提 出了两条操作性较强的实用编码原则： ( 1 ) 有意义积木块原n - 应使用能易于产生与所求问题相关且有低阶、短定 义长度模式的编码方案。 ( 2 ) 最小字符集编码原n - 应使用能使问题到自然表示或描述的具有最小编 码字符集的编码方案。 根据以上编码原则，目前人们已经提出了很多编码方法，总的来说，这些编 码可以分为三类，其特点如下表： 表4 - 1 编码方法比较 序号编码方法方法描述 特点 遗传算法中最常用的 一种编码方法，它使用的编 编码、解码操作简单易行； 码符号集是由二进制符号0交叉、变异等遗传操作便于实现； 1 二进制编码 和l 所组成的二值符号集 符合最小字符集编码原则； o ，l ，它所构成的个体基 便于利用模式定理对算法进行理论 因型是一个二进制编码符 号串。 分析： 适合于在遗传算法中表示范围较大 个体的每个基因值用 的数： 某一范围内的一个浮点数 适合于精度要求较高的遗传算法； 来表示：个体的编码长度等 便于较大空问的遗传搜索； 于其决策变量的个数。因为 改善了遗传算法的计算复杂性，提高 2 浮点数编码 了运算效率； 这种编码方法使用的是决 策变量的真实值，所以浮点 便于遗传算法与经典优化方法的混 数编码方法也叫做真值编 合使用： 便于设计针对问题的专门知识的知 码方法。 识型遗传算子； 便于处理复杂的决策变量约束条件。 个体染色体编码串中符合有意义积木块编码原则。 的基因值取自一个无数值便于在遗传算法中利用所求解问题 3 符号编码 含义、而只有代码含义的符的专门知识。 号集。这个符号集可以是一便于遗传算法与相关近似算法之间 个字母表，如“丑g q 。的混合使用。 4 钣金件加工智能排程优化算法研究硕士学位论文 以下编码设计是根据第三章建立的模型进行的。其中u 为基本空间，即3 2 节中提到的工序体在时间域上的任意排列。可行解集r 为满足式3 1 约束条件的所 有解的集合。编码要能覆盖所有满足可行解集。遗传算法的编码技术必须考虑“染 色体 的合法性、可行性、有效性以及对问题解空间表征的完全性。一个良好的 编码方案应该是编码空间到可行解空间的一一映射嘲。 图4 _ 2 可行解集与基本空间 我们知道遗传算法编码方式有很多种，根据本课题的实际问题，采用效果较 好的基于操作的编码方式，按照分类应属于符号编码方式。该表达方式将排程 编码成工序的序列，每一基因代表一道工序。对于同一零件，其包含的工序设为 相同的符号，在此基础上根据它们在染色体中出现顺序加以解码。每个基因并不 表明一个零件的具体的工序，而是指有上下依赖关系的工序。染色体的任意排列 总能够产生可行排程瞄1 一般意义上为了体现工序的顺序，选择一种合适的染色体表现型是应用遗传 算法寻优的第一步。c h e n g 咖1 分析了应用于古典生产车间调度问题的八种染色体 的优劣。考虑到存在柔性路径的情况，选择了基于工序的表达法。给所有同一工 件的工序指定相同的符号，然后根据它们在给定染色体中出现的顺序加以解释。 如下面染色体： 【2 l4334223l l 4 1 数字表示加工零件编号，相同数字表示同一零件的加工工序，不同的位置表 示加工顺序。该种编码表达了工序的先后顺序，但没有表达钣金件加工设备利用 情况，这样在设计的适应度函数中，有的染色体可能出现矛盾的情况，即超出了 可行解空间范围。 为了缩小可行解空间，且表达各工序在时间的坐标关系和钣金件加工设备利 用情况，以下编码是基于工序体的编码。基于工序体的编码表示为： 1 彳1 马乏岛 上面编码形式中前面数字表示加工零件i d ，大写字母表示钣金件加工设备 i d 。考虑到平均分批加工情况，零件i d 下标表示该零件分批数，上标表示分批i d 。 考虑到多台同种钣金件加工设备的情况，将其合并为一台设备进行，其后面的下 标表示为该种设备具有的台数。如2 ：晟表示零件2 被平均分成2 批，其中的第一 批在设备b 上加工。 硕士学位论文汽车钣金件加工智能排程方法研究与系统设计 该种编码包含了零件在钣金件加工设备上加工工序的主要信息，其显著优点 是可以实现零件分批的表达。这种分批方式在编码中是基因座个数的变化，零件 的分批对应基因座的分裂，零件的合并对应基因座的重组。该种编码方式与传统 的二进制编码不同在于各基因座之间的具有一定的先后顺序，这就决定了交叉算 子不是随意的，而是具有一定方向的。 根据图3 - 7 中的工序关系，得到个体如下图所示。设x ( i i ) 表示基因座玎在基 因的位置。 l al c2 a3 ai e2 c4 as a姐al g2 e3 c 7 a 4 gl o b b8 d 4 e3 g1 0 a8 b 9 a 弘 c强2 g 5 e dl o fef7 e7 f3 e7 g0 f el o e fl f l o h 图4 - 3 个体实例 以上个体需要满足以下条件：对于两个基因座玎、，若x ( i ) z 0 ， r i = j 则j ，。 4 2 2 遗传算法算子操作 ( 1 ) 选择算子 本文采用轮盘赌和精英法相结合来选择遗传算子。在精英法中，选择染色 体集中具有最大适应度的染色体。设染色体i 的适应度为z 。以下为选择算子 的操作流程。 s t e p l 先计算出群体中所有个体的适应度的总和为 z ( f = l ，2 ，m ) ； l l s t e p 2 其次计算出每个个体的相对适应度的大小为 只- f , z ( f = 1 ，2 ，肌) ， 1 = 1 即为每一个体被遗传到下一代群体中的概率。每个概率值组成一个区域，全部 概率值之和为l ； 3 7 4 饭金件加i 智能捧程优化算法研究顸士学位论文 ( 2 ) 交叉算子 本文采用精英遗传法。在精英遗传法中，具有屉大适应度的染色体将被复 制保留入下一代，不进行交叉运算。本文采取单点交叉的方式，即在个体编码 串中随机设置了一个交叉点。比较个体在交叉点下一个基因座如果对应基因 座不同将其进行交换，由两个体c 1 和c 2 分别得到新的个体如下图： _ 主j 旺 曩习_ 臣卫旺 、一， 图4 叫染色体交叉运算 这种交叉很容易产生非法染色体，针对这种现象，一般有四种处理方法， 分别是拒绝镱略、修复策略、改盎遗传算子策略和惩罚策略。拒绝策略要求的 充分条件很严，一般很难满足，在本问题中，这种蘸略也不具备可操作性：本 问题的约束条件较严，若采用修复策略，修复过程会比原问题更复杂。交叉操 作后的不可行解在种群中的比例较大，若采用惩罚策略，很可能找不到可行 解。对照工序体先后顺序原则，如果不满足，重新设置交叉点，产生个体。 ( 3 ) 变异算子 传统遗传算法中的变异运算是对个体的某一个或某一些基因座上的基因按 某一较小的概率进行改变，是产生新个体的一种操作方法。本文中我们采用基 本座分裂变异的方法来进行变异运算，其过程是按照各工序体中零件与单件加 工时间乘积的数值进行分裂，即实现零件的分批。由第三章建立的通道模型可 以得知瓶颈工序是影响整个生产进程的关键因素。所以要分裂的基因座就是瓶 颈管道所对应的。以下为分裂流程。 s t e p l 在个体中计算各基因座的工序体总加工时问： s t e p 2 选择分裂基因座，在染色体中选择m 缸( 虬r ，) 的位置： s t e p 3 设置分裂园予口，其中 p = o o l x 竺竺! 笠：! m a x ( pt p 一，) s t e p 4 将所有个体所有具有以上分裂特征的个体按照s t e p 3 进行分裂，如 2 e 分裂为2 ：且和2 i 且。 硕士学位论文 汽车钣金件加工智能捧程方法研究与系统设计 自然界的现象都是成对出现的，存在基因的分裂就应该存在基因的合并。 况且在该问题中零件的分批虽然是扩大了解的空间，但解的搜索路径不应该是 单方向的，而是应该双向的。故根据分裂流程设计合并流程如下： s t e p l 在个体中计算各基因座的工序体总加工时间： s t e p 2 选择合并基因座，在染色体中选择m 域，0 一，) 且为分裂后的基因 座的位置； s t e p 3 设置