求解矩形packing問題的純粹擬人算法.pdf

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

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

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

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

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

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