董德威， 顏云輝

（東北大學機械工程與自動化學院，遼寧 沈陽 110819）

缺陷板材非規(guī)則件優(yōu)化排樣

董德威， 顏云輝

（東北大學機械工程與自動化學院，遼寧 沈陽 110819）

針對理論上屬于NPC問題的非規(guī)則件優(yōu)化排樣問題，論文提出一種基于小生境技術的自適應遺傳模擬退火算法與基于內(nèi)靠接臨界多邊形最低點的啟發(fā)式布局算法相結合的方法?？紤]到算法中交叉概率和變異概率的選擇影響到算法收斂性，提出了自適應的交叉概率和變異概率，通過基于小生境技術的遺傳模擬退火算法對非規(guī)則件排樣的最優(yōu)順序和各自的旋轉角度進行優(yōu)化搜索。將非規(guī)則件定位在有缺陷原材料和非規(guī)則件多邊形的內(nèi)靠接臨界多邊形最低點以實現(xiàn)個體的解碼，同時避開了原材料表面缺陷。排樣實例表明，該優(yōu)化排樣算法行之有效，具有廣泛的適應性。

非規(guī)則件優(yōu)化排樣；小生境技術；遺傳模擬退火算法；啟發(fā)式布局算法；臨界多邊形

工程實際中經(jīng)常遇到優(yōu)化排樣問題。不規(guī)則件優(yōu)化排樣就是在給定的板材上將其按最優(yōu)方式進行排布，要求零件排放在板材內(nèi)，各個零件互不重疊且避開原材料的表面缺陷，實現(xiàn)最大限度地利用板材，提高效益的目的。排樣問題廣泛應用于機械制造、輕工、家具、皮革、服裝以及印刷等行業(yè)。因此研究不規(guī)則件在板材上的優(yōu)化排樣具有重要的理論意義和現(xiàn)實意義。

排樣問題實質(zhì)是一個組合優(yōu)化的二維布局問題，從數(shù)學復雜性理論看，是計算復雜性最高的一類 NPC問題，其計算復雜度隨著排樣規(guī)模的增大呈指數(shù)級增長，至今還無法找到解決該問題的有效多項式算法。Adamowicz[1]首次提出不規(guī)則件排樣的啟發(fā)式算法，但由于給出的只是基于某種排樣順序的準優(yōu)解，因而很多學者開始嘗試將人工智能算法或與啟發(fā)式算法相結合來對排樣問題進行研究。Liu等[2]、李明等[3]和Wang等[4]、史俊友等[5]分別應用粒子群算法和神經(jīng)網(wǎng)絡對優(yōu)化排樣進行了研究。Jakobs[6]提出了一種不規(guī)則件排樣算法，首先求取不規(guī)則件的最小包絡矩形，然后用遺傳算法(Genetic Algorithm, GA)得到矩形的最優(yōu)排樣順序，最后由啟發(fā)式算法完成排樣。因而將不規(guī)則件轉變?yōu)榫匦渭筮M行排樣成為很多學者的研究重點[7]，但此方法提高材料利用率的效果不佳。E Hopper[8]詳細闡述了不規(guī)則件排樣問題的研究現(xiàn)狀，同時提出GA與臨界多邊形(No-Fit Polygon, NFP)算法相結合將對不規(guī)則件排樣的研究起重要影響。

