基于改進粒子群算法的木材板材下料方法

黃秀玲,陶澤,尤華政,李宸,劉俊

(南京林業大學機械電子工程學院,南京 210037)

在家具行業中,以綠色環保、節約能源為目的的優化木材板材下料問題已經成為研究熱點,木材板材下料問題受重視程度日益提高。目前有很多企業生產家具產品時,對于木材板材仍使用人工下料,經常耗時較長且材料浪費嚴重。由于客戶需求的多樣性,需要合理安排下料方案,充分利用木材板材,提高企業經濟效益和節約社會資源。本研究的木材板材下料優化問題屬于二維矩形下料問題,是一種具有高度計算復雜性的問題[1-4]。

20世紀60年代,Gilmore等[5-6]提出了經典的“一刀切(guillotine cutting)”和“正交切割(non-guillotine cutting)”兩種二維切割方式,通過線性規劃和動態規劃,解決了“一刀切(guillotine cutting)”問題范圍內的下料算法,首次為解決下料問題提供了切實可行的方案和技術手段。但是由于當時計算輔助技術并不是很突出,所以僅停留在理論層面。

20世紀90年代后期,隨著計算機技術的高速發展,計算復雜性理論不斷成熟,大量的智能優化算法不斷涌現,并在各行業中得到廣泛應用[7-8],如遺傳算法(genetic algorithm)、模擬退火算法(simulated annealing)、灰狼優化(grey wolf optimization)、蜻蜓算法(dragonfly algorithm)、蟻群算法(ant colony algorithm)以及粒子群算法(particle swarm optimization algorithm)等。這些算法一般都是建立在生物智能或物理現象基礎上的隨機搜索算法,可以解決大規模的復雜下料問題,且通用性較強[9-11]。筆者主要針對單規格木材板材下料問題,在木材板材長和寬都大于零件長和寬的情況下,采用粒子群算法、變鄰域搜索算法、粒子群變鄰域搜索混合算法求解單規格木材板材下料問題,并進行分析對比。

1 數學模型的建立

本研究所采用的原材料板材為L×W的矩形木材板材,待切割的毛坯零件一共有K種。在充分考慮多方面因素和約束的前提下,選擇以剩余廢料最少為優化目的,得出數學模型如下[12]:

0≤Xk≤L,(1≤k≤Cj,1≤j≤N)

(1)

0≤Yk≤W,(1≤k≤Cj,1≤j≤N)

(2)

(3)

(4)

Rk∩Rkj=?,(1≤k≠kj≤Cj,1≤j≤N)

(5)

(6)

(7)

Tj≥1,(1≤j≤N)

(8)

(9)

式中:L和W分別為原材料板材的長度和寬度;l和w分別為零件板材的長度和寬度;i和K分別為零件類型編號和集合,i∈K;N為原材料板材的數量;Cj為j張單板上排放零件數量;(Xk,Yk)為每個矩形零件對應左下角的坐標,k∈Cj;Pk為矩形零件在原材料中的排列方式;Rk為零件所在矩形的命名;ni為第i類零件的數量;Aij為在第j張單板方案中第i種零件的數量,且Aij≤ni;Tj為第j種方式的切割次數,j∈N,Tj≥1;F為目標函數。

式(1)確保排放在原材料板材上的所有毛坯零件X軸上的長度不會超出原材料板材的長度;式(2)確保排放在原材料板材上的所有毛坯零件Y軸上的長度不會超出原材料板材的長度;式(3)和式(4)為了保證零件不會超出原材料板材的邊界,限制了長度和寬度;式(5)保證毛坯零件不會重疊排放在原材料板材上;式(6)和式(7)使所有毛坯零件的數量和配套要求得到滿足;式(9)是目標函數,使得浪費的原材料板材的面積最小,也就是保證原材料板材的利用率能夠達到最高。

2 算法求解

2.1 粒子群算法

粒子群算法也稱作粒子群優化算法(particle swarm optimization,PSO),是1995年美國Kennedy等[13]通過對鳥類群體行為進行模仿提出的一種進化算法(evolutionary algorithm,EA)。粒子群算法通常用于解決連續優化問題,將其應用于排樣問題中的排列組合問題,需要對粒子群算法進行一定的調整[14-15]。

2.1.1 編 碼

