求解三維裝箱問題的遺傳算法研究【文獻(xiàn)綜述】

1、畢業(yè)設(shè)計文獻(xiàn)綜述畢業(yè)設(shè)計文獻(xiàn)綜述計算機(jī)科學(xué)與技術(shù)計算機(jī)科學(xué)與技術(shù)求解三維裝箱問題的遺傳算法研究求解三維裝箱問題的遺傳算法研究摘要：對三維裝箱問題進(jìn)行了描述，闡述了研究求解三維裝箱問題的遺傳算法的意義。接著詳細(xì)介紹了該算法的實現(xiàn)原理和研究現(xiàn)狀，并通過對比和歸納，指出了目前存在的問題。最后在研究現(xiàn)狀的基礎(chǔ)上，提出了求解三維裝箱問題的遺傳算法的發(fā)展趨勢。關(guān)鍵詞：三維裝箱問題；遺傳算法；一、研究求解三維裝箱問題的遺傳算法的意義裝箱問題是物流企業(yè)

2、在裝卸環(huán)節(jié)上必須面對的一個核心問題，裝載方案的好壞將直接影響著企業(yè)的利潤。因此，研究求解三維裝箱問題的遺傳算法，實現(xiàn)裝箱問題的優(yōu)化顯得尤為重要。三維裝箱問題即為物體在三維空間的擺放優(yōu)化問題，可以描述為：長、寬、高分別為li、wi、hi的n個物體在多個集裝箱中擺放，在滿足一定的約束(重心位置約束、單箱重量約束、單箱空間利用率約束)條件下，使集裝箱利用率最高[1]。由于裝箱問題是NP問題，傳統(tǒng)算法的復(fù)雜度會隨著擺放物體的數(shù)量呈指數(shù)級別增加，

3、不能應(yīng)用到頻繁而龐大的裝載業(yè)務(wù)上。于是基于生物自然進(jìn)化理論具備全局優(yōu)化搜索能力的遺傳算法[2]被眾多學(xué)者應(yīng)用到裝箱問題上。如今，管理工程、工業(yè)工程等領(lǐng)域中的一些問題(例如人力資源分配、運輸計劃等)均可建議為裝箱[3]，所以尋找更準(zhǔn)確、更有效的遺傳算法是當(dāng)今裝箱問題研究者的心愿。二、求解三維裝箱問題的遺傳算法的研究現(xiàn)狀1.遺傳算法的實現(xiàn)原理1）個體編碼及解碼將n個貨物按體積從小到大排序并1至n編號，m個箱子1至m編號，物品橫放編0，豎放編

4、1，則解2:(1、3、6、8——0、1、1、0)可表示2號箱子中按0、1、1、0方位順序放置1、3、6、8貨物。2）適應(yīng)度計算通過個體適應(yīng)值的大小來評估群體中個體所對應(yīng)裝載方案的優(yōu)劣，對于違反裝載容積約束、裝載質(zhì)量約束和裝載重心約束的個體，在求解其適應(yīng)值的過程中要給于相應(yīng)的懲罰以確保符合條件而較優(yōu)的個體有較大的生存機(jī)會[4]。3)實現(xiàn)過程傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在求解速

5、度方面更有競爭力。2002年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題。2005年，江雷等針對并行遺傳算法求解TSP問題探討了使用彈性策略來維持群體的多樣性使得算法跨過局部收斂的障礙向全局最優(yōu)解方向進(jìn)化[13]。4.存在的問題遺傳算法的準(zhǔn)確性取決于初始解、適應(yīng)度函數(shù)及其遺傳算子，目前三維

6、裝箱問題的算法都只是在某一程度上逼近最優(yōu)解，但仍需通過實踐挖掘更有效的適應(yīng)度函數(shù)、遺傳算子等，此外，求解的過程中都把物品、箱子理想化為長方體以及不考慮一些約束條件，雖然這樣降低了求解的復(fù)雜度，但與實際不符。三、求解三維裝箱問題的遺傳算法的發(fā)展趨勢通過文獻(xiàn)閱讀和對國內(nèi)外研究現(xiàn)狀的分析和綜合，我認(rèn)為求解三維裝箱問題的遺傳算法的發(fā)展趨勢如下：1.隨著裝箱模型滲入到各個行業(yè)，但行業(yè)間約束條件都大不相同，所以裝箱軟件可以向多元化發(fā)展，將來可以對各

7、種可處理的問題進(jìn)行建模，并接受相應(yīng)的約束條件輸入，然后輸出滿意的解。2.對于這些啟發(fā)式算法，尋找更有效的參數(shù)、函數(shù)仍是重中之重。3.在電腦運行處理速度變得更快的情況下，可考慮在傳統(tǒng)算法與遺傳算法之間折中，使得求解更加精確，但又不超出時間的下限。4.隨著人工智能技術(shù)的發(fā)展，像神經(jīng)網(wǎng)絡(luò)等一些智能學(xué)習(xí)算法也會在裝箱問題有用武之地。四、參考文獻(xiàn)[1]鐘石泉王雪蓮.多箱型三維裝箱問題及其優(yōu)化研究[J].計算機(jī)工程與應(yīng)用，200945（22）：19

8、7~199[2]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，2000[3]方平李娟.求解裝箱問題的遺傳算法[J].南昌航空工業(yè)學(xué)院學(xué)報19982（2）：21~24[4]王長春，李銳，孫友.基于遺傳算法的軍用集裝箱裝載優(yōu)化[J].物流科技，2007，5[5]HGehringKMenschnerMMeyer.Acomputerbasedheuristicfpackingpooledshipmentcontainers.Eu