圓片下料并行遺傳算法的設計與實現

曾志陽，陳 燕，王 珂

（廣西大學計算機與電子信息學院，南寧530004）

0 引言

從板材中切割出所需的毛坯是下料問題的一個熱門研究方向，下料方案的優化可提高板材的利用率，簡化下料過程［1］。圓片的生產工藝通常分為兩種：剪切下料和非剪切下料［2］。非剪切下料是將不同圓片在原板材或卷材上進行排樣，用火焰切割或激光切割直接切割出來；剪切下料先將板材剪切成條狀，每個條帶只放置相同種類的圓片，再將所需圓片從條帶上切割出來。

下料問題是NP 難組合優化問題［3］，采用窮舉法和精確算法在求解該類問題時很難在有限的時間內得到最優解。因此，求解圓片下料問題的常用方法主要有啟發式算法和智能算法等，其中遺傳算法（Genetic Algorithm，GA）是典型的智能算法。文獻［4-6］均采用啟發式的方法求解：文獻［4］中分別采用X 向和Y 向直切布局求解，從中選擇較大利用率的單個方向的布局圖進行下料；文獻［5］中用順序分組啟發式的方法求解圓片種類多、需求量較少的圓片下料問題；文獻［6］中利用主動生成余料的策略，結合價值校正的啟發方法求解。而文獻［7］中則采用自適應遺傳模擬退火算法求解卷材的圓片非剪切下料問題。目前筆者尚未查詢到針對圓片剪切下料的遺傳算法進行討論的文獻，且大部分是應用在求解矩形件在板材上的下料問題［8-10］。

研究表明，啟發式算法能快速得到一個可行解，但無法確定是否為最優解，甚至無法確定與最優解的差距有多大。遺傳算法則具有良好的全局優化能力，但如果處理方法不當，也易發生早熟現象從而陷入局部最優的情況［11］。因此，本文考慮在遺傳算法的框架中上引入啟發式的求解方法，設計以下料方案的板材利用率作為GA 評價函數的并行遺傳下料算法（Parallel Genetic Blanking Algorithm，PGBA），將下料方案作為個體，采用多線程的方式對多個子種群進行并行的遺傳操作。每個子種群用啟發式方法求解單張板材上的布局圖以生成初始種群，再通過自適應的遺傳操作，遺傳的交叉和變異階段也采用啟發式方法產生新個體，再利用評價函數對個體進行評價，選擇其中部分個體進入下一代的進化。如此循環直至達到設定的進化代數，最終獲得一個較優的圓片下料方案。

1 下料問題描述及數學模型

設一次下料需要m 種圓片，第i（i=1，2，…，m）種的直徑和初始需求量分別為di和bi；可用板材的長寬分別為L 和W。要求從可用板材中切割出需求的圓片以滿足生產需求，同時要求消耗的板材最少。一個下料方案由一個或多個布局圖組成，并確定其使用次數。假設有K 種布局圖，每一種布局圖對應的使用次數為xk，第k 種布局圖包含的第i 種圓片的數量為aik。下料方案的整數規劃模型如下所示：

其中：式（1）為目標優化函數，目的是使消耗的板材數最少；式（2）表示下料方案中所有不同種類的圓片至少需要滿足圓片的需求量；式（3）表示每種布局圖的使用次數為非負整數。

1.1 圓片的布局

采用剪切工藝進行下料時，圓片在條帶中的布局通常有并排、品排和斜排三種，當需求數大于10 時，采用品排布局的利用率優于其他兩種布局［12］。生產中品排的布局通常不超過3 排，圓片在條帶中的品排布局詳細介紹可參文獻［12］。令第i 種圓片在條帶中布局有j(j=1，2，3)排，工藝余量為ω，對于m 種圓片，可枚舉出M=3m 種寬度的條帶，條帶寬度wij可由式（4）計算，不同寬度條帶所含第i 種圓片的個數zij可由式（5）計算。

其中：di為第i 種圓片的直徑，當圓片呈橫向排列時，len=L，當圓片呈縱向排列時，len=W。

1.2 布局圖的生成

