基于最小重力勢能原理與遺傳算法的服裝排料算法

汪朋朋 施群 謝云斌 謝家駿 潘炳偉

摘要：高效自動排料算法中布料利用率的提升對于企業具有重要的經濟價值。但排料問題屬于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.