圓片下料并行遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)

曾志陽，陳 燕，王 珂

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，南寧530004）

0 引言

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

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

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

1 下料問題描述及數(shù)學(xué)模型

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

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

1.1 圓片的布局

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

其中：di為第i 種圓片的直徑，當(dāng)圓片呈橫向排列時(shí)，len=L，當(dāng)圓片呈縱向排列時(shí)，len=W。

1.2 布局圖的生成

根據(jù)文獻(xiàn)［6］所述，條帶的剪切工藝可分為滾剪和平剪兩種方式，相對(duì)平剪方式，滾剪能大幅度減少條帶切割的工作量，適合批量圓片的生成。滾剪通常采用直切布局圖，其生成過程可看作條帶沿X 方向或Y 方向的拼接過程，條帶的長(zhǎng)度或?qū)挾染怀霭宀牡某叽?，不同方向的布局圖如圖1 所示。布局圖的生成過程是背包問題的求解過程，目的是使得板材上放置的條帶價(jià)值最大化，可用動(dòng)態(tài)規(guī)劃方法求解［13］。寬度為wij的條帶的有效圓片數(shù)為其中l(wèi) 為當(dāng)前條帶拼接方向的尺寸，條帶的價(jià)值vij=cij?vi。設(shè)F(L，W)為板材的最大價(jià)值（布局圖中有效圓片的總價(jià)值），F(xiàn)(x)為x×W 的子板材或L×y 的子板材的價(jià)值，其中1 ≤x ≤L，1 ≤y ≤W；η(l，i)記錄子板材中第i種毛坯的數(shù)量。

用動(dòng)態(tài)規(guī)劃的遞推方式生成布局圖，遞推式如下：

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

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

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

1.3 價(jià)值校正函數(shù)

用啟發(fā)式方法生成初始種群個(gè)體的過程中，如果圓片的價(jià)值固定不變，根據(jù)動(dòng)態(tài)規(guī)劃的思想，每次生成的布局圖都是不變的，并且在實(shí)際過程中發(fā)現(xiàn)，直徑較小的圓片往往都會(huì)優(yōu)先排入，導(dǎo)致后續(xù)的布局圖中組合的效果較差。通過引入價(jià)值校正函數(shù)，調(diào)整每一種圓片的價(jià)值，能夠有效降低算法的貪婪性，使得種群個(gè)體更加多樣化［14］。本文采用的價(jià)值調(diào)整函數(shù)如下：

其中：si為第i 種圓片的面積，u 為當(dāng)前布局圖的利用率，ni為當(dāng)前布局圖中第i種圓片的個(gè)數(shù)，系數(shù)Ω=0.75，p=1.03。

2 并行遺傳下料算法的設(shè)計(jì)

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

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

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

步驟2 啟用T 個(gè)線程，每個(gè)線程各自調(diào)用2.1 節(jié)的個(gè)體生成算法生成t=Q/T 個(gè)個(gè)體的子種群，初始化進(jìn)化代數(shù)k=0，用σi(i=1，2，…，T)記錄每個(gè)子種群進(jìn)化過程中出現(xiàn)的適應(yīng)度最高個(gè)體，用σbest記錄最優(yōu)的個(gè)體。

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

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

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

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

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

用啟發(fā)式方法生成個(gè)體，具體步驟如下：

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

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

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

步驟4 令K=k 為當(dāng)前個(gè)體的基因長(zhǎng)度，得到初始種群的一個(gè)個(gè)體，算法結(jié)束。

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

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

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

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

步驟3 輸出當(dāng)前布局圖，算法結(jié)束。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評(píng)價(jià)個(gè)體的優(yōu)劣。用個(gè)體對(duì)應(yīng)的下料方案利用率（利用率=所需圓片總面積/消耗板材總面積）評(píng)價(jià)個(gè)體的適應(yīng)度，利用率越大，說明個(gè)體的適應(yīng)度越好。第i 個(gè)個(gè)體適應(yīng)度Ui的計(jì)算公式為：

