（应用数学专业论文）基于统计分析的矩形件排样问题遗传算法研究.pdf

摘要 摘要 二维矩形件优化排样问题通常是指在给定矩形板材上排放所需要的矩形件，使 板材利用率最高。它属于典型的组合优化问题，已被证明是n p 完备的，具有较高的 计算复杂性。 本文在分析国内外研究现状以及原有遗传算法局限性的基础上，提出了一种基 于统计分析的单亲遗传算法，用于求解矩形件优化排样问题。 首先，提出将剩余矩形排样算法与单亲遗传算法结合起来共同求解矩形件优化 排样问题，有效地利用了两种算法的优势，通过实例验证表明，利用此方法所得结 果在计算精度或运算时间方面优于目前常用算法。进一步，在上述算法基础上，针 对矩形件排样问题本身特点，深入研究了矩形零件数量、大小差异、板材规格等与 问题解空间的关系，发现了问题次优解空间所存在的统计规律性。并根据此规律， 采用优势群体遍历搜索策略，设计基于统计分析的单亲遗传算法。经实例验证，该 算法大大提高了寻找某一特定生产环境下的矩形件排样问题全局最优解的能力，充 分表明了算法的有效性。 关键词：矩形件优化排样、组合优化、剩余矩形排样算法、单亲遗传算法、统计分 析 a b s t r a c t a b s t r a c t r e c t a n g l ep a c k i n gp r o b l e m ( r p p ) u s u a l l yc o n s i s t so fp a c k i n gg i v e nr e c t a n g l ep i e c e s i n t oal a r g er e c t a n g l es t o c kp l a t e ，w i t ham a x i m u mu s a g eo ft h es t o c kp l a t e i ti sat y p i c a l c o m b i n a t i o no p t i m i z a t i o na n dh a sb e e np r o v e dt ob ean p c o m p l e t ep r o b l e m 、i t hh i 曲 c o m p l e x i t yo f c o m p u t a t i o n i nt h i st h e s i s ，b yt h ea n a l y s i so ft h er e s e a r c ha c t u a l i t yb o t hh e r ea n da b r o a da n dt h e s h o r t a g eo ft r a d i t i o n a lg a ，ap a r t h e n o g e n e t i ca l g o r i t h mb a s e do ns t a t i s t i c a la n a l y s i sh a s b e e np r e s e n t e dt os o l v et h er e c t a n g l ep a c k i n gp r o b l e m f i r s to fa l l ，t h ep a r t h e n o - g e n e t i ca l g o r i t h m ( p g a ) a n dt h es u r p l u sr e c t a n g l ef i l l a l g o r i t h m ( s r f ) h a v eb e e nc o m b i n e d ，s ot h a tb o t ha d v a n t a g e so ft h o s et w oa l g o r i t h m s c o u l db eu s e de f f i c i e n t l yt os o l v et h eo r t h o g o n a lp a c k i n gp r o b l e mo f r e c t a n g l e s i ns e v e r a l i n s t a n c e s ，i ti sp r o v e dt h a ts o l u t i o n sa c h i e v e db yt h i sa l g o r i t h me x c e l l e dt h o s ea c h i e v e db y o t h e rc o m n l o na l g o r i t h m si nb o t hc o m p u t a t i o n a la c c u r a c ya n do p e r m i o nt i m e f u r t h e r , b a s e do nt h ea l g o r i t h mp r e s e n t e da b o v e ，t h er e l a t i o nb e t w e e nt h es o l u t i o n so fr e c t a n g l e p a c k i n gp r o b l e m sa n d t h ec h a r a c t e r i s t i c so ft h ep r o b l e m st h e m s e l v e ss u c ha st h en u m b e r o ft h o s er e c t a n g l ep i e c e s ，t h es i z ed i v e r s i t yo ft h o s er e c t a n g l ep i e c e s ，t h es p e c i f i c a t i o no f t h es t o c kp l a t ea n ds oo nh a sb e e nr e s e a r c h e d a sar e s u l t ，i ti sf o u n dt h a tt h e r ee x i s ts o m e s t a t i s t i c a ll a w sf o rt h ed i s t r i b u t i o no ft h es u b o p t i m ao fr e c t a n g l ep a c k i n gp r o b l e m s a n d t h e n , a l li m p r o v e dp g ab a s e do ns t a t i s t i c a la n a l y s i sh a sb e e nd e s i g n e db ya d o p t i n g s u p e r i o rc o l o n yt r a v e r s a ls t r a t e g ya c c o r d i n gt ot h o s es t a t i s t i c a ll a w sg a i n e d ，t os o l v e r e c t a n g l ep a c k i n gp r o b l e m s f i n a l l y , t h ea l g o r i t h mh a sb e e nt e s t e du s i n gs e v e r a la v a i l a b l e i n s t a n c e s t h ee x p e r i m e n t a lr e s u l t sh a v ed e m o n s t r a t e dt h a tt h i sa l g o r i t h mc a ni m p r o v et h e c a p a b i l i t yo fs e a r c h i n gt h eg l o b a lo p t i m u mo fs o m er p pu n d e rs p e c i f i cp r o d u c t i o n e n v i r o n m e n tg r e a t l y t h i ss h o w sa d e q u a t e l yt h a tt h ea l g o r i t h mp r e s e n t e di nt h i st h e s i si s e f f i c a c i o u s k e y w o r d s ：r e c t a n g l ep a c k i n gp r o b l e m ，c o m b i n a t i o no p t i m i z a t i o n ，s u r p l u sr e c t a n g l ef i u a l g o r i t h m ，p a r t h e n o g e n e t i ca l g o r i t h m ，s t a t i s t i c a la n a l y s i s i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 如不实，本人负全部责任。 论文作者( 签名) ：盔圭z 亟盔 。岬易年，月如日 学位论文使用授权说明： 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊 ( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被 查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究 生院办理。 论文作者( 签名) ：硅蔓丕 f d 叼易年3 - - 月如e l 第一章绪论 1 1 优化排样问题概述 第一章绪论 1 1 1 优化排样问题的总体描述 优化排样问题是指在给定的材料区域内，找出被排零件的全局最优排布，使得 材料利用率最高，且零件互不重叠。优化排样应用范围非常广泛，在工程应用领域 中如型材和棒材下料、冲裁件排样、玻璃切割、报于u 排版、家具下料、服装裁剪、 皮革下料中都存在大量的排样问题。其应用领域具体如表1 1 所示。 表1 1 优化排样问题的应用领域 应用分类举例 钣金件加工 工业用各种钣金件、厨房用具和家用电器用钣金件、打字机和 电子元件用钣金件、模具及链条链板、电动机用硅钢片、造船 业钣金件等 服装行业 各种布料、皮革排样，衬衫、西服、鞋袜、降落伞等，布料皮 革定级中的优化排样等 纸业与玻璃业 办公用纸、财务用纸的裁制等，玻璃的裁制 印刷业排版 各种书刊、报纸排版，印刷电路板 集装箱装货将货物装入有限空间的集装箱内 型材、棒材下料棒材、角钢、各种型材下料、建筑业中钢筋、铝合金下料 微电子工业集成电路的排布 军事国防图形目标的搜索等优化问题 航空航天航天器舱布局 优化排样问题的总目标是在给定的几何图形上不重叠地放置更多的满足要求的 几何图形( 一维、二维) ，如图1 1 、图1 2 ，使材料利用率最大；如何在给定空间 中放置更多的满足要求的几何形体( 三维) ，如图1 3 ，或者是给定要放置的几何形 体，如何放置使得所占空间最小。具体到不同的行业以及切割、排样环境表现为不 同的约束形式，但没有本质的差别。 河海大学硕士学位论文基于统计分析的矩形件排样问题遗传算法研究 凰霸 霸_ 一 口口 ( a ) 原材料板 ( a ) 集装箱 ( b ) 需要的小管子( c ) 小管子的下料组合 图1 1 管子切割下料 豳圜啊置曩 昂圈圈 豳豳豳圆 圈一豳 _ ( b ) 待排零件( c ) 排放零件 图1 2 矩形件排放问题 废 料 聒画 ( b ) 待装箱体( c ) 装箱结果 图1 3 集装箱装货 由以上3 个典型的优化排样问题，可以概括出优化排样问题的两个共同特征： ( 1 ) 有两组基本数据，一组是大的原材料的尺寸( 一维或多维) ，另一组是小的 零件的尺寸； ( 2 ) 排样过程是将小的零件在原材料上进行合理几何组合，如何确定优化排样方 案，以使得材料利用率最高。 由于排样问题研究的多面性，优化排样问题也可被称为下料问题( c u t t i n gs t o c k p r o b l e m ，c s p ) 、装箱问题( b i np a c k i n gp r o b l e m ) 、背包问题( k n a p s a c kp a c k i n g p r o b l e m ) 、集装箱装货问题( c o n t m n e r l o a d i n g p r o b l e m ) 、布局问题( 1 a y o u t p r o b l e m ) 等n 1 1 2 优化排样问题的分类 对优化排样问题的科学分类和标识是全面了解和解决排样问题的基础。文献1 1 】 将排样下料问题归为g e o m e t r i cc o m b i n a t o r i c s ，按照是否为空间尺寸划分为狭义排样 下料问题和广义排样下料问题。狭义排样问题可按所排零件的维数划分为：一维下 一一一一 第一章绪论 料、二维排样和三维布局。 ( 1 ) 一维下料问题。一维下料问题，主要是指按照某种分割方案，将给定长度的 线材分割成一定数量、指定长度的较短毛坯，其目标是寻求最优的切割方案，使得 既满足需要，又要使所用原材料最少。 ( 2 ) 二维排样问题。二维排样问题，又称为板材排样问题，是指将板材分割成各 种形状的毛坯。这些毛坯可以是矩形、圆形、扇形等规则形状，也可以是不规则形 状。典型的应用领域包括木材制造业、家具制造业、普通机械制造业、专用设备制 造业等行业。 二维优化排样问题大致又可以分为两大类口l ：第一类是矩形件优化排样问题 ( r e c t a n g u l a r p a c k i n g p r o b l e m ，r p p ) ，是排样问题研究的热点，在工业生产中常见 的要求有两种：一种是材料的数量无限，要排放的矩形件数量是固定的，要求在排 放完所有矩形的前提下使所消耗的材料数量最少；另一种是材料的数量有限，要求 排放出尽量多的矩形，使所产生的废料最少。第二类是二维不规则零件的优化排样， 由于材料和排放零件的形状都是任意的，处理起来难度很大，目前还没有特别有效 的算法，材料利用率也不高。 ( 3 ) 三维布局问题。三维布局问题是指将多个较小物体合理地放入较大物体中的 布局问题。目前研究的主要对象是长方体形状的盒式物体。 1 1 3 优化排样问题的复杂性 尽管国内外大量学者很早就开始了优化排样问题的研究工作，但到目前为止仍 然没有获得令人非常满意的解决方法，这主要是由于优化排样问题本身的复杂性造 成的。 算法对时间和空间的需要量称为算法的时间复杂性和空间复杂性。按照计算复 杂性理论研究问题求解的难易性，可把问题分为p 类、n p 类( n 在这里代表非确定 性，p 代表多项式算法) 和n p c 类( n o nd e t e r m i n i s t i cp o l y n o m i a lc o m p l e t e ，非确定 性多项式算法完备) 。n p c 问题( 也称为n p 完备问题) 是n p 类中最困难的问题， 这类问题的求解时间随着问题规模的增大呈指数级增长 3 1 1 4 ，即使用最快的计算机进 行计算，所花的时间和费用也是人们不可接受的，但这类问题一般都具有重要的实 际意义和工程背景。 河海大学硕士学位论文基于统计分析的矩形件排样问题遗传算法研究 排样问题与背包问题、装箱问题、j o bs h o p 和f l o ws h o p 问题、旅行商问题一样， 都属于典型的组合优化问题，已被证明为n p 完备问题，不太可能在多项式计算时间 内获得问题的最优解【5 1 。 对于一维下料优化问题，原材料的长度三是给定的，现使用这种原材料进行下 料，将其切割成弹种规格的零件，第f 种零件的长度为，需要的数量为t 个 ( f = 1 , 2 ，刀，且冉2 ，兰上) ，如何下料才能使所用原材料最少。从组合优化角度看， 可将此问题看作是一维装箱问题【6 】，装箱问题是n p 完备问题。 对于二维排样优化问题，给定开个零件的集合p = n ，p 2 ，p ) ，h z + ，第 f ( 1 f 矗) 个零件具有面积6 j 0 ，另有面积为a 加数量不限的板材，如何排样使 所用板材数量最少。可将其分成两类来考虑：( 1 ) 零件为矩形，板材为矩形，要求将 零件互不重叠地放入板材，使所用板材利用率最高；( 2 ) 零件具有任意复杂的平面形 状，板材为矩形，要求将零件互不重叠地放入板材，使材料利用率最高，并满足一 定工艺要求。 可见，( 1 ) 是二维装箱，属于n p c 类问题，需满足矩形零件间互不重叠且在板材 矩形区域内；( 2 ) 是异形零件在矩形板材上排放，仍是n p c 类问题，而且需要考虑图 形运算、合理拼接，并满足一些与实际应用相关的约束条件。 对于三维集装箱装货问题，需在长、宽、高3 个方向考虑综合最优，同时还需 考虑箱体本身的承重性、最大载重量、某些货物之问的隔离等，求解难度更大。 从以上对排样问题的分类可以看出，排样问题具有两个特性，几何特性和组合 特性。从一维、二维到三维，随着维数的增加，问题的几何特性与组合特性愈加复 杂，求解的难度加大 7 1 。由p i e r c e ( 1 9 6 4 ) 【8 】的研究显示，在一维条材排样问题中，可 行排样方案的数量很容易就超过百万，二维排样问题的可行排样方案比一维条材更 为复杂，数量也更为巨大。不可能通过对所有的可行排样方案一一枚举来规划优选， 即使是利用现有最先进的高速计算机也无法胜任。 总之，排样问题属于n p 完备问题，至今尚未找到任一有效的多项式时间算法。 人们往往改而寻求在多项式计算时间内，求得排样问题的近似最优解；或是利用启 发式搜索方法，在较短的时间内，求得问题的可行解。 第一章绪论 1 2 矩形件优化排样问题国内外研究现状及存在的问题 在实际生产实践中，许多零件毛坯为矩形，矩形件排样问题普遍存在于工业生 产的各个部门。同时，研究矩形件优化排样问题既可以解决玻璃切割等矩形件下料 问题，也可以通过提取包络矩形用于解决异形件排样问剐9 】1 1 0 】【l l 】，即对于非矩形的 不规则形状零件，可通过计算机的图形处理技术将一个或几个零件套排在一个包络 矩形中，然后对包络矩形进行排样，从而转化为矩形件排样问题。 因此在过去的5 0 多年里，国内外的大量学者一直在从事矩形件优化排样问题的 研究，对矩形件优化排样的研究理论己涉及到线性规划( l p ) 、动态规划( d p ) 、启 发式算法( h a ) 以及人工智能( a i ) 等多种学术研究的前沿理论。下面对矩形件优 化排样问题的研究动态【1 2 】作一简要介绍： 1 2 1 国外研究现状 国外有关二维矩形件排样问题的研究起步比较早，2 0 世纪5 0 年代就先后出现了 一些相关的学术论文，但这些论文所提出的理论方法在实际工业生产中并不可行。 1 9 6 1 年至1 9 6 6 年期间g i l m o r e 与g o m o r y 又先后共同发表了4 篇著名论文，其中前 两篇【1 3 】 1 4 】详细阐述了一种用于解决一维下料问题的线性规划算法，后两篇 1 5 1 6 】 将该算法推广到了二维和三维问题，第一次为解决实际生产中的二维矩形件排样问 题提供了可行的技术手段。然而，由于即使是矩形零件在一张板材上的排放问题也 是n p 完备问题【5 l ，加上实际的限制条件问题会更加复杂，因此排样问题具有多样性 特点，至今没有通用的标准方法来解决。1 9 8 8 年在e u r o1 x t i m sx x v i i i 国际会议 上，专门成立了排样问题兴趣小组s i c u p ( s 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 d p a c k i n gp r o b l e m ) 。2 0 世纪9 0 年代以前，对矩形件优化排样的求解以各种近似算法 为主【州，这些近似算法的特点是针对某类或某些排样问题的结果较好，但算法并不 具有通用性。 1 9 6 5 年g i l m o r e 和g o m o r y 1 3 - 1 6 1 对矩形件优化排样f 1 题提出了线性规划算法，针 对矩形件优化排样模型，先确定分割模式矩阵，然后通过求解整数线性规划来解决 矩形件优化排样问题。在此基础上，b e a s l e y 1 明对g i l m o r e 等人所提出的方法进行了 改进，通过为每一种零件设置二进制变量，应用分支定界( b r a n c ha n db o u n d ) 方法 河海大学硕士学位论文 基于统计分析的矩形件排样问题遗传算法研究 对矩形件在单一板材上的排放问题进行了求解。同时，b e a s l e y b 9 1 还提出了动态规划 方法，f a r l e y 2 0 提出了整数规划方法。用上述这些数学规划类方法求解矩形件优化排 样问题，虽然能解决一些问题，但计算量都非常大，求解效率比较低。 1 9 8 2 年i s m a i l t 2 1 】提出了一种启发式算法，基本思想是先将各矩形件进行两两聚 合排列，直到所有矩形件都完成两两聚合后，得到下料结果，当矩形件的需求量很 大的时候，该算法的求解时间很长，求解效率比较低。同时，由于二维下料问题可 以归结为以零件排放状态为结点、以废料增加为权值的带权有向图的最短路径f 司题， 属于集覆盖问题，基于这一点d a g l i 2 2 1 提出了一个基于图案子集的启发式算法，该算 法适合于图形组合的图案较少的情况。此外，很多学者还提出了较多其它的启发式 算法：h o r a c i ohy 田1 考虑了矩形件的优先权，d i d i e rf a y a r d 2 4 1 将矩形件排样问题转 化为求解一系列的一维背包问题。 这些启发式算法主要是针对要求解的特定问题确定合适的启发式规则，并根据 所定规则在人们可以接受的计算时间内寻求问题的最优解或近似最优解。求解效率 比较高，但是对于不同的问题都要确定不同的启发式规则，启发式规则无通用性， 影响了算法的广泛推广使用。 2 0 世纪9 0 年代后，随着智能优化算法，如模拟退火算法( s i m u l a t e d a n n e a l i n g ， s a ) 刚、遗传算法( g e n e t i c a l g o r i t h m ，g a ) 幽、禁忌搜索法( t a b us e a r c h ，t s ) 【2 5 1 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 、蚁群算法( a n t a l g o r i t h m ， a a ) 等方法的日益成熟及其在t s p ( t r a v e l l i n gs a l e s m a np r o b l e m ) 问题、空间分配、 任务调度等组合优化问题方面的成功应用，人们开始用这些智能优化算法与排样算 法( 如b l 算法、下台阶算法、最低水平线算法等) 相结合来解决矩形件优化排样问 题【2 0 】。 文献【3 1 】给出了模拟退火算法、遗传算法、随机搜索法( r a n d o ms e a r c h ，r s ) 与不同排放算法相结合，对不同问题实例的综合性能评价的结果，得出了两点主要 结论：( 1 ) 复合算法的结果优于单纯排样算法的结果，并且排样算法效果越好，复合 算法在同等条件下的效果也越好；( 2 ) 任何算法都有效果不佳的问题实例，即对矩形 件优化排样问题目前还没有完全有效的方法。 6 第一章绪论 1 2 2 国内研究现状 国内对于矩形件排样的研究始于2 0 世纪9 0 年代，主要采用启发式算法、动态 规划、整数规划方法、全局搜索算法等进行求解。 1 9 9 4 年，曹炬等【3 2 1 利用背包算法将二维矩形件优化排样问题转化为一维下料问 题，进而进行求解；1 9 9 5 年他又提出一种动态启发式算法口3 1 ，在排样过程中不断地 产生一些较小的矩形，然后用那些未排的矩形件去填充这些小矩形，直至所有矩形 件被排完为止。2 0 0 0 年，李建勇口4 1 利用c h i n n 模型，使用“b l 算法”进行矩形件 的优化排样，但c h l n n 模型不太容易处理矩形零件的横竖放置方式。此外，崔耀东 掣3 5 l 研究了单一尺寸矩形件的排布，文献【3 6 】对特定设备下料排样进行了分析。 同样，随着智能优化算法的日益成熟，国内越来越多的学者开始将这些全局搜 索方法引入到矩形件优化排样问题中来。刘德全等 3 7 1 把遗传算法与下台阶排样算法 相结合用于求解矩形件优化排样，贾志欣等p 8 】把模拟退火与最低水平线法相结合应 用到矩形件优化排样，文献【3 9 引入了蚁群算法。 此外，也有较多学者通过将多个全局搜索算法结合起来形成混合算法，用于求 解矩形件排样问题。陈学松、曹炬等【4 0 】把遗传算法和模拟退火相结合用于求解矩形 件排样，利用模拟退火法较强的局部搜索能力来弥补遗传算法局部寻优能力差的缺 陷。宋亚男等【4 1 】在将免疫算法与遗传算法相结合的基础上提出了针对矩形件排样问 题的改进算法。 虽然与国外相比，国内关于排样问题的研究在深度上和广度上都存在差距，但 很多学者已经意识到该问题的研究价值，因此目前排样问题已成为国内学者研究的 一个热点。 1 2 3 存在的问题 尽管人们对矩形件优化排样问题进行了大量研究，并取得了一些成果，但仍然 存在较多的不足： ( 1 ) 由于问题本身属于n p c 类，至今尚未找到任一通用、标准的解决方法。人 们往往都是在寻找多项式计算时间内的近似算法，用于求得矩形件排样问题的近似 最优解，而并没能找到问题的全局最优解，即便是对于一些特殊问题也没能找到全 河海大学硕士学位论文基于统计分析的矩形件排样问题遗传算法研究 局最优解。 ( 2 ) 随着智能优化算法的不断发展，不少学者采用计算机图形学处理方法与智 能优化算法相结合，或是优化算法之间相互结合来解决矩形件优化排样问题，但是 对于如何有效地综合多种算法以及哪些算法在哪一阶段综合，尚待研究。 ( 3 ) 实际生产中的矩形件排样问题具有多样性，不能仅限于材料利用率最高这 个单一目标，还应结合生产中的具体工艺和应用要求，考虑多个目标以及多个约束 条件。 ( 4 ) 对于矩形件排样问题的研究应从多个角度进行：不能单单寻找合理时间内 的最优解法，还应在算法分析方面对算法的时间复杂性、空间复杂性进行分析。对 算法性能表现方面在一般情况下、最坏情况下解的质量以及适用的问题类型进行研 究。针对不同问题的特点，如零件的情况( 零件的数量、零件的长宽比、零件的差 异变化比) ，测试和分析算法的性能。这些都是尚未能做到的。 1 3 研究的主要内容及创新点 1 3 1 本文研究的主要内容 矩形件优化排样问题通常是指在给定的矩形板材上排放所需要的矩形件，使板 材利用率最高，以达到节省板材的目的。它属于二维布局优化的范畴，广泛存在于 航空航天、交通运输、机械制造、出版印刷、纺织服装设计等许多行业中。 在如今激烈的市场竞争中，提高经济效益是企业保持长久竞争力的永恒主题。 而提高经济效益的重要途径之一就是通过提高材料的利用率来降低成本，如上面所 述材料利用率的高低在一定程度上是由排样决定的。 然而目前多数企业在实际生产中仍是根据目测和经验，采用手工进行排样。排 样工人预先用一些材料做出零件模型，当需要在板料上加工某些零件时，把这些零 件的模型尽可能紧密地放在板料上，沿模型的轮廓把形状画出来，然后再进行切割。 排样工人通过反复排放、比较来寻求较好的排放方案，劳动强度高、工作量大且效 率和材料利用率都较低。很难适应现代多品种、小批量生产的要求。 随着计算机技术以及自动加工技术在制造业应用的发展，为排样开辟了新的途 径一即基于计算机的优化排样技术( 简称为优化排样) ，它与人工排样相比具有以下 第一章绪论 几个优点： 1 ) 传统的人工排样由于受人的工作态度与能力所限，很难给出材料利用率最高 或接近最高的排样方案。而应用优化排样技术，可以充分发挥计算机强大的计算能 力，通过大量排样方案的比较，选出材料利用率最高或接近最高的排样方案，达到 节约材料的目的。 2 ) 传统人工排样时，为了得到一个较好的排样方案往往需要长时间的反复。而 应用优化排样技术，可以在非常短的时间内完成排样任务，并且得到高质量的排样 方案。 3 ) 排样时经常遇到这样的情况，即存在许多材料利用率非常接近的排样方案。 称材料利用率最高的排样方案为最优排样方案。应用优化排样技术，可以在大量的 达到最优或接近最优的排样方案中，选择切割工艺尽可能简单的排样方案，减少分 割工作量。 可见，在下料生产中采用基于计算机的优化排样技术，可以节约材料、减少排 样工作量、缩短排样时间，最终达到降低产品成本、提高企业经济效益的目的。 因此，在制造工业中对矩形件排样问题进行深入研究，目的及意义都很明确： 只要在排样算法上有一些改进，就可取得明显的经济效益，特别是当原材料比较贵 重又是大批量生产时，即便原料的利用率仅提高1 ，其产生的经济效益也是相当可 观的。因而对矩形件优化排样技术的研究具有深远的经济意义和现实意义。 同时，从计算复杂性上来看，矩形件排样问题属于具有最高计算复杂性的一类 问题n p 完备问题，不太可能在多项式计算时间内获得问题的最优解。根据计算和 难解性理论，目前还没有解决此类问题的多项式算法。故如何寻找一种更有效的算 法来求得问题的最优解或近似最优解，同样也具有重要的理论意义。 因此，本文主要研究的排样问题是二维矩形件优化排样问题。各章内容如下： 第一章描述了优化排样问题，总结了国内外矩形件优化排样问题的研究现状 以及存在的问题，并根据现状提出本文的主要研究内容及创新点。 第二章介绍了矩形件优化排样问题，建立了一般数学模型，并分析了问题的 特点和计算复杂性。介绍了几种常用的排样算法，并进行了优劣比较。 第三章讨论了矩形件优化排样问题的单亲遗传算法求解。介绍了单亲遗传算 法的基本原理及收敛性，并提出用单亲遗传算法结合剩余矩形排样算法，用于求解 矩形件排样问题。最后进行了实例验证，与现有方法所得结果进行了比较分析。 9 河海大学硕士学位论文 基于统计分析的矩形件排样问题遗传算法研究 第四章讨论了基于统计分析的矩形件排样问题的单亲遗传算法求解。介绍了 统计分析思想的原理以及具体实现，根据统计分析所得结果，改进原单亲遗传算法， 用于求解矩形件排样问题。最后给出了几个实例，将所得结果与现有结果进行了比 较，验证了所提出的基于统计分析的单亲遗传算法的有效性。 第五章总结了本文所得出的一些结论，分析了算法的先进性及存在的局限性， 对未来的研究工作提出了一些展望。 1 3 2 本文主要创新点 本文研究的主要创新点如下： ( 1 ) 根据对问题特点以及传统方法的局限性研究，提出采用序号编码的单亲遗传 算法结合剩余矩形排样法来求解一般的矩形件优化排样问题，并在此单亲遗 传算法步骤中采用两种不同的保优操作，以保证算法的全局收敛性。一是直 接保留父代群体中的一个最优个体，二是利用改进轮盘赌选择策略来隐含保 优。 ( 2 ) 区别于仅从算法方面对问题的求解效果进行改进的常规解决思路，采用逆向 思维方法，从矩形件优化排样问题本身特点出发，深入研究了矩形零件数量、 平均面积比、板材的规格等与问题解空间的关系，并首次提出利用统计分析 方法对排样问题进行分类研究，逐步发现问题的次优解空间所存在的规律 性。 ( 3 ) 选用排样高度与平均排样高度比等合适的参数描述次优解分布规律，并根据 所发现的次优解分布规律，构造优势群体遍历搜索策略，从问题本身以及算 法设计这两方面同时对矩形件排样问题进行研究，设计基于统计分析的单亲 遗传算法。利用此算法首次求出了文献 3 1 】中c 1 p 1 ，c 1 - p 3 ，c 2 p 1 ，c 2 一p 2 ， c 2 - p 3 五个实例的全局最优解，并经仿真试验，9 0 的算例都找到了问题的 全局最优解，效果显著。 1 0 第二章矩形件优化排样问题 第二章矩形件优化排样问题 2 1 矩形件优化排样问题的数学模型 矩形件排样问题按排样要求可分为在定宽无限长板材上排样求最小长度、在无 限多定宽定高板材上求最少板材块数等，但从根本上讲，都属于同一类问题。因此 在本文中不妨假设所要解决的矩形件排样问题是在定宽足够高的板材上正交地排放 所给定的矩形件，目的是寻求最佳的矩形件排放次序使板材利用率最高。这里所谓 的正交排放是指每一个矩形件的边在排放时必须平行于板材的边。同时允许矩形件 直接排放( 即横排，矩形件的宽平行于板材的定宽，矩形件的高平行于板材的高) 或是旋转九十度再排放即竖排。 基于上述假设，问题可描述为：给定板材宽，高日，所要排放的矩形件共一 个，w 。和h i 分别为矩形件i 的宽和高( i = 1 , 2 ，开) ，则板材利用率可表示为 ( 嵋x h l ) ( w x h ) ( 2 1 ) 其中i 为能排入板材中的零件，h 为所有矩形件完成排样后所占用板材的总高度。 排样基本目标：尽可能提高板材利用率。由于排放时定宽，只需考虑排放高度， 且高度足以排下所有零件，因此目标可转化为使最终排样高度h 尽可能地小。 排样基本约束条件：矩形件之间不能有相互重叠的区域，并且矩形件不能超出 板材的范围。 排样基本规则：正交排放，每一个矩形件都允许横排或竖排。 排样基本方式：从板材的最左下角开始排至板材的右上角。 设板材左下角坐标为( 0 ，0 ) ，则一块矩形件在板材上的位置可以由该矩形件的左 下角坐标和右上角坐标完全确定。设( x ，y 。，) ，( x z s , y ：1 ) 为矩形件i 在板材上的左下 角坐标和右上角坐标，则转化的排样过程就是根据一定的寻优规则，确定每一块矩 形件在板材上的左下角和右上角坐标。由于排放时允许有横排、竖排两种方式，故 矩形件的两个坐标存在两种关系： z 三z ：乏或 2 三2 二暑 ，z = - ，弹 c 2 前一种关系矩形件为横排，后一种为竖排。 河海大学硕士学位论文 基于统计分析的矩形件排样问题遗传算法研究 由此可见，对于每一块矩形件排放后的位置，实际上由三个变量决定：x 。，y l l 和决定矩形件f 横排或竖排的逻辑变量，= 0 表示横排，f = 1 表示竖排。则 0 l j y 1 1 ) 与( x 2 i ，j ，2 ) 应有如下关系： ，i = 1 ，拧 ( 2 3 ) 设置和r s 为任意两个矩形件，它们对应的左下角坐标和右上角坐标分别为 “x 。，j ，) ，q ：。，_ ，：，) l 和 ( x ，j ，。，) ，q 。，y ：，) ) 。则当下面四种情况中至少有一种出现 时，它们互不重叠： ( 1 ) x “x 2 ，矩形f 在j 的右边 ( 2 ) x h 屯。，矩形f 在j 的左边 ( 3 ) y l ，矩形f 在j 的上方 ( 4 ) y h j ，2 。，矩形f 在s 的下方 代入( 2 3 ) 式，得 ( 1 )x l r x h + ( 1 一) 1 ，+ 。 ( 2 ) x h x l t + ( 1 一r 1 ) w r + r t h t ( 3 )j ，l 。j ，h - 6 ( 1 一) 以+ 屹 ( 4 )y l ，l ，十( 1 一地+ 吩 要使得任一矩形件置没有排出板材之外，则它的坐标应同时满足： 献旺s 憾得 o 嚣：捌乏= ： 眩4 ， 由于板材定宽足够高，足以排下所有矩形件，故只需考虑排样高度，因此得到此排 样问题的目标函数为m i n ( m a x y 2 1 ，j ，2 i ，j ，2 ) ) 。 总结上面分析，得到矩形件优化排样问题的数学模型【4 2 】为： 他似 + 卜 坼岛 ) 、j 卟 一 一 1 l ，、( + + l l x ， = 1 1 2 2 x ， ，、【 0 矿0 日一 五 ( 珊 五) 与相应的状态 + 。，i ，下式成立 p x m + k = i m 。t x 。= i m ，x h = i h ，x h = i l ，xj 1 2 i i j = p x 。+ = + t i 瓦= ( 3 1 ) 则称( x 。：t = 0 , 1 ，2 ，为一个马尔可夫链。式( 3 1 ) 称为在时刻埘的| 步转移概率， 当k = 1 时，称为在时刻埘的一步转移概率( 令f + 。= j , i 。= f ) ，记为 p 。( m ) = p 以+ ，= “l x 。= ) = p x m + l = _ ，i _ = n ( 3 2 ) 它表示在时刻m 取状态i 的条件下，在时刻肿+ 1 取状态j 的条件概率。 定义3 7 对于m a r k o v 链 x t ：f = 0 4 ，2 ， ，若对于v i , j s ，状态i 到状态， 的一步转移概率p # ( 脚) 与时间起点珊无关，即 p f x 。l = j i x 。= 妇= p # ，埘= 0 ，1 2 ， ( 3 1 3 ) 则称其为齐次马尔可夫链。记p = 【舶1 为此齐次马尔可夫链的一步转移概率矩阵( 简 称为转移矩阵) ，它具有以下性质： ( 1 ) 0 茎p 口1 ，i , j s 。 ( 2 ) p u = 1 ，f s 。 e s 定义3 8 设m a r k o v 链 x 。：t = 0 , 1 ，2 ，) 的状态空间为s ，若对一切j ，j s ， 存在不依赖于f 的常数石( ，) ，使得 m l i m p # ”= 石u ) ( 3 4 ) 则称此m a r k o v 链具有遍历性，其中p c 为马氏链的七步转移概率。 定义3 9 若a r ，并且对任何正整数f 、人f ，j 1 1 ，h i ) ，有 1 ) 若 0 ，则称一为正矩阵，记为a 0 ； 2 ) 若0 ，则称a 为非负矩阵，记为a 0 ； 3 1 若a 0 ，且3 k n 使a 0 ，称爿为正则矩阵； 河海大学硕士学位论文基于统计分析的矩形件排样问题遗传算法研究 d 4 ) 若一0 ，且v f 使= 1 ，则称a 为随机矩阵。 h 在单亲遗传算法的搜索过程中，第f 代群体为x t = _ ，x ，x 。) ，f 1 ， s ，s 为搜索空间( 可列集或有限集) ，新群体x 。的产生仅仅以条件概率的方 式依赖于当前群体x 。，而且各代群体之间的转移概率与时间的起点无关，从而p g a 的搜索过程 置，f 1 ) 构成有限状态齐次马尔可夫链。 令q 为所有长度为，的有序符号串( 染色体) 的集合，则串空间q 包含 i q i = ( ) ，! ( 3 5 ) 个点( 每一点即为集合中一个元素) ，乳为同位基因数。令a 为所有包含弹条染色体 的群体五的集合( 集合中每个元素为包含弹条染色体的一个群体) ，则群体空间a 包 含 1 a i = l n r = ( 器) 4 川) 4 ( 3 6 ) 个点。对于某一选定的包含一条染色体的初始群体厶，仅仅通过基因突变算子可以 生成的子空间a 。( 子空间中的每一个点为突变所生成的一个可能群体) 包含 卜。| - “岛) 。) 。= ( 岛) 4 ( 3 7 ) 个点，其中初始群体中某一条染色体通过基因突变可形成的染色体有( 9 3 。种可能； 而仅仅通过基因换位算子可以生成的子空间a 包含 l a 。l - ( f ! ) 。 ( 3 8 ) 个点，其中初始群体中某一条染色体通过基因换位可形成的染色体有l ! 种可能。在 子空间a 。中的任何群体丑都可以通过基因换位算子生成一个子空间 ：，并且 a ：、砖、川纠互不相交。类似地，在子空间a 。中的任何群体都可以通过基因 突变算子生成一个子空间必，并且 _ 、a 乙、一，互不相交。 因此，基本的单亲遗传算法群体空间的概率变化由选择、基因换位( 换位、移 位、倒位这三种算子是等价的，故只考虑基因换位算予) 、基因突变三种基因操作引 起，它们分别用矩阵c ，e ，m 描述，则p g a 的m a r k o v 转移概率矩阵为 p = c e m 。 其中，设种群墨= x ，x n ，x 。) 中个体h 被选中的概率为 第三章矩形件优化排样问题的单亲遗传算法求解 p s e l e c t x a ：掣 0 。假定基因突变概率为p 。，则由个体x d 通过突变转变 e f ( x # ) i = x 为个体的概率为p x 。- - x ： = p ：( 1 一p ，) 。8 0 ，其中h = h ( x 。，x ：) 为这两个 个体间的h a m m i n g 距离(