劉海明， 周 炯， 吳忻生， 羅家祥

(華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣東 廣州 510641)

基于改進(jìn)最低水平線方法與遺傳算法的矩形件排樣優(yōu)化算法

劉海明， 周 炯， 吳忻生， 羅家祥

(華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣東 廣州 510641)

傳統(tǒng)的最低水平線方法用于矩形件排樣時(shí)可能產(chǎn)生較多未被利用的空白區(qū)域，造成不必要的材料浪費(fèi)。針對(duì)此缺陷，在搜索過(guò)程中引入啟發(fā)式判斷，實(shí)現(xiàn)空白區(qū)域的填充處理，提高板材利用率。在應(yīng)用遺傳算法優(yōu)化矩形件排樣順序時(shí)，在進(jìn)化過(guò)程中采用分階段設(shè)置遺傳算子的方法，改善算法的搜索性能與效果。通過(guò)改進(jìn)最低水平線方法與基于分階段遺傳算子的遺傳算法相結(jié)合，共同求解矩形件排樣問(wèn)題。排樣測(cè)試數(shù)據(jù)表明，所提出的矩形件排樣優(yōu)化算法能夠有效改善排樣效果，提高材料利用率。

矩形件排樣；優(yōu)化算法；最低水平線；遺傳算法

矩形件排樣問(wèn)題屬于二維排樣問(wèn)題中的一類特殊優(yōu)化問(wèn)題，是指將一組給定尺寸的矩形零件在矩形板材上按一定方式進(jìn)行排放，要求零件的排放不得超出板材邊界，零件之間互不重疊，同時(shí)使板材利用率最大化。矩形件排樣優(yōu)化問(wèn)題普遍存在于鈑金、紙品、玻璃、家具等現(xiàn)代制造、加工行業(yè)中。從數(shù)學(xué)計(jì)算復(fù)雜性來(lái)看，該問(wèn)題屬于NP-Complete組合優(yōu)化問(wèn)題，很難在一個(gè)合理時(shí)間內(nèi)獲得問(wèn)題最優(yōu)解。因此，研究和設(shè)計(jì)有效的矩形件排樣優(yōu)化算法，具有重要的理論研究意義和應(yīng)用價(jià)值。

自20世紀(jì)90年代以來(lái)，國(guó)內(nèi)外許多學(xué)者針對(duì)矩形件排樣問(wèn)題作了研究，提出了不同的求解方法。多數(shù)文獻(xiàn)將矩形件排樣問(wèn)題分為：矩形件的排放策略問(wèn)題與矩形件的排放順序問(wèn)題考慮。前者指矩形件被排入板材時(shí)的靠排方式；后者指各個(gè)矩形件的排放順序。對(duì)于矩形件排放策略，目前多采用基于啟發(fā)式規(guī)則的方法。Jakobs[1]提出基于BL規(guī)則的排放策略，以優(yōu)先向下、向左靠排的方式排放零件。劉德全和藤弘飛[2]在 BL策略基礎(chǔ)上提出一種下臺(tái)階方法，在向左靠排的過(guò)程中也同時(shí)考慮向下靠排。Hopper和Turton[3]也提出了一種BL改進(jìn)策略，考慮了排放過(guò)程中產(chǎn)生的孔洞的填充利用。Yeung和Tang[4]與Wei等[5]提出了一種基于最低水平線的排放策略，優(yōu)先在具有最低高度的水平輪廓線上排放零件。Christoforos和Fleszar[6]提出一種剩余矩形匹配算法，將板材可用區(qū)域不斷劃分為矩形塊并逐個(gè)排入矩形零件，以盡可能減少板材浪費(fèi)。對(duì)于矩形件排放順序問(wèn)題，其本質(zhì)為序列的組合優(yōu)化問(wèn)題。早期主要采用經(jīng)驗(yàn)性做法處理，例如按矩形件高度、面積排序等標(biāo)準(zhǔn)確定矩形件的排放順序。但這種相對(duì)硬性的處理方法，在用于不同排樣實(shí)例時(shí)結(jié)果往往時(shí)好時(shí)差，適用性不強(qiáng)。此外，該方法僅能產(chǎn)生少量特定的解序列，對(duì)于排樣問(wèn)題往往難以得到最優(yōu)解甚至次優(yōu)解。目前，多采用一些基于進(jìn)化思想的大規(guī)模搜索算法對(duì)矩形件排樣順序進(jìn)行尋優(yōu)，如遺傳算法(genetic algorithm，GA)[7]、模擬退火算法[8]等。

