資源描述：
《利用混合單新遺傳算法求解二維裝箱問題.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、分類號——UDC論文題目密級編號研究生：奎玉豎指導(dǎo)教師：塹玉副塾援專業(yè)：廑旦數(shù)堂所在學(xué)院：數(shù)堂型堂堂院2011年5月原創(chuàng)性聲明＼一本人聲明：所呈交的學(xué)位論文是本人在導(dǎo)師的指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。除本文已經(jīng)注明引用的內(nèi)容外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得凼墓直太堂及其他教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意。學(xué)位論文作者簽名：蘊(yùn)皇：!遁指導(dǎo)教師簽名：芝二i竺．日期：】翌12：』12日期：2立f!，§：!在學(xué)期間研究成
2、果使用承諾書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，即：內(nèi)蒙古大學(xué)有權(quán)將學(xué)位論文的全部內(nèi)容或部分保留并向國家有關(guān)機(jī)構(gòu)、部門送交學(xué)位論文的復(fù)印件和磁盤，允許編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，也可以采用影印、縮印或其他復(fù)制手段保存、匯編學(xué)位論文。為保護(hù)學(xué)院和導(dǎo)師的知識產(chǎn)權(quán)，作者在學(xué)期間取得的研究成果屬于內(nèi)蒙古大學(xué)。作者今后使用涉及在學(xué)期間主要研究內(nèi)容或研究成果，須征得內(nèi)蒙古大學(xué)就讀期間導(dǎo)師的同意；若用于發(fā)表論文，版權(quán)單位必須署名為內(nèi)蒙古大學(xué)方可投稿或公開發(fā)表。學(xué)位論文作者日簽名：叢指導(dǎo)教師簽名：利用混合單親遺傳算法求解二維裝箱問
3、題摘要裝箱問題是指將一些給定的不同尺寸的物品按照要求擺放入有一定容積的容器中，以獲得某種最佳的效益。裝箱問題涉及多學(xué)科、多領(lǐng)域的知識，在生產(chǎn)實(shí)踐中被廣泛的應(yīng)用。二維裝箱問題在現(xiàn)實(shí)生活中隨處可見，與人們的生產(chǎn)生活密切相關(guān)，找到二維裝箱問題的有效算法可以節(jié)省資源，提高生產(chǎn)效率，對人們的生產(chǎn)生活產(chǎn)生重大影響，從而對人類社會產(chǎn)生積極的推動作用。同時(shí)求解二維裝箱問題的各種算法也能應(yīng)用到求解三維裝箱問題中，因此研究二維裝箱問題有著重要的理論意義和應(yīng)用價(jià)值。裝箱問題是一個(gè)具有復(fù)雜約束條件的組合優(yōu)化問題，在理論上屬于NP_hard問題。其求解是極
4、為困難的。從20世紀(jì)70年代初開始，裝箱問題就引起了人們的關(guān)注。到目前為止，世界上研究的比較多的是一維及二維裝箱問題，人們提出了大量的求解裝箱問題的算法，其中最主要的算法有啟發(fā)式算法和遺傳算法。本文首先對裝箱問題的種類及研究現(xiàn)狀進(jìn)行了綜述，總結(jié)了現(xiàn)有的關(guān)于裝箱問題的一些算法，包括啟發(fā)式算方法和遺傳算法。闡述了遺傳算法的基本實(shí)現(xiàn)機(jī)理，并對單親遺傳算法進(jìn)行了概述，然后針對二維矩形裝箱問題，對現(xiàn)有的FFA算法及其改進(jìn)算法IFFA進(jìn)行了分析，并對IFFA算法進(jìn)一步加以改進(jìn)，提出了一種IFFA2算法，在IFFA2算法中，考慮了碎片的利用，并
5、通過舉例說明了碎片的產(chǎn)生及表示方法，最后嘗試把IFFA2算法與單親遺傳算法結(jié)合起來構(gòu)成混合單親遺傳算法來實(shí)現(xiàn)對二維裝箱問題的求解，并給出了算法實(shí)現(xiàn)的流II程圖。在算法中，提出了同時(shí)考慮物品裝箱順序及物品放置方向的編碼方案，并設(shè)計(jì)了新的適應(yīng)度函數(shù)和遺傳操作，在解碼過程中引入了IFFA2算法，使啟發(fā)式算法與遺傳算法有機(jī)的結(jié)合在一起。關(guān)鍵詞：二維裝箱問題，單親遺傳算法，IFFA算法，碎片IIISOLVINGTWO．DIMENSIONALPACKINGPRoBLEMBASEDONHYBRIDPARTHENo．GENETICALGoRITH
6、MABSTRACTPaCl(ingproblemisgiVentosomeofmeitemsinaccordancewiththerequirementsofdifjEIeremsizesplacedintoacertainVolumeofcontainertogetamebestresults．PackingprobleminVolVesmulti-disciplinary，multi—domainknowledge，inmeproductionpracticeiswidelyused．Two—dimensionalpaCkin
7、gproblemcanbeseeneVe呻ereinreallife，andpeople’sproductionandlifearecloselyrelated．Findane髓ctiVealgorithlnfortwo—dimensionalpackingproblemcansaveresourCesandimproVeproductione伍ciency，haVeasignificantimpactonproductionandliVingofthepe叩le，andthushaVeapositiVeroleinproJnot
8、ingforhum鋤socie夠Atthes鋤etimetwo-dimensionalpac虹ngproblemsolVingcaIlalsobe印pliedt0VariousalgorithmsforsolVingthree—dimensiona
