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

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

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

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

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

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

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