本文對(duì)原有的最低水平線排放策略作了改進(jìn)，考慮了板材空白區(qū)域的有效利用，避免材料浪費(fèi)；在應(yīng)用GA實(shí)現(xiàn)矩形件排樣順序優(yōu)化時(shí)，針對(duì)GA可能出現(xiàn)的過(guò)早收斂、搜索效率低等不足，對(duì)傳統(tǒng)GA進(jìn)行算法搜索性能改進(jìn)。改進(jìn)的最低水平線方法與GA相結(jié)合，共同求解矩形件排樣優(yōu)化問(wèn)題。

1 問(wèn)題描述與數(shù)學(xué)模型

根據(jù)不同的實(shí)際應(yīng)用與工藝要求，矩形件排樣問(wèn)題可有不同的表述。該問(wèn)題的一般化描述為：給定已知矩形件的一組尺寸，在一個(gè)寬度確定、高度不限的矩形板材上不重疊地排入這些矩形件，并使得板材利用率最高。根據(jù)問(wèn)題描述可知，排樣過(guò)程應(yīng)滿足以下3個(gè)條件：①任何一個(gè)矩形件不能超出板材邊界；②各矩形件不能出現(xiàn)重疊；③矩形件可以旋轉(zhuǎn)，但矩形件的邊需與板材邊界平行，即矩形件只能以0°或90°排放。圖1所示為一個(gè)包含8個(gè)矩形零件的排樣實(shí)例，其中，陰影部分為不能利用的板材(常稱為孔洞)。

圖1 矩形件排樣實(shí)例

且滿足約束條件：

其中，式(2)保證所有矩形排放時(shí)不超出板材邊界，式(3)保證所有矩形之間不出現(xiàn)重疊。

2 基于改進(jìn)最低水平線方法的排放策略

傳統(tǒng)的最低水平線方法只考慮在高度最低的水平輪廓線上排放零件，但排放過(guò)程中并不考慮零件尺寸對(duì)排放布局的影響，在某些情形下會(huì)使板材出現(xiàn)較多孔洞而導(dǎo)致不必要的浪費(fèi)。針對(duì)這一不足，本文提出了改進(jìn)方法：在排放過(guò)程中，考慮待排放矩形件的尺寸，通過(guò)引入啟發(fā)式判斷條件靈活選擇待排放矩形件，以充分利用板材可用區(qū)域。改進(jìn)后的最低水平線方法的算法步驟如下：

步驟 1. 初始化板材的水平輪廓線集合，其僅包含一條水平輪廓線，即板材的底部邊界，且為集合中的最低水平線；同時(shí)，設(shè)置變量i＝1。

步驟2. 在給定的矩形件序列中，對(duì)第i個(gè)待排放矩形件pi，在當(dāng)前水平輪廓線集合中找到當(dāng)前高度最低的水平線(最低水平線)，判斷該水平線的寬度是否足夠排入矩形件pi。如果可以排入，在該水平線上靠左排放該矩形件，并轉(zhuǎn)入步驟4；否則，跳轉(zhuǎn)到下一步。

步驟3. 對(duì)矩形件序列中pi后的所有未排放矩形件，判斷其寬度大小是否可以在當(dāng)前最低水平線上排放。對(duì)于能夠排入的矩形件，優(yōu)先選取寬度與最低水平線寬度相同的矩形件進(jìn)行排放(若存在多個(gè)滿足條件的矩形件，則選取高度最高的矩形件)，然后交換該矩形件與矩形件pi在矩形件序列中的位置(即交換兩者排放順序)，并轉(zhuǎn)入下一步處理。若未能在當(dāng)前最低水平線上找到可以排放的矩形件，則將當(dāng)前最低水平線的高度提升至與其相鄰且高度最接近的水平輪廓線，合并兩段水平線。更新板材的水平輪廓線集合，然后跳轉(zhuǎn)到步驟2繼續(xù)處理。

步驟 4. 根據(jù)新排放的矩形件的位置及尺寸，更新板材的水平輪廓線集合。

步驟5. 若序列中尚有矩形件未排放，令i=i+1，轉(zhuǎn)入步驟2繼續(xù)處理；若所有矩形件已完成排放，則結(jié)束算法，此時(shí)板材的用量由水平輪廓線集合中高度最大的水平線決定。

