装箱问题bfd混合遗传算法的仿真研究

《装箱问题bfd混合遗传算法的仿真研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：LDC(DDC)学号：—03304—0401—1密级：玉一河；每大考硕士学位论文装箱姆瑟BFI)混合遗传算法的仿真研究张丽岩指导老师姓名：昙圭熬攫授．瀣盔堂奎鎏堂隧申请学位级别：亟主专业名猕：窑遵垂箍趣划生篮堡论文提交射同：2QQ§笙3目论文答辩时间：2Q鳗生§月学位授予单位：．塑盘态堂学位授予日期：麴Q§生±县答辩委员会主席：丞蔓论文评阅人：理丝．塑选堑中国·南京二00六年三月摘要装箱^d题是一个典型的组合优化问题，这类问题人苗存在1-H常生活中，它们的岁芑性就是将一堆“物品”，装入所谓的“箱f”中，而使它们不柏互叠迭。对应于现实，#活中，

2、即是如俺在满足要求的情况下，合理有效地利用时问或空问等现有资源。因此，装箱问题具有重要的研究价值。装箱问题，从20世纪70年代初开始，就引起了人们的关注。到目前为止，世界上研究的比较多的是一维及二维装箱问题。虽然经过几代人的努力，但迄今尚无成熟的理论和有效的数值计算方法。因此，从80年代，F始，陆续提出的装箱算法都是各种近似算法，如下次适应、首次适应、最佳适应算法和调和算法等。本文在总结了前人用来解决装箱问题的算法后，确定了利用遗传算法来求解装箱问题，并详细分析了基本遗传算法在装箱问题中的应用；在此基础上，作者首次提出了用于解决装箱问题的结合BFD思

3、想的混合遗传算法，并用VC实现了基于数据库的图形用户界面(GUI)程序，详细说明了程序实现的步骤，并给出了关键算法的程序流程图：最后通过算例比较，得出以下结论：在求解装箱问题时，结合了BFD思想的混合遗传算法要比基本遗传算法优化许多，具有很高的实用价值。关键词：装箱问题基本遗传算法BFD算法湿合遗传算法GUI数据库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问题的提出在现实生活中，经常会遇到以下一些问题，如图】．1所示生产稍￡爪蝇EH。F衡叫嚣图I．1生活中的几个问题由图中可以看到，

8、这类问题存在于生活的方方面面中，下面给出一些实际生活中此类问题的描述：问题～：在建筑工业中，经常需要从长度一