云环境下结合改进粒子群优化与检查点技术的容错调度算法

云计算环境下基于改进粒子群算法的任务调度张照胜;李蜀瑜【期刊名称】《电子设计工程》【年(卷),期】2016(024)015【摘要】为了优化云计算环境下任务调度，考虑调度过程中任务的最短完成时间、系统的负载均衡和经济成本3个目标约束，然而3个目标约束之间存在冲突，因此提出了一种使用改进粒子群优化算法来解决云计算任务调度中多目标优化问题，达到同时兼顾3个目标约束的目的。

选择惯性权重的模糊自适应策略对粒子群算法进行改进，从而能很好的平衡粒子的全局搜索能力和局部搜索能力，尽量避免过早收敛和陷入局部极值，并且引入移动子和负载因子的概念，用于实现算法对云计算环境下的任务调度。

仿真结果表明，该算法对多目标优化问题，具有较好的寻优能力。

%For optimizing the task scheduling of cloud computing environment,it processes to consider the shortest completion time, load balancing, system constraints and economic costs of the three objectives, however, there is still have a conflict between these three objectives of constraints, thus we propose a method of using improved Particle swarm optimization (PSO) algorithms to solve the purpose of cloud computing task scheduling for multi-objective optimization problem to consider the three objectives constraints. Improving the global search ability and local search capability by using Fuzzy Adaptive Inertia Weight PSO strategy so that the particles can be well balanced to avoid premature convergence and local extremum, introducing the concept of the moving element andthe load factor for the realization of task scheduling algorithm for cloud computing environments.Simulation results show that the algorithm for multi-objective optimization problem has better search capability.【总页数】5页(P5-8,12)【作者】张照胜;李蜀瑜【作者单位】陕西师范大学计算机科学学院，陕西西安 710119;陕西师范大学计算机科学学院，陕西西安 710119【正文语种】中文【中图分类】TN602【相关文献】1.基于改进粒子群算法的云计算任务调度策略 [J], 丁阳;颜惠琴2.云计算环境下基于改进粒子群的任务调度算法 [J], 封良良;张陶;贾振红;夏晓燕;覃锡忠3.基于改进粒子群算法的云计算任务调度算法 [J], 张陶;于炯;杨兴耀;廖彬4.基于改进粒子群算法的云计算任务调度策略 [J], 马亮;李晓5.云计算环境下基于粒子群算法的任务调度研究 [J], 韦湘夫;汪一百因版权原因，仅展示原文概要，查看原文内容请购买。

第33卷第4期2017年7月齐齐哈尔大学学报（自然科学版）Journal of Qiqihar University(Natural Science Edition)Vol.33,No.4July,2017云计算中基于改进离散粒子群优化的任务调度方案郑建秋(厦门城市职业学院，福建厦门361009)摘要：针对云计算中现有智能任务调度算法容易陷入局部最优的问题，提出一种基于改进型离散粒子群优化(D P S0)算法的任务调度方案。

对传统DPS0算法中的粒子位置更新公式中的惯性权重进行改进，使其根据迭代次数非线性递减，提高算法的搜索能力；另外，融入了随机扰动操作，避免算法陷入局部最优。

实验结果表明，与传统遗传算法和粒子群算法相比，该方案能够获得最优的调度策略，有效降低任务的完成时间。

关键词：云计算；任务调度；离散粒子群优化；惯性权重；随机扰动中图分类号：TP306.1 文献标志码：兴文章编号：1007-984X(2017)04-0006-05云计算代1]是一种新的计算技术，用户可以利用云计算租借软件、硬件、基础设施和计算资源作为每个 用户的基础资源，并将他们的工作提交给云计算处理或者云存储。

云计算中的用户任务通常以工作流方式 进行。

科学工作流代2以是指将一系列在科学研究中遇到的数据管理、计算、分析等工作变成一个个独立的服 务，再把这些服务通过数据链接组合在一起，满足研究人员科学实验和数据处理中的需要，从而实现相应 的处理与科学计算'传统的计算环境已很难满足科学工作流的需要。

云计算以高性能的计算资源与海量 的存储资源为科学工作流应用提供了一种全新的部署和执行方式'目前，云计算环境下工作流任务调度方案作为云计算工作流技术的重要组成部分，已经成为该领域内 的研究热点。

工作流任务调度的主要目标是减少任务执行的总时间，减少资源的空闲时间，提高了资源利 用率代4]。

任务调度是一个组合NP-完全问题，启发式智能算法是解决这种问题的一种有效手段，常用的智 能算法有遗传算法（GA)、粒子群算法（PS0)、蚁群算法（AC0)等。

基于改进粒子群算法的车辆调度优化研究一、引言随着物流行业的发展和扩大，车辆调度优化问题显得越来越重要。

车辆调度问题是一个NP完全问题，其优化难度很大。

传统的方法往往需要大量计算时间，并且不能保证得到最优解。

为了解决这个问题，研究人员已经尝试过多种优化算法，其中包括遗传算法、模拟退火算法、禁忌搜索算法和粒子群算法。

