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

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

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

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

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

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

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

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

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