本文對不規(guī)則件排樣的3個關鍵問題（排樣順序、旋轉角度和定位規(guī)則）進行了研究?？紤]到GA具有良好的全局搜索能力，但卻存在局部尋優(yōu)能力差的缺點；而模擬退火算法(Simulated Annealing Algorithm, SA)具有較強的局部搜索能力，但把握搜索過程的能力不強，因此，將二者結合作為搜索算法。同時，考慮到交叉概率過大，遺傳模式被破壞的可能性大，使得具有高適應度值的個體結構很容易被破壞，交叉概率過小會使進化過程緩慢，以致停滯不前；對于變異概率，如果取值過小，則不易產(chǎn)生新的個體結構，如果取值過大，GA就成了純粹的隨機算法。因此，本文采用了自適應的交叉概率和變異概率[9-10]，避免了因上述情況而出現(xiàn)的問題。同時，利用基于預選擇機制的小生境技術對子輩個體是否替換父輩個體加以控制。本文將基于小生境技術的自適應遺傳模擬退火算法(Adaptive Genetic Simulated Annealing Algorithm Based on Niched Technology, ANGSA)作為搜索算法來得到不規(guī)則件的最優(yōu)排樣順序和各自旋轉角度。對于零件的定位規(guī)則，用于矩形件排樣定位的BL算法、下臺階算法或者最低水平線算法并不能用于不規(guī)則件的定位。因而，提出了將不規(guī)則件定位在有缺陷板材和不規(guī)則件多邊形的內(nèi)靠接 NFP最低點的方法。此方法不但實現(xiàn)了不規(guī)則件的定位，而且避開了原材料表面缺陷，還避免了應用最小包絡矩形定位所造成的材料利用率不高的問題。

1 不規(guī)則件排樣問題數(shù)學模型

1.1 問題描述

不規(guī)則件的優(yōu)化排樣問題是在若干張形狀不規(guī)則且有表面缺陷的板材內(nèi)，將若干不規(guī)則件P1，P2，…Pn按最優(yōu)方式進行排樣，排樣的目的是使得板材的利用率最高，在排樣過程中，不規(guī)則件的需求數(shù)量未必是 1，所以 Pi和 Pj(i≠j; i,j=1,2,…, n)可能是尺寸相同的不規(guī)則件。排樣過程要求滿足以下約束條件：

1） Pi, Pj(i≠j；i, j=1,2,…, n)互不重疊；

2） Pi(i=1,2,…, n)與板材表面缺陷不重疊；

3） Pi(i=1,2,…, n)必須放置在板材內(nèi)部；

4） 滿足一定的工藝要求。

1.2 排樣數(shù)學模型

不規(guī)則件、不規(guī)則板材以及板材表面缺陷的形狀可以分別用以字母P、M和D所代表的多邊形來表示。多邊形定義為N個按逆時針方向排列的多邊形頂點的有序集合{(x1, y1), (x2, y2), …(xi, yi),…,(xN, yN)}。取板材的最小x坐標和最小y坐標所確定的點作為坐標原點，由此便可確定M以及D的各頂點坐標。

不規(guī)則件Pi在板材上的定位需要4個參數(shù)(xi,yi,θi,fi)來確定。其中：(xi, yi)表示 Pi的參考點坐標；θi表示Pi的旋轉角度，θi∈ [0°, 360°)；fi為 Pi關于 x=xi軸的鏡像標志：fi= 0表示取 Pi本身進行排樣，fi=1表示取Pi關于x=xi軸的鏡像進行排樣。由這4個參數(shù)便可確定排樣后Pi的各頂點坐標。不規(guī)則件本身及其鏡像如圖1所示。

圖1 不規(guī)則件本身及其鏡像

設 Spi為 Pi(1≤i≤n)的面積，H為所有不規(guī)則件排樣后在板材上所達到的最大高度，H線以下（包括與H線相交）共有m個表面缺陷Dj(1≤j ≤m)，Sdj為Dj的面積（與H線相交的表面缺陷，取H線以下部分的面積），S為H線以下板材總面積，因所有不規(guī)則件未必能在一張板材內(nèi)排下，若需要k張板材Ml(1≤l≤k)，則用Sml來表示Ml的面積。板材的利用率F定義為所有不規(guī)則件的面積和與 H線以下無缺陷的板材面積之比，同時考慮約束條件，不規(guī)則件的優(yōu)化排樣問題的數(shù)學模型可表述為：

其中：第一個約束保證任意兩個不規(guī)則件不重疊；第二個約束保證不規(guī)則件與表面缺陷不重疊；第三個約束保證不規(guī)則件排樣在板材內(nèi)部。

2 不規(guī)則件排樣順序及各自旋轉角度

本文由ANGSA來得到不規(guī)則件的排樣順序及各自旋轉角度，下面對算法的一些關鍵技術進行說明。

2.1 個體編碼