然而，这些优化算法在处理车辆调度问题时面临着许多的挑战。

本文基于改进粒子群算法，进行车辆调度优化研究。

本文将介绍车辆调度问题，并对改进的粒子群算法进行阐述。

二、车辆调度问题车辆调度问题是一种优化问题，在这个问题中需要将一定的资源分配给一定的任务，同时使得任务的执行效率最大化，同时减少延误和等待时间。

在车辆调度问题中，我们需要确定最佳的车辆路径，以便最大化服务质量同时降低成本。

车辆调度问题是一个NP完全问题。

NP完全问题是指一类问题，在多项式时间内可以验证解的正确性但是无法在多项式时间内求解最优解。

通常情况下，需要使用启发式算法来进行优化。

在实际的车辆调度中，有很多限制和约束。

以下是车辆调度优化问题的一些限制条件：- 需要达到特定的驾驶员数量- 车辆需要在特定的时间内完成任务- 车辆在完成任务时需要遵守特定的交通规则- 每个任务需要耗费特定的时间- 每个任务需要维护特定的服务级别三、粒子群算法粒子群算法是一种群体智能的优化算法，模拟群体中个体的行为，通过模拟群体中的信息交流、合作和竞争，以解决优化问题。

粒子群算法最初由Kennedy和Eberhart在1995年提出。

该算法模拟鸟群和鱼群等自然生物群体的群体行为，通过不断调整个体的移动位置和速度，以寻求适应性更强的解决方案。

通常情况下，粒子群算法需要定义以下三个要素：- 群体的规模（粒子数）- 粒子的移动速率- 粒子的适应度评价方法在粒子群算法中，每个粒子的位置和速度都是一个n维向量，其中n为待优化问题的维数。

在每个时刻，每个粒子会根据当前的速度和位置，计算其在搜索空间（待优化问题的解空间）中的适应度函数。

基于改进量子粒子群算法的云计算资源调度赵莉【摘要】资源调度优化是云计算系统应用中的关键技术，针对标准量子粒子群优化算法收敛速度慢、求解效率低的缺陷，提出一种基于改进量子粒子群算法的云计算资源调度方法。

首先在分析云计算资源调度研究现状的基础上，建立了相应的数学模型，然后采用量子粒子群优化算法对其进行求解，在求解过程中，对平均最优位置进行随机扰动，协助粒子逃离局部最优解，最后采用通过仿真实验对其性能进行分析。

结果表明，该文方法可以有效提高云计算资源的利用率，保证它们之间负载均衡，具有较好的应用价值。

%Resources scheduling is the key technology in the application of the cloud computing system. In view of the defects of slow convergence speed and low efficiency of the standard quantum particle swarm optimization algorithm,a cloud computing resource scheduling method based on the improved quantum particle swarm optimization is proposed. A mathematical model is established based on the analysis of the present situation of cloud computing resources scheduling. The quantum particle swarm optimization algorithm is used to solve the problem in which the average optimal position is randomly disturbed to help particles escape from the local optimal solution. The experiment is used to test and analyze its performance. The results show that the proposed method can effectively improve the utilization of cloud computing resources, ensuring the load balance and good application value.【期刊名称】《南京理工大学学报（自然科学版）》【年(卷),期】2016(040)002【总页数】6页(P223-228)【关键词】云计算系统;量子粒子群算法;资源调度方法;资源利用率;数据处理;群智能优化算法;数学模型【作者】赵莉【作者单位】信阳农林学院信息工程学院，河南信阳464000【正文语种】中文【中图分类】TP391随着信息技术的不断发展,数据处理量越来越大,传统计算机技术难以满足其要求,同时人们对数据处理服务质量要求也日益提高,在该背景下出现了云计算(Cloud computing)[1,2]。

基于改进粒子群算法的云资源调度袁正午;李君琪【摘要】Particle swarm optimization (PSO)is easy to fall into the local optimum and precocious phenomenon occurs in the process of iteration.To improve the efficiency of cloud computing resource scheduling,an improved particle swarm optimization algorithm was put forward.The weight of cognitive term and social term changed along with the times of iteration,which was more in line with the obj ective laws of particle swarm optimization.Experiments verify that the search ability of the improved al-gorithm is stronger and it offers better cloud computing resource scheduling solution.%粒子群算法 (particle swarm optimization,PSO)迭代过程易陷入局部最优并发生 "早熟"现象.为提高云计算资源利用效率,改进粒子群算法,并将其应用于云资源调度.改进算法中认知项和社会项权重随迭代次数变化,更加符合粒子群算法的客观规律.实验结果表明,改进算法全局搜索能力更强,能获得更优的云计算资源调度方案.【期刊名称】《计算机工程与设计》【年(卷),期】2016(037)002【总页数】5页(P401-404,412)【关键词】云计算;改进粒子群算法;资源调度;适应度;迭代【作者】袁正午;李君琪【作者单位】重庆邮电大学计算机科学与技术学院3S技术集成与应用研究所,重庆400065;重庆邮电大学计算机科学与技术学院3S技术集成与应用研究所,重庆400065【正文语种】中文【中图分类】TP393通过虚拟化技术，云计算将大量闲散计算资源整合到一起，变成一个庞大的虚拟资源池，用户可以按需获得各种资源，从而满足人们对大量数据的处理要求[1]。

