利用混合单新遗传算法求解二维装箱问题.pdf

《利用混合单新遗传算法求解二维装箱问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号——UDC论文题目密级编号研究生：奎玉竖指导教师：堑玉副塾援专业：廑旦数堂所在学院：数堂型堂堂院2011年5月原创性声明＼一本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得凼墓直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：蕴皇：!遁指导教师签名：芝二i竺．日期：】翌12：』12日期：2立f!，§：!在学期间研究成

2、果使用承诺书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。学位论文作者日签名：丛指导教师签名：利用混合单亲遗传算法求解二维装箱问

3、题摘要装箱问题是指将一些给定的不同尺寸的物品按照要求摆放入有一定容积的容器中，以获得某种最佳的效益。装箱问题涉及多学科、多领域的知识，在生产实践中被广泛的应用。二维装箱问题在现实生活中随处可见，与人们的生产生活密切相关，找到二维装箱问题的有效算法可以节省资源，提高生产效率，对人们的生产生活产生重大影响，从而对人类社会产生积极的推动作用。同时求解二维装箱问题的各种算法也能应用到求解三维装箱问题中，因此研究二维装箱问题有着重要的理论意义和应用价值。装箱问题是一个具有复杂约束条件的组合优化问题，在理论上属于NP_hard问题。其求解是极

4、为困难的。从20世纪70年代初开始，装箱问题就引起了人们的关注。到目前为止，世界上研究的比较多的是一维及二维装箱问题，人们提出了大量的求解装箱问题的算法，其中最主要的算法有启发式算法和遗传算法。本文首先对装箱问题的种类及研究现状进行了综述，总结了现有的关于装箱问题的一些算法，包括启发式算方法和遗传算法。阐述了遗传算法的基本实现机理，并对单亲遗传算法进行了概述，然后针对二维矩形装箱问题，对现有的FFA算法及其改进算法IFFA进行了分析，并对IFFA算法进一步加以改进，提出了一种IFFA2算法，在IFFA2算法中，考虑了碎片的利用，并

5、通过举例说明了碎片的产生及表示方法，最后尝试把IFFA2算法与单亲遗传算法结合起来构成混合单亲遗传算法来实现对二维装箱问题的求解，并给出了算法实现的流II程图。在算法中，提出了同时考虑物品装箱顺序及物品放置方向的编码方案，并设计了新的适应度函数和遗传操作，在解码过程中引入了IFFA2算法，使启发式算法与遗传算法有机的结合在一起。关键词：二维装箱问题，单亲遗传算法，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