基于粒子群算法的二維不規(guī)則排樣

摘 要：針對(duì)工業(yè)生產(chǎn)中常見的二維不規(guī)則排樣問題，提出運(yùn)用粒子群算法求解的方法。將BL算法和NFP算法結(jié)合，作為排樣定位策略；對(duì)工件的入排順序和入排角度進(jìn)行編碼，進(jìn)行粒子群算法優(yōu)化求解，并通過交叉替代傳統(tǒng)的插值改進(jìn)粒子位置更新過程，滿足排樣的離散問題求解；通過添加粒子的變異過程，避免陷入局部最優(yōu)解。算例排樣結(jié)果驗(yàn)證了該算法的有效性。

關(guān)鍵詞：二維不規(guī)則排樣；BL算法；NFP算法；粒子群算法

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：B 文章編號(hào)：1671-5276（2024）04-0165-04

Two-dimensional Irregular Layout Based on Particle Swarm Optimization Algorithm

LYU Wanlin， YOU Youpeng

（College of Mechanical and Electrical Engineering， Nanjing University of Aeronautics and Astronautics， Nanjing 210016， China）

Abstract：A method to solve the common two-dimensional irregular layout problem in industrial production by particle swarm optimization algorithm is proposed. BL algorithm and NFP algorithm are combined as the positioning strategy.The input order and input angle of the workpiece are coded， and the particle swarm optimization algorithm is used to optimize the solution. By replacing the traditional interpolation with intersection， the process of particle position updating is improved to solve the discrete problem of layout. The mutation process of particles is added to avoid the local optimal solution. The sample layout result verifies the effectiveness of the proposed algorithm.

Keywords：two-dimensional irregular layout; BL algorithm; NFP algorithm; particle swarm optimization algorithm

0 引言

二維不規(guī)則排樣問題是在給定的原材料板材上，擺放各種不規(guī)則的工件，找出工件的最優(yōu)排布，使得板料的利用率最高。二維不規(guī)則排樣要求工件必須排布在板材內(nèi)，各個(gè)工件互不重疊，工件之間的間隙盡量小，以達(dá)到節(jié)約材料、提高效益的目的。該問題在服裝裁剪、印刷、鈑金零件切割等方面應(yīng)用廣泛，是工業(yè)生產(chǎn)加工中的重要環(huán)節(jié)。

二維不規(guī)則排樣問題屬于復(fù)雜的非確定性多項(xiàng)式（nondeterministic polynomial， NP）完全問題，具有很高的計(jì)算復(fù)雜度，國內(nèi)外也相繼提供了一些解決方案。秦振浩^[1]對(duì)不規(guī)則工件生成最小包絡(luò)矩形，將其轉(zhuǎn)化為矩形件排樣問題，應(yīng)用群遺傳算法在全局范圍內(nèi)搜尋可行解。UMETANI等^[2]提出了針對(duì)光柵化模型，在水平和垂直方向交替重復(fù)進(jìn)行直線搜索的坐標(biāo)下降啟發(fā)式算法。劉虓^[3]提出了一種基于矢量格式的零件靠接算法，依據(jù)最小勢能原理進(jìn)行不規(guī)則零件排樣。王莉^[4]以最低水平線算法為定位策略，將遺傳算法和模擬退火算法結(jié)合進(jìn)行求解。劉海明等^[5]提出了基于排擠機(jī)制的小生境遺傳算法，來進(jìn)行不規(guī)則圖形的排序優(yōu)化。陳燕等^[6]針對(duì)小批量圓形件的排樣問題，提出了順序分組啟發(fā)式算法與遞歸算法相結(jié)合的排樣方案。羅強(qiáng)等^[7]提出了基于復(fù)合評(píng)價(jià)因子的改進(jìn)遺傳算法求解矩形排樣問題改善了遺傳算法的局部搜索能力。

