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

《求解三維裝箱問題的遺傳算法研究【文獻綜述】》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、畢業(yè)設計文獻綜述計算機科學與技術(shù)求解三維裝箱問題的遺傳算法研究摘要：對三維裝箱問題進行了描述，闡述了研究求解三維裝箱問題的遺傳算法的意義。接著詳細介紹了該算法的實現(xiàn)原理和研究現(xiàn)狀，并通過對比和歸納，指出了目前存在的問題。最后在研究現(xiàn)狀的基礎上，提出了求解三維裝箱問題的遺傳算法的發(fā)展趨勢。關(guān)鍵詞：三維裝箱問題；遺傳算法；一、研究求解三維裝箱問題的遺傳算法的意義裝箱問題是物流企業(yè)在裝卸環(huán)節(jié)上必須面對的一個核心問題，裝載方案的好壞將直接影響著企業(yè)的利潤。因此，研究求解三維裝箱問題的遺傳算法，實現(xiàn)裝箱問題的優(yōu)化顯得尤為重要。三維裝箱問題即為物體在三維空間的擺放優(yōu)化問題，可以描述

2、為：長、寬、高分別為li、wi、hi的n個物體在多個集裝箱中擺放，在滿足一定的約束(重心位置約束、單箱重量約束、單箱空間利用率約束)條件下，使集裝箱利用率最高[1]。由于裝箱問題是NP問題，傳統(tǒng)算法的復雜度會隨著擺放物體的數(shù)量呈指數(shù)級別增加，不能應用到頻繁而龐大的裝載業(yè)務上。于是基于生物自然進化理論具備全局優(yōu)化搜索能力的遺傳算法[2]被眾多學者應用到裝箱問題上。如今，管理工程、工業(yè)工程等領(lǐng)域中的一些問題(例如人力資源分配、運輸計劃等)均可建議為裝箱[3]，所以尋找更準確、更有效的遺傳算法是當今裝箱問題研究者的心愿。二、求解三維裝箱問題的遺傳算法的研究現(xiàn)狀1.遺傳算法的實

3、現(xiàn)原理1）個體編碼及解碼將n個貨物按體積從小到大排序并1至n編號，m個箱子1至m編號，物品橫放編0，豎放編1，則解2:(1、3、6、8——0、1、1、0)可表示2號箱子中按0、1、1、0方位順序放置1、3、6、8貨物。2）適應度計算通過個體適應值的大小來評估群體中個體所對應裝載方案的優(yōu)劣，對于違反裝載容積約束、裝載質(zhì)量約束和裝載重心約束的個體，在求解其適應值的過程中要給于相應的懲罰以確保符合條件而較優(yōu)的個體有較大的生存機會[4]。3)實現(xiàn)過程選擇合適的編碼方式，產(chǎn)生初始群，計算初始群體的適應值，如果不滿足條件再進行選擇、交叉、變異、計算新一代群體的適應值，直到滿足條件為

4、止。結(jié)束的條件可以根據(jù)具體條件來選擇，可以以一定的代數(shù)為結(jié)束條件，也可以以兩代之間適應度之差小于某個固定的值為結(jié)束條件。2.裝箱問題的研究現(xiàn)狀從20世紀70年代初開始，裝箱問題就被廣泛地關(guān)注和研究[5]。到80年代末，各種近似求解裝箱問題的算法被提了出來，如下次適應、首次適應和調(diào)和算法等[6]。但這些算法都只針對一維、二維裝箱問題，因為相比之下三維裝箱問題的復雜性大得多，直到80年代后才出現(xiàn)了比較實用的算法：楊傳民等人[7]通過全面枚舉搜索方法來研究相同大小的立方體的裝箱優(yōu)化問題，使得求解的精度和效率上得到了提高。Mannchen[8]設計的樹搜索算法，理論上對三維箱體

5、布局有效，但隨著布局箱體的增多，解空間劇增，所以計算效率不能滿足實際需求。H．GEHRING[9]提出在深度方向按層布局的啟發(fā)式算法，提高了空間利用率和重心的平衡度。姜義東[10]等提出利用遍歷三叉樹結(jié)構(gòu)的方法對空間進行分解，雖然有效避免了空間干涉現(xiàn)象，但無法處理更復雜的約束。何大勇、查建中等[11]在簡單遺傳算法的基礎上做了改進，能處理多目標、多約束的問題；但在貨物很多時，應用遺傳算法對每件貨物進行整數(shù)編碼構(gòu)成的染色體，基因數(shù)量多，規(guī)模巨大，再加上眾多約束條件，導致算法收斂非常慢，甚至大多數(shù)情況下得不到可行解。E.E.Bischoff[12]等人針對多種物品單托盤裝載

6、問題（只考慮空間和穩(wěn)定性約束），從托盤缺少可用于支撐的垂直壁的特點和由底向上的擺放方式出發(fā)，提出了基于“平面”的算法。由底向上每次只放入一層最多由兩種物品組成的水平層，迭代填充和生成平面、水平層，獲得有效且具有高穩(wěn)定性的布局模式。算法通過設定的規(guī)則選擇合適的物品、平面、位置等布局參數(shù)，采用平面合并等方法提高平面利用率，進而生成一個較好的完整布局模式。雖然在擺放穩(wěn)定性方面表現(xiàn)不錯，但所得解的空間最優(yōu)平均利用率不高。3.遺傳算法的研究現(xiàn)狀進入90年代，遺傳算法開始變得熱門起來，尤其是在應用研究上。隨著它的應用領(lǐng)域擴大，利用遺傳算法進行優(yōu)化和規(guī)則學習的能力也顯著提高，同時產(chǎn)業(yè)

7、應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應用方面。1991年D.Whitey在他的論文中提出了基于領(lǐng)域交叉的交叉算子（Adjacencybasedcrossover），這個算子是特別針對用序號表示基因的個體的交叉，并將其應用到了TSP問題中，通過實驗對其進行了驗證。D.H.Ackley等提出了隨即迭代遺傳爬山法（StochasticIteratedGeneticHill-climbing，SIG