基于最小重力势能原理与遗传算法的服装排料算法

汪朋朋 施群 谢云斌 谢家骏 潘炳伟

摘要：高效自动排料算法中布料利用率的提升对于企业具有重要的经济价值。但排料问题属于NP完全问题，难以在有限时间内找到问题的最优解。研究提出基于最小重力势能原理的排料算法，并将遗传算法应用到排料优化问题中，最终进行排料算法的对比验证。基于最小重力势能原理及遗传算法的排料算法优化减小了每次排料过程中的计算量，可在有限的时间内得到近似最优解。结果表明，所提出的自动排料算法在提高利用率方面具有较高的实用价值。

关键词：排料算法；最小重力势能原理；遗传算法；不规则排料

中图分类号：TS195.644文献标志码：A文章编号：1009-265X（2018）03-0053-09Garment Nesting Algorithm Based on Principle of Minimum

Gravity Potential Energy and Genetic Algorithm

WANG Pengpeng， SHI Qun， XIE Yunbin， XIE Jiajun， PAN Bingwei

（School of Mechatronic Engineering and Automation， Shanghai University， Shanghai 200072， China）Abstract：The improvement of material utilization in efficient automatic nesting algorithm has important economic benefits for Enterprises. However， nesting problem is a NPcomplete problem and it is hard to find out the optimal solution to the problem within the finite time. The nesting algorithm based on the principle of minimum gravity potential energy was proposed in this paper and genetic algorithm was also applied in nesting optimization problem. Finally， the comparison validation of the nesting algorithm was conducted. To a certain extent， this nesting algorithm based on the principle of minimum gravity potential energy and genetic algorithm reduce and optimize the computation load in each process， and the quasioptimal solution can be gained within the limited time. The experimental results show that this automatic nesting algorithm has a high practical value in improving the utilization rate.

Key words：nesting algorithm； principle of minimum gravity potential energy； genetic algorithm； irregular nesting

服装排料属于不规则图形排料问题，部分研究者采用最小矩形包络法将不规则图形排料转化为矩形排料[12]，这种方法排料效率较高，但存在材料利用率低的缺陷。排料优化问题主要包括样片最优排放位置确定和样片最优排样顺序确定两个问题。

样片位置确定有多种研究策略，最常用的是Baker等[3]左下角（BottomLeft condition，BL）策略，BL策略的主要思想是在保证样片不重叠的前提下，重复将样片向左、向下移动，直到不能再移动为止，由于BL策略容易引起排料结果左侧偏高，遗留较大块的空白区域等问题，一些学者提出了相应的改进算法，如Liu等[4]向左平移优于向下的BLLF策略、Hopper等[5]左下角填充的BLF策略。采用BL策略进行排料的算法一般需要计算临界多边形（NFP），当样片数量（N）和旋转次数（RN）增大时，临界多边形的计算非常耗时；另一种常用的是最低重心排料策略，Dowsland等[6]指出如果将零件看作砂砾，母材看作玻璃瓶，通过不断摇晃“玻璃瓶”可以使“砂砾”排列更加密实，Lee等[7]提出在母材上布置多个等距离散排样点，将样片平移到各个排样点上并进行旋转来确定其排放位置，刘虓[8]提出的Hape算法中给出了排料问题的物理意义：零件总是试图通过平移和旋轉运动尽量降低零件的重心高度，从而得到更加紧密的排列。

样片排放顺序对于排料利用率具有重要影响，固定顺序的排料得到的结果往往不能令人满意。但由于N个样片存在N！种顺序，目前的计算能力下无法在可接受的时间内找到最优排料顺序，因此一些学者将优化搜索算法引入排料算法中，如Gomes等[9]使用模拟退火算法搜索排料解空间，在当前排样图的基础上，挑选两个零件互换位置，从而产生当前解的邻域解。汤安平等[10]采用遗传算法和排料约束条件相结合的方式来进行排料，对样片顺序和旋转角度进行编码，这种算法可能得到较好的排料结果，但进一步增大了算法的计算量。

本文采用Lee等[7]的方法在母材上布置等距排样点，根据最小势能原理建立数学模型，移动、旋转样片至各排样点使其重力势能最小，以此来确定各样片初始排放位置。由于等距排样点之间存在间隔，又借鉴BL策略提出了样片快速靠接算法来确定样片的最终排放位置。进一步对排料图中样片的排放顺序进行编码，利用遗传算法求解不同顺序下的排料结果，给出一种基于最小重力势能原理与遗传算法的服装排料算法。

