基于雙層啟發(fā)式遺傳算法的三維裝箱問題

于明正， 徐 斌， 陳 佳

(大連海事大學(xué)航運(yùn)經(jīng)濟(jì)與管理學(xué)院，大連 116026)

三維裝箱問題是一類多模式資源受限項(xiàng)目調(diào)度(non-deterministic polynomial, NP-hard)問題[1-2]，它通過研究如何在給定箱容器內(nèi)建立組合優(yōu)化方案從而達(dá)到優(yōu)化目標(biāo)，對于物流貨物裝載、資源分配、多處理器任務(wù)調(diào)度等方面的研究具有深遠(yuǎn)的學(xué)術(shù)前景和重要的實(shí)際應(yīng)用價(jià)值。由于裝箱算法的計(jì)算結(jié)果是不可量化的，所以國內(nèi)外的學(xué)者常采用啟發(fā)式算法來計(jì)算接近于最佳方案的整體最優(yōu)解[3-5]。

George等[6]最先提出以空間分割為原則的啟發(fā)式算法，建立了一種標(biāo)準(zhǔn)的裝箱秩序，張德富等[7-9]以此為基礎(chǔ)，受實(shí)際生產(chǎn)活動(dòng)中砌墻原理的影響提出新的啟發(fā)式算法，通過調(diào)入“參考線”這一概念來引導(dǎo)整個(gè)箱容器的裝填過程。這種算法可以降低使用以空間分割原則的啟發(fā)式算法進(jìn)行裝填時(shí)，因?yàn)闆]有引導(dǎo)約束而產(chǎn)生的局部裝填混亂，從而更加接近真實(shí)的最優(yōu)解。但是這種算法的最終結(jié)果依賴于初始裝箱順序，如果初始裝箱順序的質(zhì)量不高，很容易陷入局部最優(yōu)的情況。翟鈺[10]結(jié)合遺傳的概念提出了混合遺傳算法，這種算法減小了初始解對裝箱方案的影響，但算法穩(wěn)定性極差。由于在遺傳演化過程中未能保留優(yōu)秀的裝箱序列，導(dǎo)致對下一代可行解的搜索缺少信息指引，所以每次運(yùn)算后得到的空間利用率差距明顯。

基于以上問題，借鑒二層規(guī)劃的思想[11]，根據(jù)三維裝箱問題的特點(diǎn)與遺傳算法的規(guī)律對混合遺傳算法進(jìn)行改進(jìn)，提出一種新的遺傳演化方法，分別以廣度和深度兩種不同的搜索方向?qū)⒄麄€(gè)算法分為兩層進(jìn)行，盡可能綜合遺傳算法的優(yōu)勢來提高裝箱方案的質(zhì)量。通過兩種不同的遺傳層解決算法中出現(xiàn)的局部最優(yōu)和穩(wěn)定性問題，從而縮小最優(yōu)解與算法最佳方案的差距，提出雙層啟發(fā)式遺傳的思路來解決三維裝箱問題。

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

討論的三維裝箱問題基于以下幾個(gè)前提條件[12]：

(1)箱容器與箱體均為長方體。

(2)箱體的尺寸不同且均小于箱容器尺寸。

(3)箱體的擺放方向與箱容器邊界方向平行，有兩種擺放形式。

(4)忽略已放置箱體之間的空隙。

根據(jù)以上假設(shè)及問題描述，記符號(hào)li、wi、hi表示箱體i(i=1, 2, 3, …,n)的長、寬、高；L、W、H表示箱容器的長、寬、高；αi表示箱體i的放置狀態(tài)，αi=0代表箱體i沒有被裝入箱容器中，αi=1代表箱體i已被裝入箱容器中，同時(shí)存在坐標(biāo)(xi，yi，zi)表示箱體i在箱容器中的放置點(diǎn)位置，建立基于雙層啟發(fā)式遺傳算法的三維裝箱問題數(shù)學(xué)模型。

目標(biāo)函數(shù)的建立：

(1)

約束條件：

(2)

(3)

(4)

(5)

2 算法設(shè)計(jì)

