改进的量子遗传算法在车间调度中的应用研究

论文摘要

生产调度作为一个关键模块,是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的调度方法和优化技术的研究与应用,是实现先进制造和提高生产效益的基础和关键。遗传算法作为应用最广泛的进化计算方法之一,在调度的优化研究方面具有不可替代的优势。针对生产调度中典型的作业车间调度问题（Job-Shop Scheduling Problem）,在对标准遗传算法及量子遗传算法深入研究的基础上,本文提出了一种改进的量子遗传算法。该算法针对量子遗传算法进化的前期、中期及后期所存在的缺点及局限性,引入了精英库、干扰库和旋转角的自适应变化来克服量子遗传算法在整个进化期间所存在的缺点。精英库在算法进化的前期效果明显,利用精英库的优秀个体来代替进化种群的最差个体,这样将大大提高算法进化初期寻优速度;交叉机制的优劣直接决定着算法的效率,交叉操作对于保证遗传算法寻优过程能否收敛到全局最优,以及提高寻优过程的收敛速度都起着重要作用,量子遗传算法只要用量子旋转门来进行量子交叉,那样,量子旋转角的选择就尤为重要。在改进的量子遗传算法中,自适应调节旋转角,防止了量子遗传算法一开始如果确定的旋转角不好,整个算法将不能或很缓慢地搜索到最优解,在不断进化中自适应调节旋转角,使算法的收敛速度大大提高。当算法进行到一定阶段,种群的进化处于停滞阶段或发展缓慢时,改进的量子遗传算法引入了干扰库,利用干扰库对进化的种群进行人工干扰,使算法尽快摆脱进化停滞状态,开始新的搜索。通过对标准遗传算法、量子遗传算法和改进的量子遗传算法的函数测试比较和作业车间调度实例比较,有效地证明了改进算法的优越性和其在求解作业车间调度问题时所表现出的良好性能。

论文目录

• 摘要
• ABSTRACT
• 绪论
• 本章小结
• 第一章 调度问题及算法研究
• 1.1 引言
• 1.2 车间调度问题概述及其研究难点
• 1.2.1 车间调度问题的描述
• 1.2.2 车间调度问题的研究难点
• 1.3 遗传算法的研究现状
• 1.4 量子遗传算法的研究意义
• 本章小结
• 第二章 遗传算法
• 2.1 引言
• 2.2 遗传算法概述及具体设计
• 2.2.1 遗传算法概念
• 2.2.2 遗传算法的设计步骤
• 2.2.3 遗传算法的适应度函数
• 2.3 遗传算法的工作流程和遗传操作
• 2.3.1 遗传算法的遗传操作
• 2.3.2 遗传算法的流程图
• 2.4 遗传算法的研究现状
• 2.4.1 遗传算法的应用范围
• 2.4.2 遗传算法存在的问题
• 本章小结
• 第三章 量子遗传算法
• 3.1 量子遗传算法简介
• 3.2 量子计算原理
• 3.2.1 状态的叠加
• 3.2.2 状态的相干
• 3.2.3 状态的纠缠
• 3.3 量子遗传算法的遗传操作
• 3.3.1 量子位表示方法
• 3.3.2 量子旋转门
• 3.4 量子遗传算法步骤及流程图
• 本章小结
• 第四章 改进的量子遗传算法
• 4.1 引言
• 4.2 量子遗传算法基本原理
• 4.2.1 量子比特
• 4.2.2 染色体表示方法
• 4.2.3 量子旋转门设计
• 4.2.4 量子非门设计
• 4.3 改进的量子遗传算法模式
• 4.3.1 改进的量子遗传算法的基本思想
• 4.3.2 改进的量子遗传算法的具体实现步骤
• 4.3.3 改进的量子遗传算法的优点
• 4.3.4 改进的量子遗传算法的具体流程图
• 4.4 用标准测试集测试的结果及分析
• 本章小结
• 第五章 车间作业计划平台的应用
• 5.1 引言
• 5.2 系统开发的目的及说明
• 5.2.1 系统开发的目的
• 5.2.2 系统说明
• 5.3 系统功能模块
• 5.3.1 系统功能模块图
• 5.3.2 系统功能测试结果及相关说明
• 5.4 系统数据库设计
• 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