閆嘉， 李林峰， 林毓培， 段書凱

1. 西南大學(xué) 人工智能學(xué)院，重慶 400715；2. 智能傳動(dòng)和控制國(guó)家地方聯(lián)合工程研究中心(重慶)，重慶 400715

隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展, 汽車制造業(yè)逐漸從傳統(tǒng)制造向智能制造轉(zhuǎn)型． 汽車智能制造的關(guān)鍵環(huán)節(jié)包括汽車零件下料, 也稱為排樣, 是指將一系列不規(guī)則多邊形零件不重疊地排放在給定的原板材上, 目標(biāo)是使板材利用率達(dá)到最高, 當(dāng)給定的原板材是定寬無限長(zhǎng)板材時(shí), 該排樣又稱為二維不規(guī)則排樣, 此問題屬于NP-HARD問題． 原始材料的利用率對(duì)企業(yè)的市場(chǎng)競(jìng)爭(zhēng)和經(jīng)濟(jì)效益有很大影響, 特別是在全球自然資源有限的情況下, 最大程度地節(jié)約資源, 確保企業(yè)可持續(xù)發(fā)展顯得至關(guān)重要． 因此, 該問題長(zhǎng)期受到國(guó)內(nèi)外研究人員的關(guān)注．

汽車零件排樣屬于二維不規(guī)則排樣范疇, 因此和傳統(tǒng)二維不規(guī)則排樣一樣, 明確待排零件的排樣策略與排放次序是解決汽車零件排樣問題的關(guān)鍵． 排樣策略有“底左”策略[1]、 “重心最低”策略[2]、 “混合定位”策略[3]等． 確定定位策略后, 問題就轉(zhuǎn)化為所有待排零件排放順序優(yōu)化問題． 目前國(guó)內(nèi)外大量文獻(xiàn)都將排樣算法與智能優(yōu)化算法相結(jié)合解決排樣次序優(yōu)化問題． 湯德估等人[4]提出GEFHNA排樣方法結(jié)合遺傳算法和禁忌搜索算法優(yōu)化排樣順序, 選取ESICUP網(wǎng)站的通用數(shù)據(jù)集進(jìn)行實(shí)驗(yàn), 仿真結(jié)果明顯優(yōu)于原始的GEFHNA排樣方法; 劉海明等人[5]提出小生境遺傳算法來求解二維不規(guī)則排樣問題, 在遺傳算法中引入排擠原理的小生境策略, 改善了遺傳算法的早熟現(xiàn)象; 楊衛(wèi)波等人[6]首次將實(shí)數(shù)編碼的量子進(jìn)化算法與不規(guī)則排樣問題相結(jié)合, 為不規(guī)則排樣問題的求解提供了新思路; 王靜靜等人[7]提出并行交叉遺傳算法求解二維不規(guī)則排樣, 該算法構(gòu)造兩個(gè)種群進(jìn)行雜交進(jìn)化, 同樣改善了遺傳算法的早熟現(xiàn)象; Burke等人[8]提出了一種改進(jìn)型“底左”填充算法來解決傳統(tǒng)“底左”算法的缺陷, 并將其與爬山算法以及禁忌搜索算法相結(jié)合, 對(duì)26個(gè)通用數(shù)據(jù)集進(jìn)行了測(cè)試, 表現(xiàn)出更好的排樣性能; Rao等人[9]提出了混合分支限界禁忌搜索方法求解二維不規(guī)則排樣問題, 該算法將分支限界搜索的全局尋優(yōu)能力和禁忌搜索算法的局部尋優(yōu)能力結(jié)合, 彌補(bǔ)兩種算法的缺陷; Shalaby等人[10]使用基于實(shí)數(shù)編碼的粒子群優(yōu)化算法優(yōu)化多邊形的排放次序, 改善了以往十進(jìn)制離散編碼容易早熟的現(xiàn)象． 然而, 現(xiàn)有文獻(xiàn)中用于求解二維不規(guī)則排樣問題的優(yōu)化算法大都有一定的缺陷, 例如遺傳算法容易早熟并且局部尋優(yōu)能力差, 模擬退火算法全局尋優(yōu)能力較差等． 雖然后續(xù)論文在原有算法基礎(chǔ)上進(jìn)行了一定的改進(jìn), 但是效果并不明顯, 并且大多數(shù)文獻(xiàn)的實(shí)驗(yàn)都是選用ESICUP網(wǎng)站提供的通用數(shù)據(jù)集進(jìn)行算法驗(yàn)證, 并沒有針對(duì)具體應(yīng)用進(jìn)行實(shí)際效果測(cè)試, 利用改進(jìn)智能優(yōu)化算法對(duì)實(shí)際汽車零件排樣進(jìn)行研究, 國(guó)內(nèi)還未見相關(guān)文獻(xiàn)報(bào)道．

