混合量子算法及其在生产调度中的应用
VIP免费
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)厂商，俗称“代工厂”随之应运
而生，包揽众多企业的制造任务。代工厂的特征就是：技术在外，资本在外，市
场在外，只有生产在内。因而，企业能把握住自己的核心－研发和销售，降低生
产的风险，赢得市场时间。而代工厂也能集中力量专攻生产。代工厂不同于以往
的制造工厂，一般规模庞大，技术成熟，有能力承接多种产品。随着产品品种的
增多，产品制造周期要求缩短，质量要求加强，资金周转加速，这一切都大大加
混合量子算法及其在生产调度中的应用
4
剧了代工厂运作和管理的复杂程度。
技术在进步，观念在更新，以信息化，自动化带动工业化，走新型工业化道
路是代工厂未来的发展方向。人类从工业社会步入信息社会，新的信息制造观代
替了机械的制造观，它将制造过程看成一个对制造系统注入生产信息，从而使产
品信息获得增值的过程。在这个观念中，现代制造技术的观念逐步浮出水面，其
发展重点在于提高信息处理能力，这就离不开信息技术，计算机技术，自动化技
术，人工智能技术，数控技术和系统制造技术的发展。
随着市场竞争的日趋激烈，为了增强企业的竞争力、提高企业的经济效益和
社会效益，每个企业都在寻求较好的方式方法来提高企业的生产、经营和管理效
率。而对于代工厂等制造工厂来说，整个先进生产制造系统实现的核心是生产调
度问题。生产调度是代工厂管理工作得以优化的一种理念，追逐的目标是高效、
低耗、灵活、准时地生产合格产品和提供满意服务[8]，而在制造系统中，生产调度
问题是理论研究中最基本、最重要和最困难的问题之一。作为生产管理系统的核
心内容和关键问题，其研究具有重要的理论和实用价值，同时它对生产运作管理
和现场管理也具有重大的现实意义。
多品种中小批量的生产模式，在代工厂尤为普遍，是一大难题，同时也是一
大技术难关。针对这一难题，文献[8]提出了减少零件变化与提高生产系统的柔性，
指出要应对产品的变化性，只有从产品本身出发，将其多变性转换为零件，工艺
的少变，并推行三化(产品系列化、零部件标准化、通用化)和采用成组技术。同时，
先进管理技术准时制生产(JIT)和精益生产(LP)所倡导的“拉”式生产管理模式以最
终需求为准，倒推出制造过程中各物料，人力，设备所需的数量和所需的时刻，
能够有效减少浪费。
生产调度，作为实施过程中不可或缺的一环，却鲜为人所关注。其实，一个
工厂的技术水平的好坏，从调度的执行中可窥一斑。生产调度广义上是指对生产
过程进行作业计划[9]。狭义上，生产调度可以理解为根据待完成的订单情况，对车
间中待加工的物料，制造用的辅助工具，生产设备，人员等资源的配置。配合先
进的管理技术，运筹技术，优化技术，信息技术和自动化技术，对车间中的可用
资源进行合理地调度，能保证生产活动稳步进行，有效避免浪费和加工冲突，提
高资源利用率，让工作人员各得其所，实现按时按质按量完成生产，满足客户的
多样化需求，最终能够提高工厂的技术水平，加强工厂的竞争力。且对调度活动
的优化，也正迎合了将来企业在动态多变，充满不确定的市场环境下对品种和时
间的追求。
依托电子计算机和信息技术的发展，柔性化，自动化，智能化是生产调度将
第一章 绪论
5
来的发展方向。由于生产调度实现的是对有限资源的选择和组合，这与组合优化
问题十分相似，故而可以运用求解组合优化问题的一些方法进行求解优化。由于
车间里的调度涉及因素多，难度大，运行环境充满不确定性，故而难以用数学模
型精确地构建车间中各种调度问题模型，往往采取简化的方法，得到静态调度模
型。尽管如此，静态调度模型仍然是一类 NP 难题，具有复杂的不确定性、多目标、
多约束、多资源相互协调的特点。正因为调度过程有着上述特性，要形成一个好
的调度方案，并不容易。中国的一些制造企业在进行生产调度的时候并不是依靠
科学化的管理，而是由计划员很随意地指定，这是我们亟需改善的地方。
为了大力提高算法的并行性，加大优化的效果和速度，快速响应实际生产调
度问题的要求，大大简化生产调度系统的复杂性，提高系统的响应性[10-11]，研究
HQA 在生产调度问题中的应用是必要的，有意义的。对解决大规模实际调度问题
有重要的作用。
§1.3 课题的国内外研究现状
§1.3.1 量子算法国内外研究现状
量子算法是配合量子计算机，实现并行计算的软计算方法，其求解问题的能
力和计算速度将远远超过经典算法。将进化计算和量子计算相结合的研究始于 90
年代后期，主要分成两大领域。一个领域是研制采用自动规划技术的新量子算法，
另一个领域是研究在经典计算机上做运算的量子进化计算。量子力学已逐步走进
人们的生活，而量子计算也不仅仅专为量子计算机服务了，组合优化是新的应用
领域之一。
目前量子优化算法的应用极为广泛，已应用于 TSP 问题[12-14]，背包问题[15-18]，
函数优化[19-21]等经典优化问题，还应用于多址干扰的多用户检测问题[22-23]，布局问
题[24]，投资组合优化[25]，寻找图像稀疏分解的最佳匹配原子[26]，FIR 滤波器设计[27]
等问题。量子优化算法能够发展到现在的状况，是国内外研究者们的创新思维争
相斗艳的结果。
早在 1996 年的进化计算国际会议上，Ajit Narayanan 和Mark Moore 等就提出
了量子衍生遗传算法(QIGA)。文献[28]在求解 TSP 时，提出用变异及交替边杂交
来更新个体，并设计了全干扰交叉算子。
Kuk-Hyun Han 和Jong-Hwan Kim 等分别在 2000 和2001 年的进化计算国际会
议上提出了遗传量子算法(GQA)[29]和并行量子遗传算法(PQGA)[30]。其中，针对背
包问题，将 GQA 与基于罚函数，基于修正方法及基于解码思想的几种方法分别进
摘要：
展开>>
收起<<
I目录中文摘要ABSTRACT第一章绪论...................................................................................................................1§1.1课题的背景......................................................................................................1§1.2课题的研究意义............................................
相关推荐
-
跨境电商商业计划书模版VIP免费
2025-01-09 27 -
跨境电商方案范文VIP免费
2025-01-09 14 -
创业计划书VIP免费
2025-01-09 18 -
xx生鲜APP计划书VIP免费
2025-01-09 12 -
跨境电商创业园商业计划书(盈利模式)VIP免费
2025-01-09 8 -
跨境电商计划书VIP免费
2025-01-09 13 -
绿色食品电商平台项目计划书VIP免费
2025-01-09 22 -
农产品电子商务商业计划书VIP免费
2025-01-09 8 -
农村电商平台商业计划书VIP免费
2025-01-09 13 -
生鲜商城平台商业计划书VIP免费
2025-01-09 21
作者：牛悦
分类：高等教育资料
价格：15积分
属性：74 页
大小：2.65MB
格式：PDF
时间：2024-11-19