1基于最小势能原理的排料算法设计

1.1排料算法基本定义

1.1.1样片

样片包含参考点（RP）、旋转角度（α）、序号、面积、形心、最小包围盒和样片多边形坐标点等信息。如图1所示，样片参考点（RP）是样片平移、旋转的基点，可以任意选取，这里选择样片最小包围盒左下角顶点为参考点；旋转角度（α）由旋转次数（RN）决定，α=2πj/RN（j=0，1，2…，RN-1），样片旋转次数（RN）是影响排料效率的一个关键因素。

1.1.2母材及排样点

母材指未进行排样前的原材料，在母材上沿水平、竖直两个方向均匀布置的离散点称为排样点，排样点是确定样片位置的基础。如图2所示，排样点之间的间距为PPD，该参数值也是影响排样效率的一个关键参数。需要特别说明的是：实际排料时习惯从左至右依次排料，因此假设重力方向为从右向左方向。

1.1.3样片的旋转、平移操作

图2所示为样片旋转、平移操作。图2（a）中，待排样片的初始位置在①处，样片参考点与母材中的一个排样点重合，绕参考点旋转180°后到达位置②；如图2（b）所示，样片在位置②按箭头方向平移后到达位置③。

1.1.4样片的重叠检测算法

排样时需要保证样片之间不能发生重叠，以下给出两个样片多边形A、B快速重叠检测算法的主要流程：

a）计算多边形A与多边形B的最小包围盒；

b）快速判断A、B最小包围盒是否重叠，若不重叠则A与B不重叠，流程结束；若重叠执行下一步；

c）判断A各边与B各边是否存在交点，若存在交点则A与B发生重叠；若不存在交点则转下一步；

d）为防止A、B存在包含关系，判断A的各顶点是否在B中，若A的某一顶点位于B中，则两个多边形发生重叠，流程结束；若多边形A的所有顶点均不在多边形B中，执行下一步；

e）同理，判断多边形B的各顶点是否在多边形A中。图2样片旋转、平移操作

1.1.5样片快速靠接算法

如图3所示，根据排样点确定的样片位置之间仍然可能存在间隙。为提高排料利用率，需要使用靠接算法消除样片之间水平和竖直方向的间隙，靠接算法流程如图4所示，假设样片A最终位置已确定，B样片向左平移至恰好满足不重叠条件。

1.2最小重力势能原理与样片形心计算

最小重力势能原理的引入主要用来确定样片排放位置。假设排料过程中已确定所有样片的排料顺序，则排料问题可归结为：如何确定各样片的排放位置，使排料利用率最高。利用最低重心排样策略，根据样片在母材中的位置关系，可以求出样片的重力势能，从而很方便的建立起样片排放位置问题的数学模型。再通过样片的平移和旋转操作，遍历所有排样点和样片旋转角度，可以求出各样片在母材中不同位置的重力势能，当各样片处于最小势能状态下时，整个排版图的总势能最小，即可确定当前顺序下的样片排放位置和排料利用率。根据最小重力势能原理建立的评价样片排放位置优劣的模型，是整个算法的基础。

在排料的过程中，样片零件的重力势能为：

EG=Gyc（1）

式中：EG为零件的重力势能；G为零件的重力；yc为零件的形心高度。

排料问题的最小重力势能原理：零件在排料过程中总是尽可能地通过平移或旋转使其形心高度降低。如图5（a）所示，三角形在排料时位于矩形上方，其重力势能为Gy0；经平移后到达如图5（b）中所示位置，其重力势能为Gy1；再经旋转、平移后到达如图5（c）中所示位置，其重力势能达到最小值Gy2。服装样版中包含直线段、曲线段，为保证算法通用性，排版前将所有样片均处理为多边形。设多边形含有n个顶点，其中任一顶点的坐标为（xk，yk）（k=1，2，3，…，n），多边形面积和形心均可由格林公式（2）推导得到。

DQx-Pydxdy=∮LPdx+Qdy（2）

令式（2）中P=-y，Q=x，即得多边形的面积：

S=Ddxdy=12∮L-ydx+xdy

=12∑nk=1（xkyk+1-xk+1yk）（3）图5排料过程中的最小重力势能原理

式中：当k=n时，k+1=1。已知多边形的形心公式

yc=DydxdyDdxdy（4）

若令P=-12y2，Q=0，则可得多边形形心坐标yc：

yc=-12∮Ly2dx12∮L-ydx+xdy

