基于多智能體進化算法的布圖方法及三維裝箱方法.pdf

1、在人類活動的方方面面，我們經(jīng)常會遇到裝箱問題（Bin PackingProblem，BPP），比如運輸業(yè)的裝貨問題、制造業(yè)中的切割問題、布局問題等等。裝箱問題是一種組合優(yōu)化問題，它的合理求解算法能在很大程度上節(jié)約資源、減少損耗。裝箱問題屬于NP-Hard問題，傳統(tǒng)的精確算法會為裝箱問題的求解過程帶來計算量的組合性爆炸，所以啟發(fā)式的求解方法成為了裝箱問題的理論研究和實際應用方面的第一選擇。
　　生活中的裝箱問題因為其裝載約束和優(yōu)化目

2、標不盡相同，所以解決方法也多種多樣。裝箱問題求解算法的核心部分是放置方案，即解碼算法。目前研究的裝箱問題主要有二維裝箱問題（Two-dimensional Bin Packing Problem，2D-BPP）和三維裝箱問題（Three-dimensional Bin Packing Problem，3D-BPP）。2D-BPP的求解算法已經(jīng)有了大量學者的研究，他們提出了一些比較好的啟發(fā)式算法。很多3D-BPP的解碼算法都是由2D-BP

3、P的解碼算法擴展而來，所以為了更好的研究3D-BPP，必須先了解2D-BPP的解碼方法。超大規(guī)模集成電路（Very Large Scale Integration，VLSI）布圖規(guī)劃（Floorplanning）是二維裝箱問題的一種特例，因此，本文首先設(shè)計了解決超大規(guī)模集成電路布圖規(guī)劃問題的算法，再將該算法擴展到3D-BPP。本文使用的優(yōu)化算法有多智能體粒子群算法（Multi-agentParticle Swarm Optimizati

4、on，MAPSO）和多智能體遺傳算法（Multi-agent Genetic Algorithm，MAGA），下面是本論文的主要工作：
　　1.采用移動模式序列（Moving Block Sequence，MBS）作為解碼算法來解決超大規(guī)模集成電路布圖規(guī)劃問題。MBS是一種非二分的布圖表示方法，它的凸搜索空間為算法中交叉算子的設(shè)計提供了平臺。MBS所需的存儲量與已有方法相比更小，并可以保證所有的布局為左下緊布局。傳統(tǒng)的粒子群算法，

5、具有普遍性、魯棒性性強和可以并行優(yōu)化處理等優(yōu)點，但為了深層次研究和更加充分的利用生物的智能資源，本文將 MBS和 MAPSO相結(jié)合，構(gòu)成了一種基于移動模式序列的多智能體粒子群算法（MAPSO-MBS），并使用MCNC和GSRC兩個數(shù)據(jù)集中的部分問題對其進行性能測試，本算法能夠得到良好的結(jié)果。
　　2.改進適用于二維裝箱問題的 MBS算法為三維移動模式序列（Three-dimensional Moving Block Sequenc

6、e，3DMBS），并將其擴展到無約束三維裝箱問題上，作為無約束三維裝箱問題的解碼算法。該算法的存儲量小，并且為優(yōu)化算法中的交叉算法提供了方便，能夠使整個放置過程達到最優(yōu)的結(jié)果。
　　3.針對三維裝箱問題，由于實際需求，尋找一種合理有效地放置策略是研究的重要方向。在優(yōu)化問題的求解過程中，MAGA有非常大潛力。本文將3DMBS和 MAGA相結(jié)合，構(gòu)成了基于三維移動模式序列的多智能體遺傳算法（MAGA-3DMBS），并用隨機產(chǎn)生的數(shù)據(jù)對