2.1 基于三維裝箱的啟發(fā)式算法

基于三維裝箱的啟發(fā)式算法大體上是以空間分割為原則的裝箱思想結(jié)合層的概念并加入“參考線”來限制裝箱趨勢而形成的啟發(fā)式算法。其中，算法的核心部分是描述箱體的裝入及其裝入后產(chǎn)生的3個(gè)獨(dú)立空間。

假設(shè)箱容器內(nèi)坐標(biāo)為(0, 0, 0)處放入第一個(gè)箱子，箱子的長寬高分別為a1、b1、c1，如圖1所示，根據(jù)空間分割原則，下一個(gè)箱子的可放置點(diǎn)有3個(gè)，分別為(0, 0,c1)、(0,b1， 0)、(a1， 0, 0)。如果第二個(gè)箱子被放置在(0, 0,c1)處，且長寬高分別為a2、b2、c2，根據(jù)空間分割原則，第三個(gè)箱子的可放置點(diǎn)就有5個(gè)，分別是(0,b1， 0)、(a1， 0, 0)、(0, 0,c1+c2)、(0,b2，c1)、(a2， 0,c1)。以此類推可知，假設(shè)一個(gè)長寬高為a、b、c的箱子選取了坐標(biāo)為(x，y，z)的可放置點(diǎn)，那么實(shí)際上就是刪掉了可放置點(diǎn)(x，y，z)，增加了(x，y，z+c)、(x，y+b，z)、(x+a，y，z)3個(gè)新的可放置點(diǎn)[13-16]。

圖1 空間分割示意圖Fig.1 The diagram for spatial segmentation

綜合上述思路并引入“參考線”，以層的概念對混合啟發(fā)式算法進(jìn)行以下偽代碼形式的描述，如算法1所示。

算法1：混合啟發(fā)式裝箱算法

Rx← 0，Rz← 0，iGroup← {(0,0,0)}，bGroup←BoxList;

fort← 0 tobGroup.lengthdo

fors← 0 toiGroup.lengthdo

if 箱子bGroup[t]可以放入位置iGroup[s]中 then

pGroup←bGroup[t]，iGroup[s];

對iGroup，Rx，Rz進(jìn)行一次更新；

break;

end if

end for

ifRx為0或達(dá)到極值 then

if 箱子bGroup[t]可放入位置(0, 0,Rz)中 then

pGroup←bGroup[t]，(0, 0,Rz)；

對iGroup，Rx，Rz進(jìn)行一次更新；

else

Rz取值范圍內(nèi)最大化；

t←t-1；

continue；

end if

else

fors← 0 toiGroup.length且x達(dá)到極值y為0 do

if 箱子bGroup[t]可放入位置iGroup[s]中 then

pGroup←bGroup[t]，iGroup[s];

對iGroup，Rx，Rz進(jìn)行一次更新；

break;

end if

end for

Rx取值范圍內(nèi)最大化；

t←t-1；

continue；

end if

end for

2.2 二層規(guī)劃與混合遺傳算法

2.2.1 混合遺傳算法的改進(jìn)

利用新遺傳演化方法設(shè)計(jì)的混合遺傳算法計(jì)算出的最佳裝箱方案符合裝箱問題的最基本需求，但經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)，裝箱方案的前半部分序列幾乎不會(huì)改變。這種情況意味著算法的最佳方案很大程度上取決于初始可行解的狀態(tài)。在此基礎(chǔ)上詳細(xì)地對三維裝箱過程進(jìn)行分析，利用箱體裝入后染色體編碼所表現(xiàn)的特點(diǎn)可以進(jìn)一步在遺傳算法的結(jié)合上提出改進(jìn)方法，從啟發(fā)式算法的裝填思想和生活常識(shí)來看，一個(gè)裝箱順序的優(yōu)劣與否并不是由單獨(dú)一個(gè)箱體的位置來決定的，一段連續(xù)的裝箱序列或者說一部分箱體編碼區(qū)間才是決定整個(gè)裝箱效果是否優(yōu)秀的關(guān)鍵。所以如果在混合遺傳算法的基礎(chǔ)上，增加一層可以提高搜索廣度的遺傳迭代，這樣可以縮短得到的最佳裝箱方案與最優(yōu)解之間的差距。這樣就用到了二層規(guī)劃的概念，上層遺傳使用搜索范圍不受限制的方法找到一個(gè)基因良好的可行解，在上層的基礎(chǔ)上加入上述混合遺傳算法作為下層遺傳進(jìn)行深度搜索，找到更優(yōu)秀的可行解。

