（机械设计及理论专业论文）融合蚁群算法和遗传算法的矩形件排样问题研究.pdf

摘要 摘要 矩形件排样是指将若干尺寸相同或不相同的矩形零件在给定的矩形板材上 以最优的方式排布。矩形件排样问题普遍存在于工程领域中，如钣金下料、玻 璃切割、造船、车辆、家具生产、报刊排版、服装和皮革裁剪等。较好的排样 方案可以最大限度地节约原材料，提高原材料利用率，从而降低生产成本，在 经济上制造可观的效益。 在理论上，矩形件排样问题属于组合最优化问题和具有最高计算复杂性的 n p 完全问题。用现在常用的计算理论和方法很难精确地求得问题的最优解，只 能在一定的时间范围内求其局部最优的近似解。启发式智能优化方法是近年发 展起来的非常活跃的研究领域，如遗传算法、模拟退火算法、蚁群算法、神经 网络、粒子群算法等，它们都可以有效的解决组合优化和n p 类问题。 本文是在介绍了遗传算法和蚁群算法各自特点的基础上，提出将两种算法 相融合来求解矩形件排样问题。融合算法的前阶段采用遗传算法，充分利用遗 传算法的快速随机性、全局收敛性的优点，获得排样序列的部分优化解，并以 此作为下阶段蚁群算法的初始信息素分布；融合算法后阶段采用蚁群算法，利 用其优良的正反馈机制和高效收敛性的优点，精确求得最优排样序列。 此外，本文在建立矩形件排样问题数学模型的基础上，分析了常见的矩形 件给定排放顺序的排放算法的优缺点，提出了一种改进的排放算法。该算法充 分考虑矩形件长度和宽度对排样效果的影响，加入了旋转策略，并改进了搜索 策略。将此改进算法分别与遗传算法和融合算法结合求解矩形件排样问题，计 算实例表明了该改进排放算法更为有效，并能够和融合算法较好的结合，得到 更好的排样效果。 关键词：矩形件排样改进排放算法蚁群算法遗传算法算法融合 ab s t r a c t r e c t a n g l u a rp a c k i n gm e a n s t oa r r a n g er e c t a n g l u a rp a r t so fd i f f e r e n ts i z eo rs a m e s i z ea tag i v e nr e c t a n g u l a rp l a t ew i t ht h eo p t i m a lw a y r e c t a n g l u a rp a c k i n gp r o b l e mi s c o m m o n l yf a c e di ne n g i n e e r i n gf i e l d ，s u c ha ss h e e tm e t a lc u t t i n g ，m a c h i n i n go fg l a s s ， s h i p b u i l d i n g ，m a n u f a c t u r i n go fa u t o m o b i l e s ，c l o t h i n g ，f u r n i t u r em a n u f a c t u r i n ga n d s t ) o n w i t hab e t t e rp a c k i n gp a t t e r n t h e m a t e r i a lc a nb es a v e do b v i o u s l y , a n dt h e p r o d u c t i o nc o s tc a l lb er e d u c e d ，a n de c o n o m i cb e n e f i t sc a l lb ei n c r e a s e d r e c t a n g l u a rp a c k i n gp r o b l e m i sac o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ma n d b e l o n g st ot h en pc o m l e t ep r o b l e m sw i t ht h e m o s tc o m p l e x i t yi nt h e o r y t h eo p t i m a l s o l u t i o ni sh a r dt oo b t a i np r e c i s e l yb yt h ec u r r e n tc a l c u l a t i o nt h e o r ya n dm e t h o d ，a n d o n l vc a no b t a i nt h ea p p r o x i m a t i o n i nc e r t a i nt i m el i m i t h e u r i s t i ci n t e l l i g e n t o p t i m i z a t i o nm e t h o d si sav e r ya c t i v er e s e a r c hf i e l d si nr e c e n ty e a r s ，s u c ha sg e n e t i c a 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 ，a n tc o l o n ya l g o r i t h m ，n e u r a l n e t w o r k s ， p a n i c l e s w a r ma l g o r i t h m ，e t c ，w h i c hc a ne f f e c t i v e l y s o l v et h ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e ma n dt h en pp r o b l e m t os o l v et h er e c t a n g u l a rp a c k i n gp r o b l e m ，ah y b r i da l g o r i t h mw h i c hi sb a s e do n t h ec o m b i n a t i o no fa n tc o l o n ya l g o r i t h ma n dg e n e t i ca l g o r i t h mi sp r o p o s e di nt h i s p a p e r c o n s i d e r i n gt h ea d v a n t a g e sa n dd r a w b a c k s o fa n tc o l o n ya l g o r i t h ma n dg e n e t i c a l g o r i t h m f i r s t l yw eo b t a i nt h ed i s t r i b u t i o no fp h e r o m o n eb ym a k i n g f u l lu s eo ft h e a d v a n t a g e so fr a p i dr a n d o m n e s sa n dg l o b a lc o n v e r g e n c eo fg e n e t i ca l g o r i t h m , a n d t h e no b t a i nt h eo p t i m a lp a c k i n gs e q u e n c eb ye m p l o y i n gt h ea d v a n t a g e so fp o s i t i v e f e e d b a c km e c h a n i s ma n de f f i c i e n tc o n v e r g e n c eo fa n tc o l o n ya l g o r i t h m b e s i d e s t h em a t h e m a t i c a lm o d e lo fr e c t a n g u l a rp a c k i n gp r o b l e m i se s t a b l i s h e di n t h i sp a p e r o nt h eb a s i so fa n a l y s i n gm a i n l ya l g o r i t h m sf o rr e c t a n g u l a rp a c k i n g p r o b l e m a ni m p r o v e da l g o r i t h mi s p r o p o s e d c o n s i d e r i n gt h e e f f e c to fi e n g t ha n d w i d t ho fr e c t a n g u l a r st ot h es o l u t i o n ，t h ei m p r o v e da l g o r i t h ma d d sr o t a t i n gs t r a t e g y a n di m p r o v e st h es e a r c h i n gs o l u t i o n w es o l v et h er e c t a n g u l a rp a c k i n gp r o b l e mb y c o m b i n i n gt h ei m p r o v e da l g o r i t h mw i t hg e n e t i ca l g o r i t h ma n dh y b r i da l g o r i t h m t h e l i a b s t r a c t r e s u l t so fe x a m p l e ss h o wt h a tt h ei m p r o v e da l g o r i t h mi sm u c hm o r ee f f e c t i v e ，a n dt h e b e t t e rp a c k i n gp a r e mc a nb ep r o d u c e db yt h eh y b r i da l g o r i t h m k e yw o r d s ：r e c t a n g u l a rp a c k i n gi m p r o v e dp a c k i n ga l g o r i t h m a n tc o l o n y a l g o r i t h mg e n e t i ca l g o r i t h m c o m b i n a t i o n 1 绪论 1 绪论 本章主要介绍了排样问题的研究目的、研究意义、分类、国内外的研究现 状及研究方法，最后总结了本文的主要研究工作，以及论文的章节组织安排。 1 1 排样问题研究的目的与意义 所谓排样，就是指将若干尺寸相同或不同的零件在给定的原材料上以最合 理的方式饰置，并要求排样时满足一定的约束条件，最终达到提高原材料利用 率、减少浪费的目的。排样问题普遍存在于各种工程应用领域中，如表1 1 所示 为排样问题的主要应用领域。 表l - l 排样问题的应用领域【1 l 应川分类举例 钣金件力n 【 主嚣显曩鍪霖 2 勤曩葛毳磊寺器川钣金仆、电子元件川钣金仆、 型材、棒材下料角钢、棒材、：字钢等各种型材下料，建筑业中铝合金、钢筋下料 纸业与玻璃业财务用纸、办公用纸的裁制，玻璃的裁制 航空航天航天器仓布局 印刷业排版各种报纸、书刊排版、电路板的印刷 集装箱装货将货物优化组合后装入到有限空间的集装箱中 服装行业 毳茬意篆蒜布料排样如西服、衬衫鞋袜等，布料皮革定级中的 微电子：业集成电路的排布 _ 术材制品各种家具的制作 军事国防图形目标的搜索等优化问题 较好的排样方案在实际中可以最大限度地节约原材料，提高原材料利用率， 降低生产成本，给企业在经济上制造可观的效益。因此，对排样问题的研究有 着重要的现实意义。 排样问题在理论上属于组合最优化问趔引，因其与计算机图形学、计算几何、 逻辑推理、运筹学等多门学科知识有关联，已被证明为具有最高计算复杂性的 优化问题，即n p 完全问题。以目前的计算理论和方法很难求得问题的最优解， l 绪论 只能在一定时间的界限内求得问题的近优解。排样问题的研究已经成功涉及到 了多个领域，因此在其研究过程中，许多理论自身也得到了完善和发展。 1 2 排样问题的分类 按照零件和原材料的维数不同，排样问题可以分为以下几类【l l ： ( 1 ) 一维排样问题 一维排样问题，又可称为线材排样问题，是指在排样过程中只对单个方向 的尺寸长度进行考虑。例如，较长的棒材、型材、管材等被分割成各种较短的 毛坯。常见的应用领域有：门窗、电气机械、金属制品、普通机械、专用设备i 交通运输设备、金属结构等制造行业，它们在制造过程中，为了方便生产产品， 需要将原材料分割成较短的毛坯。 ( 2 ) 二维排样问题 二维排样问题，又可称为板材排样问题，是指把板材分割成各种规则形状 的毛坯，如矩形、扇形、圆形等，或是分割成各种不规则形状的毛坯。常见的 应用领域有：木材制品业、交通运输设备制造业、金属制品业、家具制造业、 专用设备制造业、普通机械制造业、电气机械制造业等行业。 ( 3 ) 三维排样问题 三维排样问题，又可称为空间装箱问题，是指在有限的立体空间中合理排 放各种立体零件，此时材料和毛坯都是立体的。常见的应用领域有：仓库中货 物堆放、木材加工业( 将圆木分割成尺寸较小的方木) 、制造业中的产品内部构件 布局设计、卡车或集装箱装货等。 二维排样问题中的矩形件排样问题是指将若干尺寸相同或不相同的矩形零 件在给定的矩形板材上以最优的方式排布，要求所有待排零件都必须排放在板 材内，且各个零件之间不发生重叠，并满足一定的工艺要求，以达到节约板材 的目的。 矩形件排样问题根据给定矩形板材的不同，分为两种：一种是板材的长和 宽有固定的数值，但数量无限，将所有给定的矩形零件都排放到板材上，要求 所消耗的板材数量最少；另一种是板材定宽无限高，将给定的矩形零件尽量密 集的排放在板材上，要求所占据的板材高度最小，这种排样类型称为矩形件带 排样问题。 2 1 绪论 根据工艺要求的不同，矩形件排样问题也可以分为两类p 】：一类是非剪切排 样方式，它只考虑将矩形件尽量紧密地排放在板材上而使废料最少，不要求能 够剪切下料；另一类是剪切排样方式，要求排放完后，要在板材上进行直线切 割，每一次切割都将当前矩形板块完全分割为两个小的矩形板块。 本文主要研究的是非剪切的矩形件带排样问题，下文所涉及的矩形件排样 问题都是指该问题。 1 3 排样问题的国内外研究现状 1 3 1 国外研究现状 排样问题最早是k a n t o r o v i c h 4 1 于1 9 3 9 年提出的，文章主要是讨论了一维排 样问题。六十年代初，g i l m o r e 和g o m o r y 在文献【5 】和【6 】详细阐述了一种适用于 求解一维排样问题的算法，并在文献【7 】和【8 】中将此算法进一步推广到了求解二 维和三维排样问题，第一次为解决实际生产存在的排样问题提供了可行的技术 手段。七十年代至今，众多学者对排样问题做了大量的研究，提出了多种算法。 但排样问题属于最高计算复杂性的n p 完全问题，再考虑到排样时的各种约束条 件，因此至今也没有得到求解排样问题的通用标准方法。因为排样问题的计算 复杂性及其应用的广泛性，1 9 8 8 年在巴黎e u r o t i m s 国际会议上，还专门组 成了排样问题兴趣小组e s i c u p l 9 i ( e u r os p e c i a l i 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 ) 。 从排样问题的分类上看，对二维排样问题的研究是目i j 最具有实用价值的 研究方向，尤其是对二维矩形件排样问题的研究。这是因为矩形零件的形状比 较简单，并且应用比较广泛，对矩形零件的研究不仅可以直接解决矩形件排样 问题，又可以通过包络矩形法将二维不规则零件排样问题转变成为矩形件排样 问题加以解决。因此，矩形件排样问题一直是众多学者研究的热点，他们在优 化排样算法上也提出了不少方法，主要有： ( 1 ) 数学规戈, 1 ( m a t h e m a t i c a lp r o g r a m m i n gt e c h n i q u e s ) 算法。数学舰划法是从 数学的角度出发，将排样问题抽象成某种数学模型后来求得优化解，这也是初 期研究解决排样问题的主要方法。五十年代中期，p a u l l i l 0 1 ，e i s e m a r m i 提出用 线性规划( 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 i 眩l 用数学规划的方法证明 1 绪论 了二维排样问题是一类具有最高计算复杂度的优化计算问题，即n p 完全问题。 后来动态规划( d y n a m i cp r o g r a m m i n g ) 【1 3 】，整数规划( i n t e g e rp r o g r a m m i n g ) 【l ，和 整数线性规划( i n t e g e rl i n e a rp r o g r a m m i n g ) 1 1 5 , 1 6 1 等优化方法也被相继提出用来求 解二维排样问题。 然而，考虑到排样问题的复杂性，用上述数学规划类方法求解矩形件排样 问题不是很理性，尤其是对于零件种类多、数量大的排样问题，计算量会非常 大，求解效率比较低。 ( 2 ) 启发式算法( h e u r i s t i ca l g o r i t h m s ) 。随着排样规模的扩大，启发式排样算 法得到广泛的研究，在求解排样问题中有着重要的地位。启发式算法主要是建 立一组建议性质的、指导算法搜索方向的规则集，按照这个规则集在一定时间 的界限内寻求问题的近似最优解。y a n a s s e i r 7 1 提出了按次序的启发式排样算法， 该算法根据排样零件的长、宽、面积等物理属性设定出一定的优先级准则，先 将待排零件按照这种优先级排序，然后从板材的左下角开始，依次序进行排放。 文献【1 8 】设计出了一种混合的启发式优化算法，该算法在建立排样问题的数学模 型的基础上，先是利用贪婪算法得到一个较优的初始解，再用禁忌搜索方法进 行初始优化，最后利用一种改进的穷举方法进行进一步优化求解。d a g l i 和 t a t o g l u 旧j 提出的启发式算法的启发规则不容易确定，得到的排样结果不稳定。 文献【2 0 】提出通过利用启发式算法和最小下界条件来求解装箱问题。 启发式算法的特点是易于混合各种约束条件和具体目标，但它只针对某些 特定的排样问题会有较好的排样结果，算法不具有通用性。 ( 3 ) 智能优化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) 。2 0 世纪9 0 年代后， 随着遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、蚂蚁算法( a n ta l g o r i t h m ，a a ) 、人 工神经网络( 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 ) 、粒子群优化算法( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 等智能优化方 法的出现和不断研究发展，以及它们在t s p 旅行商问题、车间作业调度问题、 分配问题等组合优化问题上的成功应用，人们丌始运用智能优化算法与排放算 法相结合来解决矩形件排样问题。f a i n a t 2 l j 通过使用模拟退火算法，解决了直线 切割和非直线切割模式下的矩形件排样问题。s e g e n r i e c h 和b r a g a l 2 2 1 运用遗传算 法解决了零件的多件多排问题。文献【2 3 】融合了遗传算法和传统启发式算法，解 决了多种零件在矩形件板材上面的自动化排样。d a g l i l 2 4 1 将神经网络、数学规划 和基因算法相结合来解决矩形件排样问题。文献【2 5 】提出用蚁群算法来解决有动 4 1 绪论 态条件约束的排样问题。文献【2 6 】将启发式算法和遗传算法相结合来对排样问题 进行求解。文献 2 7 1 将s a ，g a ，n e ，r a 与不同排样算法相结合，对不同问题实 例进行求解，得出有两点主要结论：混合算法的求解结果要优于单一排放算 法的求解结果，并且如果排放算法的求解结果越好，则同等条件下混合算法的 求解结果也越好；没有万能的算法适用于所有的问题实例，目前也没有完全 有效的排样算法能很好地解决矩形件排样问题。 1 3 2 国内研究现状 国内对于排样问题的研究起步较晚，从八十年代至今虽然已经取得了不小 的发展，但无论在广度和深度方面，与国外相比还存在着较大的差距，目前排 样问题已经成为国内研究的热点。 九十年代以后，国内对矩形件排样问题的研究有了进一步的发展。曹矩在 文献 2 8 1 中提出了一种近似算法，该算法在排样时依据一种局部最优原则连续动 态的产生一些较小的矩形区域，然后在这些小矩形区域内进行排样，同时也去 除掉一些己经排样过的矩形区域，直到排放完所有的矩形件。文献【2 9 】运用一种 动态启发式算法，来求解有固定尺寸的矩形板材的矩形件排样问题。文贵华等1 3 0 1 提出了一种包含部分穷举的启发式排样算法，使用启发算法对板材进行选取和 对单块大板材进行排样，从而提高了排样速度；使用穷举算法对小规模板材进 行排样并切割余料，保证了切割损耗的降低。文献【3 1 1 运用遗传算法对矩形件排 样问题进行了求解。李建勇等分别将混沌人工神经元网络1 3 2 1 和c h n n 人工神经 元网络【3 3 1 模型与b l 算法相结合，对矩形零件进行优化排样计算。贾志欣等f 3 4 l 利用模拟退火算法来求解矩形件排样问题。 1 4 本文的主要研究工作 本文以非剪切的矩形件带排样问题为研究对象，要求将一组给定的矩形件 在定宽无限长的矩形板材上以最优的方式排放，使所占据的板材高度最小，板 材的利用率最高。 本文在建立矩形件排样问题数学模型的基础上，改进了矩形件排样问题的 排放算法，并将其作为一种解码方法，与传统的遗传算法相结合来求解矩形件 排样优化问题。同时考虑到单一使用遗传算法进行求解的局限性和缺陷，提出 1 绪论 - 将蚁群算法与遗传算法相融合，充分利用两种算法各自的优势来解决矩形件排 样问题。论文主要工作安排如下： 第2 章：建立矩形件排样问题的数学模型，在分析常见的矩形件给定排放 顺序的排放算法的优缺点的基础上，设计出一种改进的排放算法，该算法要充 分考虑矩形件长度和宽度对排样效果的影响。 第3 章：介绍遗传算法的基本思想、特点和实现技术，应用遗传算法对矩 形件排样问题进行求解，对遗传算法的编码方式、初始种群的产生策略、适应 度函数的定义、三种遗传算子进行设计，最后对具体算例进行求解分析。 第4 章：对蚁群算法进行简述，介绍基本蚁群算法的原理、数学模型、实 现流程以及其优缺点，并介绍两种典型的改进型蚁群算法模型。 第5 章：分析介绍蚁群算法与遗传算法融合的可行性及相互融合的方法， 对求解矩形件排样的融合算法进行设计，包括矩形件排样的遗传算法设计、矩 形件排样的蚁群算法设计以及两种算法的衔接方案，给出融合算法的流程图和 对具体算例的求解分析。 第6 章：研究结论综述与展望。 6 2 矩形什排样问题的数学模型及排放算法的改进研究 2 矩形件排样问题的数学模型及排放算法的改进研究 本章在分析矩形件排样问题的数学模型的基础上，对常见的矩形件给定排 放顺序的排放算法以及它们的优缺点进行了讨论，最后详细介绍了本文提出的 改进排放算法。 2 1 矩形件排样问题的数学模型 2 1 1 矩形件排样问题的描述 矩形件排样问题是指将若干给定的矩形零件 届，尼，尼 在宽度为，高 度为的矩形板材上以最优的方式排布，要求所有零件都必须排放在板材内， 且各个零件之间不发生重叠，并满足一定的工艺要求，使板材的利用率最高， 达到节省原材料的目的。 2 1 2 数学模型 从数学的角度分析，矩形件排样问题是一个整数规划问题。为了便于叙述， 定义以下变量： 给定7 个待排零件，s = 1 ，2 ，刀 为矩形件的一组编号； k 所需板材的最小高度； 三某个已知的k i 。的上界； 形，厶矩形件r 的宽度和高度； ( 可，卜叫形件r 的左下角坐标； ( z ，卜矩形件局的右上角坐标； 另外，定义三个二进制逻辑变量： = 0 或1 ，当矩形件r 竖放时取o ，横放时取l ； 包，= o 或l ，当e 位于r j 上侧时取o ，位于下侧时取l ； t = 0 或l ，当r 位于r 右侧时取o ，位于左侧时取i ； 7 2 矩形件排样问题的数学模型及排放算法的改进研究 矩形件排样问题可表达为： m i n k i n 约束条件为： w k ；。 f s f s 群= 彰+ ( 1 一，：) 彬+ 厶 f s = 叫+ ( 1 一) 厶+ ，：彬 f s s 叫+ ( 1 一乞) f s + z o - b ) i y e s l qj 卜lj | + b 4 + b j i 芝1 i , j s ，i j k x ：，y ：，z ，0 ，；，乞，= o ，1 ( 2 9 ) 式( 2 1 ) ( 2 2 ) 限定了矩形件在板材的内部；式( 2 3 ) 与( 2 4 ) 确定了待排矩形件左 下角坐标和右上角坐标的尺寸关系；式( 2 5 ) 表示r 与e 是左右位置关系时矩形 件宽度、高度的邻接限制；式( 2 6 ) 表示墨与弓是上下位置关系时矩形件宽度、 高度的邻接限制；式( 2 7 ) 约束了r 和弓是左右位置关系或是上下位冠关系，保 证矩形件之间互相不重叠。 2 2 矩形件排样的定序规则 所谓定序规则就是确定矩形件排放的先后顺序，此先后次序将最终影响到 材料的利用率，较优的排放顺序可以有效的提高板材的利用率，节约原材料。 定序规则可以根据矩形件的长宽比、面积等各种特性来确定。人们在实践中总 结出了许多有效的定序规则，其中较好的有口5 i ： ( 1 ) 按照矩形件面积的大小来设定优先级。首先计算出每个矩形件的i f i 积，然后 将矩形件按照面积从大到小的顺序依次进行排样。通常情况下，矩形件的面 8 d 动 ” 郇 $ d 乃 动 q q q q q q q q 2 矩形件排样问题的数学模型及排放算法的改进研究 积越小越有利于排放，板材的利用率就会越高。先排放完面积大的矩形件再 排放面积小的矩形件，这样有利于提高板材的利用率；如果先排放完面积小 的矩形件，那么留给面积大的矩形件的选择空间就会越来越小，不利于对板 材的充分利用，从而降低板材的利用率。 ( 2 ) 依据矩形件长度或宽度递减的顺序排放。 ( 3 ) 计算出每个矩形件长度和宽度的比值，对于比值数较大的矩形件要优先排 放。 ( 4 ) 当要排放下一矩形件时，保持已经排放好的矩形件的位置不变。 2 3 矩形件排样给定排放顺序的排放算法 对于一组待排矩形件，给定其排放顺序，如何才能快速将它们排放到板材 上并且使板材的利用率较高，这一直是矩形件排样问题的研究热点。同时，可 将排放算法与智能算法相结合，作为智能算法的解码方法，将由智能算法得到 的可行解转换成排样图。 2 3 1b l 算法 排样过程中任何一个矩形件的微小移动都可以得到一个新的排样图，因此 矩形件排样问题的解是无限多的，为此引入了b l 条件( b o t t o m l e f tc o n d i t i o n ) 使排 样图规格化。如果排样图中任何一个矩形件在不与其他矩形件发生干涉1 3 6 1 ，并 且不超出板材边界的情况下，不能再向下或向左移动，则表示所得排样图已经 满足了b l 条件。b l 条件的引入使矩形件排样问题的解的数量大大减少。 b l 算法满足b l 条件。对于一个给定的矩形件排样序列r ( i = 1 ，2 ，3 ，刀) ， 规定正值表示为矩形件横放，负值表示为矩形件竖放，b l 算法的具体步骤如下 f 3 7 1 ： ( 1 ) 将矩形件足排放在板材的左下角，若冠为负值，即表示将其旋转9 0 度后 再排放，计算出此时所占用板材的最大高度； ( 2 ) 将矩形件r ( i = 2 ，3 ，) 放置于板材右边的最大高度处，然后交替向下向 左移动尺。先尽量向下移动，直到无法继续向下后，再尽量向左移动， 如此交管移动直到矩形件冠无法继续向下向左移动为止( 即与其他矩形 件发生干涉或是超出了板材的边界) ，计算出此时所占用板材的最大高 9 2 矩形件排样问题的数学模型及排放算法的改进研究 度； ， 重复步骤( 2 ) ，直到排放完所有的矩形件，此时计算出的最大高度就是所需 的板材高度。 但是，b l 算法存在一个很大的缺陷，就是不能求得某些问题的最优排样图， 或者说，根据一个已知的排样图反求不出其排样排列。如图2 1 所示的最优排 样图，用b l 算法即使得出所有的排样序列，也无法求解出此最优解。 图2 18 个矩形什构成的最优排样i ! i i 2 3 2 下台阶算法 为了克服b l 算法的缺陷，文献【3 8 】在其基础上进行了改进，提出了下台阶 算法( d o w n s t a i r sa l g o r i t h m ) 。对于一个给定的矩形件排样序列r ( i = 1 ，2 ，3 ，刀) ， 下台阶算法的具体步骤如下【3 8 】： ( 1 ) 将矩形件冠排放在板材的左下角，若足为负值，即表示将其旋转9 0 度后 再排放，计算出此时所占用板材的最大高度； ( 2 ) 将矩形件r ( i = 2 ，3 ，刀) 放置于板材右边的最大高度处，然后交替向下向 左移动r ，并且优先向下移动，直到r 无法再继续向下向左移动为止( 即 与其他矩形件发生干涉或是超出了板材的边界) ，计算出此时所占用板材 的最大高度； 重复步骤( 2 ) ，直到排放完所有的矩形件，此时计算出的最大高度就是所需 的板材高度。 下台阶算法与b l 算法的不同在于：b l 算法中，先考虑将矩形件尽可能向 下移动排放，当无法继续向下移动时，再考虑尽可能向左移动排放。而下台阶 l o 2 矩形件排样问题的数学模型及排放算法的改进研究 算法中，先将矩形件向下移动排放，如果不能下移时，再向左移动排放；当向 左移动过程中如果又可以向下移动，则停止向左移动，转而向下移动，依次类 推，直到无法再向下向左移动为止。 对于给定的矩形件排放序列 1 ，2 ，3 ，4 ) ，b l 算法和下台阶算法的排放 过程分别如图2 2 和图2 3 所示。由图可知，即使是同一排放序列，不同的排 放算法得到的排样结果也不相同。显然下台阶算法也满足b l 条件，对于图2 1 所示的最优排样图，用下台阶算法得到其对应的序列为 1 ，2 ，3 ，4 ，5 ，6 ， - 7 ， 8 。 图2 2b l 算法的排放过程图2 3 卜台阶算法的排放过程 2 3 3 最低水平线算法 文献1 3 9 j 恿过对比研究，发现“b l 算法”除了前面所述的缺陷之外，还容 易出现排样结果左侧偏高的现象，而“下台阶算法 则容易出现右侧偏高的现 象，所以在此基础上又提出了一种改进算法：最低水平线算法( l o w e s th o r i z o n t a l l i n ea l g o r i t h m ) 。该算法总是在排放过程中不断查询已经排放的矩形件的最高轮 廓线中最低且最左的一段水平线。对于一个给定的矩形件排样序列 r ，( i = 1 ，2 ，刀) ，最低水平线算法的具体步骤为p 9 l ： ( 1 ) 设置初始的最高轮廓线为板材的最底边； ( 2 ) 当要排入矩形件r 时，就在最高轮廓线集中选取最低且最左的一段水平 线：若浚水平线段的宽度大于或等于待排入矩形件r ，的宽度，就将r 排 放在此水平线段上，然后随即更新已排入矩形件的最高轮廓线集；否则， 2 矩形件排样问题的数学模型及排放算法的改进研究 将最低水平线提升至与其相邻的左、右两段水平线中高度较低的一段齐 平，同时更新已排入矩形件的最高轮廓线集；重复步骤( 2 ) ，直至能排入 矩形件冠； 重复上述过程，直到排放完所有的矩形件。 对于给定的矩形件排放序列 l ，2 ，3 ，4 ) ，最低水平线算法的排放过程如 图2 4 所示。在排放完矩形件l 后，最低水平线为右边一段，由于其宽度大于 矩形件2 的宽度，故将矩形件2 排放在这。此时，最低水平线变为最右端的一 小段，在排放矩形件3 时，发现矩形件3 的宽度大于最低水平线段的宽度，那 么提升最低水平线段至与其相邻的左边一段水平线齐平，这时最低水平线变为 最左边的一段，比较发现可以将矩形件3 排入，依此方法排入矩形件4 。因此， 对于图2 1 所示的最优排样图，用最低水平线算法可以容易得到其对应的序列 为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) 。 ( a )( b ) ( d ) 图2 4 最低水平线法的排放过料 1 2 ( e ) 2 矩形件排样问题的数学模刑及排放算法的改进研究 最低水平线算法和下台阶算法在排放过程中的不同之处如图2 5 所示。 ( a ) 排放问题 ( b ) 最低水平线算法( c ) 1 - 台阶算法 图2 5 最低水平线算法与。卜台阶算法的比较 2 3 4 基于最低水平线的搜索算法 文献f 4 0 】经过认真研究，认为最低水平线算法的第( 2 ) 步会造成最低水平线以 上板材的部分浪费。最低水平线算法中，当最低水平线段宽度小于待排入矩形 件的宽度时，该算法就即刻将最低水平线段进行提升操作。显然，最低水平线 段的宽度小于当前待排入矩形件的宽度，并不代表它小于所有剩下的待排入矩 形件的宽度，也就是说在所有剩下的待排入矩形件中可能存在其宽度小于最低 水平线段宽度的矩形件。 出于这种考虑，文献【4 0 】在最低水平线算法的基础上提出了一种改进算法： 基于最低水平线的搜索算法。对于一个给定矩形件的排样序列r ( i = l ，2 ，刀) ， 该算法的具体步骤如下【4 0 l ： ( 1 ) 设置初始的最高轮廓线为板材的最底边； ( 2 ) 当要排入矩形件r 时，就在最高轮廓线集中选取最低且最左的一段水平线， 将该水平线段的宽度与下一个待排矩形件r 的宽度进行比较： a ) 若该水平线段的宽度大于或等于待排入矩形件r ，的宽度，就将r ，排放在 此水平线段上，然后随即更新已排入矩形件的最高轮廓线集： b ) 否则在此排样序列中从矩形件尺，所在位胃起向后搜索第一个能够在此 水平线段上排放的矩形件，同时互换这两个矩形件的位冒；如果没有， 则将最低水平线提升至与其相邻的左、右两段水平线中高度较低的一段 1 3 2 矩形什排样问题的数学模型及排放算法的改进研究 齐平，同时更新已排入矩形件的最高轮廓线集，即：对于r = 足，r ， 冠，足i ，r ) ，1 r ， r ， 7 ，如果待排矩形件尺，的宽度大于最低水平 线段的宽度，则向后在 r + ，r ”r ， 中搜索第一个能够在此水平线 段上排放的矩形件，若搜索到矩形件尺的宽度小于最低水平线的宽度， 则将尺，排入，同时，互换r 与尺，的位置，将序列r = r 。，尺，r ， r 兄) 更新为r = 墨，r ，尺 。尺，r ；重复步骤( 2 ) ，直至能 排入矩形件r 。 重复上述过程，直到排放完所有的矩形件。 对于前面给定的矩形件排放序列 l ，2 ，3 ，4 ，基于最低水平线的搜索算 法的排放过程如图2 6 所示。在排放完矩形件l 和2 后，最低水平线为最右端 的一小段，在排放矩形件3 时，发现矩形件3 的宽度大于最低水平线段的宽度， 那么向后搜索到待排放矩形件4 ，但此最低水平线段的宽度仍然大于矩形件4 的 宽度，故提升最低水平线段与其相邻的左边一段水平线齐平，这时最低水平线 变为最左边的一段。重新对比该线段宽度与矩形件3 的宽度；按上述步骤依次 排放矩形件3 、4 。因此，对于图2 1 所示的最优排样图，用基于最低水平线的 搜索算法可以容易得到其对应的序列为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) 。 ( a )( b ) 1 4 ( c ) 2 矩形什排样问题的数学模型及排放算法的改进研究 ( d ) ( f ) ( e ) 图2 6 基于最低水平线的搜索算法的排放过程 2 3 5 本文提出的改进排放算法 本文在认真分析了最低水平线算法和基于最低水平线的搜索算法后，发现 两种算法仍然不足之处： 第一，当最低水平线段的宽度小于当前待排矩形件的宽度时，最低水平线 算法采取立即提升最低水平线段的处理方法，基于最低水平线的搜索算法采用 的是直接向后搜索可以放得下的矩形件的处理方法。显然这样的处理都会在一 定程度上造成最低水平线以上板材的部分浪费，因为虽然最低水平线段的宽度 是小于当f ； 待排矩形件的宽度，但这并不意味着它也小于当前待排矩形件的高 度。如果将此待排矩形件进行旋转9 0 度操作，则有可能就排得下当日仃待排矩形 2 矩形# l q q 样问题的数学模型及排放算法的改进研究 件，从而可以更好的提高板材的利用率。 第二，基于最低水平线的搜索算法的搜索策略是向后搜索过程中一旦发现 可以放得下的矩形件，就立刻停止搜索。这样处理虽然可以满足排样的需要， 但如果该待排矩形件后还有若干个可以放得下的矩形件，并且有的矩形件的宽 度或高度更加接近最低水平线段的宽度，那么，排放这些矩形件则可以更好的 对板材加以利用。 因此，考虑到这些情况，本文在最低水平线算法的基础上提出了改进的排 放算法。对于一个给定的矩形件排样序列r ( f = 1 ，2 ，门) ，改进算法的具体步骤 如下： ( 1 ) 设置初始的最高轮廓线为板材的最底边： ( 2 ) 当要排放矩形件r 时，就在最高轮廓线集中选择最低且最左的一段水平线： a ) 若该水平线段的长度大于或等于尺的宽度，则将该矩形件排放在此水平 线段上，然后随即更新已排入矩形件的最高轮廓线集： b ) 否则，旋转要排放的矩形件r 得到冠，此时若该水平线段的长度大于或 等于旋转后的矩形件尺的宽度，则将该矩形件在此水平线段上排放，然 后随即更新已排入矩形件的最高轮廓线集：若此时该水平线段的长度还 小于旋转后的矩形件冠的宽度，则在此序列中从该矩形件所在位置向后 搜索所有能在此水平线上排布的矩形件，然后从中选取一个长度或宽度 最接近此段水平线长度的矩形件，将它排放在这段水平线上，同时互换 这两个矩形件的位置。如果搜索不到，则将最低水平线提升至与其相邻 的左、右两段水平线中高度较低的一段齐平，同时更新已排入矩形件的 最高轮廓线集：重复步骤( 2 ) ，直到能在最低水平线段上排入此矩形件； 重复上述过程，直到所有待排矩形件都排放完毕。 对于给定的矩形件序列 1 ，2 ，3 ，4 ，5 ，6 ) ，本文的改进算法的排放过程如图2 7 所示。在排放完矩形件l ，2 后，最低水平线为最右端的一段，此时最低水平线 的长度小于待排矩形件3 的宽度，因此旋转矩形件3 ，旋转后得到的矩形件能够 在此水平线段上排放，同时最低水平线更新为最右端的一段。在排放矩形件4 时，无论旋转与否都无法排入，故向后搜索所有待排矩形件。通过比较发现矩 形件5 、6 都能排放在此段水平线上，但矩形件6 的宽度更接近于此段水平线长 度，故调换矩形件4 与6 的位置，优先排放矩形件6 ，之后顺序排放矩形件5 与 4 。故最终矩形件的排放序列更改为 1 ，2 ，3 ，6 ，5 ，4 。 1 6 2 矩形f l f l e 样问题的数学模型及排放算法的改进研究 ( a ) ( e ) ( d ) 幽2 7 改进算法的排放过稃 1 7 2 矩形竹排样问题的数学模型及排放算法的改进研究 图2 8 最低水平线算法所得排样i 鳘i 图2 9 基于最低水平线的搜索算法所得排样图 图2 8 和图2 9 分别为最低水平线法和基于最低水平线的搜索算法所得排 样图( 此排样序列所得两种算法的排样图相同) 。从最终排样结果对比来看，本 文的改进算法的使排样图更加紧凑，产生的空洞面积更少，对板材的利用率更 高。 2 4 本章小结 本章首先分析了矩形件排样问题的特点，在此基础上建立了问题的数学模 型，并给出其约束条件。然后详细介绍了几种常见的矩形件给定排放顺序的排 放算法，并在分析它们优缺点的基础上，设计一种基于最低水平线算法的改进 排放算法，该算法充分考虑矩形件长度和宽度对排样效果的影响，在排放过程 中加入旋转策略，并改进了向后搜索的方案。 1 8 3 基于遗传算法的矩形什排样 3 基于遗传算法的矩形件排样 本章介绍了遗传算法的基本思想、特点和实现技术问题，然后对矩形件排 样的遗传算法进行了设计，并将其与前一章提出的改进排放算法相结合来求解 具体的矩形件排样算例。 3 1 遗传算法概述 美国密歇根大学的h o l l a n d 教授于1 9 7 5 年首先提出遗传算法的概念，并对 遗传算法的基本理论和方法作出了系统的阐述。遗传算法( g e n e t i ca l g o r i t h m ， g a ) 是一种模拟自然界种群进化的全局随机搜索算法【4 ，它借鉴了自然界的自然 选择思想和遗传机制以此来实现种群的优化；该算法根据具体问题的特点编码 该问题的解，并将问题的每一个可行解视为一个个体，由一组个体组成该问题 的种群；算法运行时循环地通过选择、交叉、变异三种遗传算子来产生新子代 个体，并依据适应度函数将每一新子代个体的适应度值计算出来，适应度值的 高低