=16∑nk=1（y2k+ykyk+1+y2k+1）（xk-xk+1）12∑nk=1（xkyk+1-xk+1yk） （5）

1.3确定样片位置的流程

采用一种固定顺序（如样片面积大小顺序）每次取一個样片，按照如图6所示流程即可确定各样片的排放位置。流程图中：

a）排料间隔PPD越小，则排样点个数PPN越多。若排样点个数PPN越多，同时旋转次数RN越多，则排料时间越长，由算法流程图可知，单个样片的排料时间由式PPN2×RN决定。由于排样时存在大量无效排样点，因此在排样时避免访问无效点可进一步提高排样效率；

b）由于假设重力方向是从右向左方向，所以需要计算样片x方向的形心xc，计算参考式（5）。图6样片位置确定流程

2排料顺序优化

如图7所示，排料顺序对排料利用率具有重要影响，顺序固定的排料不一定能得到最优的排料结果。但由于N个样片存在N！种顺序，无法在可接受的时间内穷举样片顺序进行排料。遗传算法是基于自然选择和自然遗传机制的搜索算法，它是一种有效的解决最优化问题的方法，因此排料时可引入遗传算法，通过全局优化概率搜索来产生最佳的排料顺序。实现排料优化问题需要经过编码，初始化，适应度计算，选择，交叉，变异等操作。

2.1编码与初始化

遗传算法中常用的编码方式有实数编码、二进制编码、浮点数编码和格雷码编码等。排料前每个样片都有唯一的编号，根据样片的编号采用实数编码可以直观得到样片的排料顺序。假设N个样片的编号分别为p1、p2、p3…pN，从这N个样片中依次任意选择一个样片pn（n=1，2，…，N）在母材中进行排料，则所选样片的顺序就构成了个体的编码。实际操作时，由随机函数产生1N的一个全排列即个体。种群由指定数目的个体组成，在使用遗传算法前需要对种群进行初始化，假设种群个体数量为M，初始化即产生M个1N的全排列Xm（m=1，2，3…M）。

2.2个体适应度函数

排料利用率为所有样片的面积和与使用母材的面积之比：

fXm=EXm=∑Nn=1SnLW（6）

式中：fXm为个体Xm的适应度函数（m=1，2，3…M），EXm为个体Xm的排料利用率，L为样片占用母材的总长度，W为母材的宽度，Sn为样片n的面积（n=1，2，3…N）。

排料利用率是评价排料结果的关键因素，因此可以将式（6）作为个体适应度的评价函数。

2.3选择操作

