求解三维装箱问题的遗传算法研究【文献综述】.doc

毕业设计文献综述 计算机科学与技术 求解三维装箱问题的遗传算法研究 摘 要：对三维装箱问题进行了描述，阐述了研究求解三维装箱问题的遗传算法的意义。接着详细介绍了该算法的实现原理和研究现状，并通过对比和归纳，指出了目前存在的问题。最后在研究现状的基础上，提出了求解三维装箱问题的遗传算法的发展趋势。 关键词：三维装箱问题；遗传算法； 一、研究求解三维装箱问题的遗传算法的意义 装箱问题是物流企业在装卸环节上必须面对的一个核心问题，装载方案的好坏将直接影响着企业的利润。因此，研究求解三维装箱问题的遗传算法，实现装箱问题的优化显得尤为重要。三维装箱问题即为物体在三维空间的摆放优化问题，可以描述为：长、宽、高分别为li、wi、hi的n个物体在多个集装箱中摆放，在满足一定的约束(重心位置约束、单箱重量约束、单箱空间利用率约束)条件下，使集装箱利用率最高[1]。 由于装箱问题是NP问题，传统算法的复杂度会随着摆放物体的数量呈指数级别增加，不能应用到频繁而庞大的装载业务上。于是基于生物自然进化理论具备全局优化搜索能力的遗传算法[2]被众多学者应用到装箱问题上。如今，管理工程、工业工程等领域中的一些问题(例如人力资源分配、运输计划等)均可建议为装箱[3]，所以寻找更准确、更有效的遗传算法是当今装箱问题研究者的心愿。 二、求解三维装箱问题的遗传算法的研究现状 1. 遗传算法的实现原理 1）个体编码及解码 将n个货物按体积从小到大排序并1至n编号，m个箱子1至m编号，物品横放编0，竖放编1，则解2:(1、3、6、8——0、1、1、0)可表示2号箱子中按0、1、1、0方位顺序放置1、3、6、8货物。 2）适应度计算 通过个体适应值的大小来评估群体中个体所对应装载方案的优劣，对于违反装载容积约束、装载质量约束和装载重心约束的个体，在求解其适应值的过程中要给于相应的惩罚以确保符合条件而较优的个体有较大的生存机会[4]。 3)实现过程 选择合适的编码方式，产生初始群，计算初始群体的适应值，如果不满足条件再进行选择、交叉、变异、计算新一代群体的适应值，直到满足条件为止。结束的条件可以根据具体条件来选择，可以以一定的代数为结束条件，也可以以两代之间适应度之差小于某个固定的值为结束条件。 2. 装箱问题的研究现状 从20世纪70年代初开始，装箱问题就被广泛地关注和研究[5]。到80年代末，各种近似求解装箱问题的算法被提了出来，如下次适应、首次适应和调和算法等[6]。但这些算法都只针对一维、二维装箱问题，因为相比之下三维装箱问题的复杂性大得多，直到80年代后才出现了比较实用的算法： 杨传民等人[7]通过全面枚举搜索方法来研究相同大小的立方体的装箱优化问题，使得求解的精度和效率上得到了提高。Mannchen[8]设计的树搜索算法，理论上对三维箱体布局有效，但随着布局箱体的增多，解空间剧增，所以计算效率不能满足实际需求。H．GEHRING[9]提出在深度方向按层布局的启发式算法，提高了空间利用率和重心的平衡度。姜义东[10]等提出利用遍历三叉树结构的方法对空间进行分解，虽然有效避免了空间干涉现象，但无法处理更复杂的约束。何大勇、查建中等[11]在简单遗传算法的基础上做了改进，能处理多目标、多约束的问题；但在货物很多时，应用遗传算法对每件货物进行整数编码构成的染色体，基因数量多，规模巨大，再加上众多约束条件，导致算法收敛非常慢，甚至大多数情况下得不到可行解。E.E.Bischoff[12]等人针对多种物品单托盘装载问题（只考虑空间和稳定性约束），从托盘缺少可用于支撑的垂直壁的特点和由底向上的摆放方式出发，提出了基于“平面”的算法。由底向上每次只放入一层最多由两种物品组成的水平层，迭代填充和生成平面、水平层，获得有效且具有高稳定性的布局模式。算法通过设定的规则选择合适的物品、平面、位置等布局参数，采用平面合并等方法提高平面利用率，进而生成一个较好的完整布局模式。虽然在摆放稳定性方面表现不错，但所得解的空间最优平均利用率不高。 3.遗传算法的研究现状 进入90年代，遗传算法开始变得热门起来，尤其是在应用研究上。随着它的应用领域扩大，利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。 1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。 D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Ite