排列組合問題涉及對元素進行排列或組合,因此需要定義適合該問題的編碼方式。常用的離散式編碼方法主要包括二進制編碼、排列編碼或One-Hot編碼等方式。針對排樣問題的順序優化上選用基于位置的編碼方式,即將每個可行解看作一個由各個元素位置決定的序列。排樣過程中每個可行解可以表示為一個由n個元素位置決定的序列,其中第i個元素表示該物品在排樣中的位置,具體的零件排序方式為:

X=(x1,x2,…,xi-1,xi,xi+1,…,xn)

(10)

式中:xi表示第i個零件在排樣中的位置,i=1,2,…,n。整個序列X表示優化過程中一個完整的零件排列[16]。這樣的編碼方式可以保證每個粒子的取值范圍是固定的、不重復的,且可以直接映射到可行解的空間。

2.1.2 粒子速度

在排列優化問題中,由于粒子編碼格式的特殊性,速度與位置的運算方式需要重新定義。本研究采用基于位置編碼方式的離散式粒子群算法速度的計算方式[17]。

定義速度V為位置X2和位置X1的差值,是一個N維向量:

V=X2-X1

(11)

式中,速度V中的每個元素vi表示為X2和X1在序列上對應的元素的對比。當X1的元素與X2相同時速度V上的元素記錄為0,當X1的元素與X2不相同時速度V上的元素記錄為X2的元素,具體可表示為:

(12)

排列優化問題中,位置與速度的加法運算可表示為:

X=X1+V1

(13)

式中,進行加法運算后新產生的向量的每一個分量以序列i的順序按照以下方式計算:當V1的元素為0時,X的元素記錄為X1的元素;當V1的元素不為0時,X的元素記錄為V1的元素,并將X1中對應數值x1,i與數值v1,i的序列位置交換(由于編碼的方式為位置編碼,對于任意序列X1,當x1,i與v1,i不同時,X1中都應包含非零元素v1,i)。具體可表示為:

(14)

粒子的運動方程具體描述如下:

V=c1(Xpbest-X)+c2(Xgbest-X)

(15)

式中,速度的數乘方式具有概率意義,它可以增強計算的隨機性。在計算過程中生成一個隨機數,通過數值的比較確定速度值。

(16)

2.1.3 目標函數

矩形排樣問題的目標是在一個給定規格的矩形板材上,按照某種排列順序擺放零件,從而最大化板材的利用率。在粒子群算法中,將編碼數值作為排樣順序,將位置編碼下產生的排樣利用率作為目標。

具體的,粒子群算法下,排樣策略的全局目標如式(17)所示:

(17)

式中:f表示為下料零件總面積在所用板材面積中占據的最大比例;i為零件序號;N為零件總數;Si為第i個零件所占據面積;W為板材寬度;H*為該排樣方案下N個零件排放完畢后,零件排樣圖的最大使用高度。

2.1.4 粒子群算法流程

本研究粒子群算法的流程如圖1所示,具體流程如下:

圖1 粒子群算法流程Fig. 1 Flow chart of particle swarm optimization

1)粒子群狀態進行重置。

2)對粒子的適應度值Fit[i]進行計算。

3)個體極值pbest(i)比較,當Fit[i]>pbest(i)時,Fit[i]替換掉pbest(i)。

4)全局極值gbest(i)比較,當Fit [i]>gbest(i)時,Fit [i]替換掉gbest(i)。

5)根據式(13)和式(15)更新粒子的位置Xi和速度Vi。

6)判斷是否滿足結束條件(誤差足夠好或者達到最大循環次數),若滿足,則算法結束并輸出最優結果;若不滿足,則返回2)。

2.2 變鄰域搜索算法

變鄰域搜索算法(variable neighborhood search,VNS)是由Hansen和Mladenovi在1997年提出的一種新穎且高效的局部搜索算法[18-19]。其基本思想是:為了能夠更好地獲取局部最優解,算法擴展了解的搜索范圍,并且在搜索的過程中系統化地改變其多個鄰域結構[20-21]。

本研究變鄰域搜索算法的簡要流程如圖2所示,算法流程如下:

1)初始化。給定一個初始解S,并定義一系列鄰域結構NK,K=1,2,…,Kmax。

2)令K=1。

3)把定義的初始解S作為當前解,在當前鄰域NK內進行局部搜索獲得該鄰域的最優解S1。

