基于小生境遺傳模擬退火算法的不規(guī)則件優(yōu)化排樣

1、基于小生境遺傳模擬退火算法的不規(guī)則件優(yōu)化排樣史俊友，蘇傳生，翟紅巖(青島科技大學(xué) 機電工程學(xué)院，山東 青島 )摘要：對于二維不規(guī)則圖形零件在排樣區(qū)域上的最優(yōu)排列，將排樣和制造工藝聯(lián)系起來，將多邊形各邊向外擴充，為零件預(yù)留加工余量；然后采用遺傳模擬退火算法與小生境技術(shù)相結(jié)合，尋找排樣件在排樣時的最優(yōu)次序及各自的旋轉(zhuǎn)角度，再用基于“最低水平線與填充算法相結(jié)合”策略的啟發(fā)式排樣算法實現(xiàn)二維不規(guī)則件自動排樣，得到滿意的優(yōu)化排樣結(jié)果。關(guān)鍵詞：遺傳模擬退火算法；小生境；加工余量；最低水平線；優(yōu)化排樣 中圖分類號：TP 391.7 文獻標識碼：AOptimal layout of irregular par

2、ts based on Niching Genetic Simulated Annealing AlgorithmSHI Jun-you，SU Chuan-sheng，ZHAI Hong-yan(College of Mechanical and Electrical Engineering，Qingdao University of Science and Technology，Qingdao，China )Abstract：To solve the two-dimensional irregular parts packing problem, firstly the problem is

3、 associated with manufacturing process, every side of polygons is expanded in consideration of the machining allowance. Then genetic simulated annealing algorithm and niche are integrated to look for the best sequence of the irregular parts and each parts optimum rotating angle, finally the lowest h

4、orizontal algorithm and filling algorithm are combined to complete the automatic layout. The satisfactory results of optimal layout have been obtained.Key words： genetic simulated annealing algorithm；niche；machining allowance；the lowest horizontal algorithm；optimal layout最大限度地節(jié)約材料，提高材料利用率是實際生產(chǎn)中的一個基本

5、原則，由于在工業(yè)生產(chǎn)中排樣問題廣泛存在，因而解決它具有深遠的理論意義和現(xiàn)實意義。尋找通用性好、求解質(zhì)量和效率高、易于實現(xiàn)的排樣問題求解算法一直是該領(lǐng)域所追求的目標1。遺傳算法和模擬退火算法是當(dāng)今優(yōu)化技術(shù)領(lǐng)域應(yīng)用最廣泛的智能優(yōu)化算法2,3。然而，大量研究表明4，遺傳算法存在早熟收斂、局部尋優(yōu)能力差等許多不足，這使得最終搜索結(jié)果可能是局部最優(yōu)解。模擬退火算法能夠跳出局部最優(yōu)解，具有較強的局部搜索能力，但其把握搜索過程的能力不強。近年來，許多研究人員把不規(guī)則零件排樣轉(zhuǎn)化為矩形件排樣來處理，這種方法簡單易行，但由于沒有充分考慮零件具體的外形特征，會導(dǎo)致材料利用率的降低。為此本文充分考慮不規(guī)則件自身的形

6、狀特征，將排樣和制造工藝聯(lián)系起來，將多邊形各邊向外擴充，為零件預(yù)留加工余量，對擴充后的零件，求取其最小包絡(luò)矩形，并對一些形狀互補的零件構(gòu)造矩形排樣單元進行優(yōu)化組合，使零件區(qū)域在最小包絡(luò)矩形中所占的比例盡可能大，對組合后的圖形再求取最小包絡(luò)矩形，同時對多邊形的外輪廓與包絡(luò)矩形之間產(chǎn)生的空白區(qū)域進行填充；從遺傳模擬退火算法優(yōu)化策略的構(gòu)造出發(fā)，融合小生境技術(shù)的思想，形成一種小生境遺傳模擬退火算法NGSA算法，算法具有較強的全局和局部搜索能力，在此基礎(chǔ)上開發(fā)了不規(guī)則件優(yōu)化排樣系統(tǒng)。收稿日期：2008-12-03作者簡介：史俊友(1970-)，男(漢)，教授1 排樣模型零件在板材上的定位實際上只需3個參

