資源描述：
《裝箱問題bfd混合遺傳算法的仿真研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、分類號：LDC(DDC)學(xué)號：—03304—0401—1密級：玉一河；每大考碩士學(xué)位論文裝箱姆瑟BFI)混合遺傳算法的仿真研究張麗巖指導(dǎo)老師姓名：曇圭熬攫授．瀣盔堂奎鎏堂隧申請學(xué)位級別：亟主專業(yè)名獼：窯遵垂箍趣劃生籃堡論文提交射同：2QQ§笙3目論文答辯時(shí)間：2Q鰻生§月學(xué)位授予單位：．塑盤態(tài)堂學(xué)位授予日期：麴Q§生±縣答辯委員會主席：丞蔓論文評閱人：理絲．塑選塹中國·南京二00六年三月摘要裝箱^d題是一個(gè)典型的組合優(yōu)化問題，這類問題人苗存在1-H常生活中，它們的歲芑性就是將一堆“物品”，裝入所謂的“箱f”中，而使它們不柏互疊迭。對應(yīng)于現(xiàn)實(shí)，#活中，
2、即是如俺在滿足要求的情況下，合理有效地利用時(shí)問或空問等現(xiàn)有資源。因此，裝箱問題具有重要的研究價(jià)值。裝箱問題，從20世紀(jì)70年代初開始，就引起了人們的關(guān)注。到目前為止，世界上研究的比較多的是一維及二維裝箱問題。雖然經(jīng)過幾代人的努力，但迄今尚無成熟的理論和有效的數(shù)值計(jì)算方法。因此，從80年代，F(xiàn)始，陸續(xù)提出的裝箱算法都是各種近似算法，如下次適應(yīng)、首次適應(yīng)、最佳適應(yīng)算法和調(diào)和算法等。本文在總結(jié)了前人用來解決裝箱問題的算法后，確定了利用遺傳算法來求解裝箱問題，并詳細(xì)分析了基本遺傳算法在裝箱問題中的應(yīng)用；在此基礎(chǔ)上，作者首次提出了用于解決裝箱問題的結(jié)合BFD思
3、想的混合遺傳算法，并用VC實(shí)現(xiàn)了基于數(shù)據(jù)庫的圖形用戶界面(GUI)程序，詳細(xì)說明了程序?qū)崿F(xiàn)的步驟，并給出了關(guān)鍵算法的程序流程圖：最后通過算例比較，得出以下結(jié)論：在求解裝箱問題時(shí)，結(jié)合了BFD思想的混合遺傳算法要比基本遺傳算法優(yōu)化許多，具有很高的實(shí)用價(jià)值。關(guān)鍵詞：裝箱問題基本遺傳算法BFD算法濕合遺傳算法GUI數(shù)據(jù)庫AbstractBin—packingProblem(BP)isoneofthecombinationoptimizationproblemsItliesinourdailylife．ThecommonnessofBPisputtingso
4、me。。goods‘‘intoson31e’‘boxes”andnotoverlapping．Inotherwords，usetheresourcesuitablyafterfulfillingourneeds，So，thereisanimportantvalueinstudyingtheBEBPhasarousedmart’sattentionfromtheearly1970s．WemostlystudylinearBPand2-DBPuptonow．Therearenomaturetheoryandnumericalimplementationb
5、yfar．Scholarsbegantostudyapproximatealgorithmsfrom1980s，suchasnexlfit(NF)firstfit(FF)，bestfit(BF)andharmonicalgorithms．ThearticleutilizesGeneticAlgorithm(GA)insolvingBPonthebasicofthesuperiors．ItanalysestheStandardGeneticAlgorithm(SGA)usinginthefieldofBPindetail．Thearticleadvan
6、cedahybridgeneticalgorithmwhichisconstitutedbyBestFitDecreasing(BFD)algorithmandSGAinresolvingBEAndimplementGUtprocedurebasedontheDatabaseinVC．Thearticlediscussesthedetailstepsoftheprocedureandthemainproceduralflowcharts．Afterthecomparisonoftheexample，wehaveaconclusionthatthehy
7、bridgeneticalgorithmconstitutedbyBFDandSGAisbetterthanSGAinsolvingBPandithasallappliedvalue．Keywords：BinPackingproblem，StandGeneticAlgorithm，BestFitAlgorithm，HybridGeneticAlgorithm，GUI，theDatabasec』門，、f全通7虢第一章緒論1．1問題的提出在現(xiàn)實(shí)生活中，經(jīng)常會遇到以下一些問題，如圖】．1所示生產(chǎn)稍￡爪蠅EH。F衡叫囂圖I．1生活中的幾個(gè)問題由圖中可以看到，
8、這類問題存在于生活的方方面面中，下面給出一些實(shí)際生活中此類問題的描述：問題～：在建筑工業(yè)中，經(jīng)常需要從長度一
