基于改進(jìn)粒子群算法的木材板材下料方法

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

(南京林業(yè)大學(xué)機(jī)械電子工程學(xué)院,南京 210037)

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

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

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

1 數(shù)學(xué)模型的建立

本研究所采用的原材料板材為L(zhǎng)×W的矩形木材板材,待切割的毛坯零件一共有K種。在充分考慮多方面因素和約束的前提下,選擇以剩余廢料最少為優(yōu)化目的,得出數(shù)學(xué)模型如下[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分別為原材料板材的長(zhǎng)度和寬度;l和w分別為零件板材的長(zhǎng)度和寬度;i和K分別為零件類(lèi)型編號(hào)和集合,i∈K;N為原材料板材的數(shù)量;Cj為j張單板上排放零件數(shù)量;(Xk,Yk)為每個(gè)矩形零件對(duì)應(yīng)左下角的坐標(biāo),k∈Cj;Pk為矩形零件在原材料中的排列方式;Rk為零件所在矩形的命名;ni為第i類(lèi)零件的數(shù)量;Aij為在第j張單板方案中第i種零件的數(shù)量,且Aij≤ni;Tj為第j種方式的切割次數(shù),j∈N,Tj≥1;F為目標(biāo)函數(shù)。

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

2 算法求解

2.1 粒子群算法

粒子群算法也稱(chēng)作粒子群優(yōu)化算法(particle swarm optimization,PSO),是1995年美國(guó)Kennedy等[13]通過(guò)對(duì)鳥(niǎo)類(lèi)群體行為進(jìn)行模仿提出的一種進(jìn)化算法(evolutionary algorithm,EA)。粒子群算法通常用于解決連續(xù)優(yōu)化問(wèn)題,將其應(yīng)用于排樣問(wèn)題中的排列組合問(wèn)題,需要對(duì)粒子群算法進(jìn)行一定的調(diào)整[14-15]。

2.1.1 編 碼

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

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

(10)

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

2.1.2 粒子速度

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

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

V=X2-X1

(11)

式中,速度V中的每個(gè)元素vi表示為X2和X1在序列上對(duì)應(yīng)的元素的對(duì)比。當(dāng)X1的元素與X2相同時(shí)速度V上的元素記錄為0,當(dāng)X1的元素與X2不相同時(shí)速度V上的元素記錄為X2的元素,具體可表示為:

(12)

排列優(yōu)化問(wèn)題中,位置與速度的加法運(yùn)算可表示為:

X=X1+V1

(13)

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

(14)

粒子的運(yùn)動(dòng)方程具體描述如下:

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

(15)

式中,速度的數(shù)乘方式具有概率意義,它可以增強(qiáng)計(jì)算的隨機(jī)性。在計(jì)算過(guò)程中生成一個(gè)隨機(jī)數(shù),通過(guò)數(shù)值的比較確定速度值。

(16)

2.1.3 目標(biāo)函數(shù)

矩形排樣問(wèn)題的目標(biāo)是在一個(gè)給定規(guī)格的矩形板材上,按照某種排列順序擺放零件,從而最大化板材的利用率。在粒子群算法中,將編碼數(shù)值作為排樣順序,將位置編碼下產(chǎn)生的排樣利用率作為目標(biāo)。

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

(17)

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

2.1.4 粒子群算法流程

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

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

1)粒子群狀態(tài)進(jìn)行重置。

2)對(duì)粒子的適應(yīng)度值Fit[i]進(jìn)行計(jì)算。

3)個(gè)體極值pbest(i)比較,當(dāng)Fit[i]>pbest(i)時(shí),Fit[i]替換掉pbest(i)。

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

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

6)判斷是否滿(mǎn)足結(jié)束條件(誤差足夠好或者達(dá)到最大循環(huán)次數(shù)),若滿(mǎn)足,則算法結(jié)束并輸出最優(yōu)結(jié)果;若不滿(mǎn)足,則返回2)。

2.2 變鄰域搜索算法

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

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

1)初始化。給定一個(gè)初始解S,并定義一系列鄰域結(jié)構(gòu)NK,K=1,2,…,Kmax。

2)令K=1。

3)把定義的初始解S作為當(dāng)前解,在當(dāng)前鄰域NK內(nèi)進(jìn)行局部搜索獲得該鄰域的最優(yōu)解S1。

4)若S1優(yōu)于S,就用S1替換掉當(dāng)前解S,跳回2);若不優(yōu)于S,就令K=K+1。

5)若K>Kmax,就直接輸出最優(yōu)解,結(jié)束;若K

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

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

本研究根據(jù)排樣需要采用混合性鄰域結(jié)構(gòu)的變鄰域搜索策略[22]。其基本步驟如下:

1)初始化。選擇初始解x,鄰域結(jié)構(gòu)N(i),i=1,2,…,k,當(dāng)前最優(yōu)解xbest=x。

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

