基于量子粒子群算法的网络资源优化调度问题研究

VIP免费
3.0 陈辉 2024-11-19 4 4 1.34MB 80 页 15积分
侵权投诉
I
目录
中文摘要
ABSTRACT
目录 ................................................................. I
第一章 绪 论 ........................................................1
§1.1 课题研究背景及意义 ........................................... 1
§1.2 国内外研究综述 ............................................... 2
§1.3 本文研究内容及研究技术路线 ....................................4
§1.3.1 研究内容 ................................................. 4
§1.3.2 研究技术路线 ............................................. 5
第二章 网络相关理论 .................................................. 7
§2.1 网络的概念描述 ............................................... 7
§2.2 网络的基本特征 ............................................... 7
§2.3 网络图论相关理论 ............................................. 8
§2.3.1 图的定义 ................................................. 8
§2.3.2 最短路径问题 ............................................. 8
§2.3.3 最小生成树问题 ........................................... 9
§2.3.4 Steiner 树问题 ............................................ 9
§2.4 网络资源调度界定 ............................................ 10
第三章 量子粒子群及其改进算法研究 ...................................12
§3.1 微粒群算法（PSO 算法）描述 ...................................12
§3.1.1 PSO 算法基本原理 ......................................... 12
§3.1.2 PSO 算法流程 ............................................. 13
§3.1.3 微粒群改进算法介绍 ...................................... 13
§3.1.4 一种改进的自适应小生境微粒群算法设计 .................... 14
§3.2 量子粒子群及其改进算法研究 .................................. 17
§3.2.1 量子比特 ................................................ 17
§3.2.2 量子算法基本特征 ........................................ 18
§3.2.3 基本量子粒子群算法（QPSO）研究 .......................... 18
§3.2.4 一种基于协同进化的量子微粒群改进算法（MC-QPSO）设计 ..... 21
§3.3 本章小结 .................................................... 24
II
第四章 通信网络组播路由问题调度优化研究 .............................25
§4.1 组播技术概述 ................................................ 25
§4.2 组播路由问题的理论基础及算法介绍 ............................ 25
§4.2.1 组播路由问题的 Steiner 树描述 ............................ 25
§4.2.2 组播路由问题相关算法分析 ................................ 26
§4.3 带 QOS 多约束的组播路由问题 .................................. 27
§4.3.1 QoS 概念及主要参数 ....................................... 27
§4.3.2 QoS 度量 ................................................ 27
§4.3.3 QoS 路由问题的网络模型 ................................... 28
§4.4 组播路由问题数学描述及模型 .................................. 28
§4.4.1 时延约束的组播路由问题描述及模型 ........................ 28
§4.4.2 QoS 约束的组播路由问题描述及模型 ......................... 29
§4.5 组播路由问题 QPSO 算法求解设计方案 ........................... 30
§4.5.1 求解流程的设计 .......................................... 30
§4.5.2 求解方案的主要关键内容 .................................. 30
§4.5.3 生成备选路径集的深度优先算法 ............................ 31
§4.5.4 具体实例测试 ............................................ 31
§4.6 本章小结 .................................................... 35
第五章 制造网格资源调度优化研究 .....................................37
§5.1 网格及网格资源调度基本理论 .................................. 37
§5.1.1 网格概念 ................................................ 37
§5.1.2 网格基本特征 ............................................ 37
§5.1.3 网格资源调度特点分析 .................................... 38
§5.2 制造网格资源调度优化 ........................................ 38
§5.2.1 制造网格概念 ............................................ 38
§5.2.2 制造网格的基本特征 ...................................... 39
§5.2.3 制造网格资源调度体系结构设计 ............................ 39
§5.2.4 制造网格资源调度问题描述 ................................ 41
§5.3 制造网格资源静态调度优化研究 ................................ 42
§5.3.1 静态调度优化模型 ........................................ 42
§5.3.2 静态调度的量子粒子群及其改进算法设计 .................... 43
§5.4 制造网格资源动态调度优化研究 ................................ 44
§5.4.1 不确定事件分析 .......................................... 44
§5.4.2 不确定事件下的制造网格资源动态调度模型 .................. 44
§5.4.3 制造网格资源动态调度的 QPSO 算法设计 ..................... 45
§5.5 具体实例仿真 ................................................ 47
III
§5.5.1 具体实例描述 ............................................. 47
§5.5.2 算法参数设置 ............................................ 49
§5.5.3 算法求解及性能分析 ...................................... 49
§5.6 本章小结 .................................................... 49
第六章 物流网络资源调度优化研究 .....................................51
§6.1 物流网络相关理论 ............................................ 51
§6.1.1 物流网络的定义 .......................................... 51
§6.1.2 物流网络的结构描述 ...................................... 51
§6.2 物流配送网络车辆优化调度研究 ................................ 53
§6.2.1 问题描述 ................................................ 53
§6.2.2 模型建立 ................................................ 54
§6.2.3 QPSO 算法求解方案设计 .................................... 55
§6.2.3 具体实例测试分析 ........................................ 57
§6.3 应急物流配送网络车辆调度模型研究 ........................... 58
§6.3.1 问题描述 ................................................ 58
§6.3.2 模型建立 ................................................ 58
§6.4 突发事件下的应急物资调度优化研究 ............................ 60
§6.4.1 应急调度优化模型 ......................................... 61
§6.4.2 求解流程设计 ............................................ 62
§6.4.3 仿真算例 ................................................ 63
§6.5 本章小结 .................................................... 64
第七章 总结与展望 .................................................. 65
附录 量子粒子群算法求解物流网络配送调度问题部分源程序 ...............66
参考文献 ............................................................ 74
在读期间公开发表的论文和承担科研项目及取得成果 ......................78
致谢 ................................................................ 79
第一章 绪 论
1
第一章 绪 论
§1.1 课题研究背景及意义
在现实世界中，网络无处不在，从最基本的因特网（万维网）到经济网络、
资源供需网络、疾病传播网络等等，可以说，网络的影子遍及整个现代文明。
有关网络的研究在数学及其他自然科学领域有了很长的历史。早在 1736 年，
伟大的数学家莱昂哈德·欧拉开始对叫做 Konigsberg 桥的问题产生了兴趣，欧拉
利用一个图—由点（也叫做顶点或节点）以及线（也叫做边或者连接）构成的数
学现象，来表述现实的 Konigsberg 桥问题。一般来讲，网络最简单的形式是一系
列离散的节点，以及一系列连接这些节点的线路。从广义上讲，这些节点和线路
可以指任何有着关联特征的事情，比如：计算机终端和通信网路、制造资源节点
和配送线路、学术论文和相关引用等等，也正是因为网络定义的这种广泛性，才
使得网络理论知识得到如此广泛的应用。在不考虑影响事物运作的其它要素条件
下，网络图论能够清楚地描述事物及其关联特征所表现出的拓扑特性。因此，可
以说，网络图论的应用已经超越了纯数学领域，特别是在过去的几十年里，它已
经被广泛地应用到计算机科学、工程学、管理科学、经济学等各个领域。
而对网络科学的研究，也渐渐地呈现出与先前研究内容所不同的特点：第一，
越来越关注真实世界网络的特性；第二，网络不再是一种单一的拓扑结构，而是
一种动态分布式的系统所体现出的架构。第三，网络也不再是静态的、不变的节
点和要素系统，而是动态的、随着时间的发展而变化的系统。特别是，随着现代
信息技术以及全球化进程的飞速发展，现实世界中的这种网络化的结构形态也变
得越来越明显。
一般的讲，网络资源是指利用计算机系统通过通信设备和网络软件管理的信
息资源。在本文的研究中，对上述定义进行了适当地广义拓展，我们认为：网络
资源应该泛指那些具有基本网络结构特征（即具有节点和关联线路），或者能抽象
出这种基本网络结构特征的所有有效资源。比如：信息网络资源、物料网络资源、
资本网络资源等等。从网络资源的这种广义定义出发，我们知道，处在网络要素
节点上的各种资源能够通过它们之间的连通链路，实现资源的共享或者调度。因
此，如何有效的实现网络资源的合理调度，以发挥资源的网络化效应，减少资源
调度过程中浪费/损失，是当前资源调度领域的一个重要研究课题。
基于量子粒子群算法的网络资源优化调度问题研究
2
调度问题本身又是一个优化分配的过程，它研究的的目的就是优化一个或多
个决策目标，以实现将有限的资源合理地分配给特定时间的不同任务。因此，合
理的调度优化方案的求解，是每个管理者（决策者）进行决策的关键。然而，调
度这类问题大部分属于 NP-hard 问题，虽然这类问题描述起来相对容易，但是其
求解过程却相当困难。特别是，随着各种调度资源种类的不断增大，以及调度问
题规模的不断扩大，调度问题表现地也更加复杂。许多调度问题的求解至今没有
可以精确求得其最优解的多项式时间算法。目前对于 NP-hard 问题的求解，主要
有随机搜索算法，以及模拟退火算法、遗传算法、蚁群算法、粒子群算法等智能
优化算法，通过获得满意解以满足资源调配的需要。由于各种算法各有特点、各
有优劣，因此，寻找解决资源调度这类问题的、合适的求解算法仍是当前研究的
热点问题。
§1.2 国内外研究综述
根据上述对网络资源的广义定义，可知：在现实世界中，可以归结为网络资
源的资源种类有很多，因此，能够归结为网络资源优化调度这类问题进行研究的
问题也不在少数，比如说：国家配电网规划问题、石油、天然气管道的路径优化
问题、城市车辆调度问题、制造资源调度分配问题、物流资源调度优化问题等等。
鉴于网络资源调度这类问题所具有的共性特点，本文主要选取了在当前研究
领域中，几个比较典型的，而且很有代表性的网络资源调度问题进行研究，如：
计算机通信网络领域中的 QoS 组播路由调度问题、现代制造环境下的网格资源调
度问题、供应链一体化背景下的物流网络资源调度优化问题，因此，下面着重考
察这几个典型问题当前的国内外研究现状。
(1) 通信网络 QoS 组播路由问题研究现状综述
随着现代网络技术的飞速发展，计算机通信领域中的多媒体技术得到了广泛
的发展。在这种条件下，如何向客户提供具有完全的性能保证或一定性能保证的
服务，是多媒体服务应用的关键。对多媒体信息资源传播过程中的服务质量 QoS
(Quality of Service) 也提出了更高的要求，一般来讲，在多媒体传输时，需要
保证一定的传输带宽，延迟抖动和丢包率，并满足特定的端到端的延迟率。 QoS
路由技术是网络技术发展的核心技术，它主要要求在多约束条件下计算可行路径，
并对多条可能存在的路径进行进一步优化。
目前，针对不同的基于 QoS 约束的多播路由问题，已提出许多相应的路由算
法。最短路径算法：Dijkstra 算法和 Ford 算法是两个最著名的最短路径算法，
第一章 绪 论
3
其时间复杂度分别为
2
( )O n
和
3
( )O n
。最小生成树算法：著名的集中式最小生成树
算法是 Prim 算法[1] 。Steiner 树算法[2]：基于 Steiner 树的多播路由问题求解目的
在于构建一棵总代价最小的多播树。 Reeves 和Salama 等学者通过对已有的启发
式算法的仿真指出由 Kou 和Berman 提出的 KMB[3]算法有较好性能。在上述对 QoS
路由路由算法研究的基础上，不同学者提出了其它不同的智能优化算法，文献[4]
总结了基于禁忌搜索的 QoS 路由算法、 基于模拟退火的 QoS 路由算法、 基于遗
传算法的 QoS 路由算法和基于蚁群算法的 QoS 路由算法的方法和步骤，并分析了
它们各自的特点。从中可以看出：禁忌搜索算法、 模拟退火算法、遗传算法等这
些算法，特别是遗传算法得到了很好的应用。然而，面对各种问题的特殊性和复
杂性，每一种算法都有其自身的优缺点(具体见文献[4]的分析)。针对不同方法的
缺陷， 在 QoS 路由问题的求解过程中，也经常采用多种方法混合的策略。如：
采用遗传算法与模拟退火算法的混合策略、遗传算法与禁忌搜索的混合策略[5]、
遗传算法与蚁群算法的混合策略[6]等等。即使如此，这些传统的启发式算法在解
决多约束 QoS 路由问题中依然存在着针对大型网络，算法性能不能满足要求，很
难找到实际存在的可行路径的问题。
(2) 网络化制造环境下的网格资源调度研究现状综述
网络技术的迅速发展，不仅深刻地改变了人们生活和交流方式，也对企业的
生产经营方式产生了巨大的影响，网络经济就是在这样的背景下产生的。随着网
络经济的出现和发展，传统的制造模式也发生了根本性的变化，现代制造业已不
再局限于区域性经济，而是面临全球性的市场、资源、技术和人员的竞争，市场
需求也更具有个性化和多样化，制造资源市场也已发展成为一个开放性的全球大
市场，如何实现资源最合理的分配调度可以说是当前网络制造的根本目的。
网格（grid）[7]技术是一种重要的信息技术，它的主要目标是实现网络虚拟
环境上的高性能资源共享和协同工作，消除信息孤岛和资源孤岛。国外网格的应
用主要在于计算网格，由于其起步较早，所以相对比较成熟，而且有好多已经应
用于或者正在应用于重要的计算网格项目。国内的网格研究情况，稍晚于国外，
但进步明显，目前的主要应用领域也是计算网格，不过，最近清华大学和上海交
通大学也已经开始对制造网格的探索，已经完成的网格研究项目主要有清华大学
的先进计算基础设施 ACI 和以中科院计算为主的国家高性能计算环境 NHPCE，
此外，全国还有几十所大学和研究机构已经开始开展各种网格研究，然而，制造
网格资源调度的研究还不多，暂时没有形成主要的研究理念。
目前，对制造资源调度问题的研究，主要有以下几个方面的内容：运用 AHP、
数据包络法（DEA）、贪心算法等方法，研究虚拟企业伙伴选择、动态联盟成员
摘要：

I目录中文摘要ABSTRACT目录.................................................................I第一章绪论........................................................1§1.1课题研究背景及意义...........................................1§1.2国内外研究综述...............................................2§1.3本文研究内容及研究技术路线.........................

展开>> 收起<<
基于量子粒子群算法的网络资源优化调度问题研究.pdf

共80页,预览8页

还剩页未读， 继续阅读

相关推荐

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

开通VIP享超值会员特权

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

作者详情

相关内容

更多

推荐作者

热门标签

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