基于小生境離散粒子群算法的不規則排樣優化策略

張 宇,郭保蘇

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

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

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

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

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

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

1 排樣問題數學模型

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

表1 變量定義表

數學模型定義如下:

目標函數:

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的旋轉角分度。式(1)表示排樣目標是盡可能使工件在母板中占用的區域長度最短,式(2)保證零件互不重疊,式(3)保證零件不超出母板區域,式(4)保證各零件旋轉角在分度范圍內,式(5)保證所有零件均排入母板。

2 小生境離散粒子群算法

2.1 基本粒子群算法

在粒子群算法中,每個粒子所處的位置都對應問題的一個解。算法通過改變粒子位置來搜尋新的解[12]。基本迭代公式如下:

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

(6)

X′=X+V

(7)

式中:V′為下一代粒子的速度,V為當前粒子的速度,w為慣性權重,c1、c2為學習因子,r1、r2為介于(0,1)的隨機數,Pbest與Gbest分別為粒子的個體最優解和粒子群的全局最優解,X′為下一代粒子的位置,X為當前粒子的位置。根據式(6)與式(7)即可通過粒子當前的速度與位置計算出下一代的速度與位置。

基本粒子群算法的運行步驟如下:

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

Step2,計算每個粒子的適應度值;

Step3,對于每個粒子,比較它當前解的適應度值和它自身的歷史最優解Pbest的適應度值,并更新Pbest;

Step4,對于每個粒子,比較它當前解的適應度值和全體粒子的歷史最優解Gbest的適應度值,并更新Gbest;

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

Step6,如果滿足結束條件(解滿足要求或迭代次數達到最大),迭代結束,否則轉Step2。

2.2 離散粒子群算法

因為排樣是一種典型的組合優化問題,問題的解為零件的組合順序,所以基本粒子群算法并不能直接應用于排樣問題,需要對其進行改進。本文通過引入交換子與交換序的概念將基本粒子群算法改進為離散粒子群算法[13]。

1) 交換子。

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

2) 交換序。

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

當前解:X=[i1,i2,i3,i4,i5,i6]

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

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

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

通過交換序對基本粒子群算法進行改進,得到離散粒子群算法,就可以對排樣問題進行求解。而此算法也具備粒子群算法搜索效率高的特點,能在令人滿意的時間內求得排樣問題的解。

2.3 小生境離散粒子群算法

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

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

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

2.4 工件定位策略與個體適應度計算

2.4.1定位策略

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

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

圖2 臨界多邊形

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

2.4.2個體適應度

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

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

圖3 母板占用長度

3 實驗與分析

3.1 實驗設計

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

(8)

式中:si表示編號為i的工件面積。

小生境離散粒子群算法的參數設置見表2。

表2 小生境離散粒子群算法設置

3.2 實驗結果

按照實驗設計,針對5組實驗數據做了對比實驗,實驗結果見表3。

表3 實驗結果

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

圖4 排樣結果

3.3 結果分析

對小生境離散粒子群算法與其他算法的實驗結果進行比較,見表4。

表4 實驗結果對比

通過表4可以看出,小生境離散粒子群算法相比其他算法在材料利用率上均具有優勢。小生境離散粒子群算法的運行時間與粒子群算法相差不大,遠低于遺傳算法,略高于模擬退火算法。在實際生產中,排樣算法的評價標準主要為材料利用率,故而小生境離散粒子群算法具有很大的優勢。

4 結束語

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