不規(guī)則件的優(yōu)化排樣采用十進制編碼。將n個不規(guī)則件P1, P2, …Pn分別用整數(shù)l, 2, …, n進行編號，不規(guī)則件編號構成一個排列{x1, x2,…, xi,…, xn}，xi是排樣順序為i的不規(guī)則件編號，為排列中的每個編號增加一個角度θi和鏡像標志fi，便可得到個體的編碼X={( x1,1θ, f1), ( x2,2θ, f2),…, ( xi,iθ, fi),…, ( xn,nθ, fn)}?？紤]到排樣時間的限制，限定不規(guī)則件旋轉角度只能為某個角度基數(shù)θg的整數(shù)倍。有研究表明，不規(guī)則件旋轉角度基數(shù)θg≤7°時，材料利用率的變化很小，因此，本文取θg≤9°，即在360°范圍內(nèi)，每個不規(guī)則件有40個旋轉角度。

2.2 適應度函數(shù)

對個體的好壞用適應度函數(shù)評價，適應度函數(shù)值越大，個體質(zhì)量越好。對于優(yōu)化排樣問題，適應度函數(shù)應是衡量排樣結果優(yōu)劣的一個標準，因此，本文的適應度函數(shù)用板材的利用率用F來表示。即對于個體Xi（1≤i≤M，M為群體規(guī)模），其適應度函數(shù)值為F(Xi)。

2.3 遺傳算子

2.3.1 選擇算子

為避免父輩群體產(chǎn)生的最佳個體丟失，同時使適應度函數(shù)值較高的個體有更多的生存機會，采用最優(yōu)保存策略與“輪盤賭”選擇法相結合的選擇算子，將父輩群體中適應度函數(shù)值最大的個體直接選擇到下一代，其余的 M-1個個體采用“輪盤賭”選擇法進行選擇。

2.3.2 交叉算子

交叉是產(chǎn)生新個體的主要方法。本文采用雙點交叉，首先將父輩群體中的M個個體進行兩兩隨機配對，得到M′對個體，M′為M/2的下取整。對一對個體中的兩個個體X1，X2執(zhí)行交叉操作之前，先在[0,1]之間生成一個隨機數(shù)rc，如果rc大于交叉概率Pc，則對這對個體執(zhí)行交叉操作，產(chǎn)生兩個新個體 X1new，X2new，否則不執(zhí)行。雙點交叉是在1～n的范圍內(nèi)隨機產(chǎn)生兩個交叉位b1，b2(1≤b1＜b2≤n)，將X1中位于b1和b2之間的基因復制作為X1new前面的基因，剩余基因按在X2中出現(xiàn)的順序復制到 X1new的后面，同樣的方法可以得到另一個子輩個體X2new。

假設配對的兩個個體為：

2.3.3 變異算子

變異是產(chǎn)生新個體的輔助方法。針對個體編碼的形式，本文對父輩群體中任意一個個體X分別采用順序變異和角度及鏡像標志變異兩種變異方式。對個體X執(zhí)行變異操作之前，先在[0,1]之間生成一個隨機數(shù) rm，如果 rm大于變異概率Pm，則對這個個體執(zhí)行變異操作，否則不執(zhí)行。

順序變異就是隨機生成兩個1～n的范圍內(nèi)的順序變異位c1，c2(1≤c1＜c2≤n)，將個體X中的第c1個基因和第c2個基因的位置互換。

假設執(zhí)行順序變異操作的個體為：

X ={(4, 252°, 1), (6, 81°, 0), (1, 153°, 0), (3, 306°, 1), (5, 18°, 0), (2, 207°, 1)}

順序變異位c1=2，c2=4，則執(zhí)行順序變異之后得到的新個體為：

X′={(4, 252°, 1), (3, 306°, 1), (1, 153°, 0), (6, 81°, 0), (5, 18°, 0), (2, 207°, 1)}

角度及鏡像標志變異就是隨機生成一個1～n范圍內(nèi)的角度及鏡像標志變異位d，將執(zhí)行順序變異之后得到的新個體X的第d個基因的角度及鏡像標志分別用各自的等位數(shù)值來代替，得到執(zhí)行變異之后的新個體Xnew。