二維不規(guī)則排樣過程涉及大量多邊形重疊計(jì)算以及靠接位置計(jì)算, 現(xiàn)有多邊形重疊檢測(cè)算法的時(shí)間復(fù)雜度為O((M+N)log(M+N)), 其中N和M為兩多邊形的邊數(shù)． 為了提高算法的運(yùn)行效率, 有學(xué)者提出了臨界多邊形[11]的概念, 排樣過程采用臨界多邊形模型可以省略重疊計(jì)算, 還可以提供待排零件所有可能的靠接位置． 基于上述分析, 本文提出一種改進(jìn)的免疫遺傳算法, 優(yōu)化零件排放次序, 使用臨界多邊形作為工具計(jì)算待排零件所有靠接位置進(jìn)而基于“底左”策略選擇排放點(diǎn)． 算法驗(yàn)證方面首先使用ESICUP網(wǎng)站提供的通用數(shù)據(jù)集測(cè)試, 然后使用汽車生產(chǎn)廠商提供的實(shí)際汽車零件進(jìn)行排樣測(cè)試．

1 二維不規(guī)則排樣的數(shù)學(xué)模型

二維不規(guī)則排樣要保證零件與零件不重疊、 零件不超出原材料標(biāo)示范圍． 本文研究的是二維矩形帶排樣問題, 即原材料定寬無限長(zhǎng)． 假設(shè)待排零件集合為P={p1,p2, …,pn},n為零件數(shù),pi表示第i個(gè)零件,O為允許的旋轉(zhuǎn)角度集合, 結(jié)合二維不規(guī)則帶排樣的目標(biāo)及約束給出二維不規(guī)則條帶排樣的數(shù)學(xué)模型如式(1)所示:

minL=max{x|(x,y)∈pi(oi)}-min{x|(x,y)∈pi(oi)}, 1≤i≤n

st:pi,pj∈P,pi(oi)∩pj(oj)=?, 1≤i

pi(oi)?C(W,L), 1≤i≤n

oi∈O, 1≤i≤n

(1)

式(1)中優(yōu)化目標(biāo)L為原材料長(zhǎng)度, 即尋找一種排樣方案使得L最小; (x,y)表示零件二維坐標(biāo)點(diǎn);pi(oi)表示零件pi按角度oi進(jìn)行順時(shí)針旋轉(zhuǎn)以后的坐標(biāo)點(diǎn)集合;C(W,L)指原材料表示的坐標(biāo)范圍;W為原材料的寬度; 約束條件中pi(oi) ∩pj(oj)=?保證零件之間不重疊,pi(oi)?C(W,L)保證零件被排放在原材料內(nèi)．

2 基于重心臨界多邊形的BL排樣策略

2.1 臨界多邊形

臨界多邊形(No Fit Polygon, NFP)[11]: 給定多邊形Pi,Pj,Pi靜止, 選Pj邊上或內(nèi)部點(diǎn)作參考點(diǎn), 將Pj不旋轉(zhuǎn)地繞Pi滑動(dòng)一周, 滑動(dòng)過程Pj始終與Pi相切,Pj上的參考點(diǎn)所形成的軌跡叫做Pj相對(duì)于Pi的臨界多邊形, 記為NFP(Pi,Pj)． 如圖1,xj為Pj的參考點(diǎn):

圖1 臨界多邊形示意圖

NFP有如下重要特性: 選取Pj的參考點(diǎn)在臨界多邊形內(nèi)部時(shí)多邊形Pi和Pj重疊; 選取Pj的參考點(diǎn)在NFP邊上時(shí)多變形Pi和Pj相切但不重疊; 選取Pj的參考點(diǎn)在NFP外部時(shí)多邊形Pi和Pj處于相離狀態(tài)．