3)如果i=k+1,那么就跳轉(zhuǎn)步驟2);否則,在x的鄰域結(jié)構(gòu)N(i)中隨機(jī)選取可行解x′,在x′的鄰域結(jié)構(gòu)中搜索得到局部最優(yōu)解x″,若x″比當(dāng)前最優(yōu)解xbest更優(yōu),則xbest=x″,i=i+1。循環(huán)這步操作。

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

通過(guò)分析粒子群與變鄰域搜索算法結(jié)構(gòu)及試驗(yàn)結(jié)果,發(fā)現(xiàn)粒子群算法和變鄰域搜索算法均有各自的優(yōu)點(diǎn)和不足。

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

粒子群算法收斂速度較快,全局搜索能力較好,主要通過(guò)粒子不斷向最優(yōu)解靠近,可以較快地在很大的解空間中找到具有最優(yōu)解的大致范圍。這正好可以彌補(bǔ)變鄰域搜索算法收斂速度慢、搜索時(shí)間長(zhǎng)的缺點(diǎn),可以給變鄰域搜索的開(kāi)始提供一個(gè)高質(zhì)量的初始解。

為了克服粒子群算法可能產(chǎn)生早熟的現(xiàn)象,考慮到粒子群算法中粒子每次更新都會(huì)受到當(dāng)前解、個(gè)體歷史最優(yōu)解和種群歷史最優(yōu)解3個(gè)因素的影響,本研究將粒子的更新過(guò)程采用變鄰域搜索,動(dòng)態(tài)地改變鄰域結(jié)構(gòu)來(lái)拓展搜索的空間,使算法最終能夠跳出局部最優(yōu)解,搜索到全局最優(yōu)解。

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

1)對(duì)粒子群狀態(tài)進(jìn)行重置。

2)對(duì)粒子的適應(yīng)度值Fit[i]進(jìn)行計(jì)算。

3)個(gè)體極值pbest(i)比較,當(dāng)Fit[i]>pbest(i)時(shí),Fit[i]替換掉pbest(i)。

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

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

6)判斷是否滿(mǎn)足結(jié)束條件(誤差足夠好或者達(dá)到最大循環(huán)次數(shù)),若滿(mǎn)足,則算法結(jié)束并輸出最優(yōu)結(jié)果;若不滿(mǎn)足,則返回2)。

7)對(duì)粒子進(jìn)行調(diào)用變鄰域搜索,主要的搜索策略是:順序執(zhí)行各個(gè)模塊,一旦出現(xiàn)比當(dāng)前更優(yōu)秀的中間解,就用中間解代替當(dāng)前解,繼續(xù)調(diào)用這個(gè)模塊進(jìn)行搜索,直到搜索發(fā)現(xiàn)更差的中間解出現(xiàn);否則執(zhí)行下一模塊直到結(jié)束。

8)判斷是否滿(mǎn)足結(jié)束條件K

9)輸出全局最優(yōu)值,算法運(yùn)行結(jié)束。

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

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

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

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

3 實(shí)例分析

筆者根據(jù)某公司產(chǎn)品實(shí)際生產(chǎn)情況,選取3種不同需求的下料實(shí)例進(jìn)行分析。

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

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

表1 實(shí)例1毛坯零件數(shù)據(jù)Table 1 Data of panel parts in the example 1

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

實(shí)例2:選取下料板材為單一規(guī)格的規(guī)則矩形木材板材,板材的長(zhǎng)度為140 cm,寬度為90 cm,現(xiàn)在根據(jù)客戶(hù)要求,需要切割出9種毛坯零件,通過(guò)變鄰域搜索算法和粒子群算法計(jì)算出最優(yōu)的下料方案。具體的毛坯零件的尺寸數(shù)量要求如表2所示。

表2 實(shí)例2毛坯零件數(shù)據(jù)Table 2 Panel parts data in the example 2

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

表3 實(shí)例3毛坯零件數(shù)據(jù)Table 3 Panel parts data in the example 3

對(duì)于實(shí)例1、實(shí)例2和實(shí)例3同時(shí)用粒子群算法、變鄰域搜索算法和粒子群混合變鄰域搜索算法進(jìn)行下料計(jì)算的結(jié)果對(duì)比如表4所示。

在表4中,通過(guò)粒子群算法和變鄰域搜索算法計(jì)算結(jié)果的對(duì)比可以看出,變鄰域搜索算法計(jì)算出的木材板材的利用率與粒子群算法相近,甚至有時(shí)會(huì)超過(guò)粒子群算法,說(shuō)明變鄰域搜索算法也同樣適用于木材板材下料問(wèn)題的求解。但沒(méi)有達(dá)到預(yù)期中的理想效果,仍有需要改進(jìn)的地方。

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

綜上所述,本研究3種算法中,最優(yōu)異且適用的算法為粒子群混合變鄰域搜索算法,適合在家具等相關(guān)行業(yè)木材板材實(shí)際生產(chǎn)中進(jìn)行下料計(jì)算,解決了木材板材加工過(guò)程中的原材料利用率不高的難題,給家具等相關(guān)行業(yè)帶來(lái)了實(shí)際的經(jīng)濟(jì)效益。

4 結(jié) 語(yǔ)

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