根據文獻［6］所述，條帶的剪切工藝可分為滾剪和平剪兩種方式，相對平剪方式，滾剪能大幅度減少條帶切割的工作量，適合批量圓片的生成。滾剪通常采用直切布局圖，其生成過程可看作條帶沿X 方向或Y 方向的拼接過程，條帶的長度或寬度均不超出板材的尺寸，不同方向的布局圖如圖1 所示。布局圖的生成過程是背包問題的求解過程，目的是使得板材上放置的條帶價值最大化，可用動態規劃方法求解［13］。寬度為wij的條帶的有效圓片數為其中l 為當前條帶拼接方向的尺寸，條帶的價值vij=cij?vi。設F(L，W)為板材的最大價值（布局圖中有效圓片的總價值），F(x)為x×W 的子板材或L×y 的子板材的價值，其中1 ≤x ≤L，1 ≤y ≤W；η(l，i)記錄子板材中第i種毛坯的數量。

用動態規劃的遞推方式生成布局圖，遞推式如下：

圖1 X和Y方向的布局示意圖Fig.1 Layout diagrams of X and Y directions

當布局為X方向，x=1，2，…，L，否則x=1，2，…，W （6）其中，F(0)=0，η(0，i)=0，i=1，2，…，m，j=1，2，3。

式（6）表明板材的最大價值取X 向和Y 向價值較大的布局圖：當x=L 時，可確定所有F(L)的值；當x=W 時，可確定所有F(W)的值；最后取兩者中的較大值作為F(L，W)。通過遞推公式可得到布局圖中所有條帶的拼接情況以及所含的第i 種圓片的數量ni。確定當前布局圖后，可根據式（7）計算布局圖的使用次數xk，其中ri為毛坯的當前需求量。

1.3 價值校正函數

用啟發式方法生成初始種群個體的過程中，如果圓片的價值固定不變，根據動態規劃的思想，每次生成的布局圖都是不變的，并且在實際過程中發現，直徑較小的圓片往往都會優先排入，導致后續的布局圖中組合的效果較差。通過引入價值校正函數，調整每一種圓片的價值，能夠有效降低算法的貪婪性，使得種群個體更加多樣化［14］。本文采用的價值調整函數如下：

其中：si為第i 種圓片的面積，u 為當前布局圖的利用率，ni為當前布局圖中第i種圓片的個數，系數Ω=0.75，p=1.03。

2 并行遺傳下料算法的設計

遺傳算法具有隱式并行性，可方便進行并行的遺傳操作，與串行遺傳算法相比，可擴大搜索空間，獲得更好的優化效果。并行遺傳算法可通過分布式集群多處理器和單機多核處理器的多線程兩種方式實現。本文采用后者進行并行遺傳算法的設計來求解圓片的下料問題，通過粗粒度模型的并行模型設計并行遺傳算法，將圓片的價值vi作為臨界資源，各線程對臨界資源進行互斥共享，每個線程內用啟發式方法生成子種群，線程之間獨立地進行自適應遺傳操作，并通過一定的方式進行各子種群間的個體交流，提高算法的局部搜索能力，直至達到設定的最大進化代數R 后輸出最優個體。并行遺傳算法的線程范圍為2～8 個線程，初始種群設定在[20，120]范圍內，進化代數R設定在[20，100]范圍內。

并行遺傳算法Genetic()步驟如下：

步驟1 設定線程數T，種群的規模Q為T的正整數倍，最大進化代數R，輸入板材尺寸L×W，毛坯種類數m，直徑di，初始需求量bi。

步驟2 啟用T 個線程，每個線程各自調用2.1 節的個體生成算法生成t=Q/T 個個體的子種群，初始化進化代數k=0，用σi(i=1，2，…，T)記錄每個子種群進化過程中出現的適應度最高個體，用σbest記錄最優的個體。

步驟3 計算各子種群計算個體的適應度Ui(i=1，2，…，t)，記錄并更新適應度最高個體σi。

步驟4 令k=k+1，如果k ≤R，子種群內部進行選擇、交叉和變異操作，然后判斷每進化5 代后，將σbest遷移到其他子種群中，替換子種群內適應度最低的個體，轉至步驟3；否則，線程結束，從σi中選擇適應度最高的個體作為最優下料方案輸出，算法結束。

