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

1、基于烟花算法的云计算多目标工程任务调度研究第 1 章 绪论1.1 研究背景及意义云计算是在分布式计算、并行计算、网格计算等技术基础上发展起来的一种计算方式。通过互联互通的网络，云计算根据不同用户的需求把共同享有的软硬件资源及各种信息提供给设备终端。它分别在基础设施层，软件开放运行平台层，应用软件层实现 IaaS(基础设施即服务)，PaaS(平台即服务)和 SaaS(软件即服务)。云计算任务调度主要研究将多个相互独立的多样化任务分配到云平台中规模庞大的虚拟资源上，满足用户 QoS 要求、最优跨度准则、完成时间最短、负载均衡等目标。因此，基于云计算环境下的任务分配可以定义为一个多目标优化问题，也是

2、一个 NP(非确定多项式)问题，采用启发式算法可以得到次最优解。群体智能算法即启发式算法，如何平衡局部搜索与全局搜索是群体智能算法研究的主要内容，以便有效逃离局部最优解。这些年，倍受关注的群体智能算法可归纳为三类，第一类是仿动物类算法，主要有蚁群优化算法、粒子群优化算法、人工蜂群优化算法、人工鱼群优化算法等；第二类是仿植物类的算法，主要有杂草优化算法、向光性算法等；第三类是仿人类的算法：主要有遗传算法、和声搜索算法等。2000 年以后，研究者们相继提出了一系列新型群体智能算法1。北京大学谭营教授等人于2010 年在第一届国际群体智能大会上发表了烟花算法的第一篇学术论文，题为Fireworks

3、algorithm for optimization;2。从此，业界开始关注烟花算法，并逐渐展开烟花算法在群体智能领域的研究。为确保能够有效地进行解的搜索，烟花算法要求在某一有限的解空间内，解和其邻域的其他解具有相似的性质，且解的邻域有意义。这个要求是烟花算法应用于优化求解的有效性关键。除此之外，烟花种群可以在全局搜索和局部搜索之间寻求一个平衡，因为每个烟花的信息交互和资源分配是基于其他烟花的适应度值进行的。同时烟花的爆炸搜索机制保证单个烟花具有较强的局部爆发性。群体中的个体局部相互作用，没有直接的中心控制因素，表现出高度并行的特点。因此，烟花算法成为一种新型的群体智能算法。正是因为烟花算法具

4、有爆发性、瞬时性、多样性、适应性和分布并行性等特点，结合近几年较热门的云计算技术，不管从理论研究的角度出发，还是从应用研究的角度分析，都具有重要的学术价值和研究意义。.1.2 国内外研究现状1.2.1 烟花算法的研究现状通过对原始烟花算法深入、细致的分析，针对原始烟花算法存在的不足，相继提出了大量的改进方法，并据此发展了各种改进算法，以及几种混合型方法，极大地提高了原始烟花算法的性能，改进了烟花算法求解不同类型优化问题的能力，丰富了研究内容。目前，烟花算法的研究还是非常初步的，还处于逐渐发展的过程中。新的思想和算法还在不断涌现，许多方面的研究还有待深化。主要集中在以下几个方面：算法的理论基础和

5、分析；各种改进方法的深入研究；混合方法的研究等。(1)理论研究方面在收敛性的理论分析工作方面，Liu 等3从理论上详细分析了烟花算法的收敛性，指出烟花算法是一个吸收马尔科夫过程，进而给出了收敛性定理并予以了严格的数学证明。此外，谭营首次研究了随机数对于烟花算法性能的影响，实验表明烟花算法对于随机数产生器的要求不高，不同的随机数生成方法对于算法性能的影响不明显4。(2)算法研究方面自 FWA 提出后，很多学者在各自领域优化问题上做了大量的研究工作。Pei等5研究了适应度函数估计对于烟花算法加速性能的影响。文中讨论了不同的适应度函数值的估计方法对于性能的影响，实验表明二次多项式模型和随机选择样本策

6、略的性能最优，并且相对于烟花算法其性能优势具有显著性。Ding 等6提出了一种 GPU-FWA(并行烟花算法)，它是基于 GPU(图形处理单元)的 FWA 的高效并行实现方案，可以全面加速 FWA 的运行速度，在当前流行的 GPU 硬件和 CUDA 平台下，现实了近 200 倍的加速性能。相对于 FWA，GPU-FWA 做了一些算子上的改动，主要的目的是减少烟花之间的交互同时使得性能损失在一个可以接受的范围内。在文献6中，烟花之间每隔一定代数才会计算计算爆炸半径和爆炸幅度。这极大地降低了烟花之间的交互，提高加速比。在文献7中，Zheng 等对于烟花算法的算子进行了细致的分析，针对 FWA 存在

7、的缺陷进行了改进，并最终提出了增强烟花算法。改进的工作包括基本烟花算法中的爆炸算子、高斯变异算子、选择算子以及映射规则等 4 个方面。Zheng 等8和 Li 等9细致地研究了烟花算法中爆炸幅度的自适应策略，并分别提出了动态搜索烟花算法和自适应烟花算法。文献10将模拟退火的思想引入到烟花优化算法中，并对 FWA 中某些单个烟花个体进行高斯扰动，提出了一种基于模拟退火与高斯扰动的烟花优化算法(SAFWA)。.第 2 章 多目标任务调度的相关技术2.1 Hadoop 平台技术2.1.1 Hadoop 平台Hadoop 是 Apache 的一个分布式计算平台，它是基于 Google 的云计算开源系统