选择操作是遗传算法中的优胜劣汰机制。选择操作可以在迭代的过程中保留种群中的优良个体。采用轮盘赌进行选择，定义个体Xm被选中的概率为pm=fXm∑Mm=1fXm，进行选择时，随机生成一个[0，1）区间的随机数p，如果∑mj=1pj2.4交叉操作

交叉操作是由父代个体产生子代个体的过程。采用顺序交叉，假设Xi、Xj是进行交叉操作的一对父个体，其中Xi=[4 5 1 7 2 8 9 6 3]，Xj=[7 9 3 4 5 6 1 2 8]，具体交叉操作方式如下：

a）在父个体Xi中随机选择一个片段，如[1 7 2 8]；

b）将该片段复制到子个体Yi的对应位置[0 0 1 7 2 8 0 0 0]；

c）删除父个体Xj中子个体Yi已含有的元素，产生一个过度个体X′j=[9 3 4 5 6]；

d）将个体X′j元素依次插入子个体Yi的空缺位置上，即得到子个体Yi=[9 3 1 7 2 8 4 5 6]。

2.5变异操作

变异是种群进化的关键手段，变异操作可以防止种群早熟收敛，提高遗传算法的局部搜索能力。变异操作如下：假设子个体Yi=[9 3 1 7 2 8 4 5 6]，随机选择两个位置的元素交换即可得到变异后的子个体，如交换1、5的位置，得到变异后的个体Yi′=[9 3 5 7 2 8 4 1 6]。

3排料算法流程及实例

3.1排料算法流程

引入遗传算法后整体的排料流程如图8所示，其中确定样片n的位置即按照图6所示流程进行。

3.2算法实例

3.2.1算法验证平台和参数

本文所述的排料算法在Visual Studio 2015集成开发环境下采用MFC框架、VC++语言编程验证，算法验证所用的计算机基本配置为，CPU：Intel Core i32350M 2.30GHz；RAM：8.00GB；操作系统：Win10 64位。如图9所示，样片在母材中位置确定后，样片内的排样点被删除，排料利用率可直接显示在状态栏；如图10所示，排样时需要设置的主要参数有排样间隔PPD，样片旋转次数RN，种群迭代次数Iteration和种群个体数Population，遗传算法中的交叉操作概率取0.8，变异操作概率取0.1。图8排料算法流程

3.2.2算法测试和分析

为了验证算法的性能和有效性，有必要对其进行测试和分析。本文从欧洲排样研究组织ESICUP（https：//paginas.fe.up.pt/～esicup/datasets）提供的基准问题中挑出11个分别进行排样，排料结果如图11所示。图11本文算法排料结果

对于服装生产企业来说，在加工高级服装面料和大批量生产时，材料利用率的微小提升都意味着巨大的经济效益，即排料利用率是排料算法的关键评价因素，本文主要就排料利用率进行了测试和对比。

表1是本文算法与GEFHNA[11]算法、Nestlib商业软件的排料利用率对比。GEFHNA[11]算法是一种基于重心临界多边形和边适应度的不规则件启发式排样算法，该算法在选择样片排放顺序时采用了FFD策略（通过衡量样片与待排区域的贴合程度选择排料顺序），文献[11]给出了这11个基准问题的排料利用率；Nestlib是一款商业排料软件（其排料算法未公开），但其排料结果具有较高的参考价值。如图12为GEFHNA算法和Nestlib软件对基准问题shirts的排料结果。

软件对shirts的排料结果

通过测试和对比可得出如下结论：

a）基于最小势能原理与遗传算法的服装排料算法对任意多边形（凹、凸多边形）样片均适用。

b）与GEFHNA算法相比，本文提出的排料算法获得了8/11个相对最优的排料利用率。GEFHNA算法采用FFD策略进行启发式搜索排料，该算法实际上只进行单次排样，因此其排料的效率会比较高，但其排料利用率容易受样片与待排区域的贴合度影响；而本文采用遗传算法对排料顺序进行优化搜索，可在多次搜索迭代后获得一个较优的排料顺序，从而提高排料利用率。

c）与Nestlib软件的排料结果相比，本文提出的排料算法获得了10/11个相对最優的排料利用率。说明本文提出的排料算法在提高排料利用率方面具有较高的实用价值。

4结语

本文阐述了排料问题的基本定义，在确定样片排放位置时，介绍了最小重力势能原理及其作用，并给出了基于最小重力势能原理确定样片位置的流程。考虑到固定顺序排料得到的结果不一定是最优解，因此在确定最优排料顺序时引入遗传算法，从而可以得到近似最优排料结果，再给出整个排料算法的流程。最后，给出了算法的验证平台和详细参数，并与其他排料结果进行了对比。结果表明，本文所提出的排料算法提高了服装生产中的材料利用率，具有较高的经济价值和实用价值。

参考文献：

[1] 靳旭玲.二维不规则排样问题的研究[D].青岛：山东科技大学，2003.

[2] 胡加宰，史伟民，杨亮亮.二维不规则样片自动排料算法的优化研究[J].现代纺织技术，2014，22（5）：26-30.

[3] BAKER B S， COFFMAN E G J， RIVEST R L. Orthogonal packings in two dimensions[J]. Siam Journal on Computing， 1980， 9（4）：846-855.

[4] LIU D， TENG H. An improved BLalgorithm for genetic algorithm of the orthogonal packing of rectangles 1[J]. European Journal of Operational Research， 1999，112（2）：413-420.

[5] HOPPER E， TURTON B C H. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research， 2001，128（1）：34-57.

[6] DOWSLAND K A， DOWSLAND W B， BENNELL J A. Jostling for position： local improvement for irregular cutting patterns[J]. Journal of the Operational Research Society， 1998，49（6）：647-658.

[7] LEE W C， MA H， CHENG B W. A heuristic for nesting problems of irregular shapes[J]. ComputerAided Design， 2008，40（5）：625-633.

[8] 劉虓.基于HAPE的二维不规则零件排样算法及其性能研究[D].广州：华南理工大学，2011.

[9] GOMES A M， OLIVEIRA J F. Solving irregular strip packing problems by hybridising simulated annealing and linear programming[J]. European Journal of Operational Research， 2006，171（3）：811-829.

[10] 汤安平，杨恢先，谭正华.一种基于遗传算法的优化排料方法[J].计算机应用与软件，2009，26（1）：171-221.

[11] 汤德佑，周子琳.基于临界多边形的不规则件启发式排样算法[J].计算机应用，2016，36（9）：2540-2544.