南京林业大学李荣荣副教授团队:基于样本优化遗传算法的板式家具矩形零件排样技术

为适应板式家具大规模柔性定制生产的开料要求,提高开料效率与板材利用率,在启发式算法的基础上提出了一种以向遗传算法提供优质初始基因样本为目标的样本优化算法,满足在降低板材开料计算复杂度的前提下板式家具大规模柔性定制生产的需求。以大规模柔性定制家具的矩形零件开料问题为对象,通过双线程计算的方式,对不可成组的矩形零件采用传统的遗传算法优化,对可成组的矩形零件采用样本优化算法成组处理得到优质的初始样本,将二维矩形排样问题转化为一维线性问题降低算法维度以提高算法效率; 再结合遗传算法对遗传算子、编码方式及适应度函数进行优化设计; 最后将优化结果合并,实现板式家具大规模柔性定制的排样问题优化。比较了最低水平线搜索算法、样本优化算法以及基于样本优化的遗传算法对排样利用率的影响,研究结果表明:大规模算例中,基于样本优化的遗传算法使用的板材比原算法减少1张,总利用率比最低水平线搜索算法和样本优化算法分别提高了6.20和2.73个百分点。通过实例验证,本研究所涉及排样算法在板式家具矩形零件排样问题中求解具有有效性,显著提升材料利用率,提高企业经济效益。

智能算法的初始样本优化,不仅可以降低算法的难度,还可提高排样效率和材料利用率。

排样算法主要分为启发式算法和智能算法两种,也有学者将两种智能算法结合开发出混合算法。启发式算法通常比较简单,排样效率快,然而应用局限性大。

智能算法是在启发式算法的规则基础上,根据智能算法优化矩形零件的排入顺序,常见算法有蚁群算法、模拟退火算法、遗传算法等。

综上所述,现有的算法已经不断被优化,但在实际应用过程中全局搜索和局部搜索之间的矛盾、样本数量过多难以达到全局最优等问题依旧存在。

基于此,南京林业大学黄尚伟、李荣荣提出样本优化算法,通过同规格样本和同类型样本的矩形零件归类得到优质样本,再对矩形零件成组排样,实现将二维矩形排样问题转一维线性排样问题,突破了长宽方向必须同时考虑的限制。这种方法不仅丰富了排样算法的理论框架,同时降低了遗传算法计算难度,有助于企业生产效率和板材利用率的提高,增加企业效益。

1.1二维排样问题描述

对于开料中的矩形零件排样,好的样本能够极大地缩短智能算法计算时间,加快排样进程。目前,各类先进的智能排样算法为了追求高利用率忽视了生产效率,然而在实际生产过程中由于锯路损失、废料以及复杂切割路径等因素直接影响了材料利用率。目前,理想的板材利用率一般约为85%。二维矩形开料问题可以视作NP-Hard(非确定性多项式)问题,指所有NP问题都是能在多项式时间复杂度内归约到的问题,即随着矩形零件的增加,解的数量也呈指数倍增长,寻找最优解的时间便急剧增加,影响开料效率。正常情况下,单个矩形零件至多需要切四下,当对多个矩形零件开料时,如果保证每一刀都一路切下去且能与尽可能多的矩形零件的边重合,就能减少下刀的数量以及下刀过程中产生的原料损耗。因此,矩形零件数量相同的情况下所需下刀次数越少,原料损耗就越少,开料速度就越快。矩形排样问题可以视作寻找同类矩形零件的过程,即将长宽适应度高的矩形零件划分为一个样本,再对此样本依次排样,最终提高开料效率与板材利用率。

1.2二维排样问题的算法简化原理

二维矩形开料问题考量长和宽两个维度方向,将其转化为一维线性问题可通过约束宽度方向来实现,即定宽无限长,即先在板材宽度方向上排列等长等宽或者等长不同宽的矩形零件,同时每个组合都能保证板材切割后余料大小在允许范围内。然后,将这些零件组合再排列到板材长度方向,简化运算逻辑。矩形零件内部的成组策略不仅解决了宽度方向的定宽限制,也有利于筛选出优质样本。采用遗传算法求解排样方案的基本思想如下:每次使用待分配的成组矩形零件生成当前排样方式,在不产生多余废料的前提下,尽可能多地重复当前排样方式; 重复上述过程直到满足全部成组矩形零件的排样需求。

