（计算机应用技术专业论文）智能优化排料方法研究.pdf

硕士论文 智能优化排科方法研究 摘要 二维不规则排料问题是指，将一系列形状各异的待排件排放在给定材料上，找出使 材料的利用率最高的方案，减少原材料的浪费。排料优化问题是n p 完全问题，在许多 工业制造和生产领域都有着重要的应用，也是研究的热点。 本文给出了二维不规则排料的分层实现：最上层是负责排料布局过程整体优化的智 能优化算法，它确定了各个不规则待排件的排放次序、旋转角度和镜像方式；接着是负 责排料组织工作的启发式b l f 算法，它将排放次序、旋转角度和镜像方式确定了的不规 则待排件逐个放入面料，进行排放；然后是不规则待排件的并靠判交算法以及负责实现 不规则待排件面积计算、旋转、镜像、移动等操作的几何计算算法；最底层是不规则待 排件的几何表达方法，即栅格水平线扫描区间表示法。对每层一一进行了实现和阐述。 对于负责排料过程整体优化的智能优化算法，本文选取了遗传算法、模拟退火算法、 遗传模拟退火算法和粒子群优化算法应用n - 维不规则排料问题中。将一种基于惯性权 值凹函数递减策略的粒子群优化算法引入优化排料领域，与基于惯性权值线性递减策略 的粒子群优化算法相比较，提高了面料利用率。针对在迭代后期容易陷入局部最优这一 现象，本文提出了一种改进的基于粒子位移邻域变异的粒子群优化算法，与惯性权值递 减策略相结合，形成基于粒子位移邻域变异惯性权值递减策略的粒子群优化算法，并将 之应用到排料过程，与两种基于惯性权值递减策略的粒子群优化算法对比，提高了面料 利用率。最后对各智能优化算法在排料中的应用效果进行了多次实验，展示了排料效果 图，对实验数据进行定量对比分析，得出如下结论：( 1 ) 智能优化算法的排料效果均优 于启发式直接排料；( 2 ) 智能优化算法中粒子群系列算法和模拟退火算法在排料效果上 都比较好。模拟退火算法迭代过程完成后有时会取得非常好的效果，但也会有比较差的 结果出现，这种情况随着迭代次数的增加有所改善；而粒子群系列算法在每次迭代完成 后表现都很稳定，效果也好；( 3 ) 综合来看，基于粒子位移邻域变异惯性权值凹函数递 减策略的粒子群优化算法排料效果最好。 关键词：不规则排料，遗传算法，模拟退火，粒子群优化，邻域变异，启发式b l f a b s t r a c t g i v e nas e to fi r r e g u l a rs h a p e s ，t h et w o d i m e n s i o n a li r r e g u l a rn e s t i n gp r o b l e mi sap r o b l e m o fp a c k i n gt h es h a p e sw i t h i nas h e e ta n dt r y i n gt of r e dt h eb e s ta r r a n g e m e n tt h a tc o u l d m a x i m i z et h eu t i l i z a t i o no fm a t e r i a l s ，a n dm i n i m i z et h ew a s t a g eo fr a wm a t e r i a l s t h e p r o b l e mi sn p h a r de v e nw h e n t h es h a p e sa n dt h em a t e r i a li n v o l v e da r er e c t a n g l e s i ti m p a c t s u p o naw i d ev a r i e t yo f i n d u s t r i a la p p l i c a t i o n sa n dm o t i v a t e sm a n ya r e a so fr e s e a r c h t h i sp a p e rg i v e sag e n e r a lv i e wo ft h ei r r e g u l a rn e s t i n gp r o c e d u r eb yd i v i d i n gi ti n t o s e v e r a ll a y e r s t h et o p 1 e v e li st h ei n t e l l i g e n to p t i m a la l g o r i t h m s t h e ya r ei nc h a r g eo ft h e o v e r a l le f f e c to ft h en e s t i n gp r o c e d u r eb yw a y so fg e n e r a t i n gt h eb e s tn e s t i n go r d e r ，r o t a t i n g a n g l ea n dm i r r o r i n gw a yo fe v e r yi r r e g u l a rs h a p e t h en e x t o n ew o u l db et h eb o t t o m l e f t - f i l l h e u r i s t i ca l g o r i t h mw h i c ho r g a n i z e st h en e s t i n gp r o c e d u r e ，p u t t i n gt h es h a p e so n t ot h es h e e t o n eb yo n eu s i n gb l fs t r a t e g y w h a tc o m e sn e x ta r et h ea l g o r i t h mf o rj u d g i n gw h e t h e rt h e s h a p e si n t e r s e c tw i t he a c ho t h e r , a n dt h ec o m p u t a t i o n a lg e o m e t r ym e t h o d sf o ri r r e g u l a r p o l y g o n ss u c ha sc a l c u l a t i n ga r e a , r o t a t i n g ，m i r r o r i n g ，a n ds h i f t i n g t h eb o t t o ml a y e ri st h e g e o m e t r i cr e p r e s e n t a t i o nm e t h o df o ri r r e g u l a rs h a p e s ，a p p r o x i m a t i n gt h ei r r e g u l a rs h a p e sb y h o r i z o n t a ls c a n - l i n e s ，a n dr e p r e s e n t i n gt h e mb ys e t so fi n t e r v a l s w 油r e g a r d t ot h ei n t e l l i g e n to p t i m a la l g o r i t h m si nc h a r g eo ft h eo v e r a l ln e s t i n gp r o c e s s ， t h i sp a p e rs e l e c t st h eg e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h m ，g e n e t i cs i m u l a t e d a n n e a l i n ga l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mt og e n e r a t et h eb e s tn e s t i n g o r d e r , r o t a t i n ga n g l ea n dm i r r o r i n gw a yf o re v e r yi r r e g u l a rs h a p e s b e s i d e s ，t h ep a p e r i n t r o d u c e sat w o - d i m e n s i o n a li r r e g u l a rs h a p e sn e s t i n gp r o c e s sb a s e d o nac o n c a v e f u n c t i o ns t r a t e g yf o rd e c r e a s i n gi n e r t i aw e i g h ts w a r mo p t i m i z a t i o na l g o r i t h m t oa v o i dt h e p r o b l e mo ft r a p p i n gi n t ol o c a lo p t i m u m a tt h ee n do ft h ei t e r a t i v ep r o c e s s ，t h i sp a p e rp r o p o s e s a ni m p r o v e ds w a r mo p t i m i z a t i o na l g o r i t h mb a s e do n ak i n do fs w a r mp o s i t i o nn e i g h b o r h o o d m u t a t i o n , a n da p p l i e si tt ot h en e s t i n gf i e l dw i t ht h ec o m b i n a t i o no ft h ed e c r e a s i n gi n e r t i a w e i g h ts t r a t e g y c o m p a r ew i t ht h eo t h e rt w od e c r e a s i n gi n e r t i aw e i g h ts w a r mo p t i m i z a t i o n a l g o r i t h m s ，t h i so n eb r i n g so u tah i g h e rm a t e r i a lu t i l i z a t i o n r a t e f i n a l l ye x p e r i m e n t sa r em a d et oc o m p a r ea n dq u a n t i t a t i v e l ya n a l y z et h ed i f f e r e n tr e s u l t s o ft h e s ei n t e l l i g e n to p t i m a la l g o r i t h m s ，a n dt h ec o r r e s p o n d i n gc o n c l u s i o ni s d r a w na s f o l l o w i n g ：( 1 ) t h en e s t i n gr e s u l t so fi n t e l l i g e n to p t i m a la l g o r i t h m sa r ea l lb e t t e rt h a nt h o s eo f t r a d i t i o n a lh e u r i s t i ca l g o r i t h m ；( 2 ) a m o n gt h ei n t e l l i g e n to p t i m a la l g o r i t h m s ，b o t ht h ep a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h mc o u l dg i v eas a t i s f y i n g 硕士论文 n e s t i n gr e s u l t f o rt h es i m u l a t e da n n e a l i n ga l g o r i t h m ，p e r f e c tr e s u l t sh a p p e no c c a s i o n a l l y , a n d s od ob a do n e s n e v e r t h e l e s s ，t h er e s u l t sw i l lg e n e r a l l yg e tb e t t e rw h e ni t e r a t i o ni n c r e a s e s a s f o rt h ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m s ，t h e yp e r f o r ms t a b l ye a c ht i m ea f t e rt h e i t e r a t i o n s ，w i t hr e m a r k a b l yg o o de f f e c t s ；( 3 ) a l li na l l ，t h ep a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h mb a s e do nt h ec o n c a v ef u n c t i o ns t r a t e g yf o rd e c r e a s i n gi n e r t i aw e i g h tw i t hs w a r m p o s i t i o nn e i g h b o r h o o dm u t a t i o nh a st h eb e s tn e s t i n gp e r f o r m a n c e k e yw o r d ：i r r e g u l a rn e s t i n g , g e n e t i ca l g o r i t h m ，s i m u l a t e da n n e a l i n g , p a r t i c l es w a r m o p t i m i z a t i o n ，n e i g h b o r h o o dm u t a t i o n , b o t t o m l e f t f i l lh e u r i s t i ca l g o r i t h m i v 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除t 3 u 以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：年月 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：年月日 硕士论文智能优化排料方法研究 1 绪论 计算机图形学及相关技术的发展，使得计算机有了处理和显示图形的能力，从而为 计算机辅助设计系统的发展奠定了基础，并逐渐在航空航天、汽车制造、电子等各个领 域研制成功，并推广使用。 排料作为制造业生产过程中提高材料利用率，减少材料损失，降低生产成本的重要 途径，从一开始就是计算机辅助设计系统不可或缺的组成部分。排料问题属于典型的 n p 完全问题，即对其求解时的时间复杂度是指数阶的。在问题规模比较大时，往往因 为计算时间剧增而丧失可行性，所以必须找寻其它可行的方案。 智能优化算法是人们受自然界或生物界规律的启发，根据自然界或生物界的原理， 模仿其规律而设计的求解问题的算法【l 】。在优化组合问题上，它能够在合理时间合理空 间内给出一个较好的解。近年来随着计算能力的提高，智能优化算法如神经网络、遗传 算法、模拟退火、粒子群优化等算法不断发展成熟，给解决排料问题提供了新的思路。 1 1 优化排料研究背景和意义 排料在工业生产制作过程中地位重要，工序又比较繁琐，而排料的材料利用率将直 接关系到企业产品的成本和经济效益。因此，一个高效的自动排料系统不仅能有效地降 低排料人员的工作强度，而且会大大提高排料速度和材料利用率，同时也给企业带来可 观的经济效益l z j 。 优化排料问题就是将一系列形状各异的图形排放在给定的材料上，找出这些不规则 图形的最优排布，使得给定材料的利用率最高，以达到节约材料，提高效益的目的。排 料问题在工业生产中应用十分广泛，纸张及木材加工业、服装生产业、造船、钣金加工、 汽车工业、皮革加工等都需要处理排料问题。它在工业生产中占有非常重要的地位，并 与经济效益有直接关系。排料效果好，就能提高材料利用率，减少生产原料的浪费。排 料优化已成为降低产品成本，提高产品竞争力的主要手段之一。而且因为排料结果的好 坏直接影响到后续加工过程，所以排料是工业生产过程中的一个非常重要的环节。 排料问题根据不同的分类标准可以分为很多类。狭义排料问题按维数来分，可分为 一维排料、二维排料、三维排料和多维排料问题。其中二维排料问题按待排件形状来分， 可分为规则排料和不规则排料问题。要实现排料优化就要解决两个问题：一是如何将它 表示成数学模型；二是如何根据数学模型，尽快地求出最优解，其关键就是算法问题【3 1 。 国内外研究学者就优化排料问题开展了广泛深入的研究。从上个世纪四十年代以 来，人们便尝试着提出各种理论，设计不同的计算方法来解决优化排料问题。而优化排 料问题，尤其是不规则图形的优化排料问题，一直没有很好的解决方案。传统的解决方 l 绪论硕士论文 法，只考虑待排件的一种排料顺序，因此通过它们得出来的结果往往不尽人意。而智能 优化算法因其所自身的特点，为那些传统优化技术难以处理的排料优化问题提供了新的 可行解决方案。所以把智能优化算法引入排料优化问题有着良好的应用前景。 研究优化排料问题有着重要的意义： ( 1 ) 排料问题在工业生产中应用十分广泛。若排料问题有改进，就会惠及工业生产 的各个领域。 ( 2 ) 排料问题在工业生产中占有非常重要的地位并与经济效益直接挂钩。生产原料 的费用在产品的成本中占有较大的比例，因而如何提高材料利用率，减少生产原料浪费 便成为降低产品成本，提高产品竞争力的主要手段之一。而排料目标正是：在满足一定 的约束条件下合理、有效地布置以求最大限度地利用材料。企业在进行大量生产时，材 料利用率若有稍微提高，带来的经济效益也会相当可观。能否合理地利用材料，降低损 耗，将直接影响企业经济效益和市场竞争能力。 ( 3 ) 排料是工业生产过程中的一个重要环节。排料结果的好坏直接影响到后续的流 程。 综上，研究和解决优化排料问题具有深远的理论意义及现实意义。 1 2 优化排料研究历史与现状 由于优化问题的普遍存在，加上行业的激烈竞争，所以广大专家和学者对于优化排 料的学术兴趣有增无减，优化排料的研究一直受到人们的广泛重视。 最早关于排料的文章是前苏联人k a n t o v o r i c h 在1 9 3 9 年发表的【4 j ，讨论一维排料问题。 一维排料问题，是指在排料时只需要考虑一个方向的尺寸。例如，将较长的型材、钢管 等，分割成各种较短长度，用于生产或者再出售。g i l m o r e 和g o m o r y 早在1 9 6 1 年就一维 和二维排料问题做了系统研究，用线性规划解决了一维优化排料的问题，并发表了四篇 著名的文章【5 】【6 】【7 】【8 1 。 d y c k h o f f l t 9 】对排料问题进行了综述，依据空间维数、排料任务种类、排料材料分类 和排料零件分类等四个特点，建立了排料问题的拓扑模型。 二维排料问题可分为规则排料问题，即待排件是矩形的排料问题和不规则排料问 题。由于规则排料问题的几何学复杂度要低一些，规则排料可以直接应用于矩形件排料， 而且也可以作为解决不规则排料问题的基础，所以一直是众多学者研究的热点。 2 0 世纪9 0 年代以前，对矩形件排料的求解以各种近似方法为主。h o p p e r 和t u r t o n 1 0 1 对矩形件排料问题的以往工作做了总结和回顾。对于矩形件排料的几个基准样例，已知 的最好结果是f 1 3 b u r k e ，k e n d a l l 和w h i t w e l l 【l l j 阐述和实现的b e s t 丘t 启发式算法。 启发式方法因其易于融合各种限制条件和具体目标，在实际生产排料中起着重要的 作用。y a n a s s e 【1 2 】提出依优先级次序的启发式排料算法，算法的主要思想是根据排料零 2 硕士论文 智能优化排料方法研究 件的物理属性( 长、宽、面积) 等给出一定的优先级规则，零件按照这种优先级规则排序， 从面料的左下角开始按次序排放每一个零件。d a g l ic h 1 3 1 结合人工智能与运筹学方法， 提出了基于知识求解矩形件、异形件排料问题的系统概念模型。s c h o l l m e y e rm ，l i nj q 和k r i s h n a m u r t h yk 【1 4 】采用来自有经验的排料师的启发式规则以及冲孔、剪床下料等限 制条件存储在知识库中的方式，指导模型生成图案组合。 不规则排料问题在几何学上更为复杂，对计算能力的要求也更高。d o w s l a n dk a 和 d o w s l a n dw b 1 5 】对不规则排料问题的以往工作和方法作了总结和回顾。对于不规则排 料的几个基准样例，已知的最好结果可以在文献 1 6 】和文献 1 7 】中找到。 最早的关于不规则排料问题的研究工作来自a l b 锄。和s a p u p p o 【1 8 1 ，他们将待排件轮 廓简化以降低排料过程的几何学复杂度，利用临界多边形和b l 排料策略来实现排料功 能。临界多边形就是与多边形接触但是没有重叠的邻接多边形。排料问题的关键算法就 是寻找多边形之间排列最紧密的n f p 位置。这是a r t 【l9 j 提出临界多边形想法之后临界多 边形这个名词第一次使用。b l a z e w i c z ，h a w r y l u k 和w a l k o w i a k 【2 0 】延伸t a l b a n o 和s a p u p p o 的工作。他们使用了b l f f l 料策略，排放时首先尝试嵌套排放在先前所形成的空白处， 使用禁忌搜索的方法来实现将一个待排件嵌套排放。他们也提出了需解决的主要问题是 如何定义检测排料过程待排件移动可行性的算法。 2 0 世纪9 0 年代后，随着智能优化算法( 如遗传算法、模拟退火、粒子群优化、神经 网络等方法) 的日益成熟及其在t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 、空间分配、任务调度 等组合优化问题方面的成功应用，这些算法与传统排放算法相结合被用于排料问题的求 解。 m a r q u e s ，b i s p o 和s e n t i e i r o 2 1j 利用网格近似不规则待排件来降低排料过程的复杂 性，并与模拟退火算法相结合，用马尔可夫链来控制压缩；o l i v e i r a 和f e r r e i r a 2 2 1 讨论了 对于不规则排料优化问题的两种方法。这两种方法都是基于模拟退火算法的。第一种方 法的待排件是用光栅表示法来表示的。这种近似法虽然能够产生快速的解决方案但是亦 会有精确度上的损失。第二种使用了基于多边形的待排件表示方法，用d f u n c t i o n s ( k o n o p a s e k ：1 9 8 1 ) 团j 来解决待排件重叠问题。两种方法都允许待排件重叠，然后用评价 函数来进行甄别和筛选。整个算法的目标就是把重叠降到零，并允许根据降温策略可能 有的差的移动。结果是第一种产生不了没有重叠的可行解，第二种实现能够产生可行解， 但是执行时间比第一种慢五倍。o i g h e 和j a k i e l a 2 4 】扩展t s m i t h 【2 5 】的工作。他们设计了 复杂的遗传算法的染色体来表示不规则多边形，能够排料过程中避免待排件的重叠，显 著改善了性能。他们这种两层的方法能够产生有效和紧密的待排件布局，然后遗传算法 会从一个树结构中搜索出最佳的布局方案。评价标准是布局的最小包络矩形的面积。 j a k o b s 【2 6 l 的工作应用于钢板冲压工业。他在b a k e r ，c o f f m a n 和r i v e s t 2 7 1 对矩形件排料 的基础上，使用遗传算法对其进行改进。随后，又将其应用到不规则多边形上。他的方 l 绪论 硕士论文 法是计算不规则多边形的最小包络矩形，并运用矩形件排料方法进行排料。b o u n s a y t h i p 和m a o u c h e 2 8 1 使用了进化算法来改善f u j i t a ，a k a j i 和h i r o k a w a 2 9 】的实验结果。整个排料 过程也是分为两个层次：第一层寻找两个待排件组合的最小包络矩形；第二层使用进化 算法通过树搜索来寻找可能的组合。r a t a n a p a n 和d a g l i1 3 0 1 描述了改进的近似方法，用来 降低执行时间。 h o p p e ri t 7 l 是第一位将以往各种文献中的测试样例收集并且对所有收集的样例尝试 产生结果的人。他将遗传算法与b l 、b l f 结合起来，应用到矩形件和不规则待排件的排 料问题上。他的文章包含了许多其他作者使用的方法的信息。除了测试前人的问题样例， h o p p e r 还增加了九个新的基于多边形的测试样例。它们是随机产生的凹多边形和凸多边 形，数量从1 5 至1 j 7 5 不等。 h o p p e re 和t u r t o nb 【1 0 l 对不同问题实例的综合性能进行了评价，有两点主要结论： ( 1 ) 复合算法的结果优于单纯排放算法的结果。并且排放算法效果越好，则复合算法在 同等条件下的效果也越好。( 2 ) 任何算法都有效果不佳的算法实例，即使对矩形件排料 目前也没有完全有效的排料算法。 国内对于排料问题的研究晚于国外，始于2 0 世纪8 0 年代，主要集中在高等院校和研 究所。冲裁件排料问题从2 0 世纪8 0 年代开始研究，以华中科技大学、上海交通大学的工 作最有代表性，主要有人机交互法、边界加密方法和不相交判别法等 3 1 】，借助人机交互 方式进行图形的旋转和平移以达到优化排料的目的。多采用将零件处理为多边形的方法 或采用碰撞算法直接对冲裁件进行排料。 对规则排料问题的研究始于2 0 世纪9 0 年代。主要采用启发式算法，动态规划、整数 规划方法，遗传算法，模拟退火算法进行求解 3 2 1 。崔耀东和周儒荣【3 3 1 研究了单一尺寸矩 形件的排布：许超和金霞【3 4 】对特定设备下料排料进行了分析；四川大学对多个排料问题 进行了求解分析后发现矩形件的排料问题适宜用模拟退火算法求解，选定一组合理的 参数，可以在较短的时间内得到近似最优解。但是考虑到任何算法都难以保证总能得到 最优解，最好采用启发式算法、遗传算法、模拟退火算法等多种方法分别求解再从多种 较优方案中择优选用【3 5 】；须文波和刘瑞杰【3 6 j 提出一种基于a n t q 的矩形件优化排料算法； 华中科技大学提出了一种将填充算法和遗传算法相结合的优化排料方法。该方法应用填 充算法对遗传算法作预处理，使矩形件排料适用于“一刀切”的下料工艺，并克服了填 充算法局部搜索的缺点，使搜索空间由一点扩大为多点，最终可获得总体最优的排料结 果【3 7 】；李爱平，张丰和刘雪梅【3 8 】提出了一种基于包容矩形的优化排料算法及实现。 9 0 年代后期，国内学者开始对不规则排料问题进行研究。苏英慧和金一庆【3 9 】在基于 人工智能的启发式搜索方法的基础上提出了一种自动排料算法。该算法通过生成轮廓多 边形，根据材料利用率来确定一种鞋片的选取和定位规则，完成鞋片在样板上的自动排 放；顾振华和何援军等【4 0 】采用轨迹线算法、自适应最低重心规则和遗传算法，解决了不 4 硕士论文 智能优化排料方法研究 规则图形的计算机辅助排料问题；刘心雄 2 1 提出种基于人工智能的自动排料算法，该 算法运用问题归约理论，将自动排料的过程简化为基本块的生成与搜索，运用规则判断 与启式搜索的方法，生成基本块，对系统中大片、小片( 衣片) 进行自动判断分组，从加 快了运算速度。 一些学者尝试将人工智能的方法和传统的启发式算法相结合，形成智能优化算法， 它属于概率优化技术，即以最小浪费率为目标，在解空间中搜索。南京化工大学利用遗传 算法开发了计算机辅助排料系统【4 1 】；东北大学用自组织人工神经网络作为解决二维不 规则零件排料的方法，排料速度快，并增加了处理样条和处理零件内轮廓区域的功能， 以满足工程实际的基本需要 4 2 1 ；清华大学则针对非连续冲裁开发了优化排料系统，工作 原理是利用模拟退火算法，采用形状滑移技术，通过不断地求出重叠面积和逃越面积， 并对目标函数进行惩罚，以求出最优排料布局【4 3 】。这些算法还不太适合用于二维不规则 排料的一般问题，因为算法的效率很大程度上依赖于待排件几何形状的规则程度，在 形状比较规则的情况下算法的效率才比较高。因此，浙江大学提出了一种与几何形状无 关的启发式排料算法，然后进一步结合遗传模拟退火算法的全局概率寻优能力，有效 地实现二维不规则形状零件的计算机自动排料h 4 。 与国外相比，国内关于排料问题的研究在深度上和广度上都有差距，好在很多学者 已经意识到该问题的研究价值，目前排料问题已成为国内学者研究的一个热点。 1 3 优化排料问题的发展趋势 尽管人们对排料问题进行了大量研究，并取得了一些成果，但一直没有找到通用的、 标准的解决方法。随着计算机图形学、优化技术等相关技术的发展，对排料问题的研究 也在不断深入。结合目前的研究成果，今后对优化排料的研究有如下趋势： ( 1 ) 在不规则排料领域，研究高效的排料算法，结合人工智能、计算机图形学、图 像识别、专家系统等多领域知识，希望能达到模拟人工排料的效果。因为目前，所有的 自动排料算法都不如人工交互排料的效率高，效果好。计算机本身具有高速计算能力， 如果也能做出某些类似直觉的判断，那么两者结合，将可以在优化排料领域做出突破性 的贡献。 ( 2 ) 把已经成熟的算法恰如其分地应用到实际问题中去。 算法本身是固定的，但是，算法在实际问题中的应用却是多样化的。如何把已经成 熟稳定的算法更好地和实际应用结合，如何让算法在解决实际问题的时候更加高效，如 何让算法在具体问题中运行过程更稳定，如何让算法减少具体问题中的运行时间，这些 都是算法研究者们讨论的重要课题。 ( 3 ) 提高搜索效率。 算法的搜索路径是随机的，它在运行中没有固定的搜索轨迹，任何人都不会知道此 s l 绪论 硕上论文 时搜索点在解空间中的位置。比如智能优化算法中的随机产生种群，按概率随机进行进 化，每次运行都不一样。因此，如何控制搜索的方向，让其更快的步入最优状态就成为 专家学者的研究重点。 ( 4 ) 多种算法有效结合，形成更高效的新算法。 每一种算法都有自己固有的优点和缺点。分析各个算法，如果能合理地把各个算法 的优点取出，互相取长补短，将之有机的结合在一起，那么融合的新算法将采众家之长， 其求解问题的能力应会较之提高。 ( 5 ) 面向制造【4 5 】，使优化排料更能适应满足真正的生产需求。 2 1 世纪以后的制造业，很多被要求以批量生产的时间和成本去生产出个性化的产品， 更能贴合顾客的需要。因此，开发符合真正生产需求的优化排料系统必须面向制造，即： 在产品设计时就和排料联系起来，在设计时把产品的各个部分信息以及后续工序的信 息存入特定数据库以供排料时使用，提高产品的生产效率和质量；将具体的工艺约束 和排料联系起来，在各个不同具体工艺约束的基础上建立排料模型，既能反映产品特点， 又能满足工艺要求要求，然后生成可直接用于排料的二维平面展开图。 1 4 本文的主要工作 二维不规则排料问题在工业制造领域应用非常广泛，二维不规则排料材料利用率的 提高对制造企业降低成本，增加利润至关重要。然而目前二维不规则排料问题比较复杂， 计算量也大，对它的研究并不十分完善。本文给出了二维不规则自动排料问题的分层实 现：最上层是负责排料布局过程整体优化的智能优化算法，它确定了各个不规则待排件 的排放次序、旋转角度和镜像方式；接着是负责排料组织工作的启发式b l f 算法，它将 排料次序、旋转角度和镜像方式确定了的不规则待排件逐个放入面料，进行排放；然后 是不规则多边形的并靠判交算法以及负责实现不规则多边形面积计算、旋转、镜像、移 动等几何操作的几何计算算法；最底层是不规则待排件的几何表达算法，即栅格水平线 扫描区间表示法。对每层一一进行了实现和阐述。 根据实际需要，在各智能优化算法的基本框架上，给出了遗传算法、模拟退火算法、 遗传模拟退火算法和粒子群优化算法在二维不规则排料中的具体应用。将一种基于惯性 权值凹函数递减策略的粒子群优化算法引入优化排料领域，与基于惯性权值线性递减策 略的粒子群优化算法相比，提高了面料利用率。针对在迭代后期容易陷入局部最优的这 一现象，本文提出了一种改进的基于粒子位移邻域变异惯性权值递减策略的粒子群优化 算法，并将之应用到排料过程，与两种惯性权值递减粒子群优化算法相比，提高了面料 利用率。 最后对各智能优化算法在排料中的应用效果进行了多次实验，展示了排料效果图， 对实验数据进行定量对比分析，得出如下结论： 6 硕士论文智能优化排料方法研究 ( 1 ) 智能优化算法的排料效果均优于启发式直接排料； ( 2 ) 智能优化算法中粒子群优化系列算法和模拟退火算法在排料效果上都比较好。 模拟退火算法一次迭代过程完成后有时会取得非常好的效果，但也会有比较差的结果出 现，这种情况随着迭代次数的增加有所改善；粒子群系列算法在每次迭代完成后表现都 很稳定，效果也好； ( 3 ) 综合来看，基于粒子位移邻域变异惯性权值凹函数递减策略的粒子群优化算法 排料效果最好。 1 5 本文的组织结构 本文的主要内容按章节安排如下： 第一章绪论 引入了优化排料的概念，介绍了优化排料问题的研究背景和研究意义，归纳了优化 排料问题的国内外研究历史和现状，预测了优化排料问题的发展趋势。 第二章二维排料问题 介绍了二维排料问题的分类，建立了二维排料问题的数学模型，并按照分类给出了 应用于二维排料问题的常用方法。 第三章二维不规则排料的表达方法和排放策略 对于二维不规则排料问题，从最底层开始，首先给出了待排件和面料的记录形式、 几何表达方法以及待排件的几何计算算法和并靠判断算法，然后描述了基于b l f 和栅格 水平线扫描区间表示法的启发式排放策略，给出了排放算法的实现步骤。 第四章智能优化算法在二维不规则排料中的应用 在二维不规则排料问题的数学模型上，介绍了研究遗传算法、模拟退火算法、遗传 模拟退火算法、粒子群优化算法的原理，提出了一种改进的基于粒子位移邻域变异的粒 子群优化算法，并将各智能优化算法应用n - 维不规则排料中。针对实际问题确立了解 空间的结构和各参数的选择，设计了适应度函数以及各种算子，给出了各个智能优化算 法的总体步骤。 第五章实验结果与分析 对所采用的测试样例进行了简要介绍，给出直接启发式b l f 排料布局以及各智能优 化算法排料布局数值结果和对比曲线，根据结果和曲线对各个算法进行了对比分析。 第六章总结与展望 论文的总结，并指出了进一步的研究方向与工作。 7 2 二维排料问题研究 硕士论文 2 二维排料问题研究 2 1 二维排料问题分类 根据待排件的不同形状，二维排料问题大致可分为两类： 第一类是规则排料问题，即待排件为矩形。矩形件排料就是在给定的矩形材料区域 内找出矩形待排件的最优排布，使得材料利用率最高。由于规则排料问题的几何学复杂 度要低一些，可以直接应用于矩形件排料，而且也可以作为解决不规则排料问题的基础， 所以一直是众多学者研究的热点。 在实际的工业生产中，由于不同行业的生产加工设备不同，排料切割的方法也不同， 因此对排料也有着不同的约束。生产过程中的排料切割大致有两种方式：一种是“一刀 切 ，即直线切割方式，是指每一次切割都要从面料的一端直线切割到另一端；另一种 切割方式是“非一刀切 ，又称为正交切割，每一次切割虽然也要保持与面料的一个边 线平行，但不一定要切断到面料的另一端。“非一刀切 比一刀切材料利用率高，但切 割复杂，费时也多。 第二类是不规则排料问题。不规则排料问题在几何学上更为复杂，对计算能力的要 求也更高。二维不规则排料问题就是在给定的面料上找出待排件的最优布局，即将给定 的一系列二维不规则待排件排放在面料上，使得面料的利用率最高，并满足特定的约束 条件：( 1 ) 任意两个待排件互不重叠；( 2 ) 任意一个待排件不能超出面料的范围，必须 放在面料内；( 3 ) 满足其它一些特定的工艺要求。 二维不规则排料问题的复杂性主要是由待排件和面料的形状任意，以及待排件不同 的排放次序和旋转角度等问题组合构成的。正因为如此，待排件之间的并靠、判交等运 算也变得麻烦和复杂，计算量很大。产生的多种不同排料布局的计算、判别和选择也会 导致计算量的增大。按照面料的形状来分，二维不规则排料问题又可分为两类：面料是 规则形状( 矩形) 和面料是任意形状。当然第二类会更加复杂，计算量也更大。 不规则排料的方法可以分为三大类：( 1 ) 以矩形件排料为基础的方法。对不规则待 排件，首先求解待排件的最小包络矩形，将不规则待排件转化为矩形件，然后用矩形件 相关排料算法进行求解；( 2 ) 以计算几何和计算机图形学为基础的排料算法。它把一系 列待排件和面料都作为图形来处理，待排件的定位和判交等操作均用相关知识来处理。 ( 3 ) 以智能优化算法负责全局优化。智能优化算法一般与第一、第二种方法配合使用。 本文采用了以计算几何和图形学为基础的启发式方法与智能优化算法综合运用，即 图形的栅格水平线扫描区间表示法、启发式b l f f l 放算法与遗传算法、模拟退火算法、 遗传模拟退火算法和粒子群优化算法的结合，以期达到提高材料利用率的效果。 8 硕士论文智能优化排料方法研究 2 2 二维排料问题的数学模型 要解决二维优化排料问题，首先应该将待排件的合理排放以节省材料的问题用合适 的数学模型来描述，并确定变量，列出目标函数和有关约束条件。在此为了处理的方便， 只考虑多边形形状，其它不规则形状的图形可以通过离散化转化为多边形来求解。可以 将面料设为宽度固定，长度不固定的矩形与一些制造领域的卷状面料对应，也可以将面 料设为宽度和长度均固定的矩形。依据本文的方法，面料还可以扩展为带孔洞的不规则 形状。如果将不规则待排件排放在矩形面料上，那么只需要三个参数便可以确定待排件 在面料上的位置。这三个参数是：不规则待排件的基准点在面料上的横纵坐标 ，y ) 和 待排件的旋转角度0 。由这三个参数可以计算出多边形其它各项点在面料上的位置。 定义不规则待排件为p ；不规则待排件对应的多边形图形为q ；待排件原始基准点 的坐标为( 毛，咒) ；待排件相对重心的旋转角度为0 i ；面料上可以排放的位置坐标为 瓴。，咒i ) ；则原始待排件可以表示为o i ( x , ，咒，0 ；) 。 待排件在面料上的排料过程如下：首先将待排件绕其重心旋转e ；度，然后计算出待 排件现在的基准点( 毛，咒) ，再将整个待排件，即将待排件基准点( 毛，咒) 平移到( 五：咒i ) ， 整个待排件随之平移。此时的待排件弓可表示为g ；( 毛，咒，0 ；) 。 n - 维不规则排料的数学模型可表示为： 荟z r 墨叫) 么一。产f ， 11 、 m a xe ! r z 其中聍为待排件的个数，s 为待排件p 的面积，z i 是一个表示待排件p 是否能在面 料上排放的状态变量，互= 1 表示可以排放，互= 0 表示排放不下。形表示面料的宽度， 表示排料后面料的最终长度。 排料的约束条件为： g i ( 毛，咒，0 i ) n g j ( 毛，乃，o j ) = a o 毛( 毛，咒，0 i ) 形，o _ _ x j ( x j ，y j ，e j ) 形 o - y i ( x i ，y i ，0 i ) 三，0 _ y j ( x j ，y j ，0 j ) l ( 2 2 2 ) ( 2 2 3 ) ( 2 2 4 ) 式( 2 2 2 ) 表示任意两个待排件互不重叠，式( 2 2 3 ) 和式( 2 2 4 ) 表示任意待排件的每一 点的坐标都必须在排料区域内，不能超出规定面料的范围。 2 3 二维排料问题的常用方法 2 3 1 针对规则排料的近似算法 近似算法指在解决优化问题中，可以预知其最坏计算结果的误差界限，并且最后得 9 2 二维捧料问题研究 硕十论文 到的结果能保证在一定的误差之内的算法。最典型的近似算法思想是贪心算法，其基本 策略是每一步只做使当前评价标准最优化的选择。针对矩形排料常用的近似算法有： ( 1 ) 依次排料算法。各个矩形待排件的排料次序和排放角度( 0 度或9 0 度) 固定。将各 待排矩形件按照设定好的次序以及角度依次排料。 ( 2 ) 剩余矩形匹配排料算法【矧。首先对各个矩形待排件按照面积由大到小的顺序排 序，然后将各待排矩形件按照面积由大n d , 的顺序使用剩余最佳匹配原则依次排料，即 在面料上排放当前矩形件，这样面料上就会出现另一些划分出来的矩形，然后选择其它 未排的矩形件来填充这些新划分出来的矩形小面料。排料过程