求解云计算任务调度的粒子群优化算法研究云计算是一种新兴的计算技术，它将计算任务分配到云服务器上，从而提供充足的资源和更强大的性能。

但是，由于计算任务的复杂性和数量的增加，对于任务调度的要求也日益提高。

粒子群优化算法（PSO）在空间搜索中具有良好的性能，可以有效地帮助我们优化计算任务调度问题，而这正是本文要研究的课题。

本文将通过深入研究粒子群优化算法，探讨如何将粒子群优化算法用于云计算任务调度。

一、粒子群优化算法介绍粒子群优化算法（PSO）是一种基于智能体的优化算法，用于在各种实际应用中优化给定的目标函数。

它是一种群体智能的算法，模拟大量的粒子、昆虫或鸟类飞行的运动行为以找到最优解。

该算法是由James Kennedy和Russell最先提出的，并被许多人用于求解大规模优化问题，其中包括复杂学习、决策、控制、预测和计算任务。

PSO算法的基本概念是模拟群体智能和规则，通过粒子（体系结构）的迭代搜索来解决优化问题，使粒子从一组初始位置中以最小的空间进行优化搜索。

算法的基本思想是：每个粒子都有自己的速度和位置，它们的运动由当前位置和新位置的最优值决定，两者之间的速度差称为参数，用于控制粒子的运动。

当每个粒子搜索到更佳的位置时，它会更新自己的位置，而其他粒子将根据该位置更新自己的位置，直到所有粒子都能够达到全局最优解为止。

二、粒子群优化算法在云计算任务调度中的应用在云计算任务调度中，PSO算法可以作为一个强大的工具来优化任务调度问题，以提高任务调度的效率和准确性。

当云环境中的任务变得复杂时，PSO算法可以帮助我们解决众多调度任务所面临的挑战。

首先，PSO算法可以帮助解决任务调度的细节问题，以有效地确定调度的结果。

它可以从许多不同的策略中构建一个最佳调度方案，从而消除权衡最优策略所存在的风险。

此外，由于PSO算法是基于吸引力和排斥力的规则，所以它可以更容易地运行任务，并在有限的时间内完成任务调度。

另外，PSO算法还可以提高云计算任务调度的灵活性，这是任务调度的一个重要方面。

求解云计算任务调度的粒子群优化算法研究云计算任务调度是指在云计算环境中，将任务分配给合适的计算资源进行执行的过程。

任务调度的效率和质量直接影响着云计算系统的性能和用户体验。

为了优化任务调度的结果，研究者提出了多种优化算法，其中一种经典的算法是粒子群优化算法（Particle Swarm Optimization, PSO）。

本文将重点研究云计算任务调度的粒子群优化算法。

粒子群优化算法是一种基于模拟群体行为的优化算法，最初在20世纪90年代由美国Indiana University的Eberhart和Kennedy提出。

它通过模拟鸟群寻找食物的行为，来求解优化问题。

算法的核心思想是通过粒子之间的迭代和信息共享，不断更新粒子的位置和速度，从而找到最优解。

在云计算任务调度中，粒子群优化算法可以将任务表示为粒子的位置，计算资源表示为粒子的速度。

算法的基本流程如下：1.确定问题的目标函数。

云计算任务调度的目标一般是最小化任务的执行时间、最大化系统的利用率或者最小化能源消耗等。

目标函数应该能够评估出各个解的优劣程度。

2.初始化粒子群的位置和速度。

每个粒子代表一个任务，位置表示任务的调度方案，速度表示任务的执行时间或其他指标。

位置和速度的初始化可以采用随机生成的方式。

3.对每个粒子计算适应度值，即目标函数的值。

根据适应度值的大小，更新粒子的个体最优位置和整个群体的全局最优位置。

4.根据粒子的个体最优位置和全局最优位置，调整粒子的速度和位置。

可以借鉴其他粒子群优化算法的更新公式，例如线性或非线性的速度和位置更新公式。

5.判断终止条件，如果满足停止条件（例如达到最大迭代次数或目标函数值小于一些阈值），则输出最优解；否则返回步骤3继续迭代。

在云计算任务调度中，粒子群优化算法有以下优势：1.全局能力强。

粒子通过全局最优信息的引导，具有较好的全局性能，能够找到问题的最优解或近似最优解。

2.并行计算效率高。

粒子群算法的计算过程中粒子之间的更新是独立的，可以利用并行计算的特性，提高算法的运行效率。

改进粒子群优化算法求解车间调度问题研究改进粒子群优化算法求解车间调度问题研究摘要：设计一个高效的车间调度方案，对于提高产能和降低生产成本有着重要意义。

