求解矩形packing問(wèn)題的純粹擬人算法.pdf

1、NP難度問(wèn)題是一大類問(wèn)題，NP完全問(wèn)題則是其中最簡(jiǎn)單最基本的一類問(wèn)題。NP完全問(wèn)題在科學(xué)哲學(xué)和現(xiàn)實(shí)生活中的重要價(jià)值在于它同時(shí)具有看來(lái)相反的兩個(gè)性質(zhì)：通俗性和難解性。導(dǎo)致NP完全問(wèn)題難解的主要根源在于解空間隨問(wèn)題規(guī)模的擴(kuò)大呈指數(shù)增長(zhǎng)，甚至是一個(gè)連續(xù)歐氏空間的無(wú)窮集合。矩形packing 問(wèn)題屬于NP 難度問(wèn)題。此問(wèn)題來(lái)源于物件布局、切裁下料以及超大規(guī)模集成電路設(shè)計(jì)等實(shí)際問(wèn)題，常見(jiàn)的提法有：矩形背包問(wèn)題，矩形裝填問(wèn)題和矩形塊布局問(wèn)題。我們將

2、人類在近萬(wàn)年來(lái)所從事的一些特殊活動(dòng)中采取的方法和形成的實(shí)踐經(jīng)驗(yàn)加以形式化，把它說(shuō)精確、說(shuō)完整，并予以進(jìn)一步的發(fā)展，在此基礎(chǔ)上設(shè)計(jì)出求解矩形packing 問(wèn)題的純粹擬人算法。
　　 本研究在“占角動(dòng)作”和“穴度”兩個(gè)重要概念的基礎(chǔ)上得到了挑選占角動(dòng)作的具體策略，并提出了求解矩形背包問(wèn)題的三個(gè)具體的純粹擬人算法：最大穴度算法A0，前瞻穴度算法A1和強(qiáng)化穴度算法A2。算法A0采用純粹貪心的辦法放置矩形塊，即每次挑選穴度最大的占角動(dòng)作

3、并將動(dòng)作關(guān)聯(lián)的矩形塊按相應(yīng)的位置和方向放在容器中。算法A1在放每一塊矩形塊時(shí)，都運(yùn)用回溯的策略，以確定一個(gè)“全局最好”的動(dòng)作。算法A2僅在放第一塊時(shí)運(yùn)用回溯的策略，以后就采用最大穴度算法放置剩下的矩形塊。用Hopper和Turton 提出的21個(gè)測(cè)試實(shí)例對(duì)三個(gè)算法的性能進(jìn)行了實(shí)算測(cè)試，并與當(dāng)今國(guó)際文獻(xiàn)已報(bào)道的最先進(jìn)的兩個(gè)算法——初步擬人算法Heuristic1和混合啟發(fā)式算法(HH)進(jìn)行了對(duì)比。算法A1求出了其中15個(gè)實(shí)例的最優(yōu)解，算法

4、A2 求出了其中7個(gè)實(shí)例的最優(yōu)解，這一結(jié)果優(yōu)于算法Heuristic1和HH所得結(jié)果。以“角點(diǎn)數(shù)”和“貼邊數(shù)”兩個(gè)概念為基礎(chǔ)，對(duì)算法A0，A1和A2進(jìn)行改進(jìn)而得到了三個(gè)相應(yīng)的改進(jìn)算法A'0，A'1和A'2。對(duì)Hopper和Turton 提出的21個(gè)測(cè)試實(shí)例，算法A'1 求出了其中19個(gè)實(shí)例的最優(yōu)解，算法A'2求出了其中8個(gè)實(shí)例的最優(yōu)解，這一結(jié)果比A1和A2所得結(jié)果要好。結(jié)合二分的思想，將算法A'1 加以改造而得到了矩形裝填問(wèn)題的擬人求解

5、算法A3。用三組測(cè)試算例對(duì)算法性能進(jìn)行了實(shí)算測(cè)試。對(duì)Hopper和Turton 提出的21個(gè)測(cè)試實(shí)例，算法A3所得容器高度與最優(yōu)高度的偏差的平均值為0.04[％]；對(duì)Hopper 提出的35個(gè)裝填實(shí)例，偏差的平均值為1.8[％]；對(duì)Berkey和Martello等人提出的10組共500個(gè)裝填實(shí)例，偏差的平均值為2.28[％]。這些結(jié)果比目前國(guó)際上已報(bào)道的最先進(jìn)的啟發(fā)式算法所得結(jié)果要好。以算法A0和A1為基礎(chǔ)，結(jié)合“聚類”的思想，提出了矩

6、形塊布局問(wèn)題的擬人求解算法A4。對(duì)MCNC和GSRC兩組共21個(gè)實(shí)例，算法求出了其中20個(gè)實(shí)例的最優(yōu)解，這一結(jié)果好于CompaSS 算法(Compacting Soft and Slicing Packings)、基于角模塊序列的模擬退火算法(CBL)及遺傳算法所得結(jié)果。在算法A0和A1的基礎(chǔ)上，提出了求解價(jià)值優(yōu)化的矩形packing 問(wèn)題的純粹擬人算法A5。算法中使用了兩個(gè)主要的擬人策略——矩形塊選擇策略和占角動(dòng)作選擇策略。用國(guó)際上公