2.3 選擇過程

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

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

步驟3 若k ≤t，轉(zhuǎn)至步驟4；否則，轉(zhuǎn)至步驟5。

步驟4 在[0，1]內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)r，如果r ＜CP1，選擇個(gè)體P1；否則，選擇個(gè)體Pi，使得CPi-1＜r ＜CPi；令k=k+1，轉(zhuǎn)至步驟3。

步驟5 輸出選擇后的所有個(gè)體，算法結(jié)束。

2.4 交叉過程

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

其中：f 為當(dāng)前個(gè)體的適應(yīng)度，fbest為子種群中最優(yōu)個(gè)體的適應(yīng)度，favg為子種群中所有個(gè)體的平均適應(yīng)度；0 ＜pc2＜pc1＜1，本文中pc1=0.9，pc2=0.6。

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

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

圖2 兩點(diǎn)雙向交叉Fig.2 Crossover of two points and two directions

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

步驟1 令ri=bi以記錄毛坯當(dāng)前剩余需求量，K 為新個(gè)體基因長(zhǎng)度，若a ＜b，轉(zhuǎn)至步驟2；若a ＞b，轉(zhuǎn)至步驟4。

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

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

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

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

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

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

步驟8 輸出校正后的個(gè)體，算法結(jié)束。

2.5 變異過程

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

其中：f 為當(dāng)前個(gè)體的適應(yīng)度，fbest為種群中最優(yōu)個(gè)體的適應(yīng)度，favg為種群的平均適應(yīng)度；0.02 ＜pm2＜pm1＜0.2，pm1=0.1，pm2=0.05。

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

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

圖3 兩點(diǎn)雙向變異Fig.3 Mutation of two points and two directions

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

步驟1 令ri=bi記錄毛坯當(dāng)前剩余需求量，K 為新個(gè)體的基因長(zhǎng)度，若a ＜b，轉(zhuǎn)至步驟2；若a ＞b，轉(zhuǎn)至步驟3。

步驟2 將[a，b]的基因從個(gè)體中移除，令K=K-l為個(gè)體的基因長(zhǎng)度，由前往后調(diào)整各基因的位置，轉(zhuǎn)至步驟4。

步驟3 將[1，b]和[a，K]的基因從個(gè)體中移除，令K=K-l 更新個(gè)體的基因長(zhǎng)度，由前往后調(diào)整各基因的位置，轉(zhuǎn)至步驟4。

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

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

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

步驟7 輸出新的個(gè)體，算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 算法在不同參數(shù)條件的性能比較

在遺傳算法中，種群規(guī)模和進(jìn)化代數(shù)對(duì)算法的性能起到重要作用，一般來說，種群規(guī)模和進(jìn)化代數(shù)越大，算法搜索到更優(yōu)解的可能性越大，但同時(shí)計(jì)算開銷也會(huì)增加，因此需要根據(jù)實(shí)際需求確定合適的參數(shù)范圍。本節(jié)通過對(duì)算法不同參數(shù)進(jìn)行測(cè)試，以確定合適的種群規(guī)模和進(jìn)化代數(shù)。

1）不同進(jìn)化代數(shù)的比較。

測(cè)試用例參照文獻(xiàn)［6］的參數(shù)范圍進(jìn)行設(shè)定，相關(guān)參數(shù)取值范圍如表1所示。根據(jù)表1生成300個(gè)隨機(jī)測(cè)試算例。

表1 隨機(jī)算例相關(guān)參數(shù)Tab.1 Relevant parameters for random examples

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

圖4 不同進(jìn)化代數(shù)的平均利用率Fig.4 Average utilization rate of different evolutionary generations

2）不同種群規(guī)模的比較。

