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

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

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

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