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

摘要

装箱问题是指将一些给定的不同尺寸的物品按照要求摆放入有一定容积的容器中,以获得某种最佳的效益。装箱问题涉及多学科、多领域的知识,在生产实践中被广泛的应用。二维装箱问题在现实生活中随处可见,与人们的生产生活密切相关,找到二维装箱问题的有效算法可以节省资源,提高生产效率,对人们的生产生活产生重大影响,从而对人类社会产生积极的推动作用。同时求解二维装箱问题的各种算法也能应用到求解三维装箱问题中,因此研究二维装箱问题有着重要的理论意义和应用价值。
　　 装箱问题是一个具有复杂约束条件的组合优化问题,在理论上属于NP-hard问题。其求解是极为困难的。从20世纪70年代初开始,装箱问题就引起了人们的关注。到目前为止,世界上研究的比较多的是一维及二维装箱问题,人们提出了大量的求解装箱问题的算法,其中最主要的算法有启发式算法和遗传算法。
　　 本文首先对装箱问题的种类及研究现状进行了综述,总结了现有的关于装箱问题的一些算法,包括启发式算方法和遗传算法。阐述了遗传算法的基本实现机理,并对单亲遗传算法进行了概述,然后针对二维矩形装箱问题,对现有的FFA算法及其改进算法IFFA进行了分析,并对IFFA算法进一步加以改进,提出了一种IFFA2算法,在IFFA2算法中,考虑了碎片的利用,并通过举例说明了碎片的产生及表示方法,最后尝试把IFFA2算法与单亲遗传算法结合起来构成混合单亲遗传算法来实现对二维装箱问题的求解,并给出了算法实现的流程图。在算法中,提出了同时考虑物品装箱顺序及物品放置方向的编码方案,并设计了新的适应度函数和遗传操作,在解码过程中引入了IFFA2算法,使启发式算法与遗传算法有机的结合在一起。

目录

文摘

英文文摘

第一章 绪论

1.1 装箱问题简介

1.1.1 一维装箱问题

1.1.2 二维装箱问题

1.1.3 三维装箱问题

1.2 装箱问题的研究现状

1.2.1 装箱问题的启发式算法

1.2.2 装箱问题的遗传算法

1.3 选题意义

1.4 本文的内容及文章结构

1.4.1 本文的主要内容.

1.4.2 文章结构

1.4.3 本文的创新点

第二章 遗传算法的原理和实现

2.1 遗传算法的基本思想[6.40]

2.2 遗传算法的关键参数与操作的设计[40.41]

2.2.1 确定问题的编码方案

2.2.2 初始群体的选取与规模

2.2.3 确定适应度函数

2.2.4 控制参数的选择

2.2.5 遗传操作[15]

2.2.6 算法终止条件

2.3 遗传算法的特点及应用[40.43]

2.3.1 遗传算法的特点

2.3.2 遗传算法的应用

2.4 标准遗传算法的基本流程[41]

第三章 单亲遗传算法

3.1 单亲遗传算法的提出[44]

3.2 单亲遗传算法的描述[45]

3.2.1 单亲遗传算法的编码方式和个体评价

3.2.2 单亲遗传算法的遗传算子

3.3 单亲遗传算法的运行流程[45]

第四章 基于混合单亲遗传算法的二维装箱问题研究

4.1 IFFA2算法

4.1.1 IFFA2算法的提出

4.1.2 IFFA2算法的数据结构

4.1.3 碎片的产生及表示

4.1.4 算法举例

4.2 基于IFFA2算法的混合单亲遗传算法在二维装箱问题中的实现

4.2.1 编码与解码

4.2.2 初始种群的产生

4.2.3 适应度函数

4.2.4 选择算子

4.2.5 变异算子

4.2.6 终止条件

4.2.7 算法流程图

第五章 结论

参考文献

致谢