2.1样本优化算法

样本优化算法是以填充算法为基础改进得来的启发式算法,原理是通过合并同类样本再成组排样。成组的矩形零件分为同规格和同类型两种,满足矩形板材宽度方向的最小利用率要求,否则不成组(图1)。样本优化算法分为3个阶段:①矩形零件成组; ②余料区域填充; ③最低水平线搜索算法收尾。本算法将二维矩形排样问题拆解为一维线性问题,有利于减少排样次数、降低算法维度、提高开料效率，同时兼顾板材利用率。

2.1.1数学模型

为了方便样本优化过程的描述,需要对样本优化算法中的物理量进行解释说明。如图2所示,矩形板材为长度为L、宽度为W,矩形区域的编号为K,锯路宽度为W_r; 矩形零件编号为R_i[W_i,L_i,N,Deg=0°](i=1,2,3,…,n),其中,R_i为样本的编号,W_i为矩形零件的宽度,L_i为矩形零件的长度,N为该矩形零件的数量,Deg为矩形零件的旋转角度; 余料编号为S_i[W_i,L_i,K](i=1,2,3,…,n)。

1)成组矩形零件排样。建立同类型矩形零件集合C_j{R_i}(i、j=1,2,3,…,n),余件集合R_e{R_i}(i=1,2,3,…,n),余料集合R_s{S_i}(i=1,2,3,…,n); 规定矩形板材区域的利用率为P,矩形板材区域在宽度方向允许的最小利用率为P_min,矩形零件在矩形板材区域宽度方向上横竖叠放的利用率为P_W和P_L(图3)。公式如下:

式中:W_i为矩形零件的宽度; L_i为矩形零件的长度; N为矩形零件的数量; W_r为锯路宽度; W为矩形板材区域的宽度。

在处理矩形零件的排样问题时,一种有效的方法是对每种零件进行横向和纵向的叠放试验,以决定哪种叠放方向能够最大化板材的利用率。具体操作如下:

首先,对于每种矩形零件,将其分别横放和竖放在矩形板材上,以模拟不同的排样配置。对于每种配置,计算出两种叠放方向的利用率,分别为横向利用率P_W和纵向利用率P_L。若P_W≥P_L,则选取利用率P_W采用横放方式; 若P_W<P_L,则选取利用率P_L采用竖放方式。

在确定矩形零件的最优叠放方向后,将最优利用率P与板材区域内规定的最小利用率P_min进行比较。若P≥P_min,则最终确定矩形零件成组叠放方式,并扣除叠放所需的矩形零件数量N; 若P≤P_min,则将其归类到同类型矩形零件集合C_j中并进行同类型矩形零件成组处理,方法同上,只考虑长度相同那条边的叠放情况。

2)不成组矩形零件排样。成组的矩形零件排列完毕后,剩余的矩形零件会优先在矩形板材的余料区域排样,余料区域指每块板材排样后未被利用的部分,如图4所示。余件按照面积大小选取,以余料左上角为原点贴合两边摆放并判断剩余区域是否可以填充剩余矩形零件,若能则继续填充; 若不能则选择下一块余料。当余料区域排样结束,则对剩余待排矩形零件使用最低水平线搜索算法进行排样,直至结束。

2.1.2 样本优化算法流程

为了降低遗传算法的计算复杂度,提出了先优化样本结构再排样的算法。具体步骤如下:

1)参数设置并建立数学模型。首先,设定矩形板材区域的所有基本参数,包括板材的尺寸、形状等参数。构建数学模型来描述这些参数与排样效果之间的关系,确保所有变量都被恰当地考虑并能够反映在最终的排样结果中。

2)成组条件判断。依次对单个矩形零件进行成组叠放条件判断生成同规格成组矩形零件; 再对剩余所有矩形零件进行成组叠放条件判断生成同类型成组矩形零件并归入集合C_j中; 最后,将所有不成组的矩形零件归入余件集合R_e中。

