資源描述：
《一種求解矩形塊裝填問題的擬人算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、一種求解矩形塊裝填問題的擬人算法*)基金項目：國家自然科學基金資助項目10471051和973項目2004CB318000。陳端兵博士生，主要研究方向為NP難問題高效求解。黃文奇教授，博士生導師，主要研究方向為NP難問題高效求解，人工智能，博奕等。陳端兵黃文奇(華中科技大學計算機科學與技術(shù)學院武漢430074)摘要在貨物裝載，木材下料，超大規(guī)模集成電路(VLSI)設(shè)計等工作中提出了矩形塊裝填與切割問題，對這一問題，國內(nèi)外學者提出了諸如模擬退火算法，遺傳算法及其它一些啟發(fā)式算法等求解算法。本文利用人類的智慧和他們上萬年以來形成的經(jīng)驗，
2、提出了一種求解矩形塊裝填問題的擬人算法。該算法使用了兩個主要的思想策略，即矩形塊選擇策略和矩形塊放置策略。用本文提出的算法，對21個測試算例進行了實算測試，測試結(jié)果表明：算法所得裝填結(jié)果的優(yōu)度高，計算時間短。對這21個測試算例，用本文算法計算，得到了其中16個算例的最優(yōu)解，而計算時間都在2秒以內(nèi)。進一步的測試表明，本文提出的算法對求解矩形塊裝填問題十分有效。關(guān)鍵詞矩形塊裝填與切割擬人占角動作AQuasi-humanHeuristicAlgorithmforRectanglePackingProblemCHENDuan-BingHUA
3、NGWen-Qi(CollegeofComputerScience,HuazhongUniversityofScienceandTechnology,Wuhan430074)AbstractRectanglepacking/cuttingproblemisoftenraisedinloading,timbercutting,VeryLargeScaleIntegration(VLSI)design,andsoon.Forsolvingthisproblem,manyalgorithmssuchassimulatedannealing
4、,geneticalgorithm,andotherheuristicalgorithmshavebeenproposed.Inthispaper,anefficientquasi-humanheuristicrectanglepackingalgorithmisproposedaccordingtoten-thousand-yearexperienceandwisdomofhumanbeing.Thealgorithmutilizestwoimportantstrategies,i.e.,howtoselecttherectang
5、lebasedonitsvalueandhowtopackitaccordingtothecorneroccupyingplace.21rectanglepackingtestinstancesaretestedbytheproducedalgorithm,16instancesofthemachieveoptimumsolutions,andtheruntimeislessthan2secondsforeachinstance.Theintegratedperformanceoftheproducedalgorithmisrath
6、ersatisfied.Experimentalresultsdemonstratethatthealgorithmproposedinthispaperisratherefficientforsolvingrectanglepackingproblem.KeywordsRectanglepackingandcuttingproblem,Quasi-humanheuristic,Corner-occupyingaction.1引言對矩形塊裝填問題(或者說矩形塊切割問題)，有許多方面的應(yīng)用，如火車站、碼頭的貨物裝載，超大規(guī)模集成電路的
7、布局與布圖規(guī)劃，木材加工廠的木材下料等等。對這一問題，許多學者利用不同的思想提出了各種各樣的算法，如：BeasleyJE[1,2]，HadjiconstantinouE和ChristofidesN[3,4]，F(xiàn)eketeSP和SchepersJ[5]，LaiKK和ChanWM[6]，LeungTW[7]，WangPY[8]，WuYL[9]等，這些算法基本上可分為兩類，即隨機優(yōu)化算法和確定性構(gòu)造算法。對于隨機優(yōu)化算法，如模擬退火算法、遺傳算法，其核心是設(shè)計一種能表示裝填結(jié)果的編碼；對于確定性的構(gòu)造算法，關(guān)鍵在于確定一種裝填規(guī)則，使得在
8、一個可以接受的時間內(nèi)求得問題的近似優(yōu)化解。1985年，BeasleyJE用搜索樹方法導出了矩形塊切割問題的最優(yōu)解的上界，并給出了12個測試算例的最優(yōu)解[1]。1997年，Lai和Chan利用進化理論的方法提出了一個啟發(fā)式算法，算法的目