本文利用粒子群优化算法（PSO）来解决车间调度问题，并对其进行改进。

通过引入局部搜索和多目标方法，提高了算法的搜索能力和求解速度。

实验结果表明，改进的粒子群优化算法在车间调度问题中具有较好的性能和鲁棒性。

一、引言车间调度问题是生产管理中的重要问题之一，其目标是合理安排生产过程中的机器和工人，以最小化生产时间和生产成本，同时满足各种约束条件。

在实际生产中，车间调度问题往往是一个复杂的组合优化问题，涉及到多个工序、多个作业和多个资源的分配，具有计算复杂度高、搜索空间大的特点。

粒子群优化算法是一种启发式自适应的全局优化算法，基于群体智能和演化计算的思想。

其仿真过程类似于鸟群觅食的行为，通过不断调整粒子的状态来寻找全局最优解。

粒子群优化算法具有简单、易实现、收敛速度快等优点，在解决复杂优化问题中有广泛的应用。

二、粒子群优化算法的基本原理粒子群优化算法的基本原理包括粒子的位置、速度更新和社会经验、个体经验的信息更新等过程。

每个粒子的位置表示解向量，速度表示解向量的方向和步长。

粒子根据当前位置和速度的信息更新个体最优解和全局最优解，并改变其速度和位置。

通过迭代最大化粒子群的整体经验来实现搜索全局最优解。

三、改进粒子群优化算法的思路为了提高粒子群优化算法的求解效果，本文提出了以下改进思路：1.引入局部搜索机制。

针对车间调度问题的特点，引入局部搜索机制来加速算法的收敛速度。

在全局搜索的基础上，通过搜索邻域解空间，寻找更有可能是全局最优解的候选解。

通过局部搜索机制的引入，可以提高算法的搜索能力和求解效果。

2.利用多目标方法。

车间调度问题通常涉及到多个目标函数的优化，如最小化生产时间和最小化生产成本。

传统的粒子群优化算法只能处理单目标问题，无法同时优化多个目标。

本文利用多目标方法，通过权重优化策略将多个目标函数统一化为一个目标函数，从而实现多个目标的协调求解。

基于改进的粒子群算法的云资源调度策略
蔡晓丽;钱诚
【期刊名称】《微电子学与计算机》
【年(卷),期】2018(35)6
【摘要】云计算资源的调度是云计算中的一项关键技术.针对粒子群算法存在易陷入局部最优解和"早熟"的缺陷,提出一种改进的粒子群算法.通过改进粒子迭代过程中社会项系数和认知项系数的权重变化,使算法更符合最优解的求解规律,避免陷入局部最优解.仿真实验表明,改进后的粒子群算法适应度更强、收敛速度更快,具有更强的全局搜索能力.该算法可以有效提高云计算资源的利用率,具有良好的应用价值.【总页数】4页(P28-30)
【关键词】云计算;粒子群算法;资源调度;迭代;适应度
【作者】蔡晓丽;钱诚
【作者单位】常州工学院计算机信息工程学院
【正文语种】中文
【中图分类】TP393
【相关文献】
1.基于改进多目标粒子群算法的微网双层优化调度策略 [J], 李雪松;滕欢;郭宁;梁梦可;吴泽穹
2.基于改进粒子群算法的云资源调度 [J], 袁正午;李君琪
3.基于RBF-DE的改进蚁群算法和多 QoS约束的云资源调度策略研究 [J], 李莉;
王俊英;臧兆祥;陈鹏
4.基于改进粒子群算法的虚拟机调度策略研究 [J], 高玉娇
5.基于RBF-DE的改进蚁群算法和多QoS约束的云资源调度策略研究 [J], 李莉[1,2];王俊英[1,2];臧兆祥[1];陈鹏[1]
因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进量子粒子群算法的云计算资源调度摘要随着互联网技术和云计算的快速发展，越来越多的企业和个人选择将其业务和应用部署到云上。

然而，在云计算环境中，资源的使用效率成为了亟待解决的问题之一。

本论文针对云计算资源调度问题，提出了一种基于改进粒子群优化算法的云计算资源调度算法。

首先，对云计算资源调度问题进行了分析，提出了优化目标和算法设计指导原则。

随后，将粒子群优化算法中的权重系数与迭代次数进行调整并引入遗传算法来优化初始种群，提出了改进的量子粒子群算法。

最后，通过模拟实验和对比试验验证了改进算法的有效性，在对比试验中与其他算法相比更为高效和稳定。