2.2.2 二層規(guī)劃策略

圖2所示為基于雙層啟發(fā)式遺傳算法流程。上層遺傳使用選擇、交叉、變異等不受限的遺傳演化形式，這是為了加大可行解的搜索范圍，找到一個(gè)足夠優(yōu)秀的可行解；下層遺傳在上層遺傳的基礎(chǔ)上對這個(gè)可行解進(jìn)行有目的的多層次變異，經(jīng)過迭代進(jìn)化得到最優(yōu)解。從宏觀上對算法進(jìn)行分析，上層遺傳是面向廣度的搜索，而下層遺傳是面向深度的搜索，結(jié)合兩層遺傳的特點(diǎn)綜合使用可以找到最合適的裝箱方案。

圖2 雙層遺傳算法流程Fig.2 Flow chart for double-layer genetic algorithm

2.3 下層遺傳算法的設(shè)計(jì)

2.3.1 編碼預(yù)處理與染色體編碼

在染色體編碼之前，要對箱體編碼進(jìn)行相關(guān)的預(yù)處理：將n個(gè)箱體按照體積由大到小的順序依次編碼，i=1, 2, 3, …,n。

染色體在編碼時(shí)主要考慮箱體裝入順序的約束，一個(gè)染色體對應(yīng)一個(gè)編碼長度為n的基因段S1～n=(S1，S2，S3， …,Sn)，其中Sk表示第k位放置次序上箱體的編號(hào)i，一個(gè)位置次序k對應(yīng)一個(gè)箱體i并且S1～n內(nèi)的基因段是不可重復(fù)排列的。對于遺傳算法而言，一個(gè)編碼長度n的染色體S=(S1，S2，S3， …,Sn) 表示為三維裝箱的一個(gè)箱體組合裝入過程。

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

要求在滿足條件約束的情況下盡可能多地裝入箱體，要求箱容器的空間浪費(fèi)最少，所以決定裝箱方案好壞的因素就是箱容器的空間利用率，空間利用率越大裝箱效果越好。如式(6)所示，適應(yīng)度函數(shù)F直接選取目標(biāo)函數(shù)來使用。

(6)

2.3.3 選擇算子

遺傳過程使用輪盤賭選擇法進(jìn)行選擇算子。不同于傳統(tǒng)方法利用適應(yīng)度占比進(jìn)行概率選擇，各個(gè)染色體的適應(yīng)度差值并不明顯，因此在計(jì)算概率占比之前先對適應(yīng)度進(jìn)行處理，已知染色體Si的適應(yīng)度為f(Si)，其中最大適應(yīng)度為maxF，最小適應(yīng)度為minF，設(shè)置一個(gè)浮動(dòng)誤差值?，處理后的f(Si)為

(7)

假設(shè)遺傳算法的種群數(shù)量為M，染色體Si的適應(yīng)度為f(Si)，計(jì)算染色體Si的選擇概率Pi為

(8)

利用選擇概率計(jì)算累積概率Qk，即

(9)

輪盤賭選擇法詳細(xì)流程可以描述為隨機(jī)生成一個(gè)0～1的小數(shù)r，若r≤Q1，則染色體S1被選中，若Qk-1

2.3.4 變異算子

新的遺傳演化方法的特殊性主要體現(xiàn)在變異算子上，如圖3所示，在變異前要先確立有效裝箱區(qū)和無效裝箱區(qū)，選定一個(gè)可行解編碼次序按照裝箱算法依次放入，直到出現(xiàn)無法放入箱容器內(nèi)的箱體則停止放入，該箱體之前的次序則為有效裝箱區(qū)，其余的次序則都是無效裝箱區(qū)。

