上海论文网是一家老字号代写网站,专业提供代写硕士毕业论文服务。

基于烟花算法的云计算多目标工程任务调度研究

发布时间:2018-08-19 09:56 论文编辑:lgg 所属栏目:工程论文 关键词: 工程论文多目标优化烟花算法

本文是一篇工程论文,工程论文是学术作品,因此其表述要严谨简明,重点突出,专业常识应简写或不写,做到层次分明、数据可靠、文字凝练、说明透彻、推理严谨、立论正确,避免使用文学

本文是一篇工程论文,工程论文是学术作品,因此其表述要严谨简明,重点突出,专业常识应简写或不写,做到层次分明、数据可靠、文字凝练、说明透彻、推理严谨、立论正确,避免使用文学性质的或带感情色彩的非学术性语言。论文中如出现一个非通用性的新名词、新术语或新概念,需随即解释清楚。(以上内容来自百度百科)今天为大家推荐一篇工程论文,供大家参考。
 
第 1 章 绪论
 
1.1 研究背景及意义
云计算是在分布式计算、并行计算、网格计算等技术基础上发展起来的一种计算方式。通过互联互通的网络,云计算根据不同用户的需求把共同享有的软硬件资源及各种信息提供给设备终端。它分别在基础设施层,软件开放运行平台层,应用软件层实现 IaaS(基础设施即服务),PaaS(平台即服务)和 SaaS(软件即服务)。云计算任务调度主要研究将多个相互独立的多样化任务分配到云平台中规模庞大的虚拟资源上,满足用户 QoS 要求、最优跨度准则、完成时间最短、负载均衡等目标。因此,基于云计算环境下的任务分配可以定义为一个多目标优化问题,也是一个 NP(非确定多项式)问题,采用启发式算法可以得到次最优解。群体智能算法即启发式算法,如何平衡局部搜索与全局搜索是群体智能算法研究的主要内容,以便有效逃离局部最优解。这些年,倍受关注的群体智能算法可归纳为三类,第一类是仿动物类算法,主要有蚁群优化算法、粒子群优化算法、人工蜂群优化算法、人工鱼群优化算法等;第二类是仿植物类的算法,主要有杂草优化算法、向光性算法等;第三类是仿人类的算法:主要有遗传算法、和声搜索算法等。2000 年以后,研究者们相继提出了一系列新型群体智能算法[1]。北京大学谭营教授等人于2010 年在第一届国际群体智能大会上发表了烟花算法的第一篇学术论文,题为“Fireworks algorithm for optimization”[2]。从此,业界开始关注烟花算法,并逐渐展开烟花算法在群体智能领域的研究。为确保能够有效地进行解的搜索,烟花算法要求在某一有限的解空间内,解和其邻域的其他解具有相似的性质,且解的邻域有意义。这个要求是烟花算法应用于优化求解的有效性关键。除此之外,烟花种群可以在全局搜索和局部搜索之间寻求一个平衡,因为每个烟花的信息交互和资源分配是基于其他烟花的适应度值进行的。同时烟花的爆炸搜索机制保证单个烟花具有较强的局部爆发性。群体中的个体局部相互作用,没有直接的中心控制因素,表现出高度并行的特点。因此,烟花算法成为一种新型的群体智能算法。正是因为烟花算法具有爆发性、瞬时性、多样性、适应性和分布并行性等特点,结合近几年较热门的云计算技术,不管从理论研究的角度出发,还是从应用研究的角度分析,都具有重要的学术价值和研究意义。
............
 
1.2 国内外研究现状
 
1.2.1 烟花算法的研究现状
通过对原始烟花算法深入、细致的分析,针对原始烟花算法存在的不足,相继提出了大量的改进方法,并据此发展了各种改进算法,以及几种混合型方法,极大地提高了原始烟花算法的性能,改进了烟花算法求解不同类型优化问题的能力,丰富了研究内容。目前,烟花算法的研究还是非常初步的,还处于逐渐发展的过程中。新的思想和算法还在不断涌现,许多方面的研究还有待深化。主要集中在以下几个方面:算法的理论基础和分析;各种改进方法的深入研究;混合方法的研究等。
 
(1)理论研究方面
在收敛性的理论分析工作方面,Liu 等[3]从理论上详细分析了烟花算法的收敛性,指出烟花算法是一个吸收马尔科夫过程,进而给出了收敛性定理并予以了严格的数学证明。此外,谭营首次研究了随机数对于烟花算法性能的影响,实验表明烟花算法对于随机数产生器的要求不高,不同的随机数生成方法对于算法性能的影响不明显[4]。
 
(2)算法研究方面
自 FWA 提出后,很多学者在各自领域优化问题上做了大量的研究工作。Pei等[5]研究了适应度函数估计对于烟花算法加速性能的影响。文中讨论了不同的适应度函数值的估计方法对于性能的影响,实验表明二次多项式模型和随机选择样本策略的性能最优,并且相对于烟花算法其性能优势具有显著性。Ding 等[6]提出了一种 GPU-FWA(并行烟花算法),它是基于 GPU(图形处理单元)的 FWA 的高效并行实现方案,可以全面加速 FWA 的运行速度,在当前流行的 GPU 硬件和 CUDA 平台下,现实了近 200 倍的加速性能。相对于 FWA,GPU-FWA 做了一些算子上的改动,主要的目的是减少烟花之间的交互同时使得性能损失在一个可以接受的范围内。在文献[6]中,烟花之间每隔一定代数才会计算计算爆炸半径和爆炸幅度。这极大地降低了烟花之间的交互,提高加速比。在文献[7]中,Zheng 等对于烟花算法的算子进行了细致的分析,针对 FWA 存在的缺陷进行了改进,并最终提出了增强烟花算法。改进的工作包括基本烟花算法中的爆炸算子、高斯变异算子、选择算子以及映射规则等 4 个方面。Zheng 等[8]和 Li 等[9]细致地研究了烟花算法中爆炸幅度的自适应策略,并分别提出了动态搜索烟花算法和自适应烟花算法。文献[10]将模拟退火的思想引入到烟花优化算法中,并对 FWA 中某些单个烟花个体进行高斯扰动,提出了一种基于模拟退火与高斯扰动的烟花优化算法(SAFWA)。
.........
 
