田大肥 申 喜 周 巍

(中國艦船研究設計中心 武漢 430064)

二維裝箱問題的遺傳算法求解*

田大肥 申 喜 周 巍

(中國艦船研究設計中心 武漢 430064)

通過分析人工排列的思考過程和實際經驗,提出一種解決二維規(guī)則物體排列問題的算法。通過計算可放置點和可放置空間,高效解決物塊的排列問題。應用遺傳算法,求得最優(yōu)的排列方案。實際應用證明了該算法的有效性。

二維裝箱; 可放置點; 可放置空間; 遺傳算法

Class Number TP391.7

1 引言

二維裝箱問題是隨著計算機技術的產生而出現(xiàn)的,大量出現(xiàn)在機械制造、皮革服裝加工、汽車、造船、貨物裝載以及大規(guī)模集成電路板的設計等領域[1]。排樣布局的優(yōu)劣直接與材料的成本及經濟效益相關。目前主要存在的問題是材料的利用率偏低,造成巨大的浪費。對于規(guī)模較大的生產廠家來說,即使是材料利用率有很小的提升,也會帶來巨大的經濟效益。

根據(jù)目標的不同,二維裝箱問題可以分為以下幾類:

· 箱柜裝載問題(bin packing problem):給定一些不同類型的矩形箱子和一些規(guī)格一致的矩形容器,問題是要把所有箱子裝入最少數(shù)量的容器中。

· 容器裝載問題(container packing problem):所有箱子要裝入一個寬度為有限數(shù)值的矩形容器,它的高度不限,要求將所有物品放入容器中,并取得最小的放置高度,使容器利用率最高。

· 背包裝載問題[2](knapsack loading problem):每個箱子有一定的價值,背包裝載是選擇箱子的一部分裝入容器中,使得裝入容器中的箱子總價值最大[3]。

本文主要研究第二類裝箱問題。

目前提出的基于遺傳算法的裝箱算法主要有BL(bottom left)算法、下臺階算法、最低水平線算法和基于最低水平線的搜索算法。其中下臺階算法是在BL算法的基礎上的改進,最低水平線算法又在此基礎上改進,基于最低水平線的搜索算法則是在最低水平線算法基礎上又提出的改進[4～6]。本文提出一種新的排列方法,通過對多組實驗結果進行測試比較,證明了本文算法的有效性。

2 問題描述

對于所要研究的二維裝箱問題,可作如下抽象:給定一個矩形容器A,其寬度和高度分別為W和H。另有n個矩形物塊,其寬度和高度分別為wi,hi(i=1,2,…,n)。確定排列方案,將所有物塊放入矩形箱子,并使其所占用的空間最小。

排列過程中須滿足以下要求:

1) 放入的任意物塊的任意部分均不超出箱子邊界。

2) 任意兩個物塊的任意部分互不重疊[7]。

3 裝箱算法

在人工排列的過程中,為了使物塊占用的空間最小,我們總是試圖將物塊放置在盡可能低,且盡可能靠左的位置。在將物塊放得盡可能低的過程中,物塊最終會受到之前放入的物塊的上邊緣或是箱子底面邊界的阻擋。在將物塊放得盡可能靠左的過程中,物塊最終也會受到之前放入的物塊的右側邊緣或是箱子左側邊界的阻擋。作為物塊的左側邊與下側邊的交點,其左下角點在放置過程中會同時受到之前放入的物塊的上邊緣或是箱子底面邊界和之前放入的物塊的右邊緣或是箱子左側邊界的阻擋。所以在放置物塊的過程中,會以其左下角點作為參考點(reference point)。

3.1 可放置點

以箱子的左下角點為原點,以箱子的底邊為x軸,以箱子左側邊為y軸。在放入第一個物塊時,坐標原點為坐標系中唯一的可放置點(available point)。在放入第一個物塊之后,位于坐標原點的可放置點被占用,同時在物塊的右下角點和左上角點產生兩個新的可放置點。第一個放入的物塊的寬度和高度分別為w1和h1,則產生的兩個可放置點坐標為(w1,0)、(0,h1)。假設第二個箱子占用了點(w1,0),則刪除(w1,0)點,同時增加因物塊的右側面而產生的可放置點(w1+w2,0)。至于物塊的上側面產生的可放置點,應當有以下幾種情況:

1) 如果h2>h1,則產生可放置點(0,h2);

2) 如果h2=h1,則產生的可放置點與第一個物塊產生的可放置點(0,h1)重合;

3) 如果h2

從放置過程中可以看出,在放入一個物塊的過程中,占用了一個可放置點,同時最多增加二個可放置點。因此,考慮第i個箱子時,最多有i個可放置點。而在實際操作過程中我們發(fā)現(xiàn),由于重疊等情況的出現(xiàn),可放置點通常會少于i個。

圖1 可放置點

3.2 可放置空間

為了將物塊放入某個可放置點,需要該點在x軸方向和y軸方向有足夠的空間,至少能夠容納物塊的寬度和高度。將x軸方向的可放置空間(available space)稱為x空間,將y軸方向的可放置空間稱為y空間。一般情況下x空間為從可放置點的橫坐標開始,一直向右延伸直到接觸到已放入物塊的側面或是箱子的壁為止的這段距離。同樣,y空間為從可放置點的縱坐標開始,一直向上延伸直到接觸到已放入物塊的底面或是箱子的壁為止的這段距離。

圖2 可放置空間

在得到了可放置空間之后,物塊的放置過程就變成了簡單的排序與比較過程,不需要將物塊放入某個可放置點,就能檢驗其是否合適放入該點。極大地簡化了計算過程,提高了計算速度。

3.3 可放置點的刷新

在放入一個新的物塊之后,會產生新的可放置點,這就需要對可放置點的集合進行刷新。同時在放入物塊的過程中,有些可放置點雖然沒有被占用,但會被物塊覆蓋,這種情況下就需要對可放置點的坐標進行調整。對可放置點進行調整的過程中,也需要對可放置空間進行調整,這個過程稱為可放置點的刷新(renovation of available points)。

尤其需要說明的是,可放置點不會因為被覆蓋或是被阻擋而刪除,只是其x坐標或是y坐標以及x空間或是y空間會受到影響?？煞胖命c只會因為以下幾種原因被刪除:

1) 被放入的物塊占用;

2) 因放入物塊的影響使得可放置點的x空間小于尚未放入的物塊中最小的寬度值,或是可放置點的y空間小于尚未放入的物塊中最小的高度值;

3) 后放入的物塊產生的可放置點與現(xiàn)有的可放置點出現(xiàn)重疊,則刪除其中的一個。

圖3 可放置點的刷新

這樣就使一些沒有被當前放入的物塊利用就被封閉在了一個小空間里,但依然有希望被后續(xù)放入的物塊利用的可放置點得以保留。這樣做可以有效地提高空間的利用率,同時降低對放置順序的敏感性,可以更快地接近最優(yōu)的排列方案。這也是本算法的重要特點。

3.4 裝箱算法

綜上,我們可以得到2D-packing算法。算法以物塊集合B={b1,b2,…,bn}為輸入,返回此次排列得到的空間利用率,用use表示可放置點的集合,矩形容器的寬度和高度分別為W和H。

算法:2D-packing(B)

初始可放置點use=[0,0,W,H];

For i=1:n

待放置物塊的寬度為wi,高度為hi;

use按x坐標和y坐標由小到大順序排列;

use中有m個可放置點;

Forj=1:m

If 第j個可放置點的x空間≥wi且y空間≥hi

返回j

End

End

占用第j個可放置點;

計算右側邊產生的可放置點;

計算該點的可放置空間;

計算上側面產生的可放置點;

計算該點的可放置空間;

將新產生的可放置點放入use集合的末尾;

Fork=r:-1:1

分別計算對各可放置點及可放置空間的影響;

End

End

計算所有物塊的面積和;

返回所有物塊中最大的y坐標;