設(shè)定進(jìn)化代數(shù)R=50，用測(cè)試1）中300 個(gè)隨機(jī)算例分別在種群規(guī)模為20、40、80、100、120 的條件下進(jìn)行測(cè)試，結(jié)果如圖5 所示?？梢钥闯?，隨著種群的規(guī)模增大，300 個(gè)算例的平均材料利用率呈線性增加，當(dāng)種群規(guī)模增加到80 個(gè)之后，平均利用率的提高速率減緩。并且隨著種群規(guī)模的增大，算法的計(jì)算時(shí)間也會(huì)增加：當(dāng)Q=20 時(shí)，平均計(jì)算時(shí)間為17.54 s；當(dāng)Q=120 時(shí)，平均計(jì)算時(shí)間為83.24 s。因此設(shè)定種群的規(guī)模Q=80。

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

3.2 與串行遺傳算法的比較

3.1 節(jié)中產(chǎn)生的隨機(jī)算例特點(diǎn)屬于圓片需求種類少但需求量較大的情況。在下料的組合優(yōu)化問題中，隨著圓片的種類和需求量增加，問題的規(guī)模和求解難度也不斷增大。本節(jié)根據(jù)表2 的相關(guān)參數(shù)范圍，隨機(jī)生成四組不同規(guī)模的算例，分別用并行遺傳算法和串行遺傳算法進(jìn)行測(cè)試。

表2 不同規(guī)模算例參數(shù)設(shè)置Tab.2 Parameters setting for examples with different scales

不同規(guī)模的算例運(yùn)行結(jié)果如表3 所示?？梢钥闯觯翰⑿羞z傳算法與串行遺傳算法在材料利用率上都得到了提高，可以有效縮短計(jì)算時(shí)間；并且隨著問題規(guī)模的增加，并行遺傳算法的計(jì)算速度更快，效果更明顯。

表3 不同規(guī)模的算例運(yùn)行結(jié)果比較Tab.3 Running results comparison of examples with different scales

3.3 與文獻(xiàn)算法在材料平均利用率上的比較

文獻(xiàn)［6］中針對(duì)圓片剪切下料問題，采用主動(dòng)生成余料條帶策略，用啟發(fā)式方法求解下料方案，以提高一個(gè)周期內(nèi)的總體的材料利用率，文獻(xiàn)［6］的算例屬于圓片種類數(shù)較少，但需求量較大的情況。

1）與文獻(xiàn)［6］方法的比較。

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

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

2）更大規(guī)模問題的比較。

在3.3 節(jié)測(cè)試1）中，PGBA 對(duì)于文獻(xiàn)［6］的算例取得了較好的測(cè)試效果，為了進(jìn)一步驗(yàn)證PGBA 的有效性和適應(yīng)性，根據(jù)表5隨機(jī)生成30個(gè)更大規(guī)模問題的算例，相比文獻(xiàn)［6］的算例，這30個(gè)算例的圓片種類數(shù)更多，需求量更大。

分別用本文算法和文獻(xiàn)［6］算法和進(jìn)行測(cè)試，兩種算法的材料平均利用率如表6 所示?？梢钥闯?，30 個(gè)算例的材料平均利用率得到了提高，文獻(xiàn)［6］算法所消耗材料的總面積為57 358 m2，本文算法所消耗板材的總面積為5 6313 m2，相比之下節(jié)省板材面積1 045 m2，總體材料利用率提高1.25%，計(jì)算時(shí)間在可接受的范圍內(nèi)。

表5 隨機(jī)算例相關(guān)參數(shù)Tab.5 Relevant parameters of random examples

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

實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)于不同規(guī)模問題都能取得較好的效果，雖然計(jì)算時(shí)間增加，但在實(shí)際生產(chǎn)中，花費(fèi)較多的計(jì)算時(shí)間來獲得利用率的提高是可以接受的。

4 結(jié)語

本文針對(duì)圓片直切布局的下料問題提出了并行遺傳下料算法PGBA。在并行遺傳算法的基礎(chǔ)上，對(duì)個(gè)體采用特定的編碼方式，用啟發(fā)式的方法生成初始種群，并通過性能較好的自適應(yīng)遺傳操作來提升算法的性能和效率。實(shí)驗(yàn)結(jié)果表明，

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