對(duì)于二維不規(guī)則零件排樣問題的求解，一般分為兩部分：在給定入排順序和角度情況下，對(duì)不同工件之間碰撞的檢測和定位策略的設(shè)計(jì)；對(duì)工件入排順序和入排角度的優(yōu)化求解。本文將從這兩部分對(duì)算法進(jìn)行設(shè)計(jì)與改進(jìn)。

1 BL-NFP算法

排樣過程中，為了最大化利用板料空間，需要保證不同工件間間隙盡量小，且不能重合，即需要確定一個(gè)工件相對(duì)于另一個(gè)工件的最佳位置，本文采用基于BL算法和NFP算法的融合算法作為工件的定位算法。

1.1 BL算法

BL算法是排樣問題中常用的定位算法，如圖1所示，先將工件放置于板料的右上角處，向左平移至極限位置，之后向下平移至極限位置，該算法讓工件放置位置盡可能接近板料的左下角。

1.2 NFP算法

如圖2所示，給定兩個(gè)工件A和工件B，工件A固定，將工件B繞工件A環(huán)繞一周，工件B的角度保持不變，取工件B上任意一點(diǎn)p，p在環(huán)繞的過程中走過的軌跡，即為臨界多邊形NFP_AB。取工件B上不同的點(diǎn)p，形成的臨界多邊形形狀相同，本文取工件B的下頂點(diǎn)作為參考點(diǎn)。當(dāng)參考點(diǎn)定位在該臨界多邊形上時(shí)，工件A與工件B之間貼合。在該臨界多邊形上搜索，可計(jì)算出工件B的最佳擺放位置。

1.3 BL-NFP算法

本文的BL-NFP算法將BL算法與NFP算法相結(jié)合，在NFP算法計(jì)算出的臨界多邊形上選擇一個(gè)左下的極限位置來放置工件。設(shè)有工件A和工件B，求出工件B環(huán)繞工件A形成的NFP_AB，如圖3（a）所示。工件B放置于該臨界多邊形上的一些位置時(shí)會(huì)超出板料的范圍，這些位置是不可用的。因此，需求解出工件B在內(nèi)部圍繞板料形成的NFP_B，如圖3（b）所示。將兩個(gè)NFP進(jìn)行合并處理，可獲得新的NFP多邊形，在該NFP多邊形上，依照向左向下原則，可找到一個(gè)較好的位置來放置工件B，如圖4所示。

2 粒子群算法

BL-NFP算法解決了在板料上已放置一些工件的情況下，向板料上添加工件時(shí)該工件的最優(yōu)定位位置的計(jì)算。在實(shí)際應(yīng)用中，工件入排的順序和角度也對(duì)排樣效果有很大的影響。為此，本文通過粒子群算法來對(duì)工件的入排順序和角度進(jìn)行優(yōu)化求解。

2.1 不規(guī)則零件的預(yù)處理

為減少對(duì)入排角度進(jìn)行優(yōu)化求解的復(fù)雜度，需保證工件在初始位置時(shí)的OBB包圍盒面積最小，即先求出工件的OBB包圍盒，確定包圍盒各邊的朝向，并將其旋轉(zhuǎn)至合適的角度。OBB包圍盒的具體求解過程詳見參考文獻(xiàn)[8]。

2.2 粒子群算法

對(duì)于入排順序和入排角度的計(jì)算，大部分研究采用遺傳算法和模擬退火算法來進(jìn)行優(yōu)化求解，也取得了比較好的結(jié)果，但是遺傳算法的局部搜索能力較差，而模擬退火算法容易陷入局部最優(yōu)解。針對(duì)這兩個(gè)問題，本文采用粒子群算法來進(jìn)行排樣問題的求解。粒子群算法（particle swarm optimization，PSO）是由EBERHART和KENNEDY提出的一種進(jìn)化計(jì)算方法，它起源于對(duì)鳥群覓食行為的模擬，是一種基于群智能的優(yōu)化算法。粒子群算法初始化一群隨機(jī)粒子（解），通過迭代找到最優(yōu)解，在每一次迭代的過程中，粒子會(huì)記錄該粒子到達(dá)過的最優(yōu)位置p_best，群體會(huì)更新群體到達(dá)過的最優(yōu)位置g_best，并根據(jù)這兩個(gè)值來進(jìn)行迭代^[9]。本文中粒子的位置為一組工件的入排順序和入排角度，所有的粒子都保存最優(yōu)解的相關(guān)信息，它有更多的機(jī)會(huì)得到全局最優(yōu)解。