內(nèi)靠接矩形(Inner Fit Rectangle, IFR)[12]: 指多邊形Pi在矩形C內(nèi)部滑動(dòng)過程參考點(diǎn)形成的軌跡, 滑動(dòng)過程中也要滿足兩多邊形邊不相交, 如圖2所示:

圖2 內(nèi)靠接矩形IFR示意圖

依靠NFP與IFR可以計(jì)算待排零件在板材內(nèi)部的所有靠接位置, 假設(shè)P1,P2, …,Pi-1為已排零件, 當(dāng)前待排零件為Pi, 原材料為矩形C, 具體算法步驟如下:

步驟1 計(jì)算Pi與P1,P2, …,Pi-1的臨界多邊形, 記為NFP1,i,NFP2,i, …,NFPi-1,i;

步驟2 計(jì)算Pi與C的內(nèi)靠接矩形, 記為IFRi;

步驟3 計(jì)算NFP1,i∪NFP2,i∪…∪NFPi-1,i, 并集記為UnionNFP;

步驟4 計(jì)算IFRi-UnionNFP, 差集多邊形記為Dif,Dif邊上點(diǎn)都是Pi的可排放位置．

計(jì)算示意圖如圖3所示, 假設(shè)待排零件為三角形, 選取三角形的重心作為參考點(diǎn), 已排零件為兩個(gè)正八邊形, 灰色區(qū)域即為差集多邊形, 邊上所有點(diǎn)即為待排零件的可排放點(diǎn)．

圖3 待排零件靠接位置計(jì)算示意圖

上述算法省去了零件之間的重疊計(jì)算, 只需將待排零件的參考點(diǎn)移動(dòng)到差集多邊形上某一點(diǎn)即可, 排放就簡(jiǎn)化為基于差集多邊形的定位選優(yōu)過程． 基于該算法, 如果較大零件之間產(chǎn)生孔洞, 后續(xù)面積較小的零件還可以填充該孔洞．

2.2 通過GNFP和GIFR選取BL排樣點(diǎn)

重心臨界多邊形(Grivaty-NFP, GNFP)指選取滑動(dòng)多邊形的重心作為參考點(diǎn)構(gòu)造的臨界多邊形． 同樣, 重心內(nèi)靠接矩形(Grivaty-IFR, GIFR)的構(gòu)造也選取滑動(dòng)多邊形重心作為參考點(diǎn)． 在多邊形定位算法中, 應(yīng)用最多、 最廣泛的是“底左(Bottom-Left, BL)”[1]定位算法, 其基本思想是將待排零件盡量往板材的最左最下角排放． 采用GNFP與GIFR模型計(jì)算排樣點(diǎn)后, 將待排零件放到最左最下位置, 可以保證零件的重心位置最低． 零件的重心位置越低, 越有利于降低整體排樣方案的重心位置, 從而有利于提高面積分布密度, 提高原板材的利用率． 降低每個(gè)零件重心位置還可以使剩余板材的邊界較為平緩, 有利于后續(xù)零件的放置．

3 改進(jìn)免疫遺傳算法設(shè)計(jì)

遺傳算法(Genetic Algorithm, GA)[13]是一種模擬自然界物種遺傳進(jìn)化機(jī)理的算法, 具有很強(qiáng)的全局尋優(yōu)能力, 但是局部尋優(yōu)能力較差． 免疫算法(Immune Algorithm, IA)[14]是受人體免疫學(xué)原理啟發(fā)而提出的, 該算法通過免疫選擇、 克隆及變異操作實(shí)現(xiàn)對(duì)解空間的局部搜索, 因此具有很強(qiáng)的局部尋優(yōu)能力． 若將兩種算法結(jié)合, 既可以繼承遺傳算法的全局尋優(yōu)能力, 又可以兼顧免疫算法的局部尋優(yōu)能力．

3.1 自適應(yīng)遺傳算法設(shè)計(jì)