关键词：云计算；资源调度；粒子群算法；遗传算法；优化算法AbstractWith the rapid development of Internet technology and cloud computing, more and more enterprises and individuals choose to deploy their businesses and applications to the cloud. However, in the cloud computing environment, the efficiency of resource utilization has become one of theurgent problems to be solved. In this paper, a cloudcomputing resource scheduling algorithm based on improved particle swarm optimization algorithm is proposed for the resource scheduling problem in cloud computing. Firstly, the optimization objectives and algorithm design guidelines were proposed by analyzing the cloud computing resource scheduling problem. Then, the weight coefficients and number ofiterations in the particle swarm optimization algorithm were adjusted, and the genetic algorithm was introduced tooptimize the initial population, and the improved quantumparticle swarm optimization algorithm was proposed. Finally, the effectiveness of the improved algorithm was verified through simulation experiments and comparative experiments, and the improved algorithm was more efficient and stable compared with other algorithms in the comparative experiments.Keywords: Cloud computing; Resource scheduling; Particle swarm algorithm; Genetic algorithm; Optimization algorithm 引言随着云计算技术的不断发展，越来越多的应用和服务被部署在云平台上，极大地促进了信息化领域的发展。

云计算环境下基于改进离散粒子群的并行调度算法徐华;张庭【摘要】针对云计算环境下的任务调度优化问题和传统离散粒子群优化（DPSO）算法早熟、精度低等缺点，提出了一种适合云计算环境下动态调整惯性权重因子的方法，并给出了云计算环境下改进后的离散粒子群优化算法。

该算法能快速确定合适的并行任务分配方案，使其达到调度长度最短的优化目标。

仿真结果表明：文中改进的 DPSO 算法的收敛性、前期全局搜索和后期局部探索性能均优于传统的DPSO 算法和遗传算法；在任务数较大的情况下，采用改进 DPSO 算法的并行任务调度算法的调度长度明显优于采用传统DPSO 算法和遗传算法的并行任务调度算法。

