基于遗传算法的板式定制家具异形件排样优化研究

■胡玉婷，陈星艳，陶 涛，戴向东，黄艳丽，欧阳周洲，吕 宙，詹秀丽，张玲玲

(1.中南林业科技大学，湖南长沙 410004；2.农林生物质绿色加工技术国家地方联合工程研究中心，湖南长沙 410004；3.木竹资源高效利用省部共建协同创新中心，湖南长沙 410004；4.麓山实验室智能家居设计中心，湖南长沙 410004）

在当前日益激烈的市场竞争环境下，板式定制家具以其大批量生产的低成本、高质量和高效率优势逐渐成为家具制造业发展的主流方向[1-3]。由于产品结构和造型的多样性，板式定制家具的组合板件种类繁多且复杂，可根据外部轮廓形状是否为矩形将其分为矩形件和异形件[4]。随着智能算法在排样方面的研究不断深入[5-8]，越来越多的板式定制家具企业对矩形件的排样方案进行智能优化，以提升原材料利用率和生产效率[9-10]。但由于异形件的外部轮廓无确定长宽参数，为多条线段或曲线构成，排样难度大，在家具行业中相应研究较少。目前，不少企业在生产中多依赖人工经验排样或是将异形件包含在满足其最大长宽的矩形中进行优化开料，导致原材料浪费大、生产效率低。

遗传算法是一种在全局范围内进行随机搜索的优化算法，其优点在于对全局的解空间具有良好的搜索性能以及自适应优化等特点[11-13]，被广泛应用于金属切割、船舶制造和服装裁剪等领域中多目标且求解规模巨大的异形件排样问题中[14-16]。在板式定制家具中，遗传算法多用于矩形件排样问题研究，在异形件排样问题中较少涉及。因此，本文基于生产实际情况，将遗传算法应用于板式定制家具异形件排样问题中，以原材料利用率最大化为优化目标，构建板式定制家具异形件排样的数学模型，为企业提供合理的异形件排样方案，实现板式定制家具异形件排样问题优化，以期提升企业原材料利用率，降低人工生产成本，增强综合竞争力[17]。

1 板式定制家具异形件排样问题

1.1 问题描述

异形件排样问题属于二维平面上的排样问题，指将大量不规则异形零件放在指定的板材中以最优的方法进行排布，使排放异形零件区域在板材上的占有率最大，各个异形零件不能重叠，也不能超出板材范围。这是一个组合优化问题，也是一个具有高计算复杂性的NP完全问题[18-19]。板式定制家具的异形件排样是将轮廓和尺寸几乎不相同的多个异形件，在满足实际生产条件的情况下，按照一定的旋转角度和放置顺序在相同规格的原材料大板上进行合理排布，以提高原材料利用率。

1.2 问题建模

1.2.1 数学模型

板式定制家具异形件排样问题具体描述如下：有n个不同的异形件P=(P1,P2,..,Pn)，在满足实际生产条件的情况下可进行任意角度旋转，按照一定顺序放置在N张宽度为W，长度为L的原材料大板上，使原材料大板的利用率最高，约束条件如下所示：

（1）满足工厂实际生产中因锯路宽度产生的工艺间隙要求、异形件轮廓的加工余量要求和质量精度要求以及原材料大板的修边要求等；

（2）异形件在排布时不能发生相互重叠的情况；

（3）所有异形件在最后输出结果中的位置始终包含在原材料大板内部，不得跨越原材料大板边界。

建立板式定制家具异形件排样问题的数学模型如下：

式(1.1)中F(x,θ)为异形件排样问题的目标函数，x和θ表示异形件序号和放置前的旋转角度，i=(1,2,..N)为原材料大板的编号，piarea为第i块原材料大板的面积，Miarea为第i块原材料大板上异形件最小放置矩形的面积，使用的原材料大板越少，目标函数F(x,θ)的值越小。

式(1.2)为上述(2)(3)原则的数学表述，pi(idi,∆xi,∆yi,∆θ)中id为异形件的序号，∆xi，∆yi为异形件进行平移、旋转后坐标的变化量，△θ为异形件旋转的角度，交集为空集代表任意两个异形件之间没有相互重叠。Pi(x)为异形件在原材料大板上排布的最大横坐标，处于0到W之间，Pj(y)为异形件在原材料大板上排布的最大纵坐标，处于0到L之间，以确保排样的异形件全都包含在原材料大板中。

1.2.2 重叠判断

在异形件放置过程中，通过点与线段、点与异形件和线段与线段的相互位置来判断异形件与异形件的位置关系。异形件和异形件的位置关系主要有以下5种：相离、外接、相交、内接、内含，如图1所示。

■图1 异形件相互位置关系

在异形件的位置关系为相交、内含和内接时，判定为重叠，需将异形件重新放置或调整角度。

1.2.3 几何运算

在减少异形件彼此之间空隙时，为避免其相互重叠或超出原材料大板，需不断对异形件进行平移和旋转，运算法则如下所示：

式(1.3)中(x，y)为异形件的坐标位置，∆x，∆y为平移距离，(x',y')为平移后坐标；式(1.4)中，(rx,ry)为异形件旋转中心，θ为旋转角度。

2 异形件排样的遗传算法设计

2.1 算法原理

遗传算法是模拟生物在自然界进化过程中自然选择和遗传机理的计算模型和全局搜索最优解的概率搜索算法[20]。在面对异形排样这类目标种类多，且求解规模巨大的问题上提供了一个通用的计算框架和有效解决路径，求解路径如图2所示。

■图2 遗传算法求解路径

2.2 算法设计

2.2.1 染色体编码

进行排样的一组异形件有n件，将每件异形件视为一个个体进行旋转，然后根据顺序依次放入原材料大板中。异形件序号根据1～n进行编号，旋转角度为（0°，360°）中任意角度，采用多参数级联编码方法，最终的编码公式如（2.1）所示：

式（2.1）中xi为排放的每个异形件的序号，θi表示相对应的异形件在放置前旋转的角度。例如，假设有5块异形件进行排布，若染色体编码为β={[4,5,3,1,2],[90°,60°,30°,180°,45°]}，表示第一个放置的是序号为4的异形件，且在放置前进行90°旋转，以此类推，最后一块放置是序号为2的异形件，且放置前进行45°旋转。当有n个异形件时，按照染色体编码中位置顺序和该位置序号的异形件相应旋转角度放置，直至所有的异形件放置完毕。

2.2.2 种群初始化和适应度函数确定

初始化种群选择随机生成，按照种群的数量M对个体进行初始化。设有n个异形件，则序号x的初始化为随机排序的1到n的序列，对应的旋转角度θ初始化为（0°，360°）中的任一角度值。

适应度函数表明个体的优劣性，在板式定制家具异形件排样模型中，目标是寻找最大化利用率的异形件排样方案[21]，因此本文以目标函数的倒数为适应度函数。

2.2.3 选择算子的设计

选择操作是从旧种群中以一定的方法选择优良个体组成新的种群，以繁殖得到下一代个体。本文采取四元锦标赛选择策略，即从种群中随机挑选四个个体，通过比较适应值大小，选取值最大的个体进入下一代种群，重复进行上述挑选比较，直至新种群达到原来种群规模时停止。

2.2.4 交叉算子的设计

交叉操作是从种群中随机选择两个个体作为父代，通过两个染色体的交换组合，从而产生新的个体。本文采用分段式交叉，即对两个个体中基因x和θ分别进行多点交叉和单点交叉。交叉完后，为保证x为1～n之间不重复，需对交叉结果做重排序处理，例如：

设有6块异形板件，随机选取两个父代染色体为：

在x上的任意两个不同基因位置和θ中一个基因位置进行交叉操作：

得到子代染色体为：

因x基因中1～n中序号不可重复，对x基因中交换位点外重复的基因进行重排序处理后，得到的子代染色体为：

2.2.5 变异算子设计

为防止遗传算法在优化过程中陷入局部最优解，在搜索过程中，需对个体进行变异操作。本文采用分段式变异，即对个体基因x和θ分别进行变异。x的变异需要选择两个位置做交互突变，θ直接选中一个位置做突变即可，例如：

设有6块异形板件，随机选取变异的父代染色体为：

选取x中两个随机的位置做顺序交互的突变，θ中一个位置做突变：

突变后的个体染色体为：

3 实例仿真

3.1 异形件生产信息

本文选取某天内某板式定制家产企业异形件生产线的三组异形件生产数据作为研究对象，根据每组异形件的板件名称和尺寸轮廓等生产信息进行编号。其中，第一组异形件的生产信息如表1所示。

表1 第一组异形件生产信息

3.2 算法参数确定

遗传算法中的各个参数选取大多依靠经验值。为保障解的多样性、运行时间和种群优化速度，通常种群规模M取值范围为20～100，迭代次数N取值范围为100～500，在交叉操作中，通常交叉概率Pc取值范围为0.4～0.99，在变异操作中，通常变异概率Pm取值范围为0.0001～0.1。

本文中，采用MATLAB编写上述遗传算法程序，通过多次实验分析确定种群规模M取值为40，迭代次数N取值为120，交叉概率Pc取值为0.8，变异概率Pm取值为0.1。

3.3 运行实例分析

本研究选取三组异形件在企业常用规格的原材料大板上进行排样方案示例，第一组异形件总面积为17.53 m2，共53块异形件，第二组异形件总面积为14.69 m2，共50块异形件，第三组异形件总面积为16.41 m2，共52块异形件，将三组异形件加工信息导入MATLAB软件中进行图形数据化处理，再通过遗传算法多次迭代求解后，最终完成三组异形件排样优化方案，选取第一组的部分排样方案实例如图3所示。

■图3 部分排样方案示例

通过遗传算法多次迭代后，可得出三组异形件最终优化排样方案的原材料利用率，并与目前生产模式下将异形件包含在满足其最大长宽的矩形中进行优化开料的原材料利用率进行对比，如表2所示。

表2 不同算例的排样结果

由表2可得，对板式定制家具异形件的三组算例进行排样时，对比了某企业异形件在目前生产模式下作为矩形优化排样和采用遗传算法方案优化后进行排样对原材料利用率的影响，结果表明，本文采用遗传算法进行优化排样较目前生产模式下的原材料利用率分别提高2.36%，8.80%，4.43%。通过遗传算法多次迭代搜索异形件排样方案，能够有效减少原材料大板上的空隙部分，提高原材料利用率，为企业提高经济效益和提升竞争力[22]。

4 结语

本文以原材料利用率最大化为目标对板式定制家具异形件排样问题进行描述并构建了数学模型，将遗传算法应用于异形件旋转角度和放置顺序的求解，提出了更优的板式定制家具异形件排样方案。经多次实验分析确定遗传算法中各项参数值，通过三组实际数据进行仿真实验，对比算法优化方案与目前企业生产方式下的原材料利用率，实验结果表明，采用遗传算法优化后的异形件排样方案的原材料利用率分别提高了2.36%，8.80%，4.43%，表明本文提出的基于遗传算法的优化排样方案在求解板式定制家具异形件排样问题中的可行性和有效性。