2.1 編碼方式及初始種群生成

設種群規模為Q，種群為(P1，P2，…，PQ)，其中一個個體代表一種下料方案，由于每個下料方案由一個或多個布局圖和對應的使用次數組成，因此個體的基因由(pk，xk)組成，其中k=1，2，…，K，該編碼方式有利于后續遺傳操作和個體合法性的校正。

1）個體生成算法GetPlan()。

用啟發式方法生成個體，具體步驟如下：

步驟1 令ri=bi記錄毛坯當前剩余需求量，初始化k=0記錄下料方案中布局圖的種類數。

步驟2 如果存在任意的ri＞0，轉至步驟3；否則，轉至步驟4。

步驟3 令k=k+1，調用布局圖生成算法生成布局圖，將當前布局圖記為pk，根據式（7）確定使用次數xk，將(pk，xk)記錄成當前個體的一個基因，用ri=ri-xk×aik更新圓片剩余需求量，根據式（8）對圓片的價值vi進行調整，轉至步驟2。

步驟4 令K=k 為當前個體的基因長度，得到初始種群的一個個體，算法結束。

2）布局圖生成算法GetPattern()。

由式（4）計算出所有條帶的寬度wij，由式（5）分別計算出X 方向條帶的圓片數量zxij和Y 方向條帶的圓片數量zyij，條帶的價值分別為vxij和vyij，根據1.2節的遞推式設計生成布局圖的算法。具體步驟如下：

步驟1 令x=0 記錄X 方向子板材長度，令y=0 記錄Y方向子板材寬度。

步驟2 根據式（6）分別計算F(L)和F(W)，從而確定F(L，W)，再遞推計算得出板材中所有條帶的布局和所包含的各種圓片的總數ni。

步驟3 輸出當前布局圖，算法結束。

2.2 適應度函數

適應度函數用于評價個體的優劣。用個體對應的下料方案利用率（利用率=所需圓片總面積/消耗板材總面積）評價個體的適應度，利用率越大，說明個體的適應度越好。第i 個個體適應度Ui的計算公式為：

2.3 選擇過程

選擇過程是從當前的種群個體中選擇部分個體進行后續的交叉變異等操作，適應度越高的個體被選擇的概率越高。選擇過程采用精英保留策略和輪盤賭選擇策略，在保留適應度高的個體的同時保證個體的多樣性。用式（9）計算每個個體的適應度，用精英保留策略將適應度最高的個體直接保留為選擇后的個體之一，再用輪盤賭策略進行選擇，直至達到當前種群的規模。選擇后的個體進入交叉和變異過程。選擇操作的具體步驟如下：

步驟1 計算個體適應度Ui(i=1，2，…，t)，選擇其中適應度最高的個體為待交叉和變異個體之一。

步驟3 若k ≤t，轉至步驟4；否則，轉至步驟5。

步驟4 在[0，1]內產生一個隨機數r，如果r ＜CP1，選擇個體P1；否則，選擇個體Pi，使得CPi-1＜r ＜CPi；令k=k+1，轉至步驟3。

步驟5 輸出選擇后的所有個體，算法結束。

2.4 交叉過程

交叉過程是對兩個個體的某些基因進行交叉，交叉后需對個體的合法性進行檢驗和校正，從而產生新的個體。交叉操作是避免遺傳算法早熟的一個手段。本文采用兩點雙向交叉策略，自適應交叉概率pc的計算公式如下：

其中：f 為當前個體的適應度，fbest為子種群中最優個體的適應度，favg為子種群中所有個體的平均適應度；0 ＜pc2＜pc1＜1，本文中pc1=0.9，pc2=0.6。