%Aiming at the optimization problem of task scheduling in the cloud computing environment and the de-fects of prematurity and low precision of traditional discrete particle swarm optimization(DPSO)algorithms,a method of dynamically adjusting the inertia weight factor is proposed in a cloud computing environment,and an im-proved discrete particle swarm optimization algorithm is put forward.This algorithm can determine the appropriate parallel task allocation scheme quickly,and makes the scheme achieve the shortest schedulinglength.Simulation results show that the improved DPSO algorithm is superior to the traditional DPSO algorithm and the genetic algo-rithm in terms of the convergence,the previous global search capability and thelate local exploration performance, and that,in the case of a large numberof tasks,the parallel task scheduling algorithm using the improved DPSOalgorithm is superior to those using the traditional DPSO algorithm or the genetic algorithm in terms of scheduling length.【期刊名称】《华南理工大学学报（自然科学版）》【年(卷),期】2015(000)009【总页数】5页(P95-99)【关键词】云计算;并行算法;离散粒子群优化【作者】徐华;张庭【作者单位】江南大学物联网工程学院，江苏无锡 214122;江南大学物联网工程学院，江苏无锡 214122【正文语种】中文【中图分类】TP301随着系统虚拟化和网络技术的发展,云计算已经成为一种新的计算平台.云计算作为一种新兴的并行计算技术,是分布式计算、网格计算和并行计算等计算机技术的商业实现,从其诞生开始就具有巨大的商机[1-2].云计算的主要目的是为了更好地利用分布式资源和解决大规模计算问题.在“云”中如何对任务进行高效合理的调度,实现系统全局最优化,成为云计算研究的重点与难点[3].一般来说,云计算可以分为3种主要类型的服务:基础设施、平台和软件,这些服务可以通过网页浏览器和移动应用等云客户端进行访问[4].云计算的透明性、可扩展性、冗余性、可用性和经济性使得任务调度的地位更重要[5-6].在云计算环境中,任务调度是一个NP完全问题[7],其主要目的是优化总调度长度.目前,求解NP完全问题的主要智能优化算法有模拟退火算法、遗传算法和粒子群算法等.并行任务调度是指将任务分成更多、更小的子任务,并将资源分配给这些符合条件的子任务使用,没有依赖关系的子任务可以并行执行.云计算环境下任务量和资源量是非常庞大的,系统时刻都在处理着海量的任务.考虑到大量的任务是在分散的地理资源上执行,因此云计算环境下高效的任务调度算法的设计与实现是一个具有挑战性的问题.针对传统离散粒子群优化(DPSO)算法早熟、精度低等缺点,文中提出了一种适合云计算并行任务调度的改进离散粒子群优化算法,并通过实验分析该改进离散粒子群优化算法的前期全局搜索和后期局部探索能力、收敛性能.云计算并行任务调度是指将N个任务通过某种调度策略调度到R个资源上并行执行,使调度长度最短.其中,N个任务可以分为S个子任务,T={T1,T2,…,TN}表示任务集,r={r1,r2,…,rR}表示资源集.Tsub是一个S×N的矩阵,表示任务与子任务之间的依赖关系,第i个任务的第j个子任务Tsub,ij(i=1,2,…,N;j=1,2,…,S)没完成之前,第k(k>j)个子任务Tsub,ik(k=1,2,…,S)不能执行.在并行执行过程中,te是一个R×S的矩阵,其元素te,p j表示第j(j=1,2,…,S)个子任务在资源rp(p=1,2,…,R)上的执行时间,临时资源池st是一个S×6的矩阵,它总是存放正在执行或即将执行的子任务.st中第1至第6列分别表示资源集合、执行的子任务集合、执行对应资源的任务数量集合、任务集合、子任务在任务中的位置集合、任务执行时间集合.每个子任务只能在一个资源上执行;一个资源上如果有一个子任务在执行,则该资源不再接受其他子任务.ts,i为任务Ti执行的起始时刻,tex,pi(p=1,2,…,R;i=1,2,…,N)为Ti在资源rp 上执行完成的时刻,tpi=max(tex,pi-ts,i),则tpi为任务Ti在资源rp上执行所需的时间.优化目标是使tpi最小.采用DPSO算法求解任务调度问题的关键是建立有效的粒子编码结构,粒子编码可以采用直接编码和间接编码方式.文中采用间接编码方式对每个子任务占用的资源进行编码,编码长度为子任务的个数,这样一个编码对应着一个并行任务调度策略,通过对粒子解码产生调度方案.云计算环境下任务调度的目标就是所有任务完成时间最短,适应度一般通过目标函数值度量.在文中的云计算任务调度模型中,目标函数为mintpi.因此,适应度,∈N+. PSO算法是一种随机优化算法,它源于对鸟群捕食行为的研究[8].在粒子群优化算法中,粒子m在进化的过程中有两个向量,分别是位置向量xm=[xm,1,xm,2,…,xm,D]和速度向量vm=[vm,1,vm,2,…,vm,D],其中D为求解问题的维度.粒子的速度决定了粒子运动的方向和速率,位置代表了粒子解在解空间中的位置.PSO算法适用于计算连续的搜索空间,故其研究也主要集中在连续函数方面.然而许多实际工程应用问题是离散的,变量也是有限的,为了使PSO算法能够解决离散优化问题,Kennedy等[9]提出了离散二进制粒子群优化(BPSO)算法.在BPSO算法中,一个二进制空间表示为一个超立方体,每个粒子用一个二进制变量来表示,通过变量的某些位在0或1之间的变化来实现粒子的移动.之后BPSO算法广泛应用于离散优化问题,如经济规划、图形图像、旅行商问题、背包问题和工作流调度问题等[10-15].在云计算环境下,并行任务调度问题是离散优化问题,将DPSO算法应用到并行任务调度中,数学中的加、减、乘、除运算不再适用,需要重新定义.在DPSO算法中,粒子的位置为一个S维向量,表示为x=[x1,x2,…,xj,…,xS],粒子的速度被定义为粒子位置改变的概率,是一个S维向量,表示为v=[v1,v2,…,vj,…,vS],位置与速度的加法运算实现了粒子位置的移动,即粒子进入新的位置.云计算环境下位置减去位置等于速度,速度加速度等于速度,位置加速度等于位置,μ(μ∈R)乘以速度等于速度.求解云计算并行任务调度问题有如下操作：(1)假设粒子的位置为x,置换序列(f,g)的操作为交换x中的第f和第g个元素.(2)加法算子(⊕)分为速度和速度相加、位置和速度相加.速度和速度相加表示把后一个速度的置换序列依次加入到前一个置换序列列表的结尾.如A=(1,9,3,7,5,6)⊕(3,5)=(1,9,5,7,3,6),B=A⊕(1,6)=(1,9,5,7,3,6)⊕(1,6)=(6,9,5,7,3,1 ).(3)减法算子(-)在云计算环境下只有1种情况,即全局最优解或者个体最优解位置减去个体位置,结果为置换序列.如A=(3,1,2,4,5,6),B=(1,2,4,3,6,5),那么A-B=(4,1,2,3,6,5).(4)乘法算子(⊗)在云计算环境下只有1种情况,即w(w∈R)与速度相乘,表示以概率w保留粒子的速度.根据上面的操作,在云计算环境下粒子i的速度和位置更新公式为式中,w为惯性权重,Pm,t为个体当前最优值,Pg,t为全局当前最优值,Pt为粒子的当前位置,c1、c2为学习因子.随机产生粒子种群的初始位置和速度,然后按照式(1)和(2)进行迭代,直到满足终止条件为止,此时的全局最优值就是优化运算后的近似最优解.惯性权重w是粒子群算法中很重要的一个参数,它平衡了粒子群体的全局搜索能力和局部探索能力.为了使算法在初期能进行较强的全局搜索、而在后期进行较强的局部搜索,文中采用指数增长的惯性权重计算公式,即式中:K=wmax-wmin,wmax和wmin分别为惯性权重的最大值、最小值;M=I/Imax,I为当前迭代次数,Imax为最大迭代次数;a(a∈[0.6,1.2])、b(b∈[10,25])为调节因子.调节因子a和b的取值由经验决定,经过a、b的调整,随着进化次数的增加,惯性权重w加速减小,前期有利于全局搜索,后期有利于局部探索.文中提出的改进离散粒子群优化算法的流程图如图1所示.为测试文中算法在云计算任务调度中的应用效果,采用CloudSim平台进行测试,在Matlab 2012中进行仿真.本实验的硬件环境为:内存8 GB,硬盘500 GB;软件环境为:Windows 7操作系统,Eclipse kepler开发工具.模拟仿真了8个虚拟资源、40个不同的子任务,在相同的实验条件下对传统DPSO算法[8]、遗传算法[16]和文中算法的性能进行比较与分析.实验参数设置如下:种群规模为500,最大迭代次数为400,惯性权重最大值和最小值分别为0.96、0.36,学习因子c1=0.1、c2=0.3.在不同迭代次数下反复进行50次实验,并对实验结果取平均值,结果如表1所示.从表中可以看出:文中算法在求解并行任务调度问题时,找到的最优解远远小于DPSO 算法和遗传算法,且其最优解精度分别比DPSO算法、遗传算法提高了2.96%、6.65%;对于最优解中的最差解,文中算法略大于DPSO算法和遗传算法,表明文中算法的全局搜索能力强于DPSO算法和遗传算法;文中算法找到最优解的平均迭代次数大于其他两种算法,表明文中算法有较好的收敛性能.为进一步分析文中算法的全局搜索能力和收敛性特性,对文中算法和传统DPSO算法在400次迭代过程中的任务调度长度进行仿真,结果如图2所示.从图中可以看出,传统DPSO算法因只重视总完成时间而造成了一些潜在的优良粒子丢失,很快陷入局部极优,进入收敛状态,并最终收敛于最优解301.文中改进算法在迭代次数小于50时,粒子一直处于搜索状态,多次跳出局部极优,这表明文中算法在迭代前期具有较强的全局搜索能力;在此之后粒子慢慢局部探索,逐步寻找到全局最优解,与传统DPSO算法相比,文中算法在迭代后期具有较强的局部探索性能.文中改进算法在迭代50次时,粒子开始收敛,最终靠近全局最优解289.表1和图2表明,文中算法的收敛性、全局探索能力和局部探索能力圴优于传统DPSO算法和遗传算法.文中算法、传统DPSO算法和遗传算法在不同任务数量(20、40、60、80、100)下的适应度如图3所示.从图中可以看出,在任务数量较小的情况下,3种算法的适应度差别并不明显,但随着任务的增多,文中算法的调度长度明显优于其他两种算法,并且任务越多这个趋势越明显.文中提出了一种适用于云计算环境下的并行任务调度算法,首先定义了云计算环境下的并行任务调度数学模型,然后进行粒子的编码与解码并定义操作算子,最后采用改进的DPSO算法对任务调度方案进行并行调度迭代寻优.仿真结果表明,文中算法获得的最优解、前期全局搜索能力和后期探索性能均优于传统DPSO算法和遗传算法,并且在迭代后期具有良好的收敛性能.【相关文献】[1] Sadiku M N O,Musa S M,Momoh O D.Cloud computing:opportunities and challenges [J].IEEE Potentials,2014,33(1):34-36.[2] Stieninger Mark,Nedbal Dietmar.Characteristics of cloud computing in the business context:a systematic literature review [J].Global Journal of Flexible Systems Management,2014,15(1):59- 68.[3] 董丽丽,黄贲,介军.云计算中基于差分进化算法的任务调度研究 [J].计算机工程与应用,2014,50(5):90-95.Dong Li-li,Huang Ben,Jie Jun.Task scheduling based on differential evolution algorithm in cloud computing [J]. Computer Engineering and Applications,2014,50(5):90-95.[4] Chong H Y,Wong J S,Wang X.An explanatory case study on cloud computing applications in the built environment [J].Automation in Construction,2014,44:152-162. [5] Deng Qian-ni,Chen Quan.Cloud computing and key technology [J].Development & Application of High Perfor-mance Computing,2009,26(1):2- 6.[6] Lin Weiwei,Liang Chen,James Z,et al.Bandwidth-aware divisible task scheduling for cloud computing [J].Software:Particle and Experience,2014,44(2):163-174.[7] Arfeen M A,Pawlikowski K,Willig A.A framework for resource allocation strategies in cloud computing environment [C]∥Proceeddings of 2011 IEEE the 35th Annual Computer Software and Applications Conference Workshops.Munich:IEEE,2011:261-266.[8] Kennedy J,Eberhart R.Particle swarm optimization [C]∥Proceedings of IEEE International Conference on Neural Networks.Piscataway:IEEE,1995:1942-1948.[9] Kennedy J,Eberhart R.A discrete binary version of the particle swarm algorithm[C]∥Proceedings of the World Multiconference on Systemics,Cybernetics and Informa-tics.Piscataway:IEEE,1997:4104-4109.[10] Shao X Y,Liu W Q,Liu Q,et al.Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem [J].The International Journal of AdvancedManufacturing Technology,2013,67(9/10/ 11/12):2885-2901.[11] Iman Z,Gerard L,Arindam G.A new technique for optimal allocation and sizing of capacitors and setting of LTC [J].International Journal of Electrical Power & Energy Systems,2013,46:250-257.[12] Wang Xiao-hua,Mu Ai-qin,Zhu Shi-song.ISPO:a new way to solve traveling salesman problem [J].Intelligent Control and Automation,2013,4(2):122-125.[13] Amira G,Abdesslem L,Salim C.Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm [J].International Journal of Bio-Inspired Com-putation,2012,4(4):229-236.[14] Cao J F,Chen J J,Zhao Q S.An optimized scheduling algorithm on a cloud workflow using a discrete particle swarm [J].Cybernetics and InformationTechnologies,2014,14(1):25-39.[15] 陈自郁,何中市,何静媛.一种求解集合组合问题的离散粒子群优化模型 [J].华南理工大学学报:自然科学版,2010,38(4):141-146.Chen Zi-yu,He Zhong-shi,He Jing-yuan.Discrete particle swarm optimization model for set-based combinatorial optimization problems [J].Journal of South China University of Technology:Natural Science Edition,2010,38(4):141-146.[16] Fogel D B.An introduction to simulated evolutionary optimization [J].IEEE Transactions on Neural Networks, 1994,5(1):3-14.。