遺傳算法應(yīng)用于二維不規(guī)則排樣問題容易產(chǎn)生早熟現(xiàn)象, 算法運(yùn)行初期種群個(gè)體容易變得極為相似, 這時(shí)交叉操作很難改變個(gè)體基因順序, 而變異概率往往取值很小, 導(dǎo)致算法停滯． 文獻(xiàn)[15]通過自適應(yīng)調(diào)整遺傳算法步驟, 以及交叉、 變異概率, 有效避免了遺傳算法產(chǎn)生早熟現(xiàn)象． 本文改進(jìn)簡(jiǎn)化文獻(xiàn)[15]的算法過程, 在每次迭代進(jìn)行交叉變異前根據(jù)平均適應(yīng)度favg與最好適應(yīng)度fbest的比值與δ的關(guān)系(δ一般取(0.9, 1))修訂相關(guān)操作及參數(shù), 如果比值小于δ, 說明種群個(gè)體比較分散, 則按傳統(tǒng)遺傳算法步驟先交叉再變異, 如果比值大于等于δ, 說明種群比較集中, 交叉操作不易產(chǎn)生較大改變, 這時(shí)增大變異概率, 讓變異概率等于交叉概率, 先進(jìn)行變異再進(jìn)行交叉, 可以幫助種群跳出局部解．

3.2 改進(jìn)選擇操作

個(gè)體濃度表征種群多樣性． 個(gè)體濃度偏高意味種群中相似個(gè)體較多, 種群會(huì)集中在某一區(qū)間, 不利于全局搜索, 因此算法應(yīng)對(duì)濃度過高的個(gè)體進(jìn)行抑制, 保證種群多樣性． 個(gè)體濃度一般定義為:

(2)

D(pi)表示第i個(gè)個(gè)體的濃度;N為種群規(guī)模;s(pi,pj)表明個(gè)體pi與pj之間是否相似, 相似取值為1, 否則取值為0． 具體公式如下:

(3)

a(pi,pj)表示個(gè)體pi與個(gè)體pj的相似度;δs為相似度閾值;d為解的維度;pik為pi的第k維度． 個(gè)體之間相似度計(jì)算根據(jù)個(gè)體編碼方式不同采用不同的計(jì)算方式． 本文個(gè)體采用十進(jìn)制順序編碼, 所以采用基于海明距離[16]的計(jì)算方法． 綜合考慮適應(yīng)度和濃度, 計(jì)算種群所有個(gè)體激勵(lì)度的方法如下:

S(pi)=αF(pi)+βD(pi)

(4)

S(pi)為個(gè)體pi的激勵(lì)度;F(pi)為pi的適應(yīng)度;α和β為權(quán)重系數(shù), 滿足α+β=1, 用于調(diào)節(jié)個(gè)體適應(yīng)度和濃度對(duì)激勵(lì)度的影響． 進(jìn)行選擇操作時(shí), 根據(jù)種群個(gè)體激勵(lì)度進(jìn)行選擇可以有效保證種群的多樣性．

3.3 自適應(yīng)免疫選擇與克隆

人工免疫算法免疫選擇操作需要選擇種群中的個(gè)體進(jìn)行克隆, 假設(shè)每次迭代選擇的個(gè)體數(shù)N固定, 如果N取值較大會(huì)影響算法的運(yùn)行效率, 取值較小會(huì)影響算法的收斂精度． 所以N的取值很關(guān)鍵, 本文通過自適應(yīng)調(diào)整N的取值來確保算法的效率以及精度, 具體公式如下:

(5)

(6)

Savg(G)為第G代種群平均激勵(lì)度;SG(pi)為第G代個(gè)體pi激勵(lì)度;n表示種群規(guī)模;M(G)表示克隆選擇出的個(gè)體集合．

選擇出的個(gè)體需要進(jìn)行克隆操作, 假設(shè)每個(gè)個(gè)體復(fù)制出Nc份, 同樣Nc取值太大影響算法運(yùn)行效率, 取值太小影響收斂精度． 通過自適應(yīng)調(diào)整Nc的值能夠提高算法的運(yùn)行效率, 具體公式如下:

(7)

C(pj)為個(gè)體pj克隆出的個(gè)體數(shù);ω為克隆系數(shù);CL免疫選擇的個(gè)體數(shù);int()表示向上取整操作．

3.4 改進(jìn)免疫遺傳算法步驟

基于以上分析, 本文使用的改進(jìn)免疫遺傳算法(IGAA)具體步驟如下:

步驟1 設(shè)置參數(shù), 初始化種群, 計(jì)算初始種群的適應(yīng)度;

步驟2 判斷是否滿足終止條件, 若滿足輸出最優(yōu)解并停止迭代, 否則執(zhí)行步驟3;