7、數(shù)即可完成。這3個參數(shù)是該零件的一個給定點在板材上的坐標(X，Y)和該零件的排放角度。當(dāng)這3個參數(shù)確定后，該零件的其它各頂點坐標都可由這3個參數(shù)計算。設(shè)Gj(jJ，J為零件集合)為零件j的圖形，(xj，yj)為該零件的給定點的坐標，則該零件在板材上的定位可表示為下述過程：先將該零件以該定點為軸旋轉(zhuǎn)角度j，然后再將定點(xj，yj)在板材作位移(xj，yj)。這時零件j在板材上的方位可表示為Gj(xj，yj，j)。零件的數(shù)量為n，Sj為零件j的面積。L為板材的長，D為板材的寬，排樣圖形外接矩形高度為H，寬度為W。定義排樣布局的原材料利用率，為排樣零件的面積和與排樣圖形外接矩形的面積的比值。零件優(yōu)

8、化排樣的模型為5： (1)Gj (xj，yj，j )G( xk，yk，k ) = ， j k (2)S.t. 0 Yji ( xj，yj，j ) L ji = 0，1， nj (3)0 Xji ( xj，yj，j ) D ji = 0，1， nj (4)圖1多邊形加工余量Fig.1 The machining allowance of polygon式(2)表示零件j與零件k互不重疊；和為考慮加工余量后零件j的第i個頂點的坐標，式(3)和式(4)表示零件不能排在板材之外。2 零件預(yù)處理2.1 多邊形的近似表示排樣過程中，通過與CAD的接口，可以方便地提取零件中各實體的信息。在獲取零件中的各實體

9、信息后，還需進一步得知零件中各實體之間的拓撲關(guān)系。所以必須對實體的端點進行排序處理，使其成為一個封閉的輪廓，滿足零件表達的要求。圖2 空白區(qū)域填充Fig.2 The filling of blank space加工余量的大小對零件的加工質(zhì)量和制造的經(jīng)濟性均有較大的影響。對每個不規(guī)則件考慮其加工余量r，將零件多邊形各邊向外擴充r距離，各邊延長相交，得到與原多邊形相似的新多邊形，如圖1所示。由原多邊形各頂點坐標求出考慮加工余量后各多邊形頂點坐標，并將此作為進行優(yōu)化計算的基本數(shù)學(xué)信息。2. 2 多邊形外包絡(luò)矩形的求取不規(guī)則件的優(yōu)化排樣通常采用近似法，即把不規(guī)則件近似為矩形件來處理，從而簡化為矩形件排

10、樣問題。但如果在近似過程中未充分考慮零件的形狀特征，把不規(guī)則件簡單地當(dāng)成矩形件來處理，有可能導(dǎo)致材料利用率的降低。采用求取零件最小包絡(luò)矩形的方法，先設(shè)定一矩形包絡(luò)率，對包絡(luò)率滿足要求的零件用最小包絡(luò)矩形替代，對不滿足要求的零件進行優(yōu)化組合，使零件區(qū)域在最小包絡(luò)矩形中所占比例盡可能大，對組合后的圖形再求取最小包絡(luò)矩形，二維不規(guī)則件排樣問題就轉(zhuǎn)化為矩形件排樣問題。針對零件圖形內(nèi)部有空白區(qū)域的情況，在不發(fā)生干涉的前提下，選擇合適的零件對內(nèi)空白區(qū)域進行填充，如果有多個零件可以填充到一個空白區(qū)域中，采用最佳面積適配法。設(shè)區(qū)域面積為SE，各零件面積為Si，且SiSE，計算S=min(SE - Si)，S所

11、對應(yīng)的零件即為填充的零件?？瞻讌^(qū)域填充6如圖2所示。3 算法描述3.1 GASA混合優(yōu)化策略遺傳模擬退火算法是將遺傳算法與模擬退火算法相結(jié)合而構(gòu)成的一種優(yōu)化算法，引入了局部搜索過程；以遺傳算法運算流程為主體流程，將模擬退火機制融入其中，進一步調(diào)整優(yōu)化群體。整個算法的執(zhí)行過程由兩部分組成：首先通過遺傳算法部分的進化操作(側(cè)重全局搜索)產(chǎn)生較優(yōu)良的一個群體，再利用模擬退火算法部分的退火操作(側(cè)重局部搜索)來進行基因個體的優(yōu)化調(diào)整，運行過程反復(fù)迭代，直到滿足終止條件為止。這種算法思想策略，從對全局最優(yōu)解的搜索角度和算法的進化速度上來提高模擬退火遺傳算法的性能。3.2 小生境技術(shù)在生物學(xué)中，把某種特定