在改進(jìn)最低水平線方法中，通過(guò)啟發(fā)式規(guī)則調(diào)整矩形件的排放順序，使得板材空閑區(qū)域的利用更為靈活。算法中不僅考慮了小尺寸矩形件的填充排放，而且還考慮了寬度相同但高度不同的矩形件的排放順序優(yōu)化，優(yōu)先排放高度較大的矩形件。因?yàn)楦叨容^大的矩形件對(duì)板材用量的影響較大，優(yōu)先排入高度較大的矩形件，可避免排樣后期這些矩形件排放造成的材料浪費(fèi)。改進(jìn)最低水平線方法的算法流程如圖2所示。

圖2 改進(jìn)最低水平線方法

圖3和圖4分別為針對(duì)同一排樣算例(包含7個(gè)矩形件)按最低水平線方法和改進(jìn)最低水平線方法排放的結(jié)果，其中矩形件初始排樣序列為(1,2,3,4,5,6,7)。從排放結(jié)果可以看出，改進(jìn)后的最低水平線方法能夠更好地利用板材空間，使得板材利用率得到提高。

圖3 基于最低水平線方法的排放策略

圖4 基于改進(jìn)最低水平 線方法的排放策略

3 基于改進(jìn)遺傳算法的矩形件排樣優(yōu)化算法

3.1 可行解的編碼方式

從矩形件排樣問(wèn)題的特點(diǎn)可知，矩形件排樣結(jié)果與矩形件的排樣順序密切相關(guān)。矩形件排樣順序的優(yōu)化屬于基于序列的組合優(yōu)化問(wèn)題，相對(duì)于局部搜索算法，具有全局搜索特性的GA能夠獲得更好求解結(jié)果。

所謂可行解編碼，是指將排樣問(wèn)題的可行解從解空間轉(zhuǎn)換為GA能夠處理的搜索空間的解。常用編碼方式有整數(shù)編碼、實(shí)數(shù)編碼和符號(hào)編碼等。此處，基于排樣問(wèn)題特點(diǎn)，對(duì)排樣可行解采用直觀的十進(jìn)制編碼方式：對(duì)矩形件從1開(kāi)始順序編號(hào)，所有矩形件的編號(hào)所構(gòu)成的序列就可以代表一個(gè)可行解(各編號(hào)所對(duì)應(yīng)的矩形件在序列中的次序代表其排樣順序)。因此，對(duì)于包含n個(gè)矩形件的排樣問(wèn)題，其可行解集合為此外，為了在可行解中體現(xiàn)出矩形件是否旋轉(zhuǎn)后排放這一信息，對(duì)上述編碼方式進(jìn)行擴(kuò)展：為每個(gè)矩形件編號(hào)增加一個(gè)符號(hào)標(biāo)志，若符號(hào)為正，表示矩形件排放時(shí)不旋轉(zhuǎn)(按0°排放)；若符號(hào)為負(fù)，表示矩形件旋轉(zhuǎn)90°后再排放。

3.2 適應(yīng)度函數(shù)

在GA中，需要建立一個(gè)適應(yīng)度函數(shù)來(lái)評(píng)估可行解的優(yōu)劣。對(duì)于矩形件排樣問(wèn)題，為使適應(yīng)度函數(shù)能夠反映解的優(yōu)劣，選擇如下適應(yīng)度函數(shù)：

其中，Si為某個(gè)排樣序列，AT為所有矩形件的面積之和，W為板材寬度，Hused(Si)為排樣序列Si基于特定排樣策略下的排樣結(jié)果中矩形件水平輪廓線中最高水平線的高度。這樣，適應(yīng)度函數(shù)f (Si)的值就代表排樣序列Si對(duì)應(yīng)的板材利用率。易知，適應(yīng)度函數(shù)的取值范圍為(0, 1]。適應(yīng)度函數(shù)值越高，表示對(duì)應(yīng)的可行解(排樣序列)越優(yōu)。

3.3 遺傳算法的改進(jìn)處理

GA是一種具有全局尋優(yōu)能力的進(jìn)化算法，適合大規(guī)模組合優(yōu)化問(wèn)題的求解。但傳統(tǒng)GA也存在一些缺點(diǎn)，例如過(guò)早收斂、搜索效率低等。本文從兩方面對(duì)傳統(tǒng)GA進(jìn)行改進(jìn)：首先，根據(jù)適應(yīng)度的不同對(duì)父代解采取不同的進(jìn)化操作，保證種群多樣性，以避免種群過(guò)早收斂；其次，根據(jù)解的進(jìn)化階段動(dòng)態(tài)調(diào)整遺傳算子，提高算法自適應(yīng)能力，使搜索能夠更快逼近問(wèn)題最優(yōu)解。

