基于混合分组遗传算法的装箱问题研究

摘要

装箱问题是一类非常典型的NP-hard问题,具有很重要的理论价值与实际应用意义。这类问题的共同目的就是把若干“物体”放入指定的“箱子”中,而最终使用的“箱子”数最少。如计算机操作系统中的资源分配、服装行业中的面料裁剪、现实生活中物件的整理等各个领域都有着广泛的应用。另一方面,装箱问题作为较早研究的NP-hard问题之一,对该问题的研究也为研究其它NP-hard问题提供了重要的理论研究意义。因此,对装箱问题的研究具有十分重要的价值。
　　 从二十世纪七十年代初开始,人们就开始研究装箱问题,至今已有近四十年的历史。许多著名的组合优化方面的学者都对装箱问题表现出了很大的兴趣并且提出了很多解决装箱问题的方法与理论,尽管如此,对该问题的研究还远未结束。
　　 本文在总结前人对装箱问题研究的基础上,通过对BF、FFD近似算法与分组遗传算法的结合,提出了解决装箱问题的一种混合分组遗传算法。其主要思想是设计一种适应度函数,利用分组遗传算法结合BF算法和FFD算法来对此适应度函数进行优化,从而求得一个优化的装箱结果。用C++实现该算法并对装箱实例进行仿真实验,结果表明:在遗传算子的交叉操作过程中采用FFD+GGA的混合算法要比BF+GGA的混合分组遗传算法运算结果更好,在大部分情况下用很短的时间都可求得最优解,是一种解决装箱问题的有效方法。

目录

文摘

英文文摘

第一章 绪论

1.1 提出问题

1.2 目前的研究

1.3 本文的主要工作及组织结构

第二章 装箱问题及其常用近似算法

2.1 引言

2.2 装箱问题概述

2.2.1 一维装箱问题的定义及其数学表示

2.2.2 装箱问题的分类及其在实际中的应用

2.3 装箱问题求解的常用近似算法

第三章 遗传算法概述

3.1 基本述语

3.2 遗传算法的基本流程

3.3 遗传算法的主要操作

3.3.1 染色体的编码方法

3.3.2 目标函数和适应度函数设计

3.4 遗传操作

3.4.1 选择操作(Selection)

3.4.2 交叉操作(Crossover)

3.4.3 变异操作(Mutation)

3.5 本章小结

第四章 装箱问题的混合分组遗传算法求解

4.1 引言

4.2 分组遗传算法简介

4.3 利用混合分组遗传算法求解装箱问题

4.3.1 染色体编码方法和初始种群的生成

4.3.2 适应度函数设计

4.3.3 选择算子设计

4.3.4 交叉操作

4.3.5 变异算子设计

第五章 装箱问题的混合分组遗传算法结果分析

5.1 利用BF结合分组遗传算法的结果

5.2 利用FFD结合分组遗传算法的结果

5.3 两种混合算法及其与其他算法的比较

第六章 总结

6.1 结论

6.2 研究展望

致谢

参考文献

附录 实现混合分组遗传算法的核心代码

攻读学位期间发表的学术论文目录

学位论文评阅及答辩情况表