步驟3 計(jì)算種群平均與最高適應(yīng)度favg,fbest, 如果favg/fbest≤δ, 則執(zhí)行步驟4, 否則執(zhí)行步驟5;

步驟4 種群進(jìn)行交叉變異操作, 計(jì)算子代適應(yīng)度、 濃度, 根據(jù)式(4)選擇產(chǎn)生新一代種群;

步驟5 臨時(shí)調(diào)整變異概率等于交叉概率, 種群進(jìn)行變異交叉操作, 計(jì)算子代適應(yīng)度、 濃度, 根據(jù)式(4)選擇產(chǎn)生新一代種群;

步驟6 根據(jù)式(5)(6)計(jì)算免疫選擇操作需要選擇出的個(gè)體數(shù)量, 并進(jìn)行免疫選擇操作;

步驟7 根據(jù)式(7)計(jì)算經(jīng)免疫選擇的個(gè)體需要復(fù)制出的數(shù)量, 并進(jìn)行克隆操作;

步驟8 將步驟7中復(fù)制出的個(gè)體進(jìn)行變異操作;

步驟9 克隆抑制操作, 計(jì)算步驟8中變異后每個(gè)個(gè)體的適應(yīng)度, 保留適應(yīng)度最高的克隆變異個(gè)體, 如果其適應(yīng)度比原克隆體適應(yīng)度高就進(jìn)行替換． 否則不替換, 并轉(zhuǎn)步驟2．

4 優(yōu)化二維不規(guī)則排樣的免疫遺傳算法設(shè)計(jì)

4.1 編碼方法

優(yōu)化算法首要解決的問題是個(gè)體的編碼問題, 本文采用十進(jìn)制順序編碼, 例如某個(gè)體編碼: [(1, 90), (2, 90), (3, 180), (4, 0), (5, 90)], 每一個(gè)基因由兩位組成, 第一位表示零件編號(hào), 第二位表示對(duì)應(yīng)零件的旋轉(zhuǎn)角度．

4.2 交叉算子

本文采用順序循環(huán)交叉: 兩個(gè)父輩個(gè)體P1,P2交叉產(chǎn)生子代個(gè)體Son1,Son2, 先生成隨機(jī)數(shù)pos1,pos2,P1,P2個(gè)體[pos1,pos2]之間的基因不變． 以Son1為例進(jìn)行說明: 遍歷P2個(gè)體的基因, 并賦給P1的[0,pos1)和(pos2,N), 遍歷過程中若P2的基因已經(jīng)在P1的[pos1,pos2]之間出現(xiàn)則直接跳轉(zhuǎn)到P2的下一位,Son2同理． 具體操作如下: 假設(shè)pos1=2,pos2=5, 并且有兩個(gè)父代個(gè)體P1,P2:

P1=[(1, 90), (2, 90),(3, 0), (4, 180), (5, 270), (6, 180), (7, 0), (8, 180), (9, 90)]

P2=[(5, 270), (3, 0),(2, 90), (4, 180), (1, 90), (6, 180), (9, 90), (8, 180), (7, 0)]

P1,P2中加下劃線的表示不變的基因位, 交叉后產(chǎn)生子代個(gè)體:

Son1=[(2, 90), (1, 90),(3, 0), (4, 180), (5, 270), (6, 180), (9, 90), (8, 180), (7, 0)]

Son2=[(3, 0), (5, 270),(2, 90), (4, 180), (1, 90), (6, 180), (7, 0), (8, 180), (9, 90)]

4.3 變異算子

本文基因的變異方法使用以下3種:

序號(hào)插入法: 隨機(jī)選取染色體中的某一位基因插入到隨機(jī)位置, 設(shè)染色體: [(1, 90),(2, 90), (3, 0), (4, 180), (5, 270)], 假設(shè)將下標(biāo)為1的基因插入到下標(biāo)為3的位置, 插入后變成: [(1, 90), (3, 0), (4, 180),(2, 90), (5, 270)]．

兩個(gè)零件交換位置: 隨機(jī)選取兩位基因交換位置, 設(shè)染色體: [(1, 90),(2, 90), (3, 0),(4, 180), (5, 270)], 交換下標(biāo)為1和下標(biāo)為3的基因, 交換后變成[(1, 90),(4, 180), (3, 0),(2, 90), (5, 270)]．