(1) 選擇、交叉和變異操作。為保證種群的多樣性，根據(jù)可行解適應(yīng)度的不同采取相應(yīng)的進(jìn)化處理?；舅悸窞椋和ㄟ^(guò)選擇操作保留一部分適應(yīng)度較好的父代解到子代種群中，通過(guò)對(duì)父代解的交叉、變異操作生成新的解補(bǔ)充到子代種群中；選擇、交叉和變異操作所產(chǎn)生的解共同構(gòu)成子代種群。

設(shè)種群大小為N，且進(jìn)化過(guò)程中每一代種群大小不變，算法中的選擇、交叉和變異操作如下所述：

①選擇操作：又稱復(fù)制操作，目的是把父代種群中具有較優(yōu)適應(yīng)度的解直接復(fù)制到子代種群中，保證良好基因的存在。方法是：預(yù)設(shè)一個(gè)選擇算子ps(0

②交叉操作：是在進(jìn)化過(guò)程中產(chǎn)生新解的主要方法，可以改善種群的多樣性。本文采用如下交叉方法：在余下的父代解(未被選擇保留的父代解)中隨機(jī)選中兩個(gè)解，采用兩點(diǎn)交叉方法產(chǎn)生兩個(gè)新的可行解進(jìn)入下一代。關(guān)于兩點(diǎn)交叉方法，已有較多文獻(xiàn)介紹，此處不再贅述。每?jī)蓚€(gè)隨機(jī)選取的父代解都可以通過(guò)兩點(diǎn)交叉方法獲得兩個(gè)新解。交叉操作產(chǎn)生的新解數(shù)量為pcN，其中N為種群大小，pc為預(yù)設(shè)的選擇算子(0

③變異操作：是一種產(chǎn)生新解的方式，是交叉操作的有益補(bǔ)充。根據(jù)排樣問(wèn)題的特點(diǎn)，本文采用兩種變異操作：交換變異與旋轉(zhuǎn)變異。交換變異對(duì)隨機(jī)選中的某個(gè)父代解中的兩個(gè)隨機(jī)位置上的基因進(jìn)行位置交換，從而得到一個(gè)新的排樣序列(可行解)。旋轉(zhuǎn)變異用于調(diào)整矩形件排放時(shí)的排放角度，其操作方法是：對(duì)于隨機(jī)選中的某個(gè)父代解，在區(qū)間[1, n]之間產(chǎn)生一個(gè)隨機(jī)位置(n為排樣序列長(zhǎng)度)，將該位置對(duì)應(yīng)的矩形件編號(hào)的符號(hào)取反(意味著改變矩形件的排放角度)，從而得到一個(gè)新解。

每個(gè)被隨機(jī)選中的父代解都可以通過(guò)交換變異或旋轉(zhuǎn)變異操作得到一個(gè)新解。兩種變異操作產(chǎn)生的新解數(shù)量分別由預(yù)設(shè)的交換變異算子 pme(0

需要說(shuō)明的是，為了保持每代的種群大小不變，各算子的取值應(yīng)滿足條件：ps+pc+pme+pmr=1。

(2) 分階段遺傳算子的引入。研究發(fā)現(xiàn)，GA的收斂速度、尋優(yōu)結(jié)果與選擇、交叉、變異算子的設(shè)置有很大關(guān)系。其中，選擇算子對(duì)算法收斂速度影響較大，交叉、變異算子則對(duì)算法尋優(yōu)結(jié)果有重要影響。在算法搜索的不同階段，合理調(diào)整遺傳算子，能夠使算法性能得到改善。因此，本文對(duì)GA作了如下改進(jìn)：

在算法的初始階段，設(shè)置一個(gè)具有較大值的選擇算子ps(0.6≤ps<1)，目的在于使算法能夠在較短的時(shí)間內(nèi)逼近排樣問(wèn)題的最優(yōu)解或次優(yōu)解，從而快速獲得較好解。此時(shí)，由于所設(shè)置的交叉算子與變異算子值較小，當(dāng)算法進(jìn)行到某個(gè)階段時(shí)，可能會(huì)陷入局部最優(yōu)，在某個(gè)子空間內(nèi)反復(fù)搜索最優(yōu)解。為避免算法過(guò)早收斂，需對(duì)各遺傳算子進(jìn)行調(diào)整，將搜索范圍延伸至更大的解空間。此時(shí)，令算法進(jìn)入第二階段搜索過(guò)程。在這一階段，對(duì)遺傳算子作如下調(diào)整：將選擇算子 ps設(shè)置為一個(gè)較小值(0

在算法實(shí)際搜索過(guò)程中，兩個(gè)搜索階段進(jìn)行切換的判斷依據(jù)是當(dāng)前搜索到的最好解的變化情況。通過(guò)最好解的變化情況及預(yù)設(shè)的條件，動(dòng)態(tài)調(diào)整遺傳算子，使算法循環(huán)交替地進(jìn)入兩個(gè)搜索階段。這一處理可使算法不會(huì)總受到單一遺傳算子左右，搜索過(guò)程既能保證快速性也能保證全局性。

3.4 基于改進(jìn)最低水平線方法與遺傳算法的排樣優(yōu)化算法

利用改進(jìn)GA實(shí)現(xiàn)矩形件排樣順序的尋優(yōu)，并采用改進(jìn)最低水平線方法實(shí)現(xiàn)矩形件排樣，可構(gòu)造完整的矩形件排樣優(yōu)化算法。算法流程圖如圖5所示。在算法中，改進(jìn)最低水平線方法被用于對(duì) GA所產(chǎn)生的每代種群中的各個(gè)可行解進(jìn)行矩形件排放，通過(guò)計(jì)算可行解的適應(yīng)度來(lái)判斷解的優(yōu)劣。兩個(gè)搜索階段的切換條件為當(dāng)前搜索到的最好解是否連續(xù)多代沒(méi)有得到改進(jìn)，若是則將遺傳算子調(diào)整為第二階段的算子，否則設(shè)置為第一階段的遺傳算子。

圖5 基于改進(jìn)最低水平線方法與遺傳算法的排樣優(yōu)化算法

4 算法評(píng)估

為評(píng)估所提出的排樣優(yōu)化算法的性能，在Visual C++ 2008環(huán)境下編程實(shí)現(xiàn)該算法，并與文獻(xiàn)[9]中提出的排樣優(yōu)化算法進(jìn)行實(shí)驗(yàn)對(duì)比(文獻(xiàn)[9]采用了基于最低水平線方法與改進(jìn)GA的排樣優(yōu)化算法)。首先，以文獻(xiàn)[9]給出的算例作為測(cè)試數(shù)據(jù)，該算例包含20種不同尺寸的矩形件(總數(shù)為59個(gè))，板材寬度為400。在仿真實(shí)驗(yàn)中，本文算法的相關(guān)參數(shù)如表1所示，算法中不同搜索階段的切換條件為：當(dāng)前搜索到的最好解是否連續(xù)5代都未得到改進(jìn)；算法的終止條件為：迭代次數(shù)達(dá)到預(yù)設(shè)的最大迭代次數(shù)。

兩種算法的優(yōu)化結(jié)果如表2所示，其中，Uavg指算法重復(fù)運(yùn)行50次得到的板材利用率的平均值，

Ubest指在50次運(yùn)算中得到的最佳利用率，Tavg指平均運(yùn)算時(shí)間。

表1 本文算法采用的參數(shù)

表2 排樣結(jié)果數(shù)據(jù)(I)

從表2可看出，相對(duì)于文獻(xiàn)[9]算法，本文算法對(duì)該算例的優(yōu)化結(jié)果有明顯提高，而算法所需運(yùn)算時(shí)間略有增加。為更好地評(píng)估算法性能，通過(guò)隨機(jī)方式產(chǎn)生 10組包含數(shù)量不等、尺寸不同的矩形件的排樣數(shù)據(jù)進(jìn)行算法測(cè)試。在算法參數(shù)不變的情況下，對(duì)上述兩種算法進(jìn)行排樣對(duì)比實(shí)驗(yàn)，排樣數(shù)據(jù)及結(jié)果如表3所示。

從表3結(jié)果可以看出，本文提出的排樣優(yōu)化算法無(wú)論是在板材的平均利用率還是最佳利用率方面，均比文獻(xiàn)[9]算法有明顯提升。從算法運(yùn)算時(shí)間來(lái)看，本文算法與文獻(xiàn)[9]算法相比略有增加。隨著矩形件種類、數(shù)量的增加，這種差別相對(duì)于實(shí)際運(yùn)算時(shí)間而言幾乎可忽略不計(jì)。這表明，改進(jìn)后的優(yōu)化算法能夠在保證運(yùn)算效率的前提下，有效改善排樣效果，提高材料利用率。

表3 排樣結(jié)果數(shù)據(jù)(II)

5 結(jié) 論

本文對(duì)基于最低水平線方法的矩形件排樣策略作了改進(jìn)，通過(guò)引入啟發(fā)式規(guī)則靈活選擇矩形件進(jìn)行排樣，有效利用板材空白區(qū)域，避免板材浪費(fèi)。采用分階段設(shè)置遺傳算子的方法改進(jìn) GA，改善算法搜索性能，并將算法與改進(jìn)最低水平線方法相結(jié)合，共同求解矩形件排樣問(wèn)題。排樣測(cè)試數(shù)據(jù)表明，文中提出的算法能夠有效求解矩形件排樣問(wèn)題，不僅在板材利用率方面有明顯提升，且算法執(zhí)行效率較高，適用于現(xiàn)代制造業(yè)、加工業(yè)的實(shí)際生產(chǎn)。

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

[2] 劉德全, 藤弘飛. 矩形件排樣問(wèn)題的遺傳算法求解[J].小型微型計(jì)算機(jī)系統(tǒng), 1998, 19(12): 20-25.

[3] Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem [J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[4] Yeung L H W, Tang W K S. A hybrid genetic approach for garment cutting in the clothing industry [J]. IEEE Transactions on Industrial Electronics, 2003, 50(3): 449-455.

[5] Wei Lijun, Oon W C, Zhu Wenbin, et al. A skyline heuristic for the 2D rectangular packing and strip packing problems [J]. European Journal of Operational Research, 2011, 215(2): 337-346.

[6] Christoforos C, Fleszar K. A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts [J]. Computers & Operations Research, 2011, 38(10): 1443-1451.

[7] 龔志輝, 黃星梅. 二維矩形件優(yōu)化排樣算法的改進(jìn)研究[J]. 湖南大學(xué)學(xué)報(bào), 2003, 30(3): 47-49.

[8] 王金敏, 王保春, 朱艷華. 求解矩形布局問(wèn)題的自適應(yīng)算法[J]. 圖學(xué)學(xué)報(bào), 2012, 33(3): 29-33.

[9] Liu Haiming, Zhou Jiong, Wu Xinsheng, et al. Optimization algorithm for rectangle packing problem based on varied-factor genetic algorithm and lowest front-line strategy [C]//2014 IEEE Congress on Evolutionary Computation (CEC). Beijing: IEEE, 2014: 352-357.

Optimization Algorithm for Rectangle Packing Based on Improved Lowest Horizontal Line Method and Genetic Algorithm

Liu Haiming, Zhou Jiong, Wu Xinsheng, Luo Jiaxiang
(School of Automation Science and Engineering, South China University of Technology, Guangzhou Guangdong 510641, China)

For the issue of rectangle packing problem, traditional lowest horizontal line method might generate certain empty blocks that were not used, which would cause unnecessary waste of material. To solve the problem, heuristic estimate is introduced into search process to achieve rectangle filling for the empty blocks and improve utilization. For optimization packing sequence of rectangles using genetic algorithm, a new strategy of setting different genetic factors by stages of evolution process is applied to improve algorithm performance. The two improved methods are combined in union to solve the rectangle packing problem. The test data of packing show that the proposed algorithm can effectively improve packing results and improve utilization of material.

rectangle packing; optimization algorithm; lowest horizontal line; genetic algorithm

TP 391.72

A

2095-302X(2015)04-0526-06

2014-10-18；定稿日期：2015-01-12

廣東省科技計(jì)劃資助項(xiàng)目-工業(yè)高新技術(shù)領(lǐng)域(2014A010104004)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金重點(diǎn)資助項(xiàng)目(2014ZZ0033)

劉海明(1978–)，男，廣東陸河人，講師，博士。主要研究方向?yàn)橄到y(tǒng)優(yōu)化與調(diào)度、計(jì)算機(jī)輔助設(shè)計(jì)與優(yōu)化、智能優(yōu)化算法與智能系統(tǒng)。E-mail：hmliu@scut.edu.cn