4)若S1優于S,就用S1替換掉當前解S,跳回2);若不優于S,就令K=K+1。

5)若K>Kmax,就直接輸出最優解,結束;若K

圖2 VNS算法流程Fig. 2 Flow chart of VNS algorithm

變鄰域搜索主要包括局部搜索(local search)和改變鄰域(neighborhood change)。其中,局部搜索的作用是在同一個鄰域結構中尋找更優的局部最優解,改變鄰域的作用是為整個搜索過程提供一種迭代方法和停止準則。

本研究根據排樣需要采用混合性鄰域結構的變鄰域搜索策略[22]。其基本步驟如下:

1)初始化。選擇初始解x,鄰域結構N(i),i=1,2,…,k,當前最優解xbest=x。

2)如果滿足算法終止條件,那就輸出xbest;若不滿足算法終止條件,那就令i=1。

3)如果i=k+1,那么就跳轉步驟2);否則,在x的鄰域結構N(i)中隨機選取可行解x′,在x′的鄰域結構中搜索得到局部最優解x″,若x″比當前最優解xbest更優,則xbest=x″,i=i+1。循環這步操作。

2.3 粒子群混合變鄰域搜索算法

通過分析粒子群與變鄰域搜索算法結構及試驗結果,發現粒子群算法和變鄰域搜索算法均有各自的優點和不足。

粒子群算法的局部搜索能力較弱,搜索精度較低,所以很容易造成過早收斂的情況,但是變鄰域搜索算法具有較好的局部搜索能力且搜索精度也較高。在運算過程中,粒子群算法受歷史最優解的影響較大,經過不斷的迭代都是在向最優解靠近,缺少了解的多樣性,而變鄰域搜索算法正好可以彌補這一缺點,通過不斷搜索不同鄰域,可以跳出局部最優的情況。

粒子群算法收斂速度較快,全局搜索能力較好,主要通過粒子不斷向最優解靠近,可以較快地在很大的解空間中找到具有最優解的大致范圍。這正好可以彌補變鄰域搜索算法收斂速度慢、搜索時間長的缺點,可以給變鄰域搜索的開始提供一個高質量的初始解。

為了克服粒子群算法可能產生早熟的現象,考慮到粒子群算法中粒子每次更新都會受到當前解、個體歷史最優解和種群歷史最優解3個因素的影響,本研究將粒子的更新過程采用變鄰域搜索,動態地改變鄰域結構來拓展搜索的空間,使算法最終能夠跳出局部最優解,搜索到全局最優解。

筆者設計的粒子群混合變鄰域搜索算法的基本流程如下:

1)對粒子群狀態進行重置。

2)對粒子的適應度值Fit[i]進行計算。

3)個體極值pbest(i)比較,當Fit[i]>pbest(i)時,Fit[i]替換掉pbest(i)。

4)全局極值gbest(i)比較,當Fit [i]>gbest(i)時,Fit [i]替換掉gbest(i)。

5)根據式(14)和式(15)更新粒子的位置Xi和速度Vi。

6)判斷是否滿足結束條件(誤差足夠好或者達到最大循環次數),若滿足,則算法結束并輸出最優結果;若不滿足,則返回2)。

7)對粒子進行調用變鄰域搜索,主要的搜索策略是:順序執行各個模塊,一旦出現比當前更優秀的中間解,就用中間解代替當前解,繼續調用這個模塊進行搜索,直到搜索發現更差的中間解出現;否則執行下一模塊直到結束。

8)判斷是否滿足結束條件K

9)輸出全局最優值,算法運行結束。

粒子群混合變鄰域搜索算法流程圖如圖3所示。

圖3 粒子群變鄰域搜索混合算法流程Fig. 3 Flow chart of particle swarm variable neighborhood search hybrid algorithm

圖4 實例1的3種算法下料方案對比Fig. 4 Comparison of cutting patterns of three algorithms in the example 1

本研究首先利用粒子群算法進行運算,求出的最優解作為后續變鄰域搜索算法的初始解,再用變鄰域搜索算法繼續進行求解。粒子群算法為后續的變鄰域搜索提供了一個較好的初始解,并引導算法尋找更好的解;變鄰域搜索是集中鄰域搜索在搜索空間附近的較好解。從而提高了算法的全局搜索能力和局部搜索能力,平衡了算法在搜索過程中的普遍性和集中性。