第 2 章 多目标任务调度的相关技术
 
2.1 Hadoop 平台技术
2.1.1 Hadoop 平台
Hadoop 是 Apache 的一个分布式计算平台,它是基于 Google 的云计算开源系统。Hadoop的核心由Hadoop分布式文件系统(HDFS,HadoopDistributedFilesystem)和并行编程模型 MapReduce(Google MapReduce 的开源实现)组成,它为用户全部公开了底层基础架构。分布式文件系统 HDFS 通常由一个 NameNode 节点和多个DataNode 构成。主服务器(Master)负责管理文件的命名空间和客户端的访问操作文件系统,它由唯一的 NameNode 节点担任;从服务器(Slave)负责管理存储数据,它由多个 DataNode 节点构成。并行编程模型 MapReduce 由一个 JobTracker 进程和多个 TaskTracker 进程构成。一个 JobTracker 进程运行在 NameNode 节点上,而多个 TaskTracker 进程运行在 DataNode 节点上。NameNode 节点负责任务的调度和监控任务的执行情况;而任务分布在不同的 DataNode 节点上,DataNode 节点则负责任务的分配。所以说,HDFS 和 MapReduce 构成了 Hadoop 体系结构的重要组成部分。
.........
 
2.2 Hadoop 任务调度策略
Hadoop 自带的默认调度策略有先来先服务 (FIFO) 、计算能力调度策略(Capacity Scheduler)和公平调度策略(Fair Scheduler)。所有调度器都采用三级调度策略,即为空闲的 slot 依次选择一个队列、作业和任务,而不同的调度器所采用的策略不同。先来先服务调度(FIFO)很容易理解。在 Hadoop 中,被提交的作业按照先后顺序排列在一个作业队列中,有且只有一个队列,新来的作业只能插入到队尾。当前作业结束后,接下来将要执行的队列总是从队首被取出来。虽然这种调度策略具有简单易行的特点,同时也降低了 JobTracker 的工作量,但是它对所有的作业都平等对待,不区分作业的紧急程度和优先级,这对小作业的运行十分不利。由于系统中每个时刻只有一个正在运行的作业,因此 FIFO 就好比是上世纪 50 年代出现的单道批处理操作系统。
........
 
第 3 章 基于烟花算法的多目标任务调度模型的设计...........23
3.1 Hadoop 任务调度算法改进的必要性 .........23
3.2 烟花算法应用在 Hadoop 任务调度上的可行性分析 ......23
3.2.1 烟花算法的执行过程.....23
3.2.2 烟花算法应用在任务调度问题上的可行性.............25
3.3 基于烟花算法的任务调度模型设计 ...........25
3.4 本章小结 ...........28
第 4 章 基于烟花算法的多目标任务调度模型的实现...........30
4.1 烟花算法的实现过程 .............30
4.2 烟花算法在多目标任务调度问题上的串行实现 .............32
4.3 烟花算法在多目标任务调度问题上的并行化实现 .........34
4.3.1 算法的并行化模型.........34
4.3.2 算法的并行化实现.........35
4.4 本章小结 ...........37
第 5 章 实验结果.....38
5.1 实验环境的搭建 ..........38
5.2 串行实验及结果 ..........42
5.3 并行化实验及结果 ......45
5.4 本章小结 ...........46
 
第 5 章 实验结果
 
5.1 实验环境的搭建
5.1.1 串行算法的实验环境
串行算法的实验环境在 Cloudsim 仿真平台[46]上进行。实验环境:Intel(R)Core(TM) M-5Y10c,2GHz 主频,4.00GB 内存,Matlab7.0。烟花算法的主要参数设置:最大爆炸幅度 numMaxAmplitude=5;高斯火花个数 numGaussianSparks=1;火花总数 numMaxSparks=5;参数 numBoundA=0.8;参数 numBoundB=0.04。粒子群优化算法的主要参数设置:粒子个体跟踪自己历史最优值的权重 C1=2;粒子个体跟踪群体最优值的权重 C2=2;惯性权重 W=0.8。遗传算法主要参数设置:个体编码长度 Length=6;变异率 PM=0.05。配置 master 无密码登录所有的 slave。Master 作为客户端,要实现与服务器Slave 无密码公钥认证,先要在 Master 上生成一对包含一个公钥和一个私钥的密钥对,再克隆公钥发送到所有的 Slave 上。Master 和 Slave 之间建立通信的过程是这样的:Master 通过安全协议 SSH 与 Slave 连接时,Slave 会生成一个加密的随机数发送给 Master,由于是用 Master 的公钥加密的,需要 Master 用私钥解开,再将解密后的结果反馈给 Slave,Slave 收到并确认结果正确,就可以与 Master 建立连接了。在这个过程中,用户不需要手工输入密码。