求解二維矩形裝箱問題的算法研究.pdf

1、裝箱問題是一個(gè)經(jīng)典的組合優(yōu)化問題。簡單地說,裝箱問題就是將若干不同尺寸的物體互不重疊地放入有一定容量的箱子中以達(dá)到某種最佳目標(biāo)。裝箱問題被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域和工業(yè)領(lǐng)域,多處理器任務(wù)調(diào)度、內(nèi)存管理、貨物裝載以及原料切割等都是裝箱問題在實(shí)際應(yīng)用中的具體體現(xiàn)。因此,研究裝箱問題具有重要的理論意義和應(yīng)用價(jià)值。
　　 從二十世紀(jì)七十年代起,學(xué)術(shù)界就對裝箱問題進(jìn)行了廣泛而深入的研究,該問題又是NP完全問題,如果用精確算法求解裝箱問題,

2、勢必帶來計(jì)算量的組合爆炸,因此學(xué)者提出了很多求解該問題的啟發(fā)式算法。
　　 本文首先對裝箱問題的研究現(xiàn)狀、問題分類及求解算法進(jìn)行了綜述和分析,然后重點(diǎn)對二維矩形裝箱問題進(jìn)行研究。在總結(jié)和概括了當(dāng)前主要的裝箱優(yōu)化算法的基礎(chǔ)上,對已有的砌墻式啟發(fā)算法進(jìn)行改進(jìn),并結(jié)合遺傳算法設(shè)計(jì)了一種新的算法:基于快速啟發(fā)式分層思想和遺傳算法的求解算法。
　　 在本文設(shè)計(jì)的啟發(fā)式分層算法中,改進(jìn)了原有砌墻式算法的分層規(guī)則,每一層由一個(gè)或一系列

3、等寬的矩形條構(gòu)成,在選擇放入矩形的規(guī)則中提出了適應(yīng)度的概念。在決定輸入矩形序列方面采用了遺傳算法,根據(jù)問題的實(shí)際情況,在遺傳算法的種群初始化中采取了多種群初始化,并融入一定的啟發(fā)式規(guī)則來確保初始種群染色體的優(yōu)良性,在遺傳操作過程中采用了分配擇優(yōu)保存,環(huán)狀交叉變異,自適應(yīng)交叉變異概率等改進(jìn)的遺傳算子來保證遺傳算法的收斂性。
　　 實(shí)驗(yàn)結(jié)果表明,本文設(shè)計(jì)的算法比原有的分層式算法有較大的改進(jìn)。而且求解質(zhì)量與一些優(yōu)秀的算法如:BF+GA