2.4 基于預選擇機制的小生境技術

為了有效地保持群體的多樣性以及考慮到子輩個體與父輩個體之間的相似性，本文對于交叉操作和變異操作之后得到的子輩個體是否替換父輩個體采用了基于預選擇機制的小生境技術[11]。

交叉運算中：

對于X1和X1new，如果F (X1new)＞F (X1)，則用X1new替換X1，否則保留X1；

對于X2和X2new，如果F(X2new)＞F(X2)，則用X2new替換X2，否則保留X2。

變異運算中：

對于X和Xnew，如果F(Xnew)＞F(X)，則用Xnew替換X，否則保留X。

2.5 遺傳參數(shù)的確定

2.5.1 群體規(guī)模

群體規(guī)模 M 的大小直接影響到算法的收斂速度和求解結果，群體規(guī)模過大，算法收斂速度慢；群體規(guī)模過小，群體多樣性降低，影響最終的求解結果。因此，本文采用了自適應的群體規(guī)模，群體規(guī)模隨排樣不規(guī)則件數(shù)量n的變化而變化，且由于個體編碼中每個基因位的長度為3，則群體規(guī)模M =3n。

2.5.2 自適應的交叉概率和變異概率

在執(zhí)行交叉算子和變異算子時都是通過判斷所生成的隨機數(shù)與交叉概率Pc和變異概率Pm的大小來決定是否執(zhí)行。因為算法的性能在很大程度上受到了Pc和Pm的影響，所以，本文采用了自適應的Pc和Pm。當某個個體的適應度函數(shù)值低于群體的平均適應度函數(shù)值時，說明該個體性能較差，應取較大的交叉概率和變異概率；反之，如果其適應度函數(shù)值高于群體的平均適應度函數(shù)值，說明該個體性能優(yōu)良，應取較小的交叉概率和變異概率。本文將GA中的自適應交叉概率和變異概率[12]表示如下：

其中：Fmax——群體中的最大適應度函數(shù)值；Favg——每代群體的平均適應度函數(shù)值；F′——執(zhí)行交叉操作的2個個體中較大的適應度函數(shù)值；

F——執(zhí)行變異操作的個體的適應度函數(shù)值；

Pc1、Pc2、Pm1和 Pm2——需事先確定，且Pc1、Pc2、Pm1和Pm2∈[0,1]。

2.6 模擬退火

對執(zhí)行完GA選擇、交叉和變異所得到的M個個體進行模擬退化運算，來得到新的 M個個體，并將這新生成的M個個體作為下一次迭代時GA的群體。在執(zhí)行SA時，有4個問題需要作出說明：

2.6.1 初始溫度

SA對初始溫度要求足夠高，以便滿足接受概率為1的初始要求。但初始溫度為無窮大是無法實現(xiàn)的。本文中初始溫度設為：

其中：α——調(diào)節(jié)參數(shù)；

n——個體長度；

Fmax——初始群體中的最大適應度函數(shù)值；

Fmin——初始群體中的最小適應度函數(shù)值。

2.6.2 降溫函數(shù)

SA中，線性降溫會在高溫區(qū)停留較長時間，而在低溫區(qū)時，溫度下降又會過快，故不能很好地完成搜索工作。比例降溫彌補了這一缺陷，因此本文采用比例降溫函數(shù)：

式中β為降溫系數(shù)，且 β∈ (0,1)。

2.6.3 狀態(tài)產(chǎn)生函數(shù)

狀態(tài)產(chǎn)生函數(shù)用于在即將執(zhí)行SA的個體X的鄰域中產(chǎn)生一個新的個體Xs。結合本文中個體的編碼方式，生成兩個1～n的范圍內(nèi)的隨機數(shù)s1，s2(1≤s1＜s2≤n)，狀態(tài)產(chǎn)生函數(shù)設計為對X中位于s1到s2的基因串執(zhí)行逆序操作。

假設X ={(4, 252°, 1), (6, 81°, 0), (1, 153°, 0), (3, 306°, 1), (5, 18°, 0), (2, 207°, 1)}