圖3 有效裝箱區(qū)示意圖Fig.3 Effective packing area

如圖4所示，當(dāng)變異開始時(shí)隨機(jī)選取有效裝箱區(qū)的一位基因A和無效裝箱區(qū)的一位基因B，基因A放入無效裝箱區(qū)基因B的位置，有效裝箱區(qū)內(nèi)基因A之后的基因依次向前移動(dòng)一位，基因B放入有效裝箱區(qū)的最后一位。此后對新的有效裝箱區(qū)再運(yùn)行一遍裝箱算法并評估長度，如果與之前的有效裝箱區(qū)長度一樣，則再從無效裝箱區(qū)中隨機(jī)選取一位基因放入有效裝箱區(qū)的尾部，重復(fù)上述步驟直至有效裝箱區(qū)的長度無法再增加，則一次完整的變異過程結(jié)束。

圖4 變異演示Fig.4 Variation diagram

2.4 上層遺傳算法的設(shè)計(jì)

2.4.1 算法描述

上層遺傳迭代的目的是為了增大染色體出現(xiàn)新相性的概率，從算法邏輯上來說，這種策略并沒有帶有優(yōu)秀的基因片段，且變異的過程缺乏完備性。下層遺傳迭代的目的是為了保留染色體大體組成的同時(shí)找到更加優(yōu)秀的染色體特性并傳遞到下一代中。這種策略可以保留可行解大部分的基因形式，從算法邏輯上來說，它是在一定基因基礎(chǔ)上的進(jìn)一步深化搜索。本文中的兩層遺傳編碼形式和適應(yīng)度函數(shù)一致，上層遺傳與下層遺傳的不同主要表現(xiàn)在遺傳演化方法上，接下來對上層遺傳算法進(jìn)行描述。

2.4.2 交叉算子

上層遺傳迭代將會(huì)用到交叉算法，由于染色體編碼是利用箱體編號(hào)組成的一組裝箱順序集合，對于這樣的編碼來說，組編碼之間的差異主要體現(xiàn)在基因的順序排列上，要保證組編碼內(nèi)基因的互異性的同時(shí)又能達(dá)到交叉的目的，因此采用能夠最大限度保留父輩基因相對次序的順序交叉(order crossover, OX)算法進(jìn)行交叉。根據(jù)以往諸多論文和理論的證明，這種交叉算法是可以滿足遺傳完備性要求的。之所以會(huì)在第一層遺傳上使用交叉是因?yàn)橐畲笙薅鹊乇ＷC可行解的廣度，擺脫遺傳迭代過程中陷入局部最優(yōu)的狀態(tài)。OX交叉算子的原理如圖5所示。

圖5 OX算法原理Fig.5 OX algorithm

2.4.3 變異算子

上層遺傳使用多次對換變異的方法，當(dāng)變異發(fā)生時(shí)，對指定染色體內(nèi)的隨機(jī)兩個(gè)不同的基因進(jìn)行位置交換，并且隨機(jī)進(jìn)行多次上述變換變異出新的染色體。每一次變異過程都是隨機(jī)選取可變異位置且只變異一次。

3 實(shí)例計(jì)算與結(jié)果實(shí)現(xiàn)

利用表1所示的測試數(shù)據(jù)集對上述算法進(jìn)行驗(yàn)證與分析，其中，在算法計(jì)算過程中需要設(shè)置的各個(gè)參數(shù)值如下：箱體數(shù)量goodsNum=200，上層遺傳運(yùn)行代數(shù)MAX_GEN1=500，下層遺傳運(yùn)行代數(shù)MAX_GEN2=500，種群規(guī)模scale=30，交叉概率Pc=90%，變異概率Pm=90%，浮動(dòng)誤差值?=0.005。本次實(shí)驗(yàn)選取長、寬、高分別為3、2、1 km的箱容器，要求將表1描述的箱體數(shù)據(jù)裝入箱容器后達(dá)到最優(yōu)的空間利用率。箱體的簡易裝載方案如表2所示，基于雙層啟發(fā)式遺傳算法計(jì)算后的結(jié)果如表3所示，遺傳過程中各代的適應(yīng)度最優(yōu)值分布如圖6所示，經(jīng)過上層遺傳迭代后，可以計(jì)算出的最佳空間利用率為89.579%，繼續(xù)對這個(gè)裝箱方案進(jìn)行下層遺傳迭代，空間利用率的數(shù)值可達(dá)到91.245%，裝箱方案達(dá)到進(jìn)一步的優(yōu)化。