由P1至Pt按順序選擇兩個相鄰個體，對于選擇的兩個個體，計算交叉概率pc，在[0，1]內產生一個隨機數r，如果r ＜pc，則對這兩個個體進行交叉；否則，進行下一次選擇，直至所有個體選擇完畢。假設選擇交叉的兩個個體為P1和P2，個體長度分別為K1和K2，具體的交叉過程如下：計算f=max{Uq1，Uq2}，根據式（10）計算pc，在[0，1]內產生一個隨機數r。如果r ＜pc，在[1，min(K1，K2)]內產生兩個不相等的隨機整數a 和b，為避免無效交叉，交叉部分的基因段的長度不能等于個體的長度，因此a 和b 需滿足：當a ＜b 時，b-a+1 ≠min(K1，K2)或當a ＞b 時a-b ＞1。若a ＜b，則將個體P1和P2的[a，b]區間的基因進行交換；若a ＞b，則將個體P1和P2的[1，b]區間的基因進行交換，再將P1的[a，K1]區間的基因和P2的[a，K2]進行交換。交叉結束后產生的新個體為P1'和。

用下面的例子說明具體的交叉過程：P1和P2的個體長度分別為K1=7和K2=6。假設產生的隨機整數a=3，b=5，由于a ＜b，因 此 將P1的 基 因 段(q13，q14，q15)和P2的 基 因 段(q23，q24，q25)進行互換，互換過程如圖2（a）所示。假設產生的隨機整數a=5，b=2，由于a ＞b，因此將P1的基因段(q11，q12)和P2的 基 因 段(q21，q22)進 行 互 換，再 將P1的 基 因 段(q15，q16，q17)和P2的基因段(q25，q26)進行互換，互換過程如圖2（b）所示。

圖2 兩點雙向交叉Fig.2 Crossover of two points and two directions

通過交叉生成的新個體由于其中的部分基因序列產生了變化，導致新個體中部分種類毛坯總數明顯超出需求量，或者部分種類毛坯的需求量未得到滿足，從而導致非合法個體的出現，因此交叉后要對新個體進行合法性檢驗和校正。具體算法步驟如下：

步驟1 令ri=bi以記錄毛坯當前剩余需求量，K 為新個體基因長度，若a ＜b，轉至步驟2；若a ＞b，轉至步驟4。

步驟2 保留[1，a-1]和[b+1，K]區間的基因，并根據相應的(pk，xk)，用ri=ri-xk×aik更新圓片剩余需求量。

步驟3 遍歷[a，b]的每一個新基因(pk，xk)，若布局圖pk中存在已滿足需求的毛坯，舍棄該基因，令K=K-1；否則，保留當前布局圖pk，根據式（7）重新確定使用次數xk，用ri=ri-xk×aik更新圓片剩余需求量。遍歷結束后，由前往后調整各基因的位置，轉至步驟6。

步驟4 保留[a+1，b-1]區間的基因，并根據相應的(pk，xk)更新剩余需求量：ri=ri-xk×aik。

步驟5 遍歷[1，b]和[a，K]的每一個基因(pk，xk)，若布局圖pk中存在已滿足需求的毛坯，舍棄該基因，令K=K-1；否則，保留當前布局圖pk，根據式（7）重新確定使用次數xk，用ri=ri-xk×aik更新圓片當前剩余需求量。遍歷結束，由前往后調整各基因的位置，轉至步驟6。

步驟6 若存在任意的需求量ri＞0，轉至步驟7；否則，轉至步驟8。

步驟7 調用布局圖生成算法生成一個布局圖，令K=K+1，k=K，將當前布局圖記為pk，并根據式（7）確定使用次數xk，將(pk，xk)記錄成當前個體的一個基因，用ri=ri-xk×aik更新圓片剩余需求量，根據式（8）對圓片的價值vi進行調整，轉至步驟6。

步驟8 輸出校正后的個體，算法結束。

2.5 變異過程

變異過程是對個體的某些基因用新的基因替換，并保證變異過程中個體的合法性，從而產生一個新的個體。變異過程的目的有兩個：一是使遺傳算法具有局部的搜索能力；二是使遺傳算法維持群體多樣性，以防止出現早熟的現象。本文采用兩點雙向變異策略，自適應變異概率pm的計算公式如下：

其中：f 為當前個體的適應度，fbest為種群中最優個體的適應度，favg為種群的平均適應度；0.02 ＜pm2＜pm1＜0.2，pm1=0.1，pm2=0.05。