s1=2，s2=5，則由狀態(tài)產(chǎn)生函數(shù)得到的新個體為：

Xs={(4, 252°, 1), (5, 18°, 0), (3, 306°, 1), (1, 153°, 0), (6, 81°, 0), (2, 207°, 1)}

2.6.4 新個體接受概率

對個體X和Xs分別計算其適用度函數(shù)值F ( X )、F ( Xs)及其差值則當 ΔF ≤ 0時，用新個體 Xs代替?zhèn)€體 X，當ΔF ＞ 0時，如果大于一個0到1之間的隨機數(shù)，則用新個體Xs代替?zhèn)€體X，否則保留原個體X[13]。

2.7 算法收斂準則

在算法求解過程中，整個過程是趨于收斂的。本文設定的收斂準則為：如果兩代相鄰種群的平均適應度函數(shù)值之差＜0.05%，則認為算法收斂并停止迭代。否則，當遺傳代數(shù)大于特定代數(shù)Genmax時，迭代自動停止，則整個迭代過程中適應度函數(shù)值最大的個體所對應的排樣方案為最終排樣方案。

3 不規(guī)則件排樣定位規(guī)則

不規(guī)則件排樣的定位規(guī)則是對個體編碼的解碼過程。對一個個體的編碼進行解碼，就是要得到該個體所對應的排樣圖，以便根據(jù)排樣圖來對個體的適應度函數(shù)值進行計算。由于臨界多邊形（No Fit Polygon, NFP）給出了兩個多邊形之間的所有可能靠接位置，因此，不規(guī)則件排樣問題便轉換為基于NFP的定位選優(yōu)過程。

3.1 NFP定義及求解算法

NFP的定義：給定多邊形A和B，固定A不動，使B在不旋轉的前提下沿著A的邊界運動一周，在運動過程中，B與A始終保持接觸但不重疊，則B上的某個參考點在運動過程中所形成的軌跡就是B相對于A的NFPAB[14]。如果B在運動過程中在A的邊界內(nèi)部，則形成的NFP為內(nèi)靠接NFP，否則為外靠接NFP。

NFP的求解算法眾多，如移動碰撞法、凹多邊形凸化分割方法、Ghosh斜率圖法以及明可夫斯基矢量和法等，但由于求解算法的時間復雜度較高或者是難于處理A內(nèi)部有空腔的內(nèi)靠接NFP的問題，本文以基于軌跡線計算的 NFP算法[15]來對不規(guī)則件和板材的內(nèi)靠接NFP進行求解。

3.2 不規(guī)則件與表面有缺陷板材的內(nèi)靠接NFP

不規(guī)則件與表面有缺陷板材的內(nèi)靠接 NFP可按如下步驟求得：

Step 1 求出不規(guī)則件P與板材M的內(nèi)靠接NFPMP；

Step 2 求出P與M內(nèi)部所有表面缺陷Dj（1≤j≤m, m為M內(nèi)部表面缺陷數(shù)量）之間的外靠接NFP集合DP，DP={NFPDjP|1≤j≤m}；

Step 3 找到與NFPMP相交的NFPDjP，將其從DP集合中刪除以更新DP集合，同時將相交部分從NFPMP區(qū)域減去，更新NFPMP；

Step 4 對新的 DP集合和 NFPMP重復Step3；

Step 5 直至無法找到與 NFPMP相交的NFPDjP，此時得到的 NFPMP便是不規(guī)則件與表面有缺陷板材的內(nèi)靠接NFP。

NFPMP求解過程如圖2所示。

圖2 NFPMP求解過程

3.3 基于內(nèi)靠接NFP最低點的定位規(guī)則

由上文 NFPMP確定的不規(guī)則件位置不但保證不規(guī)則件排樣在板材內(nèi)部，并且避開了板材的表面缺陷。基于此提出一種將不規(guī)則件定位在有缺陷板材和不規(guī)則件多邊形的內(nèi)靠接 NFP最低點的定位規(guī)則。

基于內(nèi)靠接 NFP最低點的不規(guī)則件在板材內(nèi)部的定位規(guī)則步驟如下：

