混合量子算法及其在生产调度中的应用

论文摘要

量子理论是现代物理学的两大基石之一，量子技术的发展将对人类有重大的意义。其一，运用量子技术能实现并行计算，大大提高运算速度。其二，量子技术运用在计算机硬件上能够使计算机的尺寸跨越原子的障碍。其三，在经典计算机上实现量子算法可以有效地运用于求解组合优化问题。目前，根据量子特性构造的优化算法已经在连续优化领域得到了良好的应用，而在组合优化领域的应用仍处于起步阶段。量子算法并不是完美的算法，同时，其他优化算法的独特之处可为其所用。因而继承量子计算中的并行搜索能力，并根据问题特性构造各种优化算子，使之辅助量子优化作用，构造混合量子算法是一种改善策略，将能有效提高算法的优化效果。另一方面，随着市场环境和需求模式的转变，时间和品种成为追逐的对象。在这种竞争环境下，能够承接不同品种，生产工艺各异的产品的代工厂必须尽早挣脱以往生产模式和管理模式的束缚，走新型工业化道路。其有效途径之一就是运用信息技术，计算机技术，自动化技术，人工智能技术，数控技术和系统制造技术来提高制造能力，管理能力和调控能力。对于代工厂来说，整个先进生产制造系统实现的核心是生产调度问题。有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。虽然计算机技术的迅猛发展为设计功能足够强大的智能调度系统提供了重要的技术支持，但现有的智能算法如遗传算法、蚁群算法还无法有效解决大规模的生产调度问题，而且对生产调度领域的研究至今仍未形成一套系统的理论和方法。因此，新型智能算法的构建无论是理论上还是实践指导上都具有重要意义。本文首先简单介绍了遗传量子算法，遗传算法，微粒群算法等优化算法，并分析了每种算法的特点。将研究对象定位为排序优化，分析了遗传量子算法在优化序列过程中及算法本身的不足，并针对这些不足一一提出了合理有效的改进方法以及构造混合量子算法的构想。其次，在遗传量子算法的基础上，结合进化计算和微粒群算法等设计了混合量子算法。设计了可用于构造序列的解码方式，结合微粒群算法的更新方法，通过跟踪个体极值点和总体极值点对量子比特进行智能调整，借鉴遗传算法的交叉和变异算子，使更新对个体的破坏程度更大，有效地提高了算法的搜索能力。将混合量子算法应用于排序难题之一TSP，以为抛砖引玉之用。再次，本文将混合量子算法用在生产调度问题中，主要是Flow Shop和Job Shop两大典型问题。根据问题规模和问题特性，设计了便于求解的编码，解码，进化和优化方法，并用C-Free3.0和Visual C++6.0开发了相关程序。通过与相关文献的结果比较，验证了混合量子算法在生产调度上的可行性，有效性和优越性。最后，对混合量子算法的研究和应用做了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题的背景
• 1.2 课题的研究意义
• 1.2.1 混合量子算法的研究意义
• 1.2.2 混合量子算法用于调度的意义
• 1.3 课题的国内外研究现状
• 1.3.1 量子算法国内外研究现状
• 1.3.2 调度国内外研究现状
• 1.4 本文主要研究内容
• 1.5 结束语
• 第二章 几类优化算法概述及基本混合量子算法初探
• 2.1 引言
• 2.2 求解方法的选择
• 2.3 遗传量子算法
• 2.4 遗传算法
• 2.5 微粒群算法
• 2.6 混合量子算法
• 2.6.1 量子优化算法的不足
• 2.6.2 基本混合量子算法
• 第三章 求解 TSP 的混合量子算法
• 3.1 引言
• 3.2 混合量子算法的基本进化模式
• 3.2.1 编码和解码
• 3.2.2 量子进化
• 3.2.3 动态惯性权重 w
• 3.3 混合量子算法中的优化机制及算法流程
• 3.3.1 初始化
• 3.3.2 局部优化
• 3.3.3 量子映射交叉和隔离小生境多交叉
• 3.3.4 模拟退火保留
• 3.3.5 混合量子算法流程
• 3.4 仿真及结果分析
• 3.4.1 仿真
• 3.4.2 结果分析
• 3.5 结束语
• 第四章 求解小规模置换 Flow Shop 调度问题的混合量子算法
• 4.1 引言
• 4.2 置换 Flow Shop 调度问题描述及数学模型
• 4.3 混合量子算法的基本进化模式
• 4.3.1 编码和解码
• 4.3.2 更新模式
• 4.4 混合量子算法的智能优化模式及算法流程
• 4.4.1 部分映射交叉（PMX）
• 4.4.2 全干扰交叉
• 4.4.3 选择
• 4.4.4 混合量子算法流程
• 4.5 仿真及结果分析
• 4.5.1 仿真
• 4.5.2 结果分析
• 4.6 结束语
• 第五章 求解大规模置换 Flow Shop 调度问题的混合量子算法
• 5.1 引言
• 5.2 混合量子算法的基本进化模式
• 5.2.1 量子进化
• 5.2.2 最佳模式
• 5.3 混合量子算法的其他优化模式及算法流程
• 5.3.1 初始化
• 5.3.2 邻域搜索
• 5.3.3 模拟退火思想
• 5.3.4 量子映射交叉和隔离小生境多交叉
• 5.3.5 混合量子算法流程
• 5.4 仿真及结果分析
• 5.4.1 仿真
• 5.4.2 结果分析
• 5.5 结束语
• 第六章 求解 Job Shop 调度问题的混合量子算法
• 6.1 引言
• 6.2 Job Shop 调度问题描述及数学模型
• 6.3 求解 Job Shop 的混合量子算法
• 6.3.1 编码
• 6.3.2 解码
• 6.3.3 量子角的更新
• 6.3.4 混合量子算法流程
• 6.4 求解 Job Shop 的改进混合量子算法
• 6.4.1 交叉
• 6.4.2 隔离小生境技术
• 6.4.3 局部搜索
• 6.4.4 改进混合量子算法流程
• 6.5 仿真及结果分析
• 6.5.1 仿真 1
• 6.5.2 结果分析 1
• 6.5.3 仿真 2
• 6.5.4 结果分析 2
• 6.6 结束语
• 第七章 结论与展望
• 附录 混合量子算法求解大规模 Flow shop 调度问题部分源程序
• 参考文献
• 在读期间公开发表的论文和承担科研项目及取得成果
• 致谢