12、環(huán)境及其在此環(huán)境中生存的組織稱為小生境(niche) 7，而把有共同特性的一些組織稱作物種。基本遺傳算法在進行個體交配時采用的是隨機方式，這增強了對問題解空間的搜索能力，但也帶來了交配的有效性以及優(yōu)化效率不太理想等問題。為解決這些問題，在基本遺傳算法中引入小生境技術(shù)。其不僅能夠有效地保證群體中解的多樣性，而且在問題求解的收斂速度、計算精度、全局搜索能力等方面表現(xiàn)出明顯的效果，是一種較有效的方法。圖3 NGSA算法流程圖Fig.3 The flow chart of NGSA algorithm3.3 NGSA混合優(yōu)化策略NGSA算法應(yīng)用于不規(guī)則件的求解過程可描述為：(1) 設(shè)置進化代數(shù)計數(shù)器t

13、 = 1，隨機產(chǎn)生含M個個體的初始種群P0(t)，同時求出各個體的適應(yīng)度Fi(i = 1，2，M)；(2) 對種群P0(t)中的個體按其適應(yīng)度大小降序排列，記錄前N個個體(NM)為較好群體P1(t)，以免部分適應(yīng)度高的個體在遺傳操作中被淘汰掉；(3) 采用遺傳算法進行選擇、交叉、變異等操作，生成群體P2(t)； 對種群P0(t)進行預(yù)選擇操作，得種群Pop1(t)，選擇操作時，先進行賭盤選擇，再采用精英選擇。 采用單點交叉算子對種群Pop1 (t)進行交叉操作，得種群Pop2 (t)； 采用均勻變異算子對種群Pop2 (t)進行變異操作，得到種群P2(t)；(4) 以P2(t)為初始種群，對其

14、中各個體進行模擬退火運算，得到新的規(guī)模為M的群體P3(t)；(5) 將P1(t)、P2(t)、P3(t)合并構(gòu)成一個規(guī)模為N + M2的新群體P4(t)，采用小生境技術(shù)進行淘汰，兩兩比較各個體間的海明距離，若兩者間的海明距離在預(yù)先指定的數(shù)值之內(nèi)，對適應(yīng)度較低的個體施加一個較強的罰函數(shù)，極大地降低其適應(yīng)度，即增加其被淘汰的概率；(6) 對P4(t)進行評價，取出其中較好的前M個個體構(gòu)成P0(t)，降低退火溫度，轉(zhuǎn)步驟(2)，循環(huán)執(zhí)行。(7) 判斷是否滿足收斂條件，如不滿足終止條件，則更新進化代數(shù)計數(shù)器，即t = t + 1，轉(zhuǎn)至(6)；若滿足終止條件，則終止運算，輸出計算結(jié)果。算法流程如圖3所示

15、。3.4 NGSA算法的設(shè)計實現(xiàn)(1) 編碼機制由于二進制編碼不能直接反映多邊形的排樣方式，因此本文采用十進制整數(shù)編碼方法，它具有編碼和解碼操作簡單、遺傳操作便于實現(xiàn)等優(yōu)點。將所有參加排樣不同類型的零件按面積大小排列并加以編號，染色體的長度與排樣件的類型數(shù)相同。此編碼方式是基于一種排列順序的基因編碼方式，即所有排樣類型的一個排列順序作為一個染色體。編碼設(shè)計的關(guān)鍵是在染色體中產(chǎn)生不同編號的遺傳算子，相應(yīng)的解碼方法則根據(jù)所采用的解碼方法把具體的零件定位在板材上。(2) 解碼方法由遺傳算法產(chǎn)生一個個體的編碼后，能否快速求出其對應(yīng)的排樣圖是一個關(guān)鍵，同時只有求出該個體所對應(yīng)的排樣圖，才能計算其對應(yīng)的適

16、應(yīng)度值，并對該個體進行評價。筆者采用一種基于零件最高輪廓線的“最低水平線”8和填充算法相結(jié)合的解碼方法。對于在多張板材上排放零件的問題，當(dāng)零件的最高輪廓線y坐標大于板材的長度或者最高輪廓線的終點x坐標大于板材的寬度時，更換新板材，更新最低水平線及最高輪廓線，然后在新板材上按順序繼續(xù)排放零件。圖4 多種不規(guī)則件排樣結(jié)果Fig.4 The layout drawing of many irregular parts4 運行實例筆者應(yīng)用小生境遺傳模擬退火算法開發(fā)了實用的不規(guī)則件優(yōu)化排樣系統(tǒng)。已證明該系統(tǒng)能有效地解決任意二維不規(guī)則零件的最優(yōu)排樣問題。以下算例可以證明此算法的有效性和可行性。(1) 矩形