Step 1 不規(guī)則件集合SP={Pi|1≤i≤n }，板材集合 SM={Ml|1≤l≤k}，每張板材所對應的缺陷集合SDl={Dj|1≤j≤ml}，ml為第l張板材缺陷數(shù)量；

Step 2 計算第一個待排不規(guī)則件P1與第一張板材M1的內(nèi)靠接NFPM1P1；

Step 3 將 P1參考點定位在NFPM1P1縱坐標最低的位置，如NFPM1P1縱坐標最低點有多個，則將P1參考點定位在最左邊的那個坐標點；

Step 4 將定位之后的P1區(qū)域從M1的區(qū)域減去，此時若有表面缺陷與 P1接觸，則同時將此缺陷區(qū)域從M1的區(qū)域減去，更新M1，把此缺陷從SD1中去除，把P1從SP中去除；

Step 5 計算P2與更新之后的M1的內(nèi)靠接NFPM1P2，與P1類似，執(zhí)行Step 3和Step 4；

Step 6 直到某個不規(guī)則件Pi，無法找到Pi與M1的內(nèi)靠接NFPM1Pi，則計算Pi與M2的內(nèi)靠接NFPM2Pi，與P1類似，執(zhí)行Step 3和Step 4；

Step 7 直至所有不規(guī)則件排樣完畢，此時SP集合為空。

4 實例分析

用兩個實例驗證本文所提出的不規(guī)則件排樣算法的有效性和通用性。ANGSA的參數(shù)設置為：初始交叉概率Pc1為0.9，Pc2為0.6，初始變異概率Pm1為0.5，Pm2為0.1，初始溫度調(diào)節(jié)參數(shù)α為5，降溫函數(shù)的降溫系數(shù)β為0.95，算法收斂準則中Genmax為100。

實例1 矩形板材上存在有缺陷的不規(guī)則件排樣：在實際生產(chǎn)中，板材大多為矩形。本例中，排樣板材長度 L為 1000mm，板材寬度 W為640mm，每張板材均有表面缺陷。不規(guī)則件種類數(shù)為8，每類不規(guī)則件的需求數(shù)為15。排樣結果如圖3所示。

圖3 不規(guī)則件在矩形板材上的排樣結果圖

由排樣結果可知，排樣共使用兩張板材，圖中虛線為排樣結果的最高輪廓線，其高度為1554mm，板材利用率F達到了82.56%。

實例2 不規(guī)則板材上存在有缺陷的不規(guī)則件排樣：不規(guī)則件與實例1相同，每類不規(guī)則件的需求數(shù)為3。排樣結果如圖4所示。

圖4 不規(guī)則件在不規(guī)則板材上的排樣結果圖

5 結 束 語

針對在實際應用和理論研究方面都具有重要意義的不規(guī)則件優(yōu)化排樣問題，本文提出一種將ANGSA與基于內(nèi)靠接NFP最低點的啟發(fā)式布局算法相結合的方法。通過ANGSA來得到不規(guī)則件排樣的最優(yōu)順序和各自的旋轉角度，由基于內(nèi)靠接 NFP最低點的定位規(guī)則實現(xiàn)對個體的解碼。由實例可知，本文排樣算法對零件形狀和板材形狀均無要求，同時允許板材表面缺陷的存在，具有較強的有效性和通用性。在大批量生產(chǎn)時，本文提出的算法提高了板材的利用率，具有顯著的經(jīng)濟效益和重要的現(xiàn)實意義。

[1] Adamowicz M. The optimal two dimensional allocation of irregular, multiple connected shapes with linear, logical and geometric constrains [D]. New York:New York University, 1969.

[2] Liu D S, Tan K C, Huang S Y, et al. On solving multiobjective bin packing problems using evolutionary particle swarm optimization [J]. European Journal of Operational Research, 2008, 190(2):357-382.

[3] 李 明, 宋成芳, 周澤魁. 二維不規(guī)則零件排樣問題的粒子群算法求解[J]. 江南大學學報(自然科學版), 2005, 4(3):266-269.