兩組零件交換順序: 隨機(jī)選取兩組基因交換位置, 先對(duì)染色體基因進(jìn)行分組, 將染色體基因分成若干個(gè)一組, 然后隨機(jī)交換兩組基因的位置．

前兩種變異方式適用于小規(guī)模零件的排樣, 第三種方式適用于大規(guī)模零件的排樣．

上述3種變異方法是對(duì)個(gè)體基因順序變異, 如果不對(duì)角度變異就無法產(chǎn)生新的旋轉(zhuǎn)角度． 角度變異通過隨機(jī)選擇基因位, 然后根據(jù)可旋轉(zhuǎn)角度隨機(jī)修改該基因位的角度值． 每次進(jìn)行角度變異時(shí), 隨機(jī)選擇int(numPieces/10)位基因進(jìn)行角度變異, 其中numPieces為待排零件的數(shù)量．

4.4適應(yīng)度計(jì)算

本文研究的是二維矩形帶排樣問題, 即原材料是定寬無限長(zhǎng), 排樣的目標(biāo)就是使排樣方案所切割的板材長(zhǎng)度盡可能短, 所以個(gè)體適應(yīng)度表示如下:

(8)

上式pi表示第i個(gè)個(gè)體;Pj表示第j個(gè)零件;A(Pj)表示第j個(gè)零件的面積;L為切割的板材長(zhǎng)度;W為板材寬度．

4.5 算法步驟

假設(shè)種群規(guī)模為M, 交叉概率Pc, 變異概率Pm,pbest用于記錄每次迭代種群中適應(yīng)度最高個(gè)體． 迭代過程中, 若出現(xiàn)超過K代種群最優(yōu)解未發(fā)生變化, 說明算法陷入極值點(diǎn), 此時(shí)對(duì)種群中除最優(yōu)個(gè)體外所有個(gè)體進(jìn)行變異以便種群跳出局部極值．

步驟1 構(gòu)造初始種群并計(jì)算種群適應(yīng)度, 記錄適應(yīng)度最高的個(gè)體到pbest中;

步驟2 判斷是否滿足終止條件, 若滿足則輸出最優(yōu)解并停止迭代, 否則執(zhí)行步驟3;

步驟3 計(jì)算當(dāng)前種群平均適應(yīng)度favg以及適應(yīng)度最高個(gè)體fbest, 如果favg/fbest≤δ, 則執(zhí)行步驟4, 否則執(zhí)行步驟5;

步驟4 將種群個(gè)體隨機(jī)組合, 遍歷每一對(duì)個(gè)體, 根據(jù)交叉變異概率進(jìn)行交叉變異操作, 轉(zhuǎn)向步驟6;

步驟5 臨時(shí)讓Pm=Pc, 將種群中的個(gè)體隨機(jī)組合, 遍歷每對(duì)個(gè)體, 根據(jù)變異交叉概率進(jìn)行變異交叉操作, 轉(zhuǎn)向步驟6;

步驟6 計(jì)算交叉變異后子代個(gè)體的適應(yīng)度, 將子代與父代合并, 計(jì)算所有個(gè)體濃度以及激勵(lì)度, 選擇激勵(lì)度最高的前M個(gè)個(gè)體形成新的種群;

步驟7 計(jì)算免疫選擇出的個(gè)體數(shù)量, 進(jìn)行免疫選擇以及克隆操作;

步驟8 對(duì)所有克隆出的個(gè)體進(jìn)行變異操作并計(jì)算變異后所有克隆體的適應(yīng)度;

步驟9 克隆抑制, 將變異個(gè)體中適應(yīng)度最高個(gè)體與原個(gè)體適應(yīng)度比較, 如果比原個(gè)體高就進(jìn)行替換, 否則不替換;

步驟10 若新種群中適應(yīng)度最高的個(gè)體比pbest的適應(yīng)度更高, 更新pbest, 否則判斷是否超過K代pbest未更新, 是則需要對(duì)種群中除適應(yīng)度最高個(gè)體外的所有個(gè)體進(jìn)行變異, 否則轉(zhuǎn)步驟2．

5 仿真實(shí)驗(yàn)