17、板材上的優(yōu)化排樣實例1：多種不規(guī)則件NGSA算法排樣圖5 多種矩形件排樣結(jié)果圖Fig.5 The layout drawing of many regular parts從過程裝備制造廠零件數(shù)據(jù)庫中隨機選取了一組具有不同形狀的多種類、單數(shù)量零件進行混合排樣計算。從板材庫中選擇矩形板材寬為600mm，設(shè)置算法基本運行參數(shù)：群體規(guī)模為50，最大迭代數(shù)為100，交叉率為0.6，變異率為0.06，馬可夫鏈長度為8000，衰減參數(shù)為0.95，迭代初始溫度為500，容差為0.0001，小生境之間的參數(shù)距離為2.5，零件種類為30，各零件加工余量都為2mm。調(diào)用NGSA算法確定零件的排放順序和旋轉(zhuǎn)角度，用基

18、于“最低水平線法”策略的動態(tài)掃描線算法與填充算法相結(jié)合的定位算法確定零件在板材的位置。排樣結(jié)果如圖4所示。實例2：多種矩形件NGSA算法排樣從某工廠實際激光切割加工中心選取一組矩形零件如表1，取群體規(guī)模為30，最大迭代數(shù)為100，交叉率為0.5，變異率為0.05，馬可夫鏈長度為9000，衰減參數(shù)為0.95，迭代初始溫度為900，容差為0.0001，小生境之間的參數(shù)距離為2.0，選擇矩形板材長800mm，寬為600mm。排樣結(jié)果如圖5所示。從排樣結(jié)果可以得出，本文提出的算法不僅適用于不規(guī)則零件的排樣，也適用于矩形零件的排樣，同時系統(tǒng)還能正確處理單張板材和多張板排樣問題，當(dāng)一張板排完后，如零件還未

19、排完，系統(tǒng)將在下一張新板進行排樣。表1 矩形零件清單Tab.1 The bill of rectangular parts零件編號零件長(mm)零件寬(mm)加工余量(mm)零件數(shù)量零件厚(mm)8-01601523048-02806022048-03782622048-04603023048-05904022048-06603023048-07453222048-08231222048-0920102304圖6 不規(guī)則板材排樣結(jié)果Fig.6 The layout drawing of irregular material(2) 不規(guī)則板材上的優(yōu)化排樣實例3：從某企業(yè)零件切割加工中心零件庫中隨

20、機選擇一組具有任意形狀的多邊形零件，部分零件多數(shù)量，取各零件加工余量都為5mm，在一個不規(guī)則的多邊形原材料板塊上利用NGSA算法進行自動排樣。排樣結(jié)果如圖6所示。從排樣結(jié)果可以看出排放的比較緊密，取得了較好的排樣結(jié)果，由此也證明了該算法在不規(guī)則板材上進行排樣的有效性及實用性。根據(jù)上述測試實例可以驗證NGSA算法的有效性和實用性，同時也進一步證明不規(guī)則件優(yōu)化排樣系統(tǒng)完全適合現(xiàn)在制造業(yè)中各種需求的混合排樣，其排樣速度比較快，不僅滿足企業(yè)材料利用率的要求，而且也達到了節(jié)約原材料、提高企業(yè)的生產(chǎn)效率、降低產(chǎn)品的成本，提高經(jīng)濟效益的目的。5 結(jié)語實踐證明，NGSA混合優(yōu)化策略結(jié)合了GA、SA和小生境的特點，彌補了各自的弱點，它是一種優(yōu)化能力、效率和可靠性較高的全局優(yōu)化方法?？梢缘玫揭环N實用高效的優(yōu)化排樣算法，對提高板材利用率有很大的現(xiàn)實意義，它的研究對智能優(yōu)化理論的發(fā)展與應(yīng)用也很有意義。參考文獻1 Julia A Ben Nell，Kathryn A Downs-land，William B Downs-landThe irregular cutting-stock problem-a new procedure