張 宇,郭保蘇

(燕山大學(xué)機(jī)械工程學(xué)院,河北 秦皇島 066004)

排樣問題又稱為下料問題或填充問題,其目標(biāo)是在材料切割過程中尋求一個(gè)較高的材料利用率[1]。對(duì)排樣問題的研究始于20世紀(jì)70年代,該問題主要是在現(xiàn)代加工制造業(yè)的發(fā)展和市場經(jīng)濟(jì)競爭下產(chǎn)生的[2]。隨著經(jīng)濟(jì)的發(fā)展和對(duì)資源需求的增長,提高原材料的利用率可有效節(jié)約資源和降低成本,同時(shí)自動(dòng)化排樣技術(shù)的應(yīng)用也有利于提高生產(chǎn)效率和降低人力成本,對(duì)企業(yè)的經(jīng)濟(jì)效益有著較大的影響。二維不規(guī)則排樣問題廣泛存在于機(jī)械制造、航空航天、船舶、汽車、服裝、家具等相關(guān)制造業(yè)的零件下料優(yōu)化過程中[3]。

因?yàn)橹圃鞓I(yè)產(chǎn)量巨大,并且不規(guī)則輪廓排樣問題在制造業(yè)中普遍存在,所以排樣效率的微小提高就可以產(chǎn)生巨大的經(jīng)濟(jì)效益。對(duì)社會(huì)來講,材料利用率的提高可以帶來巨大的環(huán)境效益[4]。以鋼材為例,2020年全世界粗鋼產(chǎn)量約為18.8億t,若利用率提高1%,則理論上可以減少0.188億t的鋼產(chǎn)量,按照噸鋼碳排放量為1.8 t計(jì)算,可以減少碳排放0.338億t。減少鋼產(chǎn)量還可以減少硫化物、氮氧化合物等污染物的排放,環(huán)境效益巨大。目前,實(shí)際生產(chǎn)中絕大部分的排樣是通過人工實(shí)現(xiàn)的,但人工排樣效率低、成本高,排樣質(zhì)量難以保證。實(shí)現(xiàn)排樣技術(shù)的自動(dòng)化、智能化能夠進(jìn)一步提高材料的利用率,有利于提高企業(yè)生產(chǎn)效率,降低人力和原材料成本,進(jìn)而提高企業(yè)市場競爭力[5]。綜上,研究二維不規(guī)則排樣問題,提高材料利用率,對(duì)社會(huì)和企業(yè)均具有巨大的現(xiàn)實(shí)意義。

二維不規(guī)則排樣屬于NP-Hard問題,即在多項(xiàng)式時(shí)間內(nèi)沒有辦法得到最優(yōu)解,也無法在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證其正確性[6]。目前二維不規(guī)則排樣問題的求解方法主要為數(shù)學(xué)規(guī)劃法與啟發(fā)式算法[7]。其中,數(shù)學(xué)規(guī)劃法求解精度高,但計(jì)算過程非常耗時(shí),不適用于實(shí)際工業(yè)生產(chǎn)中的大規(guī)模排樣問題;而啟發(fā)式算法可以在比較短的時(shí)間內(nèi)求得一個(gè)比較滿意的解[8]。因此,求解大規(guī)模排樣問題的方法均為啟發(fā)式算法。然而算法的性能直接影響排樣結(jié)果,所以設(shè)計(jì)一種優(yōu)秀的啟發(fā)式算法具有重要的實(shí)際意義。

二維不規(guī)則排樣問題作為典型的組合優(yōu)化問題,受到了眾多的學(xué)者和專家的關(guān)注。Sato等[9]使用模擬退火算法進(jìn)行排樣,搜索速度極快,但非常容易陷入局部最優(yōu)解。Mundim與Pinheiro等[10-11]使用遺傳算法進(jìn)行排樣,搜索優(yōu)質(zhì)解的能力較強(qiáng),但受參數(shù)與初始解的影響巨大,且搜索速度較慢。