2.3 算法流程

算法的整體流程如圖5所示。

該算法的整體步驟如下。

1）粒子位置的編碼及優(yōu)化

在排樣問題中，粒子的位置編碼包含工件入排的順序和角度。有n個(gè)工件，記其編號(hào)為1—n，則將粒子位置編碼為{（p1，r1），（p2，r2），…，（pn，rn）}，其中pi的數(shù)值表示的是第i個(gè)放入排樣的工件對(duì)應(yīng)的工件號(hào)，若旋轉(zhuǎn)的角度以30°為基準(zhǔn)，ri表示對(duì)工件旋轉(zhuǎn)ri×30°。

以20個(gè)工件為例，對(duì)這20個(gè)工件排序，它的可能的解共有20！個(gè)，這個(gè)解空間是龐大的。為了解決這個(gè)問題，本文也對(duì)粒子群算法的編碼進(jìn)行了優(yōu)化，不再將某個(gè)順序編碼pi與工件號(hào)對(duì)應(yīng)，而是通過預(yù)處理，將順序編碼pi與工件的類型相對(duì)應(yīng)，即{p1，p2，…，pn中pi指的是在第i個(gè)排入的工件的型號(hào)，這避免了同種工件之間進(jìn)行排列產(chǎn)生的效率浪費(fèi)。假設(shè)同樣是20個(gè)工件，共有4種工件，每種5個(gè)，那么它的解空間的大小是20！/（5！）⁴，只有原先方案的兩億分之一，這將大大提高排樣搜索的效率。

2）適應(yīng)度函數(shù)的計(jì)算

適應(yīng)度函數(shù)是用于表示粒子在某個(gè)位置排樣優(yōu)劣的指標(biāo)，適應(yīng)度越高，說明該位置對(duì)應(yīng)的入排順序和角度排樣效果越好。對(duì)于某一粒子，本文算法會(huì)依次將工件旋轉(zhuǎn)至對(duì)應(yīng)角度，之后通過BL-NFP算法對(duì)該工件進(jìn)行定位。將所有的工件都放置好后，進(jìn)行該粒子位置適應(yīng)度的計(jì)算。本文對(duì)粒子的適應(yīng)性函數(shù)為

式中：W為板料的寬度；L為板料的長度，x_max和y_max分別表示該粒子中所有工件頂點(diǎn)在x方向上的最大值和y方向的最大值，即所有工件組成的包絡(luò)矩形的面積，α是適應(yīng)度系數(shù)。該函數(shù)表示工件是否緊湊對(duì)適應(yīng)度的影響，工件之間排布越緊湊、間隙越小，則x_max和y_max值越小，計(jì)算出的工件實(shí)際占用的區(qū)域面積越小，適應(yīng)度則越高。

3）粒子之間的交叉變異

粒子群算法中，每一個(gè)粒子都有記憶功能，除了記錄當(dāng)前排樣的順序和角度，該粒子會(huì)有一個(gè)單獨(dú)的空間來記錄其經(jīng)歷過的最優(yōu)位置p_best，它表示該粒子到達(dá)過的適應(yīng)度最高的位置。同時(shí)，有一個(gè)全局最優(yōu)位置g_best，它表示的全體粒子經(jīng)歷過的最優(yōu)位置。

對(duì)于每一個(gè)粒子的位置，在計(jì)算出當(dāng)前的適應(yīng)度后，算法會(huì)對(duì)個(gè)體最優(yōu)位置p_best和群體最優(yōu)位置g_best進(jìn)行更新，并開始迭代生成新一代的粒子的位置。粒子群算法的速度迭代公式為

式中：v^k_id表示第k次迭代粒子i速度矢量在d（x，y，z）方向上的速度分量；x^k_id表示第k次迭代粒子i在d方向上的位置分量；x^k-1_id表示在第k-1次迭代粒子i在d方向上的位置分量；α^k-1_id表示在第k-1次迭代粒子i在d方向上的位置分量；c₁、c₂表示加速度常數(shù)，調(diào)節(jié)學(xué)習(xí)最大步長；r₁、r₂表示兩個(gè)隨機(jī)參數(shù)，取值范圍[0，1]，以增加搜索的隨機(jī)性；w表示慣性權(quán)重，非負(fù)數(shù)，用來調(diào)節(jié)對(duì)解空間的搜素范圍。該式的第一部分表示該粒子的先前速度，第二部分表示該粒子當(dāng)前位置與自身歷史最佳位置p_best的距離，第三部分表示該粒子當(dāng)前位置與群體最佳位置g_best的距離。位置更新公式為

粒子群算法的思想是，下一時(shí)刻的速度受個(gè)體最優(yōu)解和群體最優(yōu)解影響，在較優(yōu)解附近尋找更優(yōu)解，慢慢找出全局最優(yōu)解。

但是，該式只適用于變量連續(xù)的情況，即x在p_best和g_best之間連續(xù)。本文中粒子位置表示工件入排順序和角度，不同位置是不連續(xù)的，在p_best和g_best兩個(gè)位置中間迭代新的位置無法直接使用位置更新公式來計(jì)算。針對(duì)該問題，本文采用交叉、變異來進(jìn)行粒子位置的迭代。假設(shè)有8個(gè)工件需要進(jìn)行排樣，其中有兩個(gè)工件型號(hào)相同，其類型為1，其余工件型號(hào)不同，為2—7，工件旋轉(zhuǎn)的基準(zhǔn)為90°。在第k次迭代后，粒子m的個(gè)體最優(yōu)位置為p_best，如圖6所示。群體的最優(yōu)位置為g_best，如圖7所示。

第i個(gè)方框內(nèi)的第1個(gè)數(shù)為該方案中第i個(gè)進(jìn)行排樣的工件型號(hào)，第2個(gè)數(shù)為排樣前對(duì)工件進(jìn)行旋轉(zhuǎn)的系數(shù)。

為了在兩者中間迭代一個(gè)新的粒子，首先是隨機(jī)生成一個(gè)大于0小于8的交叉系數(shù)，記為p。本例中為4，則在新生成的粒子中，前4個(gè)元素與g_best的前4個(gè)元素相同，之后將p_best中型號(hào)被使用過的元素進(jìn)行刪除，之后將未被刪除元素的型號(hào)依次填入新粒子的剩余元素中，具體過程如圖8所示。對(duì)于重復(fù)的工件型號(hào)1，會(huì)有單獨(dú)的數(shù)據(jù)結(jié)構(gòu)記錄該型號(hào)還需被放入的件數(shù)。本例中新粒子后4個(gè)元素的旋轉(zhuǎn)系數(shù)并不與個(gè)體最優(yōu)解中相對(duì)應(yīng)的完全一致，它是由隨機(jī)函數(shù)在群體最優(yōu)解和個(gè)體最優(yōu)解中相對(duì)應(yīng)的兩個(gè)元素旋轉(zhuǎn)系數(shù)中隨機(jī)選擇。

為了避免陷入局部最優(yōu)解，該算法中還有一個(gè)變量p_mutaion，表示變異的概率，它是人工設(shè)定的值，在迭代的過程中，有一定概率不進(jìn)行交叉求解，而是對(duì)當(dāng)前粒子進(jìn)行變異，如圖9所示。它不進(jìn)行p_best和g_best之間的交叉變異，而是通過對(duì)當(dāng)前粒子某兩個(gè)或多個(gè)順序進(jìn)行交換來生成新粒子，以防止程序過早收斂陷入局部最優(yōu)解。

3 實(shí)驗(yàn)與驗(yàn)證

為了驗(yàn)證算法的可行性和有效性，采用C++語言實(shí)現(xiàn)了本文的排樣算法，并用ESICUP提供的測試用例進(jìn)行了測試。表1為算法相關(guān)參數(shù)的配置。

圖10和圖11分別為本文算法對(duì)BLAZ樣例和TROUSERS樣例的求解結(jié)果。對(duì)于BLAZ樣例，該方案對(duì)板料的占用率為64.30%，工件總面積對(duì)占用面積的比值，即材料利用率為78.01%；對(duì)于TROUSERS樣例，板料占用率為72.19%，材料利用率為91.45%。

4 結(jié)語

針對(duì)在工業(yè)生產(chǎn)中廣泛存在的二維不規(guī)則排樣問題，本文提出了基于BL-NFP的粒子群算法求解。首先將BL-NFP算法作為排樣定位策略；對(duì)工件的排樣順序和排樣角度進(jìn)行粒子位置編碼，并根據(jù)二維不規(guī)則排樣中存在工件重復(fù)的特點(diǎn)對(duì)編碼進(jìn)行了創(chuàng)新；改進(jìn)了粒子位置更新過程，以交叉替代傳統(tǒng)的插值，使得算法能滿足排樣的離散問題求解；添加了粒子的變異過程，避免陷入局部最優(yōu)解。通過ESICUP測試用例的排樣試驗(yàn)，驗(yàn)證了該算法的有效性。

參考文獻(xiàn)：

[1] 秦振浩. 基于多種群遺傳算法和剩余矩形匹配算法不規(guī)則件優(yōu)化排樣[J]. 現(xiàn)代工業(yè)經(jīng)濟(jì)和信息化，2022，12（9）：222-224.

[2] UMETANI S，MURAKAMI S. Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes[J]. European Journal of Operational Research，2022，303（3）：1009-1026.

[3] 劉虓. 基于HAPE的二維不規(guī)則零件排樣算法及其性能研究[D]. 廣州：華南理工大學(xué)，，2011.

[4] 王莉. 矩形件排樣問題的遺傳模擬退火混合求解算法[J]. 鍛壓技術(shù)，2021，46（8）：70-76.

[5] 劉海明，周炯，吳忻生. 應(yīng)用臨界多邊形方法與小生境遺傳算法求解不規(guī)則排樣問題[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2016，37（5）： 1002-1007.

[6] 陳燕，謝琪琦，劉詠，等. 圓形件下料順序分組啟發(fā)式算法的設(shè)計(jì)與實(shí)現(xiàn)[J]. 圖學(xué)學(xué)報(bào)，2017，38（1）：5-9.

[7] 羅強(qiáng)，李世紅，袁躍蘭，等. 基于復(fù)合評(píng)價(jià)因子的改進(jìn)遺傳算法求解矩形件排樣問題[J]. 鍛壓技術(shù)，2018，43（2）：172-181.

[8] 譚同德，吳強(qiáng)，趙紅領(lǐng)，等. OBB層次包圍盒構(gòu)造方法的改進(jìn)[J]. 計(jì)算機(jī)工程與應(yīng)用，2008，44（5）：79-81，95.

[9] 王仕存，唐敦兵，朱海華，等. 基于改進(jìn)粒子群算法求解分布式多工廠生產(chǎn)調(diào)度問題[J]. 機(jī)械制造與自動(dòng)化，2021，50（4）：9-13.

收稿日期：2023-02-13