欢迎来到天天文库
浏览记录
ID:34807565
大小:2.11 MB
页数:81页
时间:2019-03-11
《装箱问题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、这类问题存在于生活的方方面面中,下面给出一些实际生活中此类问题的描述:问题~:在建筑工业中,经常需要从长度一
此文档下载收益归作者所有