第35卷第4期2019年4月科技通报BULLETIN OF SCIENCE AND TECHNOLOGYVol．35No．4Apr．2019基于一种改进的粒子群算法在云计算中的任务调度研究朱珍（广东工程职业技术学院信息工程学院，广州510520）摘要：针对粒子群算法在云计算任务调度中存在效率低等问题，提出在将鸡群算法引入到粒子群算法中，将粒子的分布按照鸡群算法中的公鸡，母鸡和小鸡来进行区分，同时对粒子的学习因子进行了改进，有效的避免算法陷入局部，收敛速度快的缺点，在云计算仿真平台中，将本文算法与粒子群算法，鸡群算法在虚拟机负载均衡，消耗成本和完成时间上进行对比都取得了一定的优势，说明本文算法能够有效的提高云计算任务调度效率。

关键词：云计算；任务；粒子群算法；鸡群算法中图分类号：TP301.6文献标识码：A文章编号：1001－7119（2019）04－0115－05DOI ：10.13774/j．cnki．kjtb．2019.04.021Research on Task Scheduling in Cloud Computing Based on AnImproved Particle Swarm Optimization AlgorithmZhu Zhen（School of Information Technology ，Guangdong Engineering Polytechnic College ，Guangzhou 510520，China ）Abstract ：Aiming at the low efficiency of particle swarm optimization algorithm in the scheduling of cloud computing tasks ，this paper proposes a new method of introducing particle swarm optimization．The distribution of the particles is distinguished according to the rooster ，hen and chicken in the flock algorithm ，and the learning factor of the particle is improved at the same time ，which effectively avoids the algorithm falling into a local area and has the disadvantage of fast convergence speed．In cloud computing simulation platform ，this algorithm has gained some advantages compared with particle swarm optimization algorithm ，flock algorithm in virtual machine load balancing ，cost and completion time ，which shows that this algorithm can effectively improve the cloud computing task scheduling effectiveness．Keywords ：cloud computing ；task ；particle swarm optimization ；chicken flock algorithm 收稿日期：2018－05－20基金项目：广东省第一批高职教育品牌专业建设项目（2016gzpp031）；广东省优秀青年教师建设项目（YQ2015187）。

