（光学工程专业论文）矩形件优化排样算法的研究与实现.pdf

摘要 摘要 矩形件优化排样问题是指在矩形的板材上，要排放多种不同尺寸的矩形件，如何使 这些矩形件既不互相重叠，又不超出板材边界的条件下，使得材料的利用率达到最高。 它广泛应用于玻璃、钢板、木材和皮革等。从数学计算复杂性理论看，优化排样问题属 于具有较高计算复杂性的n p 完全问题，至今还无法找到解决该问题的有效多项式时间 算法【。好的排样结果可以提高生产效率，提高材料的利用率，降低生产成本，提高企 业的竞争力。对矩形件优化排样问题的研究具有深远的理论意义和实际意义。 本文在分析矩形件优化排样问题特点的基础上，建立了该问题的数学模型，描述了 一些常见的优化算法和排样算法。在一定的约束条件下，应用遗传算法方法对矩形件排 样问题进行优化求解，对算例的求解结果进行比较与分析。 首先介绍了矩形件优化排样问题的数学模型和矩形件排样问题的排样算法，如剩余 矩形匹配法、b l 算法、下台阶算法、基于最低水平线的搜索算法。比较了这些算法的优 缺点。 其次介绍了在大规模生产中矩形件的下料工艺，如“一刀切”；为了提高生产效率， 相同的零件尽可能排放在一起；在加工时，要有安全距离的保障等。 再次介绍了遗传算法的基本原理，采用遗传算法对矩形件排样问题进行求解。在求 解过程中，给出了遗传算法的编码与解码方法、适应度函数的定义方法、遗传算子的设 计方法以及关键参数。通过对具体的算例进行求解，对求解的结果进行分析比较。 最后，基于以上理论，用v b n e t 开发了矩形件优化排样系统。其中包括用户登录 模块，零件与板材管理模块，利用优化算法进行排样的模块等。 本文将遗传算法与基于最低水平线的搜索算法相结合应用到矩形件排样优化中，产 生的排样结果满足“一刀切”和相同的矩形件尽量排放在一起等工艺要求，并且使板材 的利用率在9 4 9 6 左右，可以应用到企业的实际生产中。 关键词：矩形件优化排样；排样系统；遗传算法；遗传算子；搿一刀切 ； 大连交通大学工学硕十学位论文 a b s t r a c t t h ep r o b l e mo fr e c t a n g u l a rl a y o u ti st op u tv a r i o u sd i f f e r e n ts i z e sr e c t a n g u l a ro b j e c t s i n t os t o c ks h e e t s ，h o wt om a k et h er a t i oo fm a t e r i a lh i g h l yu n d e rt h ec o n d i t i o no fn o i n t e r f e r e n c ea n dn o tb e y o n dt h eb o u n d a r yl h i ti se x t e n s i v e l ya p p l i e di n t ot h eg l a s s ，s t e e l p l a t e ，t i m b e r ，l e a t h e re t c f r o mm a t h e m a t i c sc a l c u l a t i o nc o m p l e x i t yt h e o r y ，t h ep r o b l e m w h o s ec o m p u t a t i o ni st h em o s tc o m p l e xi nt h e o r yb e l o n g st ot h en pc o m p l e t ep r o b l e m t h e s o l u t i o no ft h ev a l i dp o l y n o m i a lt i m ec a l c u l a t ew a yc a n tf i n do u tb yn o w ag o o dp a c k i n g s c h e m ec a nn o to n l ys a v er a wm a t e r i a la n dr e d u c ep r o d u c t i o nc o s t ，b u ta l s ob r i n ge c o n o m i c b e n e f i tf o ra n de n h a n c et h ec o m p e t i t i v e n e s so fe n t e r p r i s e s t h e r e f o r e ，r e s e a r c ho nt h e p r o b l e mo fo p t i m a ll a y o u tf o rr e c t a n g u l a rp a r ti sv e r yi m p o r t a n ti nt h e o r ya n da p p l i c a t i o n s i nt h i s p a p e r , t h ef e a t u r e so fp r o b l e m a r es t u d i e da n di t sm a t h e m a t i c sm o d e li s e s t a b l i s h e d s o m ek i n do fo p t i m a la l g o r i t h m sa n dc o m m o nl a y o u ta l g o r i t h m sf o rt h eo p t i m a l l a y o u to fr e c t a n g u l a rp a r ta r ei n t r o d u c e d u n d e rc e r t a i nc o n s t r a i n t s ，g e n e t i ca l g o r i t h mi s a p p l i e di n t ot h eo p t i m a ll a y o u to fr e c t a n g u l a rp a r t t h er e s u l t so fi n s t a n c e sa r ec o m p a r e de a c h o t h e ra n da n a l y z e di nd e t a i l f i r s t l y , i n t r o d u c et h em a t h e m a t i c sm o d e lo ft h eo p t i m a ll a y o u to fr e c t a n g u l a rp a r ta n d s o m ek i n do fc o m m o nl a y o u ta l g o r i t h m s ，s u c ha st h es u r p l u sr e c t a n g u l a rt om a t c ha l g o r i t h m ， b o t t o m l e f ta l g o r i t h m ，d o w n s t a i r s a l g o r i t h m ，o nt h eb a s i so ft h el o w e s th o r i z o n t a ll i n e - s e a r c h a l g o r i t h m w ec o m p a r et h e s ea l g o r i t h m s s e c o n d l y , i n t r o d u c e dt h er e c t a n g u l a rp a r t s c u t t i n gd r a f to ft h el a r g e s c a l ep r o d u c t i o n ， s u c ha sg u i l l o t i n e ；l a yt h es a m er e c t a n g u l a ro b je c tt o g e t h e ri no r d e rt oi m p r o v ee f f i c i e n c y ； t h e r ei st h eg u a r a n t e eo ft h es a f ed i s t a n c ew h i l ep r o c e s s t h e ni n t r o d u c et h eb a s i ct h e o r yo fg e n e t i ca l g o r i t h m t h eg e n e t i ca l g o r i t h mi su s e dt o s o l v et h ep r o b l e mo fr e c t a n g u l a rp a r to p t i m a ll a y o u t i nt h em e a n t i m e ，t h ec o d i n gm e t h o d ， f i t n e s sf u n c t i o nd e f i n i t i o n ，g ao p e r a t o ra n ds o m ek e yp a r a m e t e r sa r eg i v e n t h er e s u l ti s a n a l y z e da n dc o m p a r e dw i t he a c ho t h e rt h r o u g he x a m p l e s f i n a l l y , a c c o r d i n gt oa b o v et h e o r y , w ed e v e l o ps y s t e mo fr e c t a n g u l a ro b j e c to p t i m a l l a y o u tw i t hv b n e t , i n c l u d i n gu s e rl o g i n ，t h em a n a g e m e n to fp a r t sa n ds t o c ks h e e t sa n d o p t i m a ll a y o u t t h ep a p e ra p p l i e dg e n e t i ca l g o r i t h ma n do nt h eb a s i so ft h el o w e s th o r i z o n t a ll i n e s e a r c h a l g o r i t h mi n t or e c t a n g u l a ro b j e c to p t i m a ll a y o u t t h ee x p e r i m e n t a lr e s u l t ss a t i s f y c r a f t r e q u i r e m e n to fg u i l l o t i n ea n dl a y i n gt h es a m er e c t a n g u l a ro b j e c tt o g e t h e r , a n dt h er a t i oo f u s i n go fs t o c ks h e e t si sa b o u t 9 4p e r c e n t s i tc a nb eu s e di np r a c t i c e k e yw o r d s ：r e c t a n g u l a ro p t i m a ll a y o u t ；l a y o u ts y s t e m ；g e n e t i ca l g o r i t h m ；g e n e t i c o p e r a t o r ；g u i l l o t i n e ； 第一章绪论 第一章绪论 1 1 问题的提出 随着社会生产力的不断提高，生产规模不断扩大，原材料的消耗量也越来越大，许 多产品生产中，零件毛坯是从板材上下料得到的，而钢材价格大幅上涨，已经导致企业 生产成本大幅上升，利润下降，一些企业甚至出现亏损。现在企业的当务之急是在钢材 切割下料生产环节有效提高钢材利用率，节省钢材，降低产品的生产成本。 剪床和锯床下料，历史悠久，设备保有量最多，是大量切割各种板材、型材、管材、 棒材、铝合金等的主要下料设备。这二种下料设备的下料方式相同，都是由操作工人按 照零件尺寸和数量在钢板上简单排列顺序切割下料。 这种传统的手工下料生产方式存在着显而易见的弊端，首先是造成大量边角余料。 原因在于操作工人只能按照零件尺寸和数量顺序排列切割，无法做到优化套料，从而导 致企业钢材浪费严重；其次是企业钢材大量积压，资金占用严重，原因在于企业不能做 到套料预算，为保证持续生产，不得已而采购各种类型的钢材作为库存；再次是切割下 料生产过程处于紊乱无序的状态，很难定时定量定额的管理锯床剪床切割下料生产过 程，从而造成切割下料生产效率低，钢材浪费严重。 如何改善和提高剪床切割下料管理水平，提高钢材利用率，减少钢材浪费? 并且我 国又是钢材消耗量大国，减少钢材浪费具有很重要的现实意义。本文研究的矩形件优化 排样是解决这一问题的有效途径之一。 1 2 优化排样问题国内外研究现状 国外有关下料排样问题的研究起步比较早。最早关于排样的文章是前苏联人 k a n t o v o r i c h 在1 9 3 9 年发表的i 引，讨论一维下料问题。五十年代中期，p a u l l t 引，e i s e m a n n l 4 | ， h e r r m a n n 和v a j d a l 5 】率先提出用线性规划( l i n e a rp r o g r a m m i n g ) 方法解决印刷和造纸工业 的矩形件排样问题，但材料利用率不高。g a r e y 和j o h n s o n l 6 1 证明用数规戈i j ( m a t h e m a t i c a l p r o g r a m m i n gt e c h n i q u e s ) 的方法解决二维切割问题是优化问题中具有最高计算复杂度的 一类优化计算问题刊p 完全问题。6 0 年代初，g i l m o r e 和g o m o r y 7 - 1 0 j 发表了四篇著 名的文章，提出了一维下料方案和二维排样问题。7 0 年代至今，许多学者对排样问题进 行了大量的研究，取得了一定的成果。但排样问题为n p 完全问题，复杂难解；同时由 于排样时存在各种限制条件，因此至今也没用通用的标准方法来进行求解。由于排样问 题的复杂性和广泛性，在1 9 8 8 年的p a d se u r o t i m s 国际会议上，专门成立了下料问 题兴趣小组e s i c u p 1 ( e u r os p e c i a li n t e r e s tg r o u po nc u t t i n ga n dp a c k i n gp r o b l e m ) 。 由于研究矩形件排样既可以直接解决矩形件排样问题，也可以作为解决二维不规则 大连交通大学t 学硕+ 学位论文 零件排样问题的基础( 以包络矩形法将不规则零件排样问题转换为矩形件排样问题) ， 所以一直是众多学者研究的热点，有大量的研究成果出现【1 2 1 5 1 。 启发式算法在排样问题求解中占据了重要的地位。y 抽a s s e 6 j 提出依次序的启发式 排样算法，算法的主要思想是根据排样零件的物理属性( 长、宽、面积) 等给出一定的优 先级规则，零件按照这种优先级规则排序，从板材的左下角开始，按次序排放每一个零 件。d a g l i 和t a t o g l u t l 7 j 提出使用启发式算法，但该启发式算法的启发规则难以确定，排 样结果不稳定。a m a r a l 1 8 】提出一种交互式排样方法，计算结果比较稳定，但排样效果一 般化。p r a s a d 和s o m a s u n d a r a m i l 9 】吸收两种理论的优缺点，针对三种不同的问题提出了 不同的算法。文献【2 0 j 提出了一种混合启发式优化算法，在建立新的数学模型的基础上， 采用一个三步算法进行求解，首先利用贪婪算法获得一个较好的初始解，然后利用禁忌 搜索进行初步优化，最后利用一个改进的穷举方法( e x a c ti m p l i c i te n u m e r a t i o nm e t h o d ) 进 行优化。文献1 2 l 】利用启发式算法和最小下界条件来解决装箱问题。 d y c k h o f f 对排样问题进行了综述，依据空间维数、排样任务种类、排样材料分类和 排样零件分类等四个特点，建立t样问题的拓于b ( t y p o l o g y ) 模型。7 0 、8 0 年代，随着 智能优化算法如神经网络、遗传算法、禁忌搜索、模拟退火等的不断出现，给解决排样 问题提供了新的思路。9 0 年代后，智能优化算法不断发展，日益成熟，它们在t s p 、装 箱问题、任务调度等组合优化问题得到了成功的应用，体现了智能优化算法的优越性。 这些算法与排样算法相结合解决排样问题正日益成为热门。e h o p p e r 和b t u r t o n 2 2 j 对 遗传算法在排样问题中的应用进行了综述，按照空间维数和排样图形的几何形状对排样 问题进行了分类。对遗传算法中的排样问题编码方法、遗传算子和解码算法进行了讨论； s e g e n r i e c h 和b r a g a 弱j 提出用遗传算法解决零件多件多排问题；文献l z 4 j 提出一种新型的 结合遗传算法和模糊控制的排样算法，利用模糊控制规则来降低遗传算法的适应度函数 值( 该算法中，适应度函数值越小越好) ，可以获得较好的排样效果；文献【2 5 j 提出神经网 络算法，较好地结合了算法和人的智能因素，排样结果较好；文献1 2 6 j 应用模拟退火算法 解决圆形排样问题；文献1 2 7 】应用蚁群算法来求解具有动态条件约束的排样问题：d a g li 1 2 s j 采用神经网络、数学规划和基因算法来求解定宽无限长板材的矩形件排样问题；文献【2 9 j 综合利用启发式算法和遗传算法求解排样问题：文献【3 0 j 提出一种“树形搜索，算法来 解决切割下料问题；文献【3 l j 给出了s a ，g a ，n e ，r a 与不同排样算法结合，对不同问题实例 的综合性能评价的结果，有两点主要结论：复合算法的结果优于单纯排放算法的结果， 并且排放算法效果越好，则复合算法在同等条件下的效果也越好。任何算法都有效果 不佳的算法实例，即使对矩形件排样目前都没有完全有效的排样算法。 我国的计算机辅助排样研究工作开展的比较晚，始于8 0 年代，开始时，一般都集 中在矩形件排样的研究上，出现了许多研究成果1 3 2 q 6 j 主要集中在清华大学、浙江大学、 2 第一章绪论 上海交通大学、华中科技大学和四川大学等高等院校和研究所。至今已经获得了很大的 发展，但是总体上，国内就排样问题研究和国外相比，无论是深度和广度方面，仍然有 很大的差距。进入9 0 年代之后，矩形件排样技术有了进一步的发展。曹炬【37 】提出了一 个利用背包问题解法的矩形件排样的近似优化算法；崔耀东【3 8 j 提出了组块策略，将制造 同一种产品所需各种不规则形状零件套排成大小各异的矩形组块，每一组块包括多个零 件，下料时在整张板上按矩形组块剪切，同一张板上可以排列多个矩形组块；文献【3 9 】 构造了一个近似算法，该算法的主要思想是在排样过程中根据一种局部最优原则不断地 动态产生一些较小的矩形，然后对这些小矩形区域排样，同时也消去一些己经排过的矩 形区域，直至所有的矩形件被排完；文献【4 0 】提出用遗传算法求解矩形件排样问题；文献 1 4 l 】提出一种带预选搜索步深的二维一刀切矩形优化排料算法；李建勇提出分别用混沌人 工神经元网络f 4 2 】和c i i n n 人工神经元网络进行排料优化计算；文献删提出一种基于 c a s e 推理的优化排料算法，主要思想是对每块板材的布局都进行c a s e 推理，选取最佳 布局，若没有相应的c a s e ，则调用启发算法搜索【4 5 1 。 1 3 优化排样问题主要应用领域 在许多行业中，都会遇到材料分割问题。计算机辅助优化排样的作用，就是生成高 利用率的材料分割排样方案，因此，凡是需要进行材料分割的行业，都可以应用计算机 辅助优化排样，达到提高生产率、节约材料、降低成本的目的【4 5 1 。 优化排样的主要应用领域： 服装制造业服装生产过程中的布匹等材料的分割 皮革制品业将大张皮革分割成各种形状的毛坯 木材加工业圆木、方木或胶合板的分割 家具制造业木制家具的胶合板分割 金属家具的型材、管材和板材分割 纸制品业将成卷的纸分割成小块 体育用品制造业制造体育器材的型材、管材和板材等金属材料的分割 塑料制品业塑料板材、型材和棒材的分割 金属制品业模具、金属包装品、金属门窗等金属制品制造过程中，对型材、棒材、 卷材、板材等进行分割 普通机械制造业制造过程中型材、管材的锯切，中厚钢板的气割，金属薄板的剪 切等 交通运输设备制造业铁路运输设备、汽车、电车、船舶、航空航天器等制造行业 的金属材料分割问题 电气机械制造业电机制造业的硅钢片材料，各种金属材料的分割 3 大连交通大学t 学硕十学位论文 1 4 课题的来源及主要研究内容 根据长春客车股份有限责任公司在材料定额的计算与管理上存在与企业生产经营 客观要求不相适应的情况，如新产品大量增加、交货期短、定额计算与管理人员不足等， 使定额计算结果在指导采购、指导生产中的及时性和准确性等方面不能满足要求。长期 以来对原材料消耗定额的计算只能做到大尺寸零件和关键件进行人工排料，尺寸较小， 数量较多的零件按重量换算的办法，加上企业原材料和在制品管理上存在的不足，近年 来随着公司内部体制改革的深化而得以暴露。经对剩余物资的盘查发现明显的材料积 压、浪费，造成大量资金占用，无法参与周转。板材套料优化与定额管理系统是将要加 工的零件进行自动优化排样产生排样图，并计算出所用材料的利用率及原材料的消耗 量，可以很好的指导生产和采购。该系统是解决企业目前所面临问题的有效方法之一。 该论文是对其中的矩形件优化排样进行研究，根据长春客车股份有限责任公司的下料工 艺，将遗传算法应用到矩形件优化排样中，使材料利用率最高，系统寻优效率高，最主 要的是满足实际的生产需要。 论文各章节的内容安排如下： 第一章：绪论。 第二章：在分析矩形件排样问题的基础上，建立了该问题的数学模型，对矩形件优 化排样算法进行了分析。接下来介绍了矩形件优化算法，如启发式算法，模拟退火算法， 遗传算法，伪并行遗传算法，蚁群算法等。然后介绍了几种常用的矩形件排样算法及它 们的优缺点。 第三章：分析了矩形件排样问题影响因素及约束条件。结合长春轨道客车股份有限 公司的板材下料中的具体实例，介绍了几种对矩形件排样问题的主要影响因素，如几何 因素、加工工艺因素和约束条件等。 第四章：介绍了遗传算法的生物学基础，遗传算法的特点与应用，以及基本遗传算 法描述，小生境遗传算法和混合遗传算法。应用遗传算法对矩形件排样问题进行求解， 给出了遗传算法的编码方法、遗传算子、适应度函数的定义和关键参数，以及对具体算 例的求解结果。 第五章：矩形件优化排样系统总体结构的设计以及各模块功能的描述。矩形件优化 排样系统主要包括系统管理、用户管理、数据管理、矩形件优化套料等模块。 第六章：总结与展望。 1 5 论文的创新点 ( 1 )将遗传算法与基于最低水平线的搜索算法相结合。零件的大小差异对此算法 影响不大。 4 第一章绪论 ( 2 )产生的排样结果满足大规模生产中剪板机的工艺要求。如“一刀切 、纹理 要求、安全距离、剪切方向和相同的零件尽可能放在一起。 ( 3 )初始化群体的设计方法。 大连交通大学t 学硕十学位论文 第二章矩形件排样问题的数学模型及优化排样算法 2 1 矩形件排样问题的数学模型 2 1 1 矩形件排样问题的描述 矩形件优化排样问题是指在矩形的板材上，要排放多种不同尺寸的矩形件，如何使 这些矩形件既不互相重叠，又不超出板材边界的条件下，使得材料的利用率达到最高。 矩形件排样优化问题实际上是一个十分困难的问题。从数学的计算复杂性来看，它属于 具有较高计算复杂性的一类问题叫p 完全问题f 4 6 i 。 2 1 2 数学模型 设排样所用的板材的长为l 、宽为w ( 凶) ，板材的数量足以排下所有要排的矩形件。 所有要排的矩形件共有k 种，第i 种矩形件的个数为n 。，长度为l i ，宽度为w ；( 1 i k ) 。 则全部要排的矩形件总数为： k n = 刀， f = 1 ( 2 1 ) 基本目标是：使得排样所用的板材数尽可能少，以提高材料的利用率。排样的基本 约束条件为：矩形零件之间不能有相互重叠的区域，并且矩形件不能有排出板材之外的 部分，满足“一刀切 的工艺要求。排样规则为：每一个矩形件可以被横向排放或竖向 排放。排样方式为：从板材的最左下角开始，排至板材的右上角结束一块板材的排样。 板材左下角的坐标为( o ，o ) 。我们知道一块矩形件在板材上的位置可以由该矩形件的左 上角和右下角的坐标完全确定。设( x l i ，y l i ) ，( x 2 i ，y l i ) 为第i 块矩形件的板材上的左上角 和右下角的坐标( 1 i 9 ) 。则排样的过程就是根据一定的寻优规则，确定每一块矩形件在 板材上的左上角( x l i ，y i i ) 和右下角( x 2 i ，y l i ) 的坐标。在一般的矩形件排样问题中，矩形 件可以有横排或竖排两种方式。因此矩形件的两个坐标之间存在两种关系： i x 2 f = x l f + t ix 2 f = 五，+ w 1y 2 i = y l f 一心卯1y 2 i = 乩一l i ( 2 2 ) 【 = f 一心 【 = y l f 一 诤一7 i = 1 ，n ，前一种关系为横排，后一种为竖排，见图2 1 。 6 第二章矩形件排样问题的数学模型及排样算法 ( x l i ，y 】i ) 增 ( x 2 i ，y 盖) 图2 。1 排样方案 f i g 2 1s c h e m eo fl a y o u t 由此可见，对于决定每一块矩形件的排放，实际上只有三个自由量：x y 。，和决定 矩形件j 横排或竖排的逻辑变量r ，r j = 0 表示横排，r j = l 表示竖排。则( x h ，y t i ) 与( x 2 。， y ：；) 应有下面关系： jx 2 ，= 五f + ( 1 一巧) + w 【y 2 ，= y i ，- ( 1 一巧) 嵋一鹕 ( 2 3 ) 设r t 和r 。为任意两个矩形件，它们对应的左上角和右下角的坐标分别为 0 甜( x 2 t o x o ( 2 7 ) 从上面数学模型可以看到，该优化问题是一个混合不可微的规划问题；在( 2 5 ) 式 中变量x n ，y n 是连续的，r ；，z 。是离散的；函数u ( x ) 是不可微的。总共有4 n 个变量。 对于这类规划问题，目前在理论上还没有有效的求最优解的算法。 2 2 优化排样算法分析 在提出矩形件优化排样算法时，一般有如下一些问题应该加以考虑： ( 1 )板材尺寸与矩形件尺寸的比例不确定之问的矛盾：不同的排样问题，有的问 8 、 打y y_ 、 ：= x一 甜 x ，一 乙 玎：e 觚m 第二章矩形什排样问题的数学模型及排样算法 题的板材尺寸与矩形件尺寸的比例相差很大，有的则相差不大；有的问题矩形零件之间 的尺寸相差很大，有的则相差很小。这些问题影响着算法的适应性，不同的矩形件排样 问题的排样情况并不完全相同。有的算法可能适应于这类问题，有的算法则可能适应于 那类问题。 ( 2 )矩形件种类与数量之间的矛盾：有的排样问题矩形件种类不多，而每类矩形 件要排样数量很多，批量的生产情况往往属于这种情况；而有的排样问题矩形件种类很 多，而每类矩形件要排的数量却很少，非批量生产即是属于这种情况。 ( 3 )优化排样的效率与计算速度和计算时间之间的矛盾：一般情况下，如果一个 优化算法可以获得很高的材料利用率，但需要很长的计算时间，则不能说它是一个好的 算法，因为人们一般不会接受耗用很长时间去等待一个近似的最优结果。实际上人们更 愿意花费不多的时间，先得到一个较好的近似最优解，然后再通过人机交互的方式，对 排样的结果进行少量适当调整。 ( 4 )下料工艺问题：矩形件板材下料工艺可分为直线切割和正交切割，在排样算 法中必须进行考虑。正交切割允许割枪在板材上任意纵横行走，可以节约材料，但正交 切割的成本很高，例如最近兴起的激光切割，价格昂贵；因此传统的剪切加工仍是下料 工艺的主流途径，剪切加工工艺要求对板材通裁通割，即是直线切割下料工艺。在采用 直线切割的同时，算法必须考虑矩形件在板材上的连续性。下料工艺问题将在第三章进 一步介绍。 2 3 矩形件优化算法 矩形件优化实际上是对目标函数求最优解的问题，常用的算法有枚举法、启发式算 法、贪心算法、模拟退火算法、遗传算法、伪并行遗传算法等等。 2 3 1 枚举法 枚举法是枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数， 该方法要求对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另 外，当枚举的空间比较大时，该算法的求解效率比较低，有时甚至在目前最先进的计算 工具上都无法求解。 2 3 2 启发式算法 启发式算法是寻求一种可能产生可行解的启发式规则，以找到一个最优解或者近似 最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有 的启发式规则，这个启发式规则无通用性，不适合其他问题。 9 大连交通大学工学硕士学位论文 2 3 3 贪心算法 贪心算法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进 行，根据某个优化测度( 可能是目标函数，也可能不是目标函数) ，每一步上都要保证 能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个 数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所 有数据枚举完，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处 理方法称为贪心法。 2 3 4 模拟退火算法 在金属热加工工艺中，退火是指将金属材料加热到某一高温状态，然后让其慢慢冷 却下来这样一个金属热处理问题。从统计热力学的观点来说，随着温度的降低，物质的 能量将逐渐趋近于一个较低的状态，并最终达到某种平衡。模拟退火算法( s i m u l a t e d a n n e a l i n g ) 就是基于金属退火的机制而建立起来的一种全局最优化方法，它能够以随 机搜索技术从概率意义上找出目标的全局最小点。 模拟退火算法的构成要素如下： ( 1 )搜索空间：搜索空间也成为状态空间，它由可行解的集合所组成，其中一个 状态x 就代表一个可行解。 ( 2 )能量函数e ( x ) ：能量函数也就是需要进行优化计算的目标函数，其最小点 为所求的最优解。 ( 3 )状态转移规则p ：状态转移规则是指从一个状态x 。( 一个可行解) 向另一个 状态x 。( 另一个可行解) 的转移概率，它与当前的温度参数t 有关。 ( 4 ) 冷却进度比表t ( t ) ：冷却进度表是指从某一高温状态t o 向低温状态冷却时 的降温管理表。假设时刻t 的温度用t ( t ) 来表示，则经典模拟退火算法的降温方式为： t ( t ) = t o i n ( t + 1 ) 而快速模拟退火算法的降温方式为： t ( t ) = t o ( 1 + t ) 这两种方式都能够使得模拟退火算法收敛于全局最小点。 另外，在实际应用中，为计算简便起见，也可以用下式来进行温度管理： t ( t ) = k 木t ( t 一1 ) 式中，k 为略小于1 0 的系数。 模拟退火算法可描述如下： 算法s i m u l a t e da n n e a li n g ( 1 )随机产生一个初始最优点，以它作为当前最优点，并计算目标函数 值。 1 0 第二章矩形件排样问题的数学模型及排样算法 ( 2 )设置初始温度：t = t 0 。 ( 3 )设置循环计数器初值：i = l 。 ( 4 )对当前最优点作一随机变动，产生一新的最优点，计算目标函数值， 并计算目标函数值的增量。 ( 5 )如果 = o ，则以概率p = e x p ( 一a t ) 接受该新产生的最优点为当前最优点。 ( 6 )如果i 小于终止步数，则：i = i + l ，转向第( 4 ) 步 ( 7 )如果未到达冷却状态，则：t = t ( i ) ，转向第( 3 ) 步 如果以达到冷却状态，输出当前最优点，计算结束。 2 - 3 5 遗传算法 基于对自然界中生物遗传与进化机制的模仿，针对不同的问题，很多学者设计了多 种不同的编码方法来表示问题的可行解，开发了许多种不同的遗传算子来模仿不同的环 境下的生物遗传特性。这样，由于不同的编码方法和不同的遗传算子就构成了各种不同 的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、 交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点， g o l d b e r g 总结出了一种统一的最基本的遗传算法简单遗传算法( s i m p l eg e n e t i c a l g o r i t h m s ，简称s g a ) 。基本遗传算法只使用选择算子、交叉算子、变异算子这三种基 本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础， 它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。遗传算法将 在第四章详细介绍。 2 3 6 伪并行遗传算法 在遗传算法的应用过程中，一个比较突出的问题是它容易产生早熟现象 ( p r e m a t u r e ) ，这将严重影响遗传算法的应用效果。另一方面，为了提高遗传算法运行 速度而引入的并行遗传算法，除了提高运算速度外，也有维持群体多样性的能力，从而 有可能抑制早熟现象的发生，但并行遗传算法却一般要运行在并行机或局域网上。而对 于很多无实时性要求的问题，并不需要如此高档的运行环境，我们在微机上利用并行遗 传算法的思想，对简单的遗传算法进行改进，开发出一种伪并行遗传算法，使其具有克 服早熟现象的能力。 在简单遗传算法中，群体是一个不可分割的整体，交叉、变异、选择等遗传算子作 用在整个群体上。由于简单的遗传算法是一种随机的算法，旨在对多个不同的个体来进 行隐含并行寻优的过程，有可能使各个个体在未达到最优点之前就停在某一局部最优 点，而导致其染色体趋于一致。这时产生新个体能力最强的交叉算子不再起作用，从而 大连交通大学工学硕士学位论文 产生早熟现象。为了克服早熟现象，在简单遗传算法中利用并行遗传算法的思想，将群 体划分为一些子群体，各群体按一定的模式分别进行独立进化，在适合的时候，某一些 群体之间交换一些信息。这样可以维持群体的多样性，从而达到抑制早熟现象的效果。 子群体之间信息交换模型采用岛屿模型，踏脚石模型，邻居模型。由于这些子群体并未 在不同的处理器上独立进化，仍是在单处理机上串行的执行，故称之为伪并行遗传算法 ( p s e u d o p a r a l l e l6 e n e t i ca l g o r i t h m s ，简称p p g a ) 。 伪并行遗传算法描述： 算法p p g a ( 1 )遗传代数计数器初始化：t = 0 。 ( 2 )随机产生初始群体p ( t ) ，按信息交换模型划分p ( t ) 为子群体： p ( t ) = p 1 ( t ) ，p 2 ( t ) ，p 3 ( t ) ，p i ( t ) ，p n ( t ) ) 其中，n 为分组数。 ( 3 )分组计算个p i ( t ) ( i = l ，2 ，3 ，1 1 ) 中个体的适应度。 ( 4 ) 对各p i ( t ) ( i = l ，2 ，3 ，n ) 进行分组独立进化： 由选择算子进行复制操作：p i ( t ) ! - s e l e c t i o n p i ( t ) 。 由交叉算子进行交叉操作：p i ”( t ) - - c r o s s o v e r p i ( t ) 。 由变异算子进行变异操作：p i ( t ) ! - m u t a t i o n p i ( t ) 。 ( 5 ) 分组计算个p i ( t ) ( i = l ，2 ，3 ，r 1 ) 中个体的适应度。 ( 6 ) 有信息交换模型进行各p i ( t ) ( i = l ，2 ，3 ，n ) 之间的信息交换， 得到下一代群体： p i ( t + 1 ) ! - e x c h a n g e p i ( t ) ，p i ”( t ) 子群体之间信息交换模型采用岛屿模型，踏脚石模型和邻居模型中的一种。 ( 7 ) 终止条件的判断。 若不满足终止条件，则：t = t + l ，转向第( 4 ) 步： 若满足终止条件，则：输出优化结果，算法结束。 2 2 7 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，又称蚂蚁算法，是一种用来寻找最优解决 方案的机率型技术。它由m a r c od o r i g o 于1 9 9 2 年在他的博士论文中用蚂蚁算法解决经 典的离散组合优化问题中的旅行商问题( t s p ) 、二次分配问题( q a p ) 等，并得出了理想的 结论。蚂蚁算法因其很强的鲁棒性、分布式的计算和比较容易与其他算法工具相结合的 优点而越来越受到人们的关注。 蚂蚁算法是受其真实蚂蚁群体路径寻优方式的启发而提出的。动物学家的观察表 明，蚂蚁在从巢穴去食物源沿途中释放一种叫做信息素( p h e r o m o n e ) 的化学物质，这些信 息素构成信息素的迹( t r a i l ) 。蚂蚁总是依概率根据沿途信息素迹的大小来选择路径，信息 1 2 第二章矩形件排样问题的数学模犁及排样算法 素的迹大的路径，被选择的概率也就大。设想有一只蚂蚁随机选择了一条较短的路径， 那么，它就能在较短的时间回来，并在该条路上留下信息素。而这些信息素又会吸引其 它蚂蚁也选择这条路径，从而，在最短路径上遗留的信息素越来越多，选择该路径的蚂 蚁也就越来越多，这就是蚂蚁算法的正反馈过程。另一方面，信息素会随着时间的推移 而挥发( e v a p o r a t e ) ，较长路径上的信息素由于难以得到加强而越来越少，最终完全消失。 2 4 矩形件优化算法的优缺点 ( 1 )枚举法，当枚举的空间比较小时，这种方法很有效，能够快速的找到最优解； 当枚举的空间比较大时，该算法的求解效率比较低，有时甚至在目前最先进的计算工具 上都无法求解。 ( 2 )启发式算法与贪心算法，算法比较简单，比较容易实现，但是该种算法找到 最优解的概率比较小，其结果可能甚至相当差，当大批零件排样时，材料的浪费可能很 严重；该种算法只能找出一种方案，而不能找出一批较好的结果供选择，而且这些算法 无通用性。 ( 3 )模拟退火算法，模拟退火算法具有较强的局部搜索能力，并能使搜索过程避 免陷入局部最优解，但模拟退火算法却对整个搜索空间的状况了解不多，不便于搜索过 程进入最有希望的搜索区域，从而使得模拟退火算法的运行效率不高。 ( 4 )遗传算法，遗传算法的全局搜索能力比较强，找到最优解的概率比较大，具 有很强得鲁棒性，很适合求解组合优化问题，有可能发生早熟现象，但是如果合理的设 计初始群体可以避免早熟现象的发生。 ( 5 )伪并行遗传算法，伪并行遗传算法除了具有基本遗传算法的特点外，提高了 算法的运算速度，有维持了群体的多样性的能力，抑制了早熟现象的发生，但是实现起 来比较复杂。 ( 6 )蚁群算法，蚁群算法与其它算法相比，在求解性能上，具有很强的鲁棒性； 具有很强的通用性，只要稍加修改就可以应用到其他领域。但该算法存在收敛速度慢， 易出现停滞，以及全局搜索能力较低的缺陷。 2 5 矩形件排样算法 矩形件排样算法是指将多种不同尺寸的矩形件按照一定的规则排放在板材上的过 程。对于利用遗传算法对矩形件进行优化排样的排样算法是指将一个优化完的排列( 数 字串) 转化成其对应排样图的过程。 2 5 1 剩余矩形匹配法 剩余矩形匹配算法是一种动态的局