由P1至Pt按順序選擇個體，對于當前選擇個體，計算變異概率pm，在[0，1]內產生一個隨機數r，如果r ＜pc，則對該個體進行變異；否則，進行下一次選擇，直至所有個體選擇完畢。具體的變異過程如下：假設選擇的個體為P，個體長度為K，根據式（11）計算pm，在[0，1]內產生一個隨機數r，若r ＜pm，在[1，K]內產生兩個不相等的隨機整數a 和b。若a ＜b，將[a，b]區間基因進行變異；若a ＞b，則將[1，b]，[a，K]的基因進行變異。變異后的新個體為P'。

用下面的例子說明具體的變異過程：P 的個體長度為K=7。假設產生的隨機整數a=3，b=5，由于a ＜b，因此將基因段(q3，q4，q5)進行變異，變異過程如圖3（a）所示；假設產生的隨機整數a=6，b=2，由于a ＞b，因此將P 的基因段(q1，q2)和(q6，q7)進行變異，變異過程如圖3（b）所示。

圖3 兩點雙向變異Fig.3 Mutation of two points and two directions

在變異過程中，需要保證變異產生的新基因不包含已滿足需求的毛坯，具體算法步驟如下：

步驟1 令ri=bi記錄毛坯當前剩余需求量，K 為新個體的基因長度，若a ＜b，轉至步驟2；若a ＞b，轉至步驟3。

步驟2 將[a，b]的基因從個體中移除，令K=K-l為個體的基因長度，由前往后調整各基因的位置，轉至步驟4。

步驟3 將[1，b]和[a，K]的基因從個體中移除，令K=K-l 更新個體的基因長度，由前往后調整各基因的位置，轉至步驟4。

步驟4 遍歷當前個體的每個基因，根據(pk，xk)用ri=ri-xk×aik更新圓片剩余需求量。

步驟5 若存在任意ri＞0，轉至步驟6；否則，轉至步驟7。

步驟6 調用布局圖生成算法生成布局圖，令K=K+1，令k=K，將當前布局圖記為pk，并根據式（7）計算使用次數xk，將(pk，xk)記錄成當前個體的一個基因，用ri=ri-xk×aik更新圓片剩余需求量，根據式（8）對圓片價值vi進行調整，轉至步驟5。

步驟7 輸出新的個體，算法結束。

3 實驗結果及分析

PGBA 用C#語言編程實現，運行機器CPU 為i5-4590，主頻3.30 GHz，四核四線程，內存16 GB。為與后續比較的一致性，板材尺寸設為L×W=2 000×1 000，工藝余量ω=5。根據文獻［7］的分析，線程的數量增加有利于提高算法的運算性能，因此將算法的線程數設為T=4。實驗首先對遺傳算法的進化代數和種群規模兩個參數進行測試，分析兩者對算法的性能影響；再通過與串行遺傳算法和相關文獻算法進行比較分析，驗證算法的有效性。

3.1 算法在不同參數條件的性能比較

在遺傳算法中，種群規模和進化代數對算法的性能起到重要作用，一般來說，種群規模和進化代數越大，算法搜索到更優解的可能性越大，但同時計算開銷也會增加，因此需要根據實際需求確定合適的參數范圍。本節通過對算法不同參數進行測試，以確定合適的種群規模和進化代數。

1）不同進化代數的比較。

測試用例參照文獻［6］的參數范圍進行設定，相關參數取值范圍如表1所示。根據表1生成300個隨機測試算例。

表1 隨機算例相關參數Tab.1 Relevant parameters for random examples

設種群規模Q=80，分別在進化代數10、20、50、100 的條件下進行測試，300 個算例在不同進化代數的材料平均利用率如圖4 所示。可以看出，當R 較小時，隨著進化代數的增加，平均利用率的提高速度較快，當R 達到50 代之后，平均利用率的提高速率減緩。同時，隨著進化代數的增加，平均利用率有所提高，但運算時間也不斷增加：當R=10 時，平均每個算例的計算時間為13.54 s；當R=100 時，平均計算時間達到了103.67 s。綜合利用率和運算時間，設定算法的進化代數R=50。

圖4 不同進化代數的平均利用率Fig.4 Average utilization rate of different evolutionary generations

2）不同種群規模的比較。