針對(duì)以上問題,本文為了在排樣填充率滿足要求的前提下,盡可能使算法搜索速度加快,提出一種小生境離散粒子群算法。該算法具有粒子群算法搜索速度快的優(yōu)勢,并且融入了小生境思想,大大提高了全局搜索能力。

1 排樣問題數(shù)學(xué)模型

二維不規(guī)則排樣問題可描述為:將所有工件在滿足約束條件的前提下排入寬度一定、長度不限的母板,使工件在母板內(nèi)占用的長度最短。各變量定義見表1。

表1 變量定義表

數(shù)學(xué)模型定義如下:

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

minF=max{x|(x,y)∈ri,ri∈R}-

min{x|(x,y)∈ri,ri∈R}

(1)

約束條件:

ri∩rj=?i≠j

(2)

r∈R

(3)

Oi∈O

(4)

(5)

式中:r為任意零件,Oi為零件i的旋轉(zhuǎn)角分度。式(1)表示排樣目標(biāo)是盡可能使工件在母板中占用的區(qū)域長度最短,式(2)保證零件互不重疊,式(3)保證零件不超出母板區(qū)域,式(4)保證各零件旋轉(zhuǎn)角在分度范圍內(nèi),式(5)保證所有零件均排入母板。

2 小生境離散粒子群算法

2.1 基本粒子群算法

在粒子群算法中,每個(gè)粒子所處的位置都對(duì)應(yīng)問題的一個(gè)解。算法通過改變粒子位置來搜尋新的解[12]?；镜饺缦?

V′=w×V+c1×r1×(Pbest-X)+c2×r2×(Gbest-X)

(6)

X′=X+V

(7)

式中:V′為下一代粒子的速度,V為當(dāng)前粒子的速度,w為慣性權(quán)重,c1、c2為學(xué)習(xí)因子,r1、r2為介于(0,1)的隨機(jī)數(shù),Pbest與Gbest分別為粒子的個(gè)體最優(yōu)解和粒子群的全局最優(yōu)解,X′為下一代粒子的位置,X為當(dāng)前粒子的位置。根據(jù)式(6)與式(7)即可通過粒子當(dāng)前的速度與位置計(jì)算出下一代的速度與位置。

基本粒子群算法的運(yùn)行步驟如下:

Step1,初始化各粒子的位置X和速度V;

Step2,計(jì)算每個(gè)粒子的適應(yīng)度值;

Step3,對(duì)于每個(gè)粒子,比較它當(dāng)前解的適應(yīng)度值和它自身的歷史最優(yōu)解Pbest的適應(yīng)度值,并更新Pbest;

Step4,對(duì)于每個(gè)粒子,比較它當(dāng)前解的適應(yīng)度值和全體粒子的歷史最優(yōu)解Gbest的適應(yīng)度值,并更新Gbest;

Step5,根據(jù)式(6)和式(7)更新每個(gè)粒子的速度V和位置X;

Step6,如果滿足結(jié)束條件(解滿足要求或迭代次數(shù)達(dá)到最大),迭代結(jié)束,否則轉(zhuǎn)Step2。

2.2 離散粒子群算法

因?yàn)榕艠邮且环N典型的組合優(yōu)化問題,問題的解為零件的組合順序,所以基本粒子群算法并不能直接應(yīng)用于排樣問題,需要對(duì)其進(jìn)行改進(jìn)。本文通過引入交換子與交換序的概念將基本粒子群算法改進(jìn)為離散粒子群算法[13]。

1) 交換子。

設(shè)排樣問題的零件編號(hào)為i1～in,解的零件組合順序?yàn)閄=[i1,i2,…,in]。定義交換子V(1,2)為交換解X中i1和i2的位置,即解X與交換子V(1,2)相加后的新解為X′=X+V(1,2)=[i2,i1,…,in]。

2) 交換序。

由于算法每次迭代都會(huì)有很多零件的組合順序發(fā)生改變,而單一交換子并不能很好地表達(dá)零件組合順序的改變方式,因此本文將若干個(gè)交換子合并成一個(gè)交換序。計(jì)算新解時(shí),將當(dāng)前解與交換序中的各交換子依次相加。為了便于理解,這里以6個(gè)零件的組合為例。

