基于遗传和递归的装箱算法研究

摘要

装箱问题就是将不同尺寸的物品摆放入有一定容量的容器中，以获得某种最佳的效益。装箱问题广泛地用于机械生产和交通运输等行业当中。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。装箱问题属于组合最优化问题和NP完全问题，具有高度复杂性，用一般的数学方法很难求解，目前研究得最多的是用启发式方法解决装箱问题。 本文为求解二维装箱问题提出了GA+HR、GA+IHR和GA+OIHR三个算法。这三个算法是在已提出的HR算法的基础上改进的。GA+HR算法是HR算法结合遗传算法的全局搜索能力，通过遗传算法搜索到更优的排列顺序，使得解的效果进一步提高。GA+IHR算法中，定义了参考矩形和结合层的概念，通过找出所有结合层，然后计算每个结合层数所产生的解，最后从这些解中找出最优的解和最佳结合层数。GA++OIHR算法中，在HR算法中加入了穷举的思想，即对每一层的第一块矩形的放置都考虑水平放置和垂直放置两种情况，然后分别计算出这两种放置方式所带来的空间利用率。采用利用率比较大的方式作为该层的放置方式。而且在每一层子空间采用HR递归算法时，先搜索那些长或宽要么和子空间的高度相同要么和子空间的宽度相同的矩形，先把这些矩形放置好，这样放置后该子空间还是只被划分成一个更小的子空间，可以减少子空间的个数。从而减少因为不断递归划分成两个子空间，使得一些小空间因为再也放置不下任何一块矩形而造成的浪费。在本文中我们还把计算二维装箱问题的HR算法和GA+HR算法运用到三维装箱问题中。计算结果显示HR算法运行时间短，但所带来的空间利用率并不理想；GA+HR算法运行时间较长，但有较高的空间利用率。特别地，GA+HR算法的平均结果比著名的Bischoff算法要好。

目录

文摘

英文文摘

声明

第一章绪论

1.1装箱问题综述

1.1.1一维装箱问题

1.1.2二维装箱问题

1.1.3三维装箱问题

1.2论文研究的内容

第二章遗传算法

2.1传统遗传算法的基本步骤

2.2遗传算法中的基本实现技术

第三章二维装箱问题的启发式算法

3.1 BL(Bottom-Left)和BLF(Bottom-Left-Fill)算法

3.2 Best Fit算法

3.2.1预处理阶段

3.2.2装箱阶段

3.2.3后处理阶段

3.3启发式递归策略(HR)

3.4改进的启发式递归策略(IHR)

3.5优化后的IHR算法(OIHR)

第四章混合遗传算法的实现

4.1改进后的遗传算法规则

4.1.1编码

4.1.2适应度函数

4.1.3初始化种群

4.1.4选择算子

4.1.5交叉算子

4.1.6变异算子

4.1.7最优保存策略

4.2三种混合遗传算法的描述及参数设置

第五章二维装箱问题的计算结果

第六章三维装箱问题的算法及测试结果

6.1三维装箱问题的算法描述

6.2计算结果

第七章结束语

7.1工作总结

7.2存在问题及今后工作

参考文献

攻读硕士学位期间公开发表的论文

致谢