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