[4] Wang Chunxi, Cao Yuedong, Zha Jianzhong. Neural algorithms of two dimensional packing [C]// Proceeding of the 3rd World Congress on Intelligent Control and Automation. Hefei, China, 2000:1127-1131.

[5] 史俊友, 蘇傳生, 瞿紅巖. 不規(guī)則零件優(yōu)化排樣的神經(jīng)網(wǎng)絡混合優(yōu)化算法[J]. 工程設計學報, 2009, 16(4):271-275.

[6] Jakobs S. On genetic algorithms for the packing of polygon [J]. European Journal of Operational Research, 1996, 88(1):165-181.

[7] 賈志欣, 殷國富, 羅 陽. 二維不規(guī)則零件排樣問題的遺傳算法求解[J]. 計算機輔助設計與圖形學學報, 2002, 14(5):467-470.

[8] Hopper E, Turton H. A review of the application of meta-heuristic algorithms to 2D regular and irregular strip packing problems [J]. Artificial Intelligence Review, 2001, 16:257-300.

[9] Bekiroglu S, Debe T, Ayvaz Y. Implementation of different encoding types on structural optimization based on adaptive genetic algorithm [J]. Finite Elements in Analysis and Desigh, 2009, 45(11):826-835.

[10] Lee Chienpang, Lin Wenshin, Chen Yuhmin, et al. Gene selection and sample classification on microarray data based on adaptive genetic algorithm/k-nearest neighbor method [J]. Expert Systems with Applications, 2011, 38(5):4661-4667.

[11] 周 明, 孫樹棟. 遺傳算法原理及應用[M]. 北京:國防工業(yè)出版社, 1999:74-78.

[12] 王小平, 曹立明. 遺傳算法——理論、應用與軟件實現(xiàn)[M]. 西安:西安交通大學出版社, 2001:73-74.

[13] Suman B. Study of simulated annealing based algorithm for multi objective optimization of a constrained problem [J]. Computer & Chemical Engineering, 2004, 28(9):1849-1871.

[14] Burke E K, Hellier R S R, Kendall G, et al. Complete and robust no-fit polygon generation for the irregular stock cutting problem [J]. European Journal of Operational Research, 2007, 179(1):27-49.

[15] 劉胡瑤, 何援軍. 基于軌跡計算的臨界多邊形求解算法[J].計算機輔助設計與圖形學學報, 2006, 18(8):1123-1129.

Optimal Packing of Irregular Parts on Plates with Defects

Dong Dewei, Yan Yunhui
( School of Mechanical Engineering & Automation, Northeastern University, Liaoning Shenyang 110819, China )

Aiming at the optimal packing problem of irregular parts, known as a NP-complete problem, an approach is presented, which combines adaptive niche genetic simulated annealing algorithm with a heuristic packing algorithm based on the lowest point of inside no fit polygon. Considering that the choice of crossover probability and mutation probability will affect algorithm convergence, the adaptive crossover probability and the adaptive mutation probability are putted forward. The proposed approach automatically looks for the best sequence of the irregular parts and each part’s optimum rotation angle by the genetic simulated annealing algorithm which is based on the niche technology. The lowest point of inside no fit polygon, which is created by the damaged raw material polygon and the irregular part polygon, is selected to locate the part. Meanwhile, the overlap of the part and the surface defect of raw material are avoided. Examples indicate that the approach is effective and practical.

optimal packing of irregular parts; niche technology; genetic simulated annealing algorithm; heuristic packing algorithm; no fit polygon

TP 391.7

A

2095-302X (2013)02-0031-07

2012-05-03；定稿日期：2012-06-27

國家自然科學基金資助項目(50574019)；國家高技術研究發(fā)展計劃(863計劃)資助項目(2008AA04Z135)；中央高校基本科研業(yè)務費專項資金資助項目(N100603002)

董德威（1983-），男，遼寧朝陽人，博士研究生，主要研究方向為圖像處理、計算機輔助設計。E-mail：weidragon007@sina.com

顏云輝（1960-），男，江蘇丹陽人，教授，主要研究方向為圖像處理與計算機應用技術，虛擬設計與仿真技術。E-mail：yanyh@mail.neu.edu.cn