計算空間利用率。

在該算法中,初始可放置點為坐標原點,可放置空間為箱子的寬度和高度,按順序放置每個物塊。將所有可放置點分別按x坐標和y坐標由小到大排列,依次檢測每個可放置點的x空間和y空間能否容納將要放入的物塊,選擇占用第一個滿足要求的可放置點。然后計算物塊產生的新的可放置點,向可放置點集合中加入新產生的點并刪除已經占用的點。計算新放入的物塊對其他可放置點及其可放置空間的影響。算法結束時,返回該排列方案對應的空間利用率,即裝箱物塊的總面積對箱子面積的比率。

4 遺傳算法求解過程

遺傳算法的主要運算過程如下:

1) 編碼:解空間中的解數(shù)據(jù)x,作為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱為編碼。遺傳算法在進行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結構數(shù)據(jù),這些串結構數(shù)據(jù)的不同組合就構成了不同的點。在本算法中,將每一種排列方案編碼成一個二進制字符串。

2) 初始群體的生成:隨機產生N個初始串結構數(shù)據(jù),每個串結構數(shù)據(jù)稱為一個個體,N個個體構成了一個群體。遺傳算法以這N個串結構作為初始點開始迭代。設置進化代數(shù)計數(shù)器t←0;設置最大進化代數(shù)T;隨機生成M個個體作為初始群體P(0)。

3) 適應度值評價檢測:適應度函數(shù)表明個體或解的優(yōu)劣性。對于不同的問題,適應度函數(shù)的定義方式不同。根據(jù)具體問題,計算群體P(t)中各個個體的適應度。在本算法中,空間利用率是最重要的適應度評價標準。

4) 選擇:將選擇算子作用于群體。

5) 變異:將交叉算子作用于群體。

6) 變異:將變異算子作用于群體。

群體P(t)經過選擇、交叉、變異運算后得到下一代群體P(t+1)。

7) 終止條件判斷:若t≤T,則t←t+1,轉到步驟2);若t>T,則以進化過程中所得到的具有最大適應度的個體作為最優(yōu)解輸出,終止運算[8～10]。

遺傳算法有三個基本操作:選擇(selection)、交叉(crossover)和變異(mutation)。

1) 選擇。選擇的目的是為了從當前群體中選出優(yōu)良的個體,使它們有機會作為父代為下一代繁殖子孫。根據(jù)各個個體的適應度值,按照一定的規(guī)則或方法從上一代群體中選擇出一些優(yōu)良的個體遺傳到下一代群體中。遺傳算法通過選擇運算體現(xiàn)這一思想,進行選擇的原則是適應性強的個體為下一代貢獻一個或多個后代的概率大。這就體現(xiàn)了達爾文的適者生存原則。

2) 交叉。交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體,新個體組合了父輩個體的特性。將群體內的各個個體隨機搭配成對,對每一個個體,以某個概率交換它們之間的部分染色體。交叉體現(xiàn)了信息交換的思想。

3) 變異。變異操作首先在群體中隨機選擇一個個體,對于選中的個體以一定的概率隨機改變串結構數(shù)據(jù)匯總某個串的值,即對群體中的每一個個體,以某一概率改變某一個或某一些基因座上的基因值為其他的等位基因。同生物界一樣,遺傳算法中變異發(fā)生的概率很低。變異為新個體的產生提供了機會[11～12]。

5 算例分析

為測試算法的性能,本文對文獻[13]中提到的BL算法無法解決的圖形排列問題及文獻[13]中的算例進行求解。

算例1 將一個8×8的方形分成8個大小不完全相等的小矩形。如圖4所示,其對應的編碼也已經標注在圖4上。如果用BL算法,即使遍歷所有的排列方案,也不可能得到最優(yōu)排樣圖。用本文算法,可以很容易地得到圖5所示的排樣結果,對應的裝入順序為Popt={1,2,3,7,5,6,4,8}。

圖4 最優(yōu)排樣圖

圖5 得到的一個最優(yōu)解