當(dāng)前解:X=[i1,i2,i3,i4,i5,i6]

交換子:V1=(1,2),V2=(2,3),V3=(4,6)

交換序:V=(V1,V2,V3)

新解計(jì)算方式:X′=X+V=[i2,i3,i1,i6,i5,i4]

通過交換序?qū)玖Ｗ尤核惴ㄟM(jìn)行改進(jìn),得到離散粒子群算法,就可以對(duì)排樣問題進(jìn)行求解。而此算法也具備粒子群算法搜索效率高的特點(diǎn),能在令人滿意的時(shí)間內(nèi)求得排樣問題的解。

2.3 小生境離散粒子群算法

本文將小生境思想融入粒子群算法,其基本原理是將粒子群分為2個(gè)群體。2個(gè)群體分別迭代,每次迭代適應(yīng)度好的群體中適應(yīng)度差的粒子與適應(yīng)度差的群體中適應(yīng)度好的粒子交換位置。這樣操作的好處是不但能進(jìn)一步提高收斂速度,還能提高全局搜索能力。

首先,建立兩個(gè)相互獨(dú)立的種群A和B。種群中的每個(gè)個(gè)體分別代表該問題的一個(gè)解。每個(gè)解表示零件排入母板的一種順序。A、B的初始種群均為隨機(jī)生成。種群A中的一個(gè)解按照零件面積從大到小排序生成。隨機(jī)的初始種群保證了種群的多樣性,降低了陷入局部最優(yōu)解的可能。此外,種群A包含了人工排樣按照面積大小排序的經(jīng)驗(yàn),其本身就是一個(gè)較優(yōu)解,既保證了種群的解不會(huì)太差,也可以為種群的進(jìn)化方向提供指導(dǎo)。在種群迭代過程中,A、B兩個(gè)種群分別迭代。每迭代一次后,將種群A中適應(yīng)度最差的p%個(gè)體與種群B中適應(yīng)度最好的p%個(gè)體互換。p越大,種群A的收斂速度越快,但可能使種群B難以搜索到比較好的解。本文將p設(shè)為10,即每次迭代交換10%的個(gè)體。此算法不但提高了種群A的搜索效率,還通過種群B的并行迭代避免過早陷入局部最優(yōu)解。算法流程如圖1所示。

圖1 小生境離散粒子群算法流程

2.4 工件定位策略與個(gè)體適應(yīng)度計(jì)算

2.4.1定位策略

排樣問題的求解分為兩部分:定序策略與定位策略。在工件的排樣順序確定后,需要制定合理的定位策略將工件排入母板,即確定工件在母板中的位置。工件的定位則涉及到許多復(fù)雜的幾何計(jì)算,如工件之間的距離計(jì)算,碰撞、重疊判斷等。

為了準(zhǔn)確地判斷零件之間的位置關(guān)系,本文采用臨界多邊形(no fit polygon,NFP)[14]定位工件。此方法能夠精確地求出零件定位的可行區(qū)域。臨界多邊形的定義為:給定兩個(gè)多邊形A和B,其中多邊形A固定,將多邊形B繞多邊形A旋轉(zhuǎn)一周,多邊形B上的參考點(diǎn)移動(dòng)所形成的軌跡便是臨界多邊形,記為NFPAB[15],如圖2所示。

圖2 臨界多邊形

通過求解兩個(gè)多邊形之間的臨界多邊形,可以將多邊形之間的位置關(guān)系判斷轉(zhuǎn)化為環(huán)繞多邊形與臨界多邊形的位置關(guān)系判斷。當(dāng)參考點(diǎn)在臨界多邊形內(nèi)時(shí),多邊形A與B相互重疊[16];當(dāng)參考點(diǎn)在臨界多邊形上時(shí),多邊形A與B正好接觸但不重疊[17];當(dāng)參考點(diǎn)在臨界多邊形外時(shí),多邊形A與B相互分離[18]。因此,臨界多邊形不但簡化了零件之間的位置關(guān)系判斷,還提供了零件可能定位的位置[19]。為了使工件排布盡量緊密,本文將工件定位在臨界多邊形上的最低點(diǎn)。

