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

Furniture Intelligent Manufacturing Research家具智能制造8基金项目:湖南省教育厅科学研究重点项目(20A509);麓山实验室研究计划项目;湖南省财政科研专项(2050205)作者简介:胡玉婷(2000-),女,硕士研究生,研究方向:家具设计与工程,E-mail:hu_通信作者:陈星艳(1980-),女,博士,讲师,研究方向:家具设计与工程,E-mail:引文格式:胡玉婷,陈星艳,陶涛,戴向东等.基于遗传算法的板式定制家具异形件排样优化研究J.家具与室内装饰,2023,30(11):08-11.HU Yuting,CHEN Xingyan,TAO Tao,DAI Xiangdong,et al.Research on Special-Shaped Parts Layout Optimization of Panel Customized Furniture Based on Genetic AlgorithmJ.Furniture&Interior Design,2023,30(11):08-11.在当前日益激烈的市场竞争环境下，板式定制家具以其大批量生产的低成本、高质量和高效率优势逐渐成为家具制造业发展的主流方向1-3。由于产品结构和造型的多样性，板式定制家具的组合板件种类繁多且复杂，可根据外部轮廓形状是否为矩形将其分为矩形件少。目前，不少企业在生产中多依赖人工经验排样或是将异形件包含在满足其最大长宽的矩形中进行优化开料，导致原材料浪费大、生产效率低。遗传算法是一种在全局范围内进行随机搜索的优化算法，其优点在于对全局的解空间具有良好的搜索性能以及自和异形件4。随着智能算法在排样方面的研究不断深入5-8，越来越多的板式定制家具企业对矩形件的排样方案进行智能优化，以提升原材料利用率和生产效率9-10。但由于异形件的外部轮廓无确定长宽参数，为多条线段或曲线构成，排样难度大，在家具行业中相应研究较Research on Special-Shaped Parts Layout Optimization of Panel Customized Furniture Based on Genetic Algorithm胡玉婷1,4，陈星艳1,2,3,4，陶 涛1,2,3,4，戴向东1,4，黄艳丽1,4，欧阳周洲1,4，吕 宙1,4，詹秀丽1,4，张玲玲1,4 Hu Yuting1,4&Chen Xingyan1,2,3,4&Tao tao1,2,3,4&Dai Xiangdong1,4&Huang Yanli1,4&Ouyang Zhouzhou1,4&L Zhou1,4&Zhan Xiuli1,4&Zhang Lingling1,4(1.中南林业科技大学，湖南长沙 410004；2.农林生物质绿色加工技术国家地方联合工程研究中心，湖南长沙 410004；3.木竹资源高效利用省部共建协同创新中心，湖南长沙 410004；4.麓山实验室智能家居设计中心，湖南长沙 410004）摘 要：异形件排样问题，是指将一定量不规则异形件放在一定规格的板材中，在满足实际生产要求和约束条件的前提下，提高所排放异形件在板材上的占有率，达到最大化利用板材的优化目标。本文以板式定制家具的异形件排样问题为研究对象，运用具有良好全局寻优解和自适应优化特点的遗传算法，以原材料利用率最大化为目标，构建板式定制家具异形件排样的数学模型，得出排样方案，实现板式定制家具的异形件排样问题优化。在实验部分本研究基于某板式定制家具企业实际生产情况进行算法设计，使用MATLAB软件针对三组样本算例进行了仿真实验。结果表明：采用遗传算法进行异形件排样较企业当前异形件排样方案原材料利用率分别提高2.36%、8.8%、4.43%，验证了本文提出的遗传算法优化排样方案在求解板式定制家具异形件排样问题中的可行性和有效性。关键词：板式定制家具；异形件排样；遗传算法DOI:10.16771/43-1247/ts.2023.11.002中图分类号：TS664.1 文献标识码：A 文章编号:1006-8260(2023)11-0008-04Abstract:The problem of special-shaped parts layout refers to placing a large number of special-shaped parts in a certain specification panel,improving the share of the arranged special-shaped parts in the panel under the premise of meeting the actual production requirements and constraints,and achieving a certain optimization goal.This paper takes the layout problem of special-shaped parts of panel customized furniture as the research object,combining the genetic algorithm with a good global optimization solution and adaptive optimization characteristics,aiming to maximize the utilization rate of raw materials,building the mathematical model of the layout of special-shaped parts of panel customized furniture,obtaining the layout scheme,and realizing the optimization of the layout problem of special-shaped parts of panel customized furniture.Based on the actual production situation of a panel customized furniture enterprise,the algorithm design was carried out in this study.Simulation experiments were conducted on three groups of sample examples in MATLAB software.The results showed that the use of genetic algorithms in the layout of special-shaped parts increases the utilization rate of raw materials by 2.36%,8.8%,and 4.43%,respectively,compared with the current layout scheme of special-shaped parts of enterprises,which verifies the feasibility and effectiveness of the genetic algorithm optimization layout scheme proposed in this paper in solving the layout problem of special-shaped parts of panel customized furniture.Key words:Panel customed furniture;Layout of special-shaped parts;Genetic algorithm基于遗传算法的板式定制家具异形件排样优化研究9F&ID第30卷第11期 2023年11月 家具与室内装饰适应优化等特点11-13，被广泛应用于金属切割、船舶制造和服装裁剪等领域中多目标且求解规模巨大的异形件排样问题中14-16。在板式定制家具中，遗传算法多用于矩形件排样问题研究，在异形件排样问题中较少涉及。因此，本文基于生产实际情况，将遗传算法应用于板式定制家具异形件排样问题中，以原材料利用率最大化为优化目标，构建板式定制家具异形件排样的数学模型，为企业提供合理的异形件排样方案，实现板式定制家具异形件排样问题优化，以期提升企业原材料利用率，降低人工生产成本，增强综合竞争力17。1 板式定制家具异形件排样问题1.1 问题描述异形件排样问题属于二维平面上的排样问题，指将大量不规则异形零件放在指定的板材中以最优的方法进行排布，使排放异形零件区域在板材上的占有率最大，各个异形零件不能重叠，也不能超出板材范围。这是一个组合优化问题，也是一个具有高计算复杂性的NP完全问题18-19。板式定制家具的异形件排样是将轮廓和尺寸几乎不相同的多个异形件，在满足实际生产条件的情况下，按照一定的旋转角度和放置顺序在相同规格的原材料大板上进行合理排布，以提高原材料利用率。1.2 问题建模1.2.1 数学模型板式定制家具异形件排样问题具体描述如下：有n个不同的异形件P=(P1,P2,.,Pn)，在满足实际生产条件的情况下可进行任意角度旋转，按照一定顺序放置在N张宽度为W，长度为L的原异形件和异形件的位置关系主要有以下5种：相离、外接、相交、内接、内含，如图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.1 染色体编码进行排样的一组异形件有n件，将每件异形件视为一个个体进行旋转，然后根据顺序依次放入原材料大板中。异形件序号根据1n进行编号，旋转角度为（0，360）中任意角度，采用多参数级联编码方法，最终的编码公式如（2.1）所示：材料大板上，使原材料大板的利用率最高，约束条件如下所示：（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 重叠判断在异形件放置过程中，通过点与线段、点与异形件和线段与线段的相互位置来判断异形件与异形件的位置关系。（1）相离 （2）外接 （3）相交 （4）内接 （5）内含,=010?(1.1).(,)(,)=,=1,2,3,.,0 (),()=1,2,3,.,0 (),()=1,2,3,.,=010?(1.1).(,)(,)=,=1,2,3,.,0 (),()=1,2,3,.,0 (),()=1,2,3,.,（1.1）（1.2）（1.3）（1.4）=(1.3)=?()+(1.4)=(1.3)=?()+图1 异形件相互位置关系图2 遗传算法求解路径图 1图210 式（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，因此本文以目标函数的倒数为适应度函数。Fitness=1/F(x,)2.2.3 选择算子的设计选择操作是从旧种群中以一定的方法选择优良个体组成新的种群，以繁殖得到下一代个体。本文采取四元锦标赛选择策略，即从种群中随机挑选四个个体，通过比较适应值大小，选取值最大的个体进入 下一代种群，重复进行上述挑选比较，直至新种群达到原来种群规模时停止。2.2.4 交叉算子的设计交叉操作是从种群中随机选择两3 实例仿真3.1 异形件生产信息本文选取某天内某板式定制家产企业异形件生产线的三组异形件生产数据作为研究对象，根据每组异形件的板件名称和尺寸轮廓等生产信息进行编号。其中，第一组异形件的生产信息如表1所示。3.2 算法参数确定遗传算法中的各个参数选取大多依靠经验值。为保障解的多样性、运行时间和种群优化速度，通常种群规模M取值范围为20100，迭代次数N取值范围为100500，在交叉操作中，通常交叉概率Pc取值范围为0.40.99，在变异操作中，通常变异概率Pm取值范围为0.00010.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所示。个个体作为父代，通过两个染色体的交换组合，从而产生新的个体。本文采用分段式交叉，即对两个个体中基因x和 分别进行多点交叉和单点交叉。交叉完后，为保证x为1n之间不重复，需对交叉结果做重排序处理，例如：设有6块异形板件，随机选取两个父代染色体为：在x 上的任意两个不同基因位置和 中一个基因位置进行交叉操作：得到子代染色体为：因x基因中1n中序号不可重复，对x基因中交换位点外重复的基因进行重排序处理后，得到的子代染色体为：2.2.5 变异算子设计为防止遗传算法在优化过程中陷入局部最优解，在搜索过程中，需对个体进行变异操作。本文采用分段式变异，即对个体基因x和分别进行变异。x的变异需要选择两个位置做交互突变，直接选中一个位置做突变即可，例如：设有6块异形板件，随机选取变异的父代染色体为：选取x中两个随机的位置做顺序交互的突变，中一个位置做突变：突变后的个体染色体为：表1 第一组异形件生产信息 序号 板件名称 成品 长度 宽度 厚度 数量 编码1234.484950加厚 背板加厚 背板左侧板右侧板.台 面板右侧板台 面板主卧衣柜客厅 电视柜次卧平开门衣柜主卧梳妆台.客餐厅酒柜儿童房 床头柜客餐厅 电视柜1389.5399.5754.5749.5.411.5499.51833.5446.5599.5449.5499.5.600.3399.5600.618181818.1818181111.11119387045610001194272286200771941329652000319404677910001.194227374100021945880701001119344825910001=1,2,.,1,2,.,（2.1）（2.2）1=1,2,3,4,5,6,0,30,45,60,90,2702=4,5,6,3,2,1,0,45,60,30,90,1801=,3,4,5,6,0,30,45,90,2702=,6,3,2,1,0,45,60,90,1801=4,5,3,4,5,6,0,30,45,30,90,2702=1,2,6,3,2,1,0,45,60,60,90,1801=4,5,3,1,2,6,0,30,45,30,90,2702=1,2,6,3,4,5,0,45,60,60,90,180=1,2,4,5,6,3,0,30,45,60,120,270=1,4,5,3,0,30,45,120,270=1,6,4,5,2,3,0,30,45,90,120,270Furniture Intelligent Manufacturing Research家具智能制造11F&ID第30卷第11期 2023年11月 家具与室内装饰通过遗传算法多次迭代后，可得出三组异形件最终优化排样方案的原材料利用率，并与目前生产模式下将异形件包含在满足其最大长宽的矩形中进行优化开料的原材料利用率进行对比，如表2所示。由表2可得，对板式定制家具异形件的三组算例进行排样时，对比了某企业异形件在目前生产模式下作为矩形优化排样和采用遗传算法方案优化后进行排样对原材料利用率的影响，结果表明，本文采用遗传算法进行优化排样较目前生产模式下的原材料利用率分别提高2.36%，8.80%，4.43%。通过遗传算法多次迭代搜索异形件排样方案，能够有效减少原材料大板上的空隙部分，提高原材料利用率，为企业提高经济效益和提升竞争力22。4 结语本文以原材料利用率最大化为目标对板式定制家具异形件排样问题进行描述并构建了数学模型，将遗传算法应用于异形件旋转角度和放置顺序的求解，提出了更优的板式定制家具异形件排样方案。经多次实验分析确定遗传算法中各项参数值，通过三组实际数据进行仿真实验，对比算法优化方案与目前企业生产方式下的原材料利用率，实验结果表明，采用遗传算法优化后的异形件排样方案的原材料利用率分别提高了2.36%，8.80%，4.43%，表明本文提出的基于遗传算法的优化排样方案在求解板式定制家具异形件排样问题中的可行性和有效性。（责任编辑：向 东）214.14汤德佑,周子琳.基于临界多边形的不规则件启发式排样算法J.计算机应用,2016,36(09):2540-2544.15高勃,张红艳,朱明皓.面向智能制造的不规则零件排样优化算法J.计算机集成制造系统,2021,27(06):1673-1680.16秦振浩.基于多种群遗传算法和剩余矩形匹配算法不规则件优化排样J.现代工业经济和信息化,2022,12(12):262-264.17葛志辉,王阳,潘海鸿等.工艺约束策略下的二维不规则零件排样算法J.广西大学学报(自然科学版),2018,43(02):580-588.18唐坚刚,刘丛,张丽红.基于改进遗传算法的不规则图形排样J.计算机工程,2010,36(21):185-187.19张连兴.旋转因子在真皮二维不规则排版利用率最优算法中的影响研究J.家具与室内装饰,2021,(03):30-35.20沈国峰.基于遗传算法的家具生产作业排序研究D.中南林业科技大学,2019.21冯雨.中国传统家具演变历程研究J.林产工业,2021,58(03):32-36.22唐开军.基于CMF内涵的家具用材设计研究J.林产工业,2021,58(07):22-27.参考文献：1陶涛,吴义强,戴向东等.我国家具智能制造的高质量发展路径研究J.家具与室内装饰,2022,29(07):1-5.2彭亮.对全屋整装与定制家居发展趋势的再思考J.家具与室内装饰,2020,(01):09-10.3 房 西 栓.中 国 定 制 家 具 企 业 成本控制管理研究J.家具与室内装饰,2020,(03):52-53.4王朋.三类典型二维排样问题的智能算法及其应用D.华中科技大学,2021.5罗强.基于灰狼算法的矩形优化排样及其在板式家具开料中的应用D.华中科技大学,2019.6郭巧.面向定制家具生产系统的排产排样算法研究D.天津大学,2019.7时恒秀.家具板材智能排料控制系统优化研究J.机电信息,2018(27):54-55.8王洁,陶涛,陈星艳等.蚁群算法在定制家具矩形零件排样中的应用J.林业工程学报,2022,7(01):192-196.9詹秀丽,戴向东,吴义强等.“双碳”战略背景下的家具减量化设计技术研究J.家具与室内装饰,2022,29(09):1-5.10王张恒,孙德林,黄丽,等.木质家具绿色生产关键影响因素及评价体系构建J.家具与室内装饰,2021,(02):01-05.11郭长江.基于改进双种群遗传算法的二维异形件排样研究D.西华大学,2022.12王迅,陈星艳,陶涛等.遗传算法在板式定制家具混合流水车间调度中的应用J.家具与室内装饰,2022,29(11):1-5.13闫嘉,李林峰,林毓培等.基于改进免疫遗传算法的汽车零件排样J.西南大学学报(自然科学版),2023,45(05):204-表2 不同算例的排样结果12353505217.5314.6916.4172.48%71.51%72.52%74.84%80.30%76.95%2.36%8.80%4.43%组异形件数面积/m2目前生产模式下原材料利用率算法优化方案原材料利用率原材料利用率变化图3 部分排样方案示例图3