秦振浩
（河北工业大学经济管理学院，天津 300400）
引言二维不规则件排样问题是指将一系列形状不规则的二维平面零件尽可能以最优方式排放到矩形板材当中，使得板材的利用率最大。该问题广泛存在于现实生产生活中，从钣金下料、玻璃切割、纸品剪裁到家具生产，都能够看到其实际应用。在数学上该问题属于NP-hard的组合优化问题，计算过程复杂多变，计算量是呈爆炸性的，很难求出最优解。因此，对二维不规则件排样问题的研究具有重要的理论和实用价值。本文通过矩形包络法将二维不规则件排样问题转化为矩形件排样问题，研究基于多种群遗传算法在零件入排序列和角度上的应用以及剩余矩形匹配算法在零件排放策略中的应用，从而实现二维不规则件排样问题的综合求解。
1 问题描述及模型建立二维不规则件排样问题通常可以描述为：将n个形状不完全相同的二维不规则件{p1，p2，…，pn}不重叠地排放到m张长为W、宽为H的矩形板材A中，在排样过程中，入排零件需要满足特定的条件，才能保证排样过程顺利进行。这些约束条件包括：
1）pi与pj互不重叠，i≠j，i、j＝1，2，…，n；
2）pi必须排在板材A内部，i＝1，2，…，n；
3）pi可以旋转一定的角度，i＝1，2，…，n。
假设F为板材利用率，S为所有入排零件的面积之和。本文的研究目标为板材利用率最大，定义板材利用率为所有入排零件的面积之和与板材面积之比，则二维不规则件的数学模型如下：
式（2）确保了入排零件之间没有交叠部分，式3确保了入排零件不超过板材的边界，式（4）中的o表示零件旋转的角度，式（4）限制了零件可旋转的角度。
2 相关方法描述2.1 不规则件的预处理直接将不规则件排放到板材内部，操作起来相当复杂，需要考虑到复杂的几何问题，包括需要计算不规则件的大小、判断其排放位置和是否重叠等，为了简化不规则件的排样问题，学者们相继提出了一些零件预处理方法，包括矩形包络法、组合包络法等[1]。本研究组合使用这两种方法，对近似矩形的不规则件直接使用矩形包络法求其最小包络矩形，对形状互补的两个或多个零件首先进行平移、旋转进行组合包络，然后运用矩形包络法求其最小包络矩形，如图1所示。
图1 零件的预处理
2.2 多种群遗传算法零件的入排顺序问题属于典型的NP-hard组合优化问题，针对该问题，本研究采用多种群遗传算法，设置3个进化种群，并将这3个进化种群分为2个部分。第1部分有1个种群，该种群内的个体基因序列依据待排零件的面积有序生成，这是启发于现实中工人的经验排样，先排放面积大的零件再排放面积小的零件。这种排样方式能够起到加速收敛的目的，同时优先排放面积大的零件，面积小的零件在后续排样中将具有更高的灵活性[2]。第2部分有2个种群，这2个种群内的个体序列都是随机生成的，设置2个随机种群也是为了提高算法的搜索范围。
2.2.1编码
本研究采用组合编码方式，用整数编码来确定零件的入排顺序，每个零件给定一个入排序号。用二进制编码来确定零件的入排角度，1代表零件旋转90°，0代表零件旋转0°，将零件入排序号排列成串再加上一个与之对应的二进制编码串就是一个可行解。
2.2.2 适应度函数
适应度函数是用来评价个体质量优劣的，个体的适应度值越高，质量越高。反之，质量越低。文中采用的适应度函数为目标函数。
2.2.3 选择操作
本文基于轮盘赌法对个体进行选择操作，该方法以个体的适应度值为选择和淘汰的依据，个体的适应度值越大，被选中的可能性越大。反之，被淘汰的可能性越大。
2.2.4 交叉操作
为了提高算法的局部寻优性能，本研究采用自适应交叉概率，交叉概率的调整公式为：
式中：f1、favg、fmax分别为要执行交叉操作的两个父代个体中较大的适应度值、种群内当前进化代数中父代个体的平均适应度值和种群内当前进化代数中父代个体中最大的适应度值；pc1和pc2为预先设定的两个固定值。从式（5）中可以看出，个体的交叉概率pc会随着适应度值的取值情况进行动态调整，可克服算法的不成熟收敛，并避免优秀染色体被破坏[3]。判断两个父代个体是否交叉，通过在（0，1）内随机生成一个数r，当pc＞r时，执行交叉操作，否则不执行。当染色体执行交叉操作时采用两点环形交叉方式[4]。
2.2.5 变异操作
与交叉操作相同，本研究同样基于自适应的思想，采用自适应的变异概率pc，变异概率的调整公式为：
式中：fm为种群内待变异个体的适应度值；pm1和pm2为预先设定的两个固定值。对变异概率进行动态的调整既能保持种群内个体的多样化，还可以克服算法限入局部解的弊端。
判断某个染色体是否变异，通过在（0，1）内随机生成一个数r，当pm＞r时，执行变异操作，否则不执行。文中变异操作是对零件的入排顺序向量和入排角度向量进行的，对零件的入排顺序向量执行交换变异，对入排角度向量执行旋转变异。
2.2.6 移民操作
移民操作主要通过移民算子来进行，以使各个种群的进化不是相互独立的，而是相互影响、相互协调、协同进化的过程[5]。实施的原则是将每个种群中适应度值最低的个体用相邻种群中适应度值最高的个体进行替代。
2.3 剩余矩形匹配算法在由多种群遗传算法产生个体编码后，需要对其进行解码。本文采用目前最有效的排样定位方法——剩余矩形匹配算法进行解码，该方法排样效果优于其他板材定位方法，可充分利用板材区域，使板材利用率达到最大。具体执行步骤如下：
1）初始剩余矩形集为整个板材。
2）按排样序列将零件排入到板材中，当排入零件时，先从最下方剩余矩形尝试排入，如果剩余矩形的长和宽均大于入排零件的长和宽，则排入。排入时将零件放置到剩余矩形的左下方，更新剩余矩形集。如果待排零件不能排入到最下方剩余矩形的话，对其旋转90°再尝试排放，如能排入，则更新入排零件的入排角度，更新剩余矩形集。如还不能排入，则尝试下一个剩余矩形，如果所有的剩余矩形都不能排入，则尝试排放下一个零件，更新零件的入排序列。
3）直到目前正在使用的板材拍不下任何零件后，将剩余未入排的零件排放到下一张板材中，排放方法同第一张板材，直至所有零件全部排放到板材中。
3 实例验证与分析为了验证本文算法的实用性和有效性，本文通过MATLAB 2018进行编程实现，从A公司收集了一些已经排样完的零件数据，对其进行预处理，采用预处理完的零件数据作为实验数据，所使用的原材料板材的规格为2 500 mm×1 250 mm。
本文算法的参数设置为：每个种群大小均为40，交叉概率和变异概率分别取［0.6，0.9］、［0.05，0.1］之间的动态值，最优个体最少保持代数为40代。公司实际排样结果和本文算法所得排样结果如表1所示。
表1 排样结果对比
本文算法得到的第1张板材排样图，如下页图2所示。
图2 第1张板材排样图
由表1可以看出，排完所需零件公司和本文算法均需使用3张板材。但本文算法对原材料利用的更加充分，前2张板材的平均利用率高达97.25%，第3张板材的利用率仅为67.3%，要优于公司的排样结果。并且，本文算法的运行结果相对稳定，运行时间相对也较短，因此，使用本文算法对板材进行优化排样，可提高板材的利用率和排样效率，节约生产成本。
4 结论为了求解现代工业生产中普遍存在的二维不规则件排样问题，提出一种基于多种群遗传算法和剩余矩形匹配算法的排样优化算法。通过提取不规则件的最小包络矩形，将其转化为矩形件排样问题，然后应用多种群遗传算法在全局范围内搜寻可行解，采用剩余矩形匹配算法作为解码算法，将搜索到的可行解解码为排样图，最后进行量化评价，推动种群的进化，找到最优解。实例证明，本文算法优于公司现有排样方法，可提高板材的利用率和排样效率，降低企业的生产成本。