3)排样。更新矩形零件和集合信息,根据同规格成组、同类型成组、不成组的顺序依次将矩形零件排列在矩形区域上。

4)输出对应的成组矩形零件排样信息、余件信息。

2.2基于样本优化的遗传算法

传统遗传算法随着算法的迭代,样本中的染色体趋于相似,交叉、变异操作进化作用有效性降低,样本难以进化,导致算法陷入早熟。本研究通过样本优化算法为遗传算法提供优质的初始样本数据,将成组的矩形零件集合看作单一的样本个体,从而把二维矩形排样问题转化成一维线性问题,避免算法陷入早熟。

2.2.1 遗传算法编码与解码

遗传算法编码方式主要有二进制编码和十进制编码两种。十进制编码占用内存低,编程简单易实现。因此,本研究采用十进制编码方式。BL算法、最低水平线算法等主要是研究定宽无限长的板材,且只适用于正交切割的情况,在实际应用中往往会受到限制。本研究用最低轮廓线搜索算法作为解码方法,加入板材长度的限制,从而满足“一刀切”的工艺约束。

2.2.2 基于一维线性的遗传算法数学模型

求解使用板材数量最少的排样方案,可以通过求和每块板材废料的长度来简化计算过程。本研究算法设计中对待排成组矩形零件随机排列形成多个样本,再选取几个优质样本进行交叉、变异操作,最后根据适应度值判断是否满足终止条件,适应度值为所有成组矩形零件的横向长度与(板材数K-1)的比值,满足即得出最优解; 若不满足,达到最大迭代次数后终止。

目标函数如下:

2.2.3基于样本优化的遗传算法流程

将样本中所有染色体代入适应度函数(4)中可以得到各染色体评估的适应度值。按照基本遗传算法逻辑将样本中的染色体进行选择、交叉、变异操作的运行,直到满足终止条件,获得最优解。最后采用填充算法和遗传算法对不成组矩形零件进行收尾,如图5所示。

3.1实 例

本次研究选取了小、中、大3种规模算例数据,根据矩形零件的序号对零件进行编码,根据矩形零长度、宽度、数量等材料信息对编码零件赋值。矩形零件信息如表1～表3所示。

3.2算法参数设置

算例计算过程通过MATLAB编写的程序实现,对样本优化算法和遗传算法中的各个参数进行赋值,算法参数设置如表4所示。

3.3算例结果分析

对小、中、大3个规模算例中的试验数据,应用最低水平线搜索算法、样本优化算法和基于样本优化的遗传算法3种算法进行对比论证。原料的尺寸规格为1 220 mm×2 440 mm。大规模算例中,待排样的矩形零件共29种,数量为159个。取样本规模为20,最大迭代次数为200次。最终得到矩形零件排样优化图,如图6所示。

通过最低水平线搜索算法、样本优化算法、基于样本优化的遗传算法计算,得出3种算法的最终排样方案以及每块板材的利用率对比结果。在小规模算例中,3种算法都使用了5张板材,利用率分别为83.32%,87.57%,88.35%; 在中规模算例中,3种算法都使用了8张板材,利用率分别为89.11%,88.46%,91.87%; 在大规模算例中,最低水平线搜索算法总共使用了13张矩形板材,总利用率为85.62%。样本优化算法总共使用了12张板材,总利用率为89.09%; 基于样本优化的遗传算法总共使用了12张板材,总利用率为91.82%。

结果显示,在处理不同规模的矩形零件开料问题时,基于样本优化的遗传算法可降低原材料消耗。在小规模的实例中,其利用率比最低水平线搜索算法提高了5.03个百分点,比单纯的样本优化算法提高了0.78个百分点; 在中等规模的实例中,利用率比最低水平线搜索算法提高了2.76个百分点,比样本优化算法提高了3.41个百分点; 而在大规模的实例中,利用率比最低水平线搜索算法提高了6.20个百分点,且节省了一块板材,比样本优化算法提高了2.73个百分点。