表1 測試數(shù)據(jù)Table 1 Text data

表2 裝載方案Table 2 Loading solution

表3 三維裝箱計(jì)算結(jié)果Table 3 3D loading calculation result

圖6 適應(yīng)度最優(yōu)值分布Fig.6 Fitness optimal value distribution

如表4所示，利用表1的數(shù)據(jù)分別計(jì)算各個(gè)算法下的空間利用率。其中，A1是文獻(xiàn)[7]提出的啟發(fā)式算法，A2是結(jié)合本文提出的遺傳演化方法設(shè)計(jì)的混合遺傳算法，A3是文獻(xiàn)[10]提出的混合遺傳算法，A4是本文所提出的算法。A1沒有引入機(jī)器學(xué)習(xí)的概念，而且一旦初始裝箱順序固定，最終的裝箱方案也就無法改變；A2在此基礎(chǔ)上引入了遺傳算法，但是與初始裝箱順序相比，裝箱方案中裝箱序列的前5位沒有變化，這說明遺傳過程很容易陷入局部最優(yōu)，而本次實(shí)驗(yàn)所用的初始解預(yù)先會(huì)按照體積和長寬高排序，所以當(dāng)出現(xiàn)初始解的質(zhì)量不高的情況時(shí)，算法可能會(huì)產(chǎn)生隱患；A3算法的遺傳演化方法與A2不同，可行解的搜索是偏向廣度的，裝箱方案不受初始解的影響，但從結(jié)果來看，這種算法的穩(wěn)定性不高，可行解的搜索過程缺少導(dǎo)向性，最終方案的質(zhì)量依賴遺傳代數(shù)；A4算法引入二層規(guī)劃的概念，設(shè)計(jì)出兩種搜索方向不同的遺傳演化方法。實(shí)驗(yàn)結(jié)果表明，利用本文的算法進(jìn)行三維裝箱的效果是最好的。

表4 各類算法對比分析Table 4 Comparative analysis of various algorithms

實(shí)驗(yàn)可以使用Three.js架構(gòu)并結(jié)合Java Web等相關(guān)技術(shù)對實(shí)驗(yàn)方案進(jìn)行對應(yīng)的三維可視化實(shí)現(xiàn)，聯(lián)系實(shí)際的信息管理系統(tǒng)拓展出對某個(gè)領(lǐng)域的三維可視化功能，提升整個(gè)信息管理系統(tǒng)的綜合競爭力。對本次實(shí)驗(yàn)結(jié)果進(jìn)行三維可視化結(jié)果如圖7所示，從圖中可以看出，該方案可以滿足裝箱問題的最基本原則。

圖7 可視化結(jié)果Fig.7 The result of visualization

4 結(jié)論

針對混合遺傳算法在裝箱過程中因?yàn)檫z傳演化方法的缺陷導(dǎo)致局部最優(yōu)和算法穩(wěn)定性差的問題，結(jié)合二層規(guī)劃的思想，通過建立兩類遺傳層來提高最優(yōu)解搜索的廣度和深度，對局部最優(yōu)和穩(wěn)定性的缺陷進(jìn)行有效規(guī)避，進(jìn)而提升最終裝箱方案的質(zhì)量。實(shí)驗(yàn)結(jié)果表明，雙層啟發(fā)式遺傳算法要優(yōu)于其余的混合遺傳算法。同時(shí)可以將算法理論和結(jié)果用可視化技術(shù)描述出來，這樣可以為三維裝箱問題結(jié)合現(xiàn)代化管理思想實(shí)現(xiàn)規(guī)范的商業(yè)平臺(tái)模式提供一定的理論基礎(chǔ)。