基于遗传算法对二维下料问题的研究
来源:用户上传
作者:
摘要：切割问题是生活中常见的一类问题。本文依据线性规划方程和遗传算法来研究矩形切割问题。对于复杂的二维下料问题，所需木板样件的种类样式增多，可采用遗传算法，改变木板切割的适应度函数，从而实现木板切割的利用率最大化。
关键词：线性规划方程;遗传算法;二维下料
矩形切割问题是二维切割一个重要研究方向，怎样实现木材最优化切割，使木板的利用率达到最高，是工业生产的重要课题。近几年来，随着传统算法的发展，各种智能算法的不断完善着矩形切割的方案。而本文是利用遗传算法探究在一块木板上的二维下料问题。
一、单一木板切割模型的建立
仅含一种约束条件：假设对一个长为3000mm、宽为1500mm的矩形木板进行切割，需要得到n个矩形原件P1（长为373mm宽为201mm）。不考虑木板的厚度，怎样切割才能得到最多的矩形原件P1，实现木板的利用率最大化呢？
木板利用率与切割出的小矩形的数量成正相关。依据运筹学中的整数规划问题，可将切割问题分为横向切割和纵向切割两种方案。由于斜向切割会造成原料的滥用且讨论情况更复杂，所以不采用斜向切割的方式。通过构建线性规划方程组，以木板的长、宽为限制条件，得出使木板材料剩余面积最小的方案。
根据木板的排放方式，建立整数规划方程组：
式中：木板的长与宽分别为L、W;P1原件的长与宽分别为l1、w1;m表示将P1原件的宽w1沿着木板的L方向排列的个数;b指P1原件的长l1沿着木板的W方向排列的个数。运用LINGO软件对方程组求解得：m=13，n=1，a=0，b=4.即目标值z=44888，但并不是最优方案。
分析求解结果得，P1原件的宽沿着木板的长排列最多可排13列;P1原件的长沿着木板的宽排列最多可排4行。此时木板的长边剩余387mm，宽边剩余8mm，所以可再放置一个P1原件的长边。故仍可以排放7个P1原件。综上所述，在木板上切割P1原件时，当切割59个P1板时，木板利用率为98.3%，达到最高利用率。
二、多元木板切割模型的建立
两种约束条件的切割方案：现多考虑一个矩形原件P3（长度为406mm，宽为229mm）。由于矩形原件P3的切排样方式不定，加深求解的难度。针对NP类问题可建立有关遗传算法的数学模型进行求解。
構建一个函数：
k（x）=1x0
0x<0（1）
由于切割原件在排放时受到木板尺寸的影响，且每个原件之间的排放互不重叠，依此建立如下方程：
k（xli-xrj）+k（yti-ybj）+k（xlj-xri）+k（ytj-ybi）1（2）
式中：第i个原件排放在第j个原件后面，且i<j恒成立。为了限制矩形原件排放的长宽范围，还需满足：min（xli）≥0，max（xri）≤W，min（xbi）≥0，max（yri）≤L。其中：xli、xri、ybi、yti分别指第i个原件的左侧、右侧、下侧和上侧。
（1）遗传算法的建立：
首先初始化种群，对各个矩形原件采用符号编码，将两种原件命名为1、2。原件既可横排也可竖排，取横排为正，竖排为负。下面以P1、P3原件在长为635mm，宽为610mm的木板上的排放为例，p={1，1，2，2}表示底层竖排一个原件P1，再横排一个原件P1，第二层先横排一个原件P3，再竖排一个一个原件P3。
其次构建适应度函数。将木板利用率作为函数，得到适应度函数方程：
H（p）=h（p）LW=∑niliwiLW（3）
式中：H（p）表示算子，指编码为p的个体的面积，ni为标号为i的原件的出现次数，li、wi分别表示标号为i的原件的长与宽（这里的i与方程（4）约束条件中的i有区别）。其余参量均取默认值。
（2）初始化种群的构建：
由于初始化种群的编码较多，一般初始种群的大小要在20个以上，可采用逐层排列生成初始化种群。
步骤一：建立一个坐标系，确定上限宽度与长度（即木板尺寸）。
步骤二：生成一个随机序列数，取值在集合{2，1，1，2}内，表示待排样的原件。
步骤三：根据随机数，将木块从左往右按层排列。
步骤四：当排样高度达到宽度限度时，跳出循环，给出排列编码。
步骤五：重复上述步骤，直至给出20个以上的初始个体，构建成一个初始化种群。
（3）模型的求解：
运用MATLAB实现遗传算法，可得三种利用率较高的方案：
在实际生产中，所需原材料的种类是多样的（不仅限于矩形），求解情况更加复杂。对于多种约束条件，仍然利用遗传算法，加入新的约束条件，对适应度函数进行改造。
H（p，N）=h（p）NLW=∑niliwiNLW
P=P{p1，p2，…，pn}（4）
式中：ni是已知量，N是待求解量。然后改造初始化种群，对所加的参数Ci对原件进行计数，引入参数N对木板计数。合并每个板的编码排序，一个板组成一个编码，原件全部排完时构成P。进一步对初始种群改造，再次建立坐标系。
三、评价与总结
本文构建的模型中没有给出具体的解码算法和筛选算法，另外遗传算法也的稳定性较差，因为算法属于随即类算法，对初始种群有很强的依赖性，不同的初始种群得到结果与速度也不尽相同。可采用模拟退火算法和蚁群算法相结合，当面临实际解决时，可以通过构建这两个算法解决人力解码的问题。
参考文献：
[1]马广焜，刘嘉敏，黄有群，等.一种有约束矩形排样问题的求解算法[J].沈阳工业大学学报，2006，28（4）.
[2]赵新芳，崔耀东，杨莹，等.矩形件带排样的一种遗传算法[J].计算机辅助设计与图形学学报，2008，20（4）：540544.
作者简介：田康（2000），男，汉族，安徽铜陵人，本科，研究方向：信号处理。
指导老师：杨静（1980），汉族，安徽濉溪人，博士，副教授，研究方向：DNA计算与组合优化。
转载注明来源:https://www.xzbu.com/1/view-15133199.htm