基于双粒子群LDW粒子群改进算法的云计算任务调度算法吴宇星;刘媛华
【期刊名称】《物流科技》
【年(卷),期】2018(041)011
【摘要】云计算资源调度是一个极其复杂的NP问题,不易求解.为缩短任务完成时间,文章提出了一种双粒子群的粒子群改进算法,并将其应用于云资源调度.首先,在惯性权重线性递减的基础上,加入随机数扰动,使惯性权重大幅增大,以便于跳出局部搜索,进行全局搜索,从而防止局部收敛;其次,针对粒子群算法在迭代后期进化减慢的缺点,采用了一种双粒子群的寻优机制,以便于更好地保持粒子群多样性.最后,在Matlab GUI平台下采用几种不同的粒子群算法进行仿真试验.仿真结果表明,在相同条件下改进的粒子群算法能够寻到更精确的解.
【总页数】5页(P12-15,18)
【作者】吴宇星;刘媛华
【作者单位】上海理工大学管理学院, 上海 200093;上海理工大学管理学院, 上海200093
【正文语种】中文
【中图分类】F224.39
【相关文献】
1.云计算环境下基于改进粒子群的任务调度算法 [J], 封良良;张陶;贾振红;夏晓燕;覃锡忠
2.基于改进粒子群算法的云计算任务调度算法 [J], 张陶;于炯;杨兴耀;廖彬
3.基于粒子群优化与蚁群优化的云计算任务调度算法 [J], 王登科;李忠
4.云计算环境下基于改进离散粒子群的并行调度算法 [J], 徐华;张庭
5.改进粒子群的云计算任务调度算法 [J], 曹凯
因版权原因，仅展示原文概要，查看原文内容请购买。