并行遗传算法在装箱问题中的应用研究

论文摘要

装箱问题是最经典的组合优化问题之一,同时也是算法分析理论中研究的重点。装箱问题源于现实生活,有着极为广泛和深厚的应用背景。例如装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等各领域有着广泛的应用。而且装箱问题理论的形成也有着深刻的意义,作为一种最早研究的NP难解问题,为其它NP难解问题的研究提供了理论性研究平台和诸多借鉴的典范。该问题已经有四十多年的研究历史,在此期间,许多著名的组合优化方面的学者为装箱问题创建了比较完善的理论和丰富的算法,但是关于装箱问题及其算法的研究仍远未结束。本文利用并行遗传算法来求解一维装箱问题,针对一维装箱问题,围绕如何提高并行算法的效率以及求解的精度提出了一些关键性的技术。主要内容如下:1、本文比较了解决一维装箱问题较好的组遗传算法,针对组遗传算法交叉算子的不足,在叉的过程中增加了一种“替换”机制,从而提出了一种改进的交叉算子。此交叉算子能够保证染色体在交叉的过程中尽量的减少箱子的个数,同时尽可能使能箱子装满物品。2、为了提高种群的多样性,在进化的过程中跳出局部最优解,本文设计了新的变异算子,在变异的过程中主要采取增加一个箱子,减少一个箱子,箱子数不变但箱子所装物品进行恰当重组的操作。3、从“多群体粗粒度”并性遗传算法模型入手,受“金字塔”模型的启发,本文提出了一种并行遗传算法的“金字塔层次模型”,根据种群的平均适应度将各个种群分成不同的层次,每一层具有不同交叉和变异概率。层次较高的种群具有较低的交叉和变异概率,迁移时只是从低层次向高层次迁移。4、在迁移策略上,为了尽可能降低通信费用,本文提出了“双阈值”的迁移策略,根据相邻两层之间种群的适应度方差设置双阈值,将迁移分为三种情况:小于最小阈值时不迁移;介于两个阈值之间用下层的优秀个体去替换上层的较差个体;大于最大的阈值,进行层次调整。5、在迁移周期上,本文采用的不固定间隔的迁移周期,当进化缓慢时才进行迁移的申请。基于上述的研究,最后本文给出了实现并行遗传算法求解装箱问题的伪代码,并在实践中利用伪并行遗传算法来模拟并行遗传算法求解一维装箱问题,通过实际数据的运算精度和效率说明了这种算法的优越性。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景
• 1.2 装箱问题的分类及衍生问题
• 第2章 遗传算法概述
• 2.1 自然进化与遗传算法
• 2.2 遗传算法基本流程
• 2.3 遗传算法参数与操作的设计
• 2.3.1 编码
• 2.3.2 适应度函数
• 2.3.3 算法参数
• 2.3.4 遗传操作
• 2.3.5 算法终止条件
• 2.4 遗传算法的改进
• 2.5 并行遗传算法
• 第3章 一维装箱问题
• 3.1 一维装箱问题的定义和数学描述
• 3.2 一维装箱问题的研究现状
• 3.2.1 一维装箱问题的近似算法
• 3.2.2 一维装箱问题的遗传算法
• 第4章 求解装箱问题的并行遗传算法的实现
• 4.1 求解装箱问题的遗传算法的实现
• 4.1.1 编码
• 4.1.2 适应度函数的设计
• 4.1.3 选择算子的设计
• 4.1.4 交叉算子的设计
• 4.1.5 变异算子的设计
• 4.2 并行模式的实现
• 4.3 仿真结果
• 第5章 总结
• 第6章 参考文献
• 致谢
• 攻读学位期间发表的主要学术论文
• 学位论文评阅及答辩情况表