3 實例分析

筆者根據某公司產品實際生產情況,選取3種不同需求的下料實例進行分析。

實例1:根據某公司生產的木家具產品實際情況,選取下料板材長度為230 cm、寬度為160 cm的單一規格的規則矩形板材,根據客戶需求,需要做3套成品,一共有6種毛坯零件的需求。

毛坯零件的具體尺寸和數量如表1所示。

表1 實例1毛坯零件數據Table 1 Data of panel parts in the example 1

經過計算得到利用粒子群算法的利用率是84.846%,利用變鄰域搜索算法的利用率是85.658%,粒子群混合變鄰域搜索算法的利用率為92.281%。3種算法具體的下料方案如圖4所示,下料都只消耗了1塊板材,雖然下料的利用率可以接受,但是從下料的方案中可以看出,前兩種下料方案仍有很大的改進空間。粒子群混合變鄰域搜索算法相比粒子群算法和變鄰域搜索算法的計算都有較大幅度的提升,且通過粒子群混合變鄰域搜索算法生成的具體下料方案可以看到,并沒有產生面積過大的廢料,剩下的余料仍然可以投入后續生產使用。

實例2:選取下料板材為單一規格的規則矩形木材板材,板材的長度為140 cm,寬度為90 cm,現在根據客戶要求,需要切割出9種毛坯零件,通過變鄰域搜索算法和粒子群算法計算出最優的下料方案。具體的毛坯零件的尺寸數量要求如表2所示。

表2 實例2毛坯零件數據Table 2 Panel parts data in the example 2

實例3:選取下料板材長度為230 cm、寬度為160 cm的單一規格的規則矩形板材,根據客戶需求,一共有12種毛坯零件的需求,具體的毛坯零件的尺寸和數量要求如表3所示。

表3 實例3毛坯零件數據Table 3 Panel parts data in the example 3

對于實例1、實例2和實例3同時用粒子群算法、變鄰域搜索算法和粒子群混合變鄰域搜索算法進行下料計算的結果對比如表4所示。

在表4中,通過粒子群算法和變鄰域搜索算法計算結果的對比可以看出,變鄰域搜索算法計算出的木材板材的利用率與粒子群算法相近,甚至有時會超過粒子群算法,說明變鄰域搜索算法也同樣適用于木材板材下料問題的求解。但沒有達到預期中的理想效果,仍有需要改進的地方。

通過粒子群算法與粒子群混合變鄰域搜索計算結果的對比可以看出,實例1利用率從84.846%提升到92.281%,實例2利用率從83.175%提升到91.244%,實例3從86.238%提升到92.245%,由改進后的粒子群算法計算出的木材板材利用率明顯比粒子群算法高出很多。粒子群混合變鄰域搜索算法不會受到規格數量的影響,計算出的利用率可以達到90%以上,同時也不會產生面積較大的廢料。這也充分證明了本研究提出的將變鄰域搜索算法的思想加入粒子群算法中,能夠有效解決粒子群算法容易早熟缺陷、局部搜索能力差的問題。

綜上所述,本研究3種算法中,最優異且適用的算法為粒子群混合變鄰域搜索算法,適合在家具等相關行業木材板材實際生產中進行下料計算,解決了木材板材加工過程中的原材料利用率不高的難題,給家具等相關行業帶來了實際的經濟效益。

4 結 語

本研究主要根據某公司生產的木家具產品將其轉化為單規格的二維矩形下料問題,并將其運用到該企業的生產實際中。在利用離散粒子群進行求解過程中,通過動態改變鄰域結構來改善粒子群算法容易陷入早熟的情況。該算法避免了粒子群算法易陷入局部最優解的問題,給變鄰域搜索算法提供了質量較高的初始解,加快了算法的收斂速度,使得結果趨于全局最優。為驗證算法的可靠性,根據公司生產實例,設計了3組基于利用率的試驗分析,通過3種不同的算法對矩形板材進行切割計算,以實例3為例,在選取長度為230 cm、寬度為160 cm的單一規格的規則矩形板材后,改進后的粒子群算法的利用率由86.238%提升為92.245%。實驗結果表明,粒子群混合變鄰域搜索算法可以有效地節約木材板材資源,提升企業經濟效益。