為了驗(yàn)證算法的可行性及性能, 本文下載ESICUP的14個(gè)基準(zhǔn)問題來測(cè)試算法性能, 然后使用汽車生產(chǎn)廠商提供的汽車零件圖測(cè)試本文算法． 本文算法仿真使用的計(jì)算機(jī)為PC機(jī), 處理器為AMD R7 5800H, 基準(zhǔn)頻率為3.2 GHz, 內(nèi)存為16 G, Win11操作系統(tǒng), 在VisualStudio2017平臺(tái)進(jìn)行, 使用C++作為仿真語言． 本文將每個(gè)測(cè)試用例測(cè)試30次, 記錄最優(yōu)結(jié)果以及平均結(jié)果． 相關(guān)參數(shù)以及操作說明:

1) 初始化參數(shù)說明: IGAA中的免疫克隆操作后會(huì)對(duì)所有克隆體進(jìn)行適應(yīng)度評(píng)估, 為了保證算法收斂速度, 種群規(guī)模不宜太大, 設(shè)置種群規(guī)模為12． 交叉概率過小不利于種群特征遺傳, 變異概率過大會(huì)使算法近似于隨機(jī)搜索, 因此交叉概率設(shè)為0.9, 變異概率設(shè)為0.1; 閾值δ和δs一般取接近1的數(shù), 本文δ=δs=0.95; 在能夠找到最優(yōu)解的情況下盡可能減少迭代次數(shù)以減少算法運(yùn)行時(shí)間, 因此最大迭代次數(shù)設(shè)為200次; 克隆系數(shù)與種群規(guī)模有關(guān), 為了保證每代都能產(chǎn)生克隆體, 本文ω=20, 激勵(lì)度計(jì)算的權(quán)重系數(shù)α=0.9,β=0.1; 在迭代過程中, 若出現(xiàn)超過K代種群最優(yōu)解未發(fā)生變化, 說明算法陷入極值點(diǎn), 此時(shí)對(duì)種群中除最優(yōu)個(gè)體外所有個(gè)體進(jìn)行變異操作以便種群跳出局部極值,K取值太大起不到作用, 取值太小算法隨機(jī)性太強(qiáng), 本文K=15．

2) 本文取零件數(shù)為30, 60為分界值, 當(dāng)小于30時(shí)零件數(shù)較少, 以相同概率采取4.3部分所述的前兩種變異方式; 大于30小于60時(shí)以0.4的概率采取第三種變異方式; 大于60時(shí), 以0.9的概率采取第三種變異方式．

3) 種群初始化: 種群初始化方法包括按零件面積遞減、 遞增排序; 按矩形度遞減、 遞增排序; 按零件長(zhǎng)邊遞減、 遞增排序; 其他個(gè)體隨機(jī)產(chǎn)生．

5.1 ESICUP的通用數(shù)據(jù)集測(cè)試

目前, 用于求解二維不規(guī)則排樣的優(yōu)化算法大多都是遺傳算法(GA)、 模擬退火(SA)等, 因此本文首先選取3種傳統(tǒng)優(yōu)化算法GA、 SA、 IA以及近幾年被提出的鯨魚優(yōu)化算法(WOA)[17-18]、 烏鴉搜索算法(CSA)[19-20]等5種優(yōu)化算法與IGAA進(jìn)行比較, 其中WOA與CSA解的編碼方式使用文獻(xiàn)[10]中的方法, 對(duì)比結(jié)果見表1. 其次, 本文還將IGAA與文獻(xiàn)[9]的混合分支限界禁忌搜索算法(BSTS)以及文獻(xiàn)[21]的混合遺傳模擬退火算法(GSAA)進(jìn)行對(duì)比, 結(jié)果見表2． 表中Best表示運(yùn)行的最優(yōu)利用率; Avg表示運(yùn)行的平均利用率; Dev表示算法最優(yōu)結(jié)果與平均結(jié)果的差值; 最后一行的Tot Avg表示14個(gè)數(shù)據(jù)庫(kù)對(duì)應(yīng)指標(biāo)的平均值． 從表1可以看出, 混合IGAA算法無論在最優(yōu)利用率還是平均利用率方面都要優(yōu)于單一智能優(yōu)化算法．