算例2 對于文獻[14]中的算例,將一個40×15的矩形分成25個大小不完全相等的小矩形。如圖6所示,其對應的編碼已經標注在圖6上?，F(xiàn)以寬度為40,高度不限的箱子為例,將分成的25個物塊放入箱中,求解最小的排樣高度。文獻[14]在第2000代終止時得到的高度為17,應用本文算法,在群體規(guī)模與文獻[14]同樣為m=20的情況下,取交叉概率為1,單點交叉與雙點交叉各占一半,變異概率pm1=pm2=0.3,在100代內終止時能夠求得高度為17的排列結果。如圖7所示,對應的裝入順序為Popt={2,9,20,25,22,19,12,5,11,10,3,8,6,17,7,23,15,21,16,14,1,18,13,4,24}

圖6 最優(yōu)排樣圖;高度15

圖7 進化100代得到的一個最優(yōu)解;高度17

6 結語

本文對二維空間布局問題進行了研究,提出了新的解決方法。從目前的實驗結果來看,本文算法更為簡便高效。而且此方法經過適當?shù)母膭又?可以應用于箱柜裝載問題(bin packing problem)和三維空間內的裝箱問題,同時也可以應用于有瑕疵材料的下料問題。

[1] Lodi A, Martello S, Vigo D. A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems[J]. Annals of Operations Research,2004,131:203-213.

[2] 樂天.遺傳算法求解0/1背包問題的綜述[J].浙江海洋學院學報(自然科學版),2013,32(1):71-74.

[3] 張德福,魏麗軍,陳青山,等.三維裝箱問題的組合啟發(fā)式算法[J].軟件學報,2007,18(9):2083-2089.

[4] 郝洪霆.有瑕疵材料二維下料問題的研究和應用[D].濟南:山東大學,2008.

[5] 劉艷娟.二維裝箱問題的啟發(fā)式算法研究[D].廈門:廈門大學,2007.

[6] 李玉賢.利用混合單親遺傳算法求解二維裝箱問題[D].內蒙古:內蒙古大學,2011.

[7] 黃少麗,楊劍,侯桂玉,等.解決二維下料問題的順序啟發(fā)式算法[J].計算機工程與應用,2011,47(13):234-237.

[8] 趙新超,韓宇,艾文寶.求解背包問題的一種改進遺傳算法[J].計算機工程與應用,2011,47(24):88-89.

[9] 王秋芬,梁道雷.一種求解0/1背包問題的啟發(fā)式遺傳算法[J].計算機應用與軟件,2013,30(2):33-37.

[10] 田建立,晁學鵬.求解0/1背包問題的混沌遺傳算法[J].計算機應用研究,2011,28(8):131-133.

[11] 雷英杰,張善文,李續(xù)武,等.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2011:11-13.

[12] 王麗娟.用單親遺傳算法求解二維裝箱問題[D].內蒙古:內蒙古大學,2012.

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

[14] Stefan Jokobs. On Genetic Algorithms for the Packing of Polygons[J]. European Journal of Operational Research,1996,88:165-181.

Genetic Algorithm of Two-Dimensional Container Packing

TIAN Dafei SHEN Xi ZHOU Wei

(China Ship Develop and Design Center, Wuhan 430064)

By analyzing the process and experience of human packing, an algorithm for solving two-dimensional packing is proposed. Packing problem is solved with high efficiency by creating and calculating the available points and available spaces. Genetic algorithm is used to get optimal arrangement. Practical applications show the validity and efficiency of the algorithm.

two-dimensional packing, available point, available space, genetic algorithm

2013年7月8日,

2013年8月21日

國防科工局基礎科研重點項目(編號:A0820110001)資助。

田大肥,男,碩士研究生,研究方向:艦船總體研究與設計。申喜,男,碩士研究生,研究方向:艦船電力系統(tǒng)的優(yōu)化設計。周巍,女,碩士,研究員,研究方向:艦船總體研究與設計。

TP391.7

10.3969/j.issn1672-9730.2014.01.016