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

VIP免费
3.0 牛悦 2024-11-19 4 4 2.65MB 74 页 15积分
侵权投诉
I
目 录
中文摘要
ABSTRACT
第一章 绪 论...................................................................................................................1
§1.1 课题的背景......................................................................................................1
§1.2 课题的研究意义..............................................................................................2
§1.2.1 混合量子算法的研究意义....................................................................2
§1.2.2 混合量子算法用于调度的意义............................................................3
§1.3 课题的国内外研究现状..................................................................................5
§1.3.1 量子算法国内外研究现状....................................................................5
§1.3.2 调度国内外研究现状............................................................................6
§1.4 本文主要研究内容..........................................................................................8
§1.5 结束语..............................................................................................................9
第二章 几类优化算法概述及基本混合量子算法初探...............................................11
§2.1 引言................................................................................................................11
§2.2 求解方法的选择............................................................................................11
§2.3 遗传量子算法................................................................................................12
§2.4 遗传算法........................................................................................................15
§2.5 微粒群算法....................................................................................................16
§2.6 混合量子算法................................................................................................18
§2.6.1 量子优化算法的不足..........................................................................18
§2.6.2 基本混合量子算法..............................................................................19
第三章 求解 TSP 的混合量子算法 ..............................................................................21
§3.1 引言................................................................................................................21
§3.2 混合量子算法的基本进化模式....................................................................22
§3.2.1 编码和解码..........................................................................................22
§3.2.2 量子进化..............................................................................................22
§3.2.3 动态惯性权重 w ..................................................................................23
§3.3 混合量子算法中的优化机制及算法流程....................................................24
§3.3.1 初始化..................................................................................................24
§3.3.2 局部优化..............................................................................................25
II
§3.3.3 量子映射交叉和隔离小生境多交叉..................................................26
§3.3.4 模拟退火保留......................................................................................26
§3.3.5 混合量子算法流程..............................................................................27
§3.4 仿真及结果分析............................................................................................27
§3.4.1 仿真......................................................................................................27
§3.4.2 结果分析..............................................................................................28
§3.5 结束语............................................................................................................29
第四章 求解小规模置换 Flow Shop 调度问题的混合量子算法 ............................... 30
§4.1 引言................................................................................................................30
§4.2 置换 Flow Shop 调度问题描述及数学模型 ................................................ 30
§4.3 混合量子算法的基本进化模式....................................................................31
§4.3.1 编码和解码..........................................................................................31
§4.3.2 更新模式..............................................................................................32
§4.4 混合量子算法的智能优化模式及算法流程................................................32
§4.4.1 部分映射交叉(PMX) .......................................................................... 33
§4.4.2 全干扰交叉..........................................................................................33
§4.4.3 选择......................................................................................................33
§4.4.4 混合量子算法流程..............................................................................34
§4.5 仿真及结果分析............................................................................................34
§4.5.1 仿真......................................................................................................34
§4.5.2 结果分析..............................................................................................36
§4.6 结束语............................................................................................................36
第五章 求解大规模置换 Flow Shop 调度问题的混合量子算法 ............................... 38
§5.1 引言................................................................................................................38
§5.2 混合量子算法的基本进化模式....................................................................39
§5.2.1 量子进化..............................................................................................40
§5.2.2 最佳模式..............................................................................................40
§5.3 混合量子算法的其他优化模式及算法流程................................................41
§5.3.1 初始化..................................................................................................41
§5.3.2 邻域搜索..............................................................................................41
§5.3.3 模拟退火思想......................................................................................41
§5.3.4 量子映射交叉和隔离小生境多交叉..................................................42
§5.3.5 混合量子算法流程..............................................................................43
III
§5.4 仿真及结果分析............................................................................................43
§5.4.1 仿真......................................................................................................43
§5.4.2 结果分析..............................................................................................45
§5.5 结束语............................................................................................................46
第六章 求解 Job Shop 调度问题的混合量子算法 ......................................................47
§6.1 引言................................................................................................................47
§6.2 Job Shop 调度问题描述及数学模型............................................................47
§6.3 求解 Job Shop 的混合量子算法 ...................................................................48
§6.3.1 编码......................................................................................................48
§6.3.2 解码......................................................................................................48
§6.3.3 量子角的更新......................................................................................49
§6.3.4 混合量子算法流程..............................................................................49
§6.4 求解 Job Shop 的改进混合量子算法 ...........................................................50
§6.4.1 交叉......................................................................................................50
§6.4.2 隔离小生境技术..................................................................................50
§6.4.3 局部搜索..............................................................................................51
§6.4.4 改进混合量子算法流程......................................................................51
§6.5 仿真及结果分析............................................................................................51
§6.5.1 仿真 1 ...................................................................................................51
§6.5.2 结果分析 1 ...........................................................................................53
§6.5.3 仿真 2 ...................................................................................................53
§6.5.4 结果分析 2 ...........................................................................................53
§6.6 结束语............................................................................................................55
第七章 结论与展望.......................................................................................................56
附录 混合量子算法求解大规模 Flow shop 调度问题部分源程序............................58
参考文献.........................................................................................................................67
在读期间公开发表的论文和承担科研项目及取得成果.............................................72
致谢.................................................................................................................................73
第一章 绪论
1
第一章 绪 论
§1.1 课题的背景
在探求光，原子，电子等本质的进程中，逐步形成了量子的概念。随着科学
家们对微观物质深入的研究，形成了量子力学的理论体系。量子的理念对光进行
了一定程度的诠释，对探索原子的构成，原子核以及电子在原子中的相互关系起
到了积极的推动作用。同时，量子的提出也带来了相当棘手的问题，如光具有波
粒二象性，电子会发生跃迁。历史的车轮在向前迈进，诸如此类的思考和推测也
在世界各地源源不断地浮出水面，很多看似不可思议，但都有一定的依据，量子
计算机是这些思考和推测的产物之一。
目前虽然用于制造电子器件的技术越来越成熟，器件的尺寸也随之小而又小，
但如果不能逾越原子的鸿沟，那么这种技术上的改进以及反映到器件上的体积大
小也是有一个限度的。科学家曾预言在 21 世纪计算机硬件能力的发展将不再遵从
Moore 定律，事实证明当尺度小到一定的程度，器件的功能将受到量子效应的干扰，
此时传统的制造方法失效。在寻求解决这一问题的进程中，Feynman 首次提出了量
子计算的概念。如果从原子规模的角度去考虑物质内部构造的相互作用，就可以
使物质变得要多小有多小[1]，因而量子技术在计算机的更新换代上具有较大的潜
力。无独有偶，随着随机算法的引入，强 Church-Turing 论题后来被改为更强的
论题[2]，科学家也在思考能否进一步推导出更强的 Church-Turing 论题，Deutsch
运用量子力学的理论，提出了通用量子计算机。如果量子计算机能够研制成功，
将掀起一场巨大的革命。
区别于传统计算机的二进制比特数据存储方式，量子计算机中的量子比特随
位数的增加能指数级地增加数据存储量。因而，量子计算机具有更高的并行性，
量子计算机的这种特点能大大提高使用者的工作效率。目前，大量的研究者将各
种优化算法应用于求解复杂的组合优化问题，由于多数问题的求解规模呈指数级
增长，计算时间开销巨大，研究者们不得不退而求次优。量子计算机指数级的数
据存储能力加上其并行计算能力，使寻求最优成为了可能。虽然实现量子计算机
原理上已无障碍，但尚未掌握制备与操纵量子态的技术[3]。量子计算机的物理实现
在实际上和技术上仍然是一个巨大的挑战[4]。
在 Deutsch 的令人瞩目的理论提出后，Shor 和 Grover 的研究取得了进展。Shor
证明了整数质因子分解问题和求解离散对数问题可以用量子计算机有效解决，而
Grover 证明在没有机构的搜索空间上进行搜索的问题能够在量子计算机上被加速
混合量子算法及其在生产调度中的应用
2
[5]。因此，尽管量子计算机无法在近期造出来，人们对于量子计算的理论研究已经
达到了一定的层次。目前，具有干涉，叠加，并行等特质的量子计算在许多领域
已有所涉足，尤其是量子指数级数据的存储及并行计算的能力更是令人叹为观止，
量子计算是一种潜力极大的技术手段。
如果运用得当，量子计算的思想可用于优化，目前各种基于量子行为的优化
算法正不断地涌现。随着社会日新月异的变化，以量子计算为核心的量子优化算
法正大放光芒。
§1.2 课题的研究意义
§1.2.1 混合量子算法的研究意义
量子计算理论已相当成熟，而基于量子行为的优化算法在组合优化领域仍处
于起步阶段。Shor 和Grover 的研究成果能够证明在量子效应下计算具备强大的并
行能力，而在经典的计算机中求解组合优化问题上是否能利用这种并行能力仍然
需要进一步的研究和试验来验证。一些量子优化算法已经在连续优化问题中体现
较好的寻优能力，但在部分组合优化问题中也暴露出不足。用于解决生产调度问
题的量子算法研究成果相对较少，在很大程度上正是因为这类算法的缺陷，目前
各种量子优化算法的不足主要体现在以下几个方面：
(1)困难的编码和解码使得个体构造的可行性得不到保障，且使码的存储需要
较大的空间。
(2)优化中的逻辑判断分类太多，造成量子比特的更新操作繁琐。
(3)量子优化算法独特的进化模式造成进化后期探索效果不显著。
每种智能算法在其生命周期中不可避免会遭到质疑，但这也是该算法得以成
熟的基础。在不断地开发和试验后，逐渐对问题本身和算法的运用重新加以认识，
自然而然，算法会不断地得到改善。构造量子优化算法也是同样的道理，尽管目
前存在不足，但仍有很大的改进余地。
鉴于量子优化算法的上述不足，考虑进行变化来达到改善的目的。将各种算
法的优化理念引入原算法形成了混合算法的方法在文献中频频出现，混合的意义
在于集各算法之长，在适当的条件下，凸显各算法的特色，促进优化的顺利进行。
这是一种改善手段，改善的本质是针对编码或更新操作加以变化，使得算法在优
化过程中每一个环节都在最大程度上发挥其作用。
但混合并不容易，虽然各种算法都能嵌入或被嵌入，但并不是依靠随意的组
合就能达到期望的效果。在求解调度问题过程中，也曾经尝试了几种组合方法，
第一章 绪论
3
结果只能说明算法用于调度的可行性，但优化的效果仍然不显著，主要表现在随
问题规模的增加，算法表现出邻域覆盖面小，搜索面不够，变化性不强等问题。
因而，扎实的理论基础，务实的开发以及大量的实验才是理想的混合算法得以诞
生的充分条件。
在量子比特编码的基础上，纳入微粒群算法(PSO)的寻优理念，保留 PSO 中的
邻域搜索及极值跟踪，采用进化计算(EA)，模拟退火算法(SA)等算法中所用到的
各种优化算子以及选择和保留等的操作方法，形成了混合量子算法(HQA)。HQA
是针对上述量子优化算法的缺陷所提出来的，从形式，理论和运算结果上来看，
的确能够较好地用于求解生产调度等问题。
§1.2.2 混合量子算法用于调度的意义
制造是人类最主要的活动之一，是国民经济的支柱产业之一。制造业为国民
经济各部门和科技、国防提供技术装备，是整个工业、经济与科技、国防的基础[6]。
据研究，早在 190 万年前的“能人”[7](Homo habilis)就能以石块为材料制造石
器工具。随着知识的积累和制造工艺的不断改进，人类经历了从手工作业到
机器作业的发展性历程，从而步入了工业时代。工业社会背景下，由于需求的
稳定，单一，制造工厂在从事生产活动的过程中不断地学习，实践和改革，得以
壮大。伴随着机器的发明，技术的成熟，劳动分工的产生，制造业得到大力发展。
随着信息技术突飞猛进，科学技术飞速发展，市场经济一统天下，生产要素
等经济技术资源在全球范围内自由流动和优化配置，经济全球化已成为当今世界
的基本特征。因而，贸易、投资、金融、生产等活动可以走出时间和空间的限制，
跨越民族和国界在全球范围内进行。全球市场对产品的需求呈饱和趋势，大热门
主导市场的时代已经过去了，随之而起的是多样化，独具一格的非热门和大热门
并存的市场，客户的消费方式和消费观念也发生了深刻的变化，导致企业间的竞
争集中到时间和品种上[8]。
由于市场环境的变化，企业本身面对的不再是单一大量的需求，而是由许多
客户群体组成的各式各样的需求总和。多品种中小批量的生产需求已成为当前的
一大态势。OEM(Original Equipment Manufacture)厂商，俗称“代工厂”随之应运
而生，包揽众多企业的制造任务。代工厂的特征就是：技术在外，资本在外，市
场在外，只有生产在内。因而，企业能把握住自己的核心－研发和销售，降低生
产的风险，赢得市场时间。而代工厂也能集中力量专攻生产。代工厂不同于以往
的制造工厂，一般规模庞大，技术成熟，有能力承接多种产品。随着产品品种的
增多，产品制造周期要求缩短，质量要求加强，资金周转加速，这一切都大大加
摘要：

I目录中文摘要ABSTRACT第一章绪论...................................................................................................................1§1.1课题的背景......................................................................................................1§1.2课题的研究意义............................................

展开>> 收起<<
混合量子算法及其在生产调度中的应用.pdf

共74页,预览8页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：牛悦 分类：高等教育资料 价格：15积分 属性：74 页 大小：2.65MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 74
评分 收藏
分享
立即下载 VIP免费下载
客服
关注