設定進化代數R=50，用測試1）中300 個隨機算例分別在種群規模為20、40、80、100、120 的條件下進行測試，結果如圖5 所示。可以看出，隨著種群的規模增大，300 個算例的平均材料利用率呈線性增加，當種群規模增加到80 個之后，平均利用率的提高速率減緩。并且隨著種群規模的增大，算法的計算時間也會增加：當Q=20 時，平均計算時間為17.54 s；當Q=120 時，平均計算時間為83.24 s。因此設定種群的規模Q=80。

圖5 不同種群規模的平均利用率Fig.5 Average utilization rate of different population sizes

3.2 與串行遺傳算法的比較

3.1 節中產生的隨機算例特點屬于圓片需求種類少但需求量較大的情況。在下料的組合優化問題中，隨著圓片的種類和需求量增加，問題的規模和求解難度也不斷增大。本節根據表2 的相關參數范圍，隨機生成四組不同規模的算例，分別用并行遺傳算法和串行遺傳算法進行測試。

表2 不同規模算例參數設置Tab.2 Parameters setting for examples with different scales

不同規模的算例運行結果如表3 所示。可以看出：并行遺傳算法與串行遺傳算法在材料利用率上都得到了提高，可以有效縮短計算時間；并且隨著問題規模的增加，并行遺傳算法的計算速度更快，效果更明顯。

表3 不同規模的算例運行結果比較Tab.3 Running results comparison of examples with different scales

3.3 與文獻算法在材料平均利用率上的比較

文獻［6］中針對圓片剪切下料問題，采用主動生成余料條帶策略，用啟發式方法求解下料方案，以提高一個周期內的總體的材料利用率，文獻［6］的算例屬于圓片種類數較少，但需求量較大的情況。

1）與文獻［6］方法的比較。

針對文獻［6］不主動產生余料的策略，用文獻［6］中的30個算例對本文算法進行測試，結果如表4所示，其中30個算例的消耗板材總面積為S，材料平均利用率為UL，平均計算時間為T，Δ 則表示兩個對比算法的參數結果差值。可以看出，文獻［6］算法所消耗材料的總面積為35 388 m2，本文算法所消耗板材的總面積為33650 m2，相比之下節省板材面積1 738 m2，材料利用率提高3.21%，雖然運算時間增加較多，但仍在可接受范圍內，并且材料利用率得到了較大的提高。

表4 兩種算法的剪切下料結果比較Tab.4 Comparison of cutting results of two algorithms

2）更大規模問題的比較。

在3.3 節測試1）中，PGBA 對于文獻［6］的算例取得了較好的測試效果，為了進一步驗證PGBA 的有效性和適應性，根據表5隨機生成30個更大規模問題的算例，相比文獻［6］的算例，這30個算例的圓片種類數更多，需求量更大。

分別用本文算法和文獻［6］算法和進行測試，兩種算法的材料平均利用率如表6 所示。可以看出，30 個算例的材料平均利用率得到了提高，文獻［6］算法所消耗材料的總面積為57 358 m2，本文算法所消耗板材的總面積為5 6313 m2，相比之下節省板材面積1 045 m2，總體材料利用率提高1.25%，計算時間在可接受的范圍內。

表5 隨機算例相關參數Tab.5 Relevant parameters of random examples

表6 兩種算法在大規模問題算例上的剪切下料結果比較Tab.6 Comparison of cutting results of two algorithms for large-scale examples

實驗結果表明，本文算法對于不同規模問題都能取得較好的效果，雖然計算時間增加，但在實際生產中，花費較多的計算時間來獲得利用率的提高是可以接受的。

4 結語

本文針對圓片直切布局的下料問題提出了并行遺傳下料算法PGBA。在并行遺傳算法的基礎上，對個體采用特定的編碼方式，用啟發式的方法生成初始種群，并通過性能較好的自適應遺傳操作來提升算法的性能和效率。實驗結果表明，

PGBA 具有良好的性能，可以在滿足實際生產中對計算時間要求的情況下，使板材的利用率普遍達到或超過一般的啟發式方法，在解決圓片剪切下料問題上具有良好的實用性。在今后的研究中，我們可以在PGBA 的基礎上，從實際生產的需求出發，通過對算法的相關參數和采用的策略進行修正和測試分析，或是結合其他算法，進一步對下料問題的優化進行研究。