分析表2中14個(gè)數(shù)據(jù)集的運(yùn)行結(jié)果, IGAA在10個(gè)數(shù)據(jù)集的最優(yōu)利用率結(jié)果高于BSTS的最優(yōu)利用率; IGAA在9個(gè)數(shù)據(jù)集的平均利用率高于BSTS的平均利用率, 其中Dighe1、 Dighe2、 Dagli數(shù)據(jù)集的平均利用率比BSTS的最優(yōu)利用率都要好; 與GSAA比較, IGAA的所有數(shù)據(jù)集, 無論是最優(yōu)優(yōu)利用率還是平均利用率, 都比GSAA的要高; 分析總體平均Total Avg值, 無論是最優(yōu)利用率還是平均利用率, IGAA均為最高; 算法穩(wěn)定性方面分析每一行Dev的值, 由于Dighe1、 Dighe2屬于“拼圖”類型的排樣, 零件數(shù)較少, 所以IGAA的平均利用率與最優(yōu)利用率相差很大, 但是隨著數(shù)據(jù)集規(guī)模的增大, IGAA算法的穩(wěn)定性要比BSTS、 GSAA的穩(wěn)定性要好． 圖4展示了算法運(yùn)行所有數(shù)據(jù)集的收斂曲線:

表1 GA、 IA、 SA、 WOA、 CSA算法與IGAA算法結(jié)果對(duì)比

表2 BSTS、 GSAA與IGAA算法結(jié)果對(duì)比

圖4 各個(gè)數(shù)據(jù)集曲線收斂情況

分析圖4, Fu、 Dighe1、 Dighe2、 Jakobs1、 Marques、 Shapes0曲線可以在100代內(nèi)收斂; Albano、 Jakobs2、 Shapes1、 Blaz1、 Trousers、 Swim曲線可以在150代內(nèi)收斂, Mao、 Dagli曲線在150代以后出現(xiàn)輕微變化． 總的來說IGAA可以在150代以內(nèi)收斂到一個(gè)不錯(cuò)的解． 圖5展示了幾個(gè)基準(zhǔn)數(shù)據(jù)集排樣圖．

5.2 實(shí)際汽車零件排樣測(cè)試

為了驗(yàn)證本文算法的實(shí)用性, 本文選取重慶某汽車裝配制造公司提供的汽車零件數(shù)據(jù)進(jìn)行算法測(cè)試． 實(shí)際生產(chǎn)當(dāng)中, 往往需要對(duì)單一零件進(jìn)行排樣, 因此本文測(cè)試單一零件的排樣以及多種零件的混合排樣, 并將本文算法的運(yùn)行結(jié)果同開源軟件SvgNest以及5.1節(jié)的GA、 IA、 SA、 WOA、 CSA的運(yùn)行結(jié)果進(jìn)行對(duì)比, 將每個(gè)汽車零件數(shù)據(jù)集運(yùn)行20 min并記錄最終結(jié)果, 對(duì)比結(jié)果見表3．

表3 實(shí)際汽車零件數(shù)據(jù)的對(duì)比結(jié)果

從表3可以看出, 無論是單一零件還是多種零件混合排樣, IGAA算法仿真結(jié)果都要優(yōu)于其他算法的仿真結(jié)果． 表明本文的IGAA算法具有一定的實(shí)用性． 圖6為IGAA算法的排樣結(jié)果．

6 結(jié)論

本文針對(duì)二維不規(guī)則排樣問題, 使用基于重心臨界多邊形選取“BL”排放點(diǎn), 保證將待排多邊形排放到重心最低的位置; 在確定定位規(guī)則后, 問題就轉(zhuǎn)化為基于序列的優(yōu)化問題, 對(duì)于此, 本文提出一種改進(jìn)的免疫遺傳算法, 兼顧了兩者的全局與局部尋優(yōu)特性, 并且自適應(yīng)調(diào)整算法的運(yùn)行步驟及相關(guān)參數(shù), 從而有效避免算法的早熟現(xiàn)象． 對(duì)相關(guān)基準(zhǔn)問題測(cè)試, 表明了該算法的有效性． 對(duì)于實(shí)際汽車零件的排樣, 本文算法表現(xiàn)出的排樣效果也優(yōu)于開源軟件SvgNest和現(xiàn)有5種智能優(yōu)化算法的排樣結(jié)果． 總的來說, 本文提出的IGAA算法在解決汽車零件排樣問題方面具有一定的應(yīng)用價(jià)值．

圖5 IGAA算法排樣圖

圖6 汽車零件排樣