2.4.2個(gè)體適應(yīng)度

排樣的目標(biāo)是使材料利用率達(dá)到最大化。因此,為了更好地表示排樣方案的效果,且使計(jì)算過程盡量簡單,定義如式(1)所示適應(yīng)度函數(shù)。

工件在母板中占用的長度越短,則代表材料利用率越高,如圖3所示。圖3中:Lmax(Xi)為零件在母板中占用的長度,W為母板的寬度。

圖3 母板占用長度

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證本文算法的效果,采用Python編程語言實(shí)現(xiàn)了本文的方法,并與經(jīng)典的模擬退火算法、遺傳算法、粒子群算法做對(duì)比。實(shí)驗(yàn)數(shù)據(jù)來源于歐洲排樣興趣小組ESICUP(https://www.euro-online.org/websites/esicup/)。為了更好地驗(yàn)證本文方法在實(shí)際生產(chǎn)中的效果,選擇5組零件數(shù)量較多的數(shù)據(jù)集作為實(shí)驗(yàn)樣本。實(shí)驗(yàn)采用材料利用率ρ作為算法優(yōu)劣的評(píng)判標(biāo)準(zhǔn),計(jì)算公式如下:

(8)

式中:si表示編號(hào)為i的工件面積。

小生境離散粒子群算法的參數(shù)設(shè)置見表2。

表2 小生境離散粒子群算法設(shè)置

3.2 實(shí)驗(yàn)結(jié)果

按照實(shí)驗(yàn)設(shè)計(jì),針對(duì)5組實(shí)驗(yàn)數(shù)據(jù)做了對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果見表3。

表3 實(shí)驗(yàn)結(jié)果

從表中可以看出,在材料利用率方面,小生境離散粒子群算法對(duì)于所有數(shù)據(jù)集均最高,粒子群算法與遺傳算法各有千秋,模擬退火算法最低;在運(yùn)行時(shí)間方面,小生境離散粒子群算法與粒子群算法相差不大,遺傳算法時(shí)間最長,模擬退火算法時(shí)間最短。小生境離散粒子群算法在各數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 排樣結(jié)果

3.3 結(jié)果分析

對(duì)小生境離散粒子群算法與其他算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較,見表4。

表4 實(shí)驗(yàn)結(jié)果對(duì)比

通過表4可以看出,小生境離散粒子群算法相比其他算法在材料利用率上均具有優(yōu)勢。小生境離散粒子群算法的運(yùn)行時(shí)間與粒子群算法相差不大,遠(yuǎn)低于遺傳算法,略高于模擬退火算法。在實(shí)際生產(chǎn)中,排樣算法的評(píng)價(jià)標(biāo)準(zhǔn)主要為材料利用率,故而小生境離散粒子群算法具有很大的優(yōu)勢。

4 結(jié)束語

二維不規(guī)則排樣問題廣泛存在于工業(yè)生產(chǎn)中。在ESICUP數(shù)據(jù)集上的實(shí)驗(yàn)表明,本文提出的基于小生境離散粒子群算法的不規(guī)則排樣優(yōu)化策略能夠有效解決二維不規(guī)則排樣問題,且具有很高的材料利用率。此外,該算法通過兩個(gè)種群并行運(yùn)算來提高全局搜索能力的方式在處理其他問題時(shí)也具有借鑒意義。本文提出的算法中有一些參數(shù)需要配置,且這些參數(shù)對(duì)算法性能有一定的影響,而目前參數(shù)是根據(jù)經(jīng)驗(yàn)人工配置的。因此,后續(xù)工作的重點(diǎn)是設(shè)計(jì)一種合理的參數(shù)配置方法,實(shí)現(xiàn)自動(dòng)配置參數(shù),提高算法的自動(dòng)化水平。