8、。Hadoop的核心由Hadoop分布式文件系统(HDFS，HadoopDistributedFilesystem)和并行编程模型 MapReduce(Google MapReduce 的开源实现)组成，它为用户全部公开了底层基础架构。分布式文件系统 HDFS 通常由一个 NameNode 节点和多个DataNode 构成。主服务器(Master)负责管理文件的命名空间和客户端的访问操作文件系统，它由唯一的 NameNode 节点担任；从服务器(Slave)负责管理存储数据，它由多个 DataNode 节点构成。并行编程模型 MapReduce 由一个 JobTracker 进程和多个 Tas

9、kTracker 进程构成。一个 JobTracker 进程运行在 NameNode 节点上，而多个 TaskTracker 进程运行在 DataNode 节点上。NameNode 节点负责任务的调度和监控任务的执行情况；而任务分布在不同的 DataNode 节点上，DataNode 节点则负责任务的分配。所以说，HDFS 和 MapReduce 构成了 Hadoop 体系结构的重要组成部分。.2.2 Hadoop 任务调度策略Hadoop 自带的默认调度策略有先来先服务 (FIFO) 、计算能力调度策略(Capacity Scheduler)和公平调度策略(Fair Scheduler)。所

10、有调度器都采用三级调度策略，即为空闲的 slot 依次选择一个队列、作业和任务，而不同的调度器所采用的策略不同。先来先服务调度(FIFO)很容易理解。在 Hadoop 中，被提交的作业按照先后顺序排列在一个作业队列中，有且只有一个队列，新来的作业只能插入到队尾。当前作业结束后，接下来将要执行的队列总是从队首被取出来。虽然这种调度策略具有简单易行的特点，同时也降低了 JobTracker 的工作量，但是它对所有的作业都平等对待，不区分作业的紧急程度和优先级，这对小作业的运行十分不利。由于系统中每个时刻只有一个正在运行的作业，因此 FIFO 就好比是上世纪 50 年代出现的单道批处理操作系统。.第

11、 3 章 基于烟花算法的多目标任务调度模型的设计.233.1 Hadoop 任务调度算法改进的必要性 .233.2 烟花算法应用在 Hadoop 任务调度上的可行性分析 .233.2.1 烟花算法的执行过程.233.2.2 烟花算法应用在任务调度问题上的可行性.253.3 基于烟花算法的任务调度模型设计 .253.4 本章小结 .28第 4 章 基于烟花算法的多目标任务调度模型的实现.304.1 烟花算法的实现过程 .304.2 烟花算法在多目标任务调度问题上的串行实现 .324.3 烟花算法在多目标任务调度问题上的并行化实现 .344.3.1 算法的并行化模型.344.3.2 算法的并行化实

12、现.354.4 本章小结 .37第 5 章 实验结果.385.1 实验环境的搭建 .385.2 串行实验及结果 .425.3 并行化实验及结果 .455.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；参数 nu

13、mBoundA=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 与 Sla

14、ve 连接时，Slave 会生成一个加密的随机数发送给 Master，由于是用 Master 的公钥加密的，需要 Master 用私钥解开，再将解密后的结果反馈给 Slave，Slave 收到并确认结果正确，就可以与 Master 建立连接了。在这个过程中，用户不需要手工输入密码。.结 论本文对烟花算法的云计算多目标任务调度优化与研究的目的主要是为了满足云计算中用户的 QoS(Quality of Service，服务质量)需求，合理利用云数据中心的资源问题，期望通过新兴的群体智能算法来提高云计算任务调度的效率，其次是改进串行算法的编程效率，希望利用 MapReduce 并行编程模型和 Had

15、oop 平台强大的分布处理能力，解决现有Hadoop自带的调度算法在处理大规模集群计算的不足，在提高执行效率的同时保证 Hadoop 集群在处理任务调度问题时的负载均衡。首先，本文在第一章总结了云计算的研究背景及其研究意义，并介绍了关于群体智能算法以及烟花算法在国内外的研究现状。随着业界对群体智能算法的关注度越来越高，经典的粒子群优化算法和蚁群算法引起了许多专家学者的兴趣，研究群体智能算法的工作者越来越多。2010 年出现的烟花算法，其研究还是非常初步的，还处于逐渐发展的过程中。新的思想和算法还在不断涌现，许多方面的研究还有待深化。其次，第二章对 Hadoop 平台、任务调度算法、多目标优化模

16、型的求解计算方法及并行计算技术进行了导入式的介绍与分析。通过学习 Hadoop 生态系统和核心技术 HDFS 架构和 MapReduce 并行编程模型，细致剖析了 Hadoop 默认自带的任务调度策略。由于 Hadoop 任务调度策略存在某些弊端，如多个 Hadoop 集群运行时会造成集群整体利用率低下，造成复杂不均衡等问题，从而引出本文要研究的问题。本文第三章针对 Hadoop 任务调度策略存在的问题，分析了使用群体智能算法解决任务调度问题的必要性，从而提出了从任务到虚拟机的多目标任务调度模型，确定了执行时间和负载两个优化目标，定义了适应度评估函数。在第四章中，针对烟花算法的多目标任务调度问题，将第三章建立的任务调度模型进行了具体的实现。首先进行串行算法的实现，再通过建立 MapReduce 并行编程模型，将该算法的应用进行了并行化，大大提高了算法的执行效率。最后，在第五章中，在 CloudSim 仿真平台上进行串行实验，并与粒子群优化算法(PSO)和遗传算法(GA)进行有效性和执行时间上的对