许向阳，张芳磊

（河北科技大学 信息科学与工程学院，河北 石家庄 050000）

粒子群优化（PSO）算法在云计算环境下任务调度方面应用十分广泛。针对算法易陷入局部最优、收敛速度慢的缺陷，从基本概念入手，在算法中加入改进的动态惯性权重和外部扰动策略，改善PSO算法的局部寻优能力，提高算法迭代后期收敛速度和搜索的精度，最后利用Cloudsim进行实验，将新算法与其他算法任务执行总的迭代次数的结果进行对比，新算法克服了粒子群算法的缺点，能够有效地平衡全局和局部搜索能力，任务的完成时间相对较少。

云计算；任务调度；粒子群优化算法；Cloudsim

中图分类号：TP301文献标识码：ADOI：10.19358/j.issn.2096-5133.2018.08.007

引用格式：许向阳，张芳磊.基于混沌扰动PSO算法的云计算任务调度［J］.信息技术与网络安全，2018,37（8）：27-30.

Task scheduling based on chaotic disturbance particle swarm

optimization algorithm in Cloud computing environment

Xu Xiangyang，Zhang Fanglei

（School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang 050000, China）

Abstract:Particle swarm optimization (PSO) algorithm is widely used in the task scheduling in Cloud computing environment. Aiming at the problem that the particle swarm algorithm is easy to fall into local optimum and has slow rate of convergence, this paper begins with basic concept, adds dynamic inertia weight and external disturbance strategy in particle swarm algorithm to improve the local-optimization. This algorithm can solve the problems of the slow convergence and low search precision .Finally, Cloudsim simulation platform is used for testing. Comparing the results of the number of iterations between the new algorithm and other algorithms at the execution time of task, new algorithm overcomes the shortcoming of particle swarm optimization, and can effectively balance the global search and local search. The completion time of the task is observably shorter.

Key words:Cloud computing; task scheduling; particle swarm optimization ; Cloudsim

0 引言

云计算环境下任务调度算法的执行效率直接影响到用户对服务质量的体验，而多数传统的优化算法已经不能满足现在的需求，因此许多研究学者提出了蚁群算法、遗传算法等启发式智能类的算法。本文主要研究的是智能算法中的粒子群优化（Particle Swarm Optimization，PSO）算法。粒子群算法的模型就是在一块区域里让距离食物最近的一只鸟去寻找食物，减少寻找时间，提高速率。PSO算法由于具有参数少、计算效率高、搜索快速、编程容易且应用广泛等特点，从而被许多学者应用于云计算环境下任务调度算法的研究上。

许多专家和学者不断分析和研究影响任务调度的因素，已经在此算法上研究出许多有价值的方案。文献［1］通过分析粒子飞行轨迹提出广义和狭义中心粒子的双中心粒子群优化算法，改善粒子算法的精度和收敛速度。文献［2］在满足用户多任务服务质量的要求下，提出一种多QoS约束离散粒子群的优化算法。文献［3］将混合粒子群算法结合Pareto最优工作流调度解集合，解决冲突的三目标优化问题。文献［4］提出一种反向学习和局部学习的粒子群优化算法，通过反向学习增加种群粒子的多样性，降低算法局部最优的情况。文献［5］通过自适应地调整惯性权重来平衡算法的全局收敛性和收敛速度，提高算法性能。

优化粒子群算法通常也会与其他粒子群算法相结合。文献［6］利用遗传算法中交、变异的特点，将遗传算法与改进的粒子群算法相混合，增强了粒子的变异能力，又提高了粒子的搜索精度，大大降低了任务完成时间。文献［7］结合粒子群算法和蚁群算法各自的优点，用粒子群算法使粒子群前期迭代产生的优良粒子生成初始信息素，再将信息素应用于蚁群算法上，最后得到最优解。

本文首先分析粒子群算法的基本原理和粒子群在解决任务调度问题时的缺点，针对缺点，对粒子群算法在惯性权重上进行改进，解决算法在前期出现“早熟”和后期收敛精度低的问题，并加入混沌扰动，通过给出的适应度函数，以不同任务数为研究对象，对比算法任务完成总时间，并观察迭代次数的情况。

1 粒子群算法介绍

1.1 粒子群优化算法基本原理

传统粒子群优化算法是由美国心理学家KENNEDY J和电气工程师EBERHART RC于1995年根据鱼群、鸟群觅食的活动提出的一种智能化算法［8］。但传统粒子群优化算法不存在对粒子运动速度的调整，使算法对局部搜索和全局搜索的能力降低。因此为了弥补传统粒子群优化算法的不足，SHI Y和EBERHART R C在此算法的前提下引入了惯性权重，并深入研究，使粒子的运动速度不再是单一固定不变的速度［9-10］。

粒子群中的所有粒子都有自己的位置、运动方向和速度。每个粒子都是一个个体，粒子本身在经历多次迭代后出现的个体最优解叫做个体极值pbest，群粒子组成的群体会出现全局最优解，即全局极值gbest。所有的粒子都会寻找最佳位置，就是说粒子会向最优解进行搜索，这是由优化函数的一个适应值决定的。PSO算法首先要初始化粒子群，然后粒子通过在个体最优解和全局最优解反复更新自己的位置和速度，经过反复迭代，最终得到极值。

记粒子群中粒子个数为N，粒子在d维空间运动，则k时刻粒子i的位置和速度公式如下。

由优化函数适应值决定粒子个体最优位置和全局最优位置的公式如下。

个体最优位置：

全局最优位置：

在取得两个极值之前，粒子会根据如下公式进行搜索，更新位置和速度：

其中，d为粒子搜索空间维数；k为迭代次数，也指当前时刻下；c1，c2为两个正常数，即学习因子，也叫加速因子；α、β是两个介于0和1之间的随机数。

ω为惯性权重，SHI Y和EBERHART R C将惯性权重引入粒子群算法中，即

ω=ωmax－(ωmax－ωmin)×k/Kmax(7)

其中， ωmax、ωmin分别是最大和最小惯性权重， k为此刻粒子迭代次数，Kmax为粒子最大迭代次数。

根据标准粒子群算法原理，影响PSO算法的主要参数有：粒子群规模、惯性权重、学习因子及粒子运动的最快速度等。

1.2 粒子群算法的应用及问题

PSO算法已经被广泛应用于解决多目标问题、动态优化、参数优化、组合优化等各类优化问题，以及应用于模糊系统控制、电力分配系统、神经网络、流水车间调度、生物医学等各领域中。但是用在云计算环境解决任务调度的优化问题时，会出现陷入局部最优、后期收敛速度慢等问题；与其他启发类智能算法一样，这一种算法不可能解决所有的优化问题。PSO算法较适用于解决连续化的问题上对于任务调度这个离散型问题不能够很好地发挥其优势，因此需要在PSO算法的基础上进一步改进算法性能，以去除算法在任务调度过程中存在的弊端，从而取得更好的实际效果，改善资源利用率和平台的服务质量，提高用户体验。

2 改进型粒子群算法研究

在现实应用中，算法的优化提高不可能只是单方面的，通常情况下都是多个目标优化问题，但是多目标优化多数情况下是互相矛盾、存在冲突的，所以最好的优化只能是根据实际情况，权衡各个目标而得到相对的极值。本文以任务完成时间为算法性能优劣的主要依据。

2.1 适应度函数

粒子需要通过适应值判断当前位置的优劣。任务调度就是用最短的时间最高效率地完成任务，完成任务时间越小，目标函数值就越大，种群中粒子的适应度就越好。因此首先要定义适应度函数，并将式（1）中xkid代入适应函数f（x），求适应值。

设有 r个资源，s个粒子，任务i在资源j上的执行时间用T(i,j)表示：

完成任务的总时间为：

定义适应度函数为:

2.2 惯性权重的计算

PSO算法在解决任务调度问题时容易出现的问题就是前期陷入局部最优，后期全局的搜索精度降低。所以为了平衡全局和局部搜索能力，在相关研究中权重的改进包括自适应权重、随机权重等。本文采用指数形式的惯性权重ω的改进方法。惯性权重ω的取值较大，全局的搜索能力会提高，但局部的搜索能力会变差；若ω取值较小，算法的局部搜索能力会提高，但是全局的搜索能力不佳。根据惯性权重存在的问题，本文将惯性权重的表达式改进为：

ω=ωmin+exp［－((ωmax－ωmin)×k/Kmax)2］ (10)

由上式可知，式中ω会以指数的形式在迭代前期保持一个较大的值，从而使粒子群在迭代前期全局搜索能力增强；在迭代后期ω能够保持一个较小且变化平缓的值，提高算法后期局部的搜索能力，加快收敛速度。依据前人相关研究，本文惯性权重取值范围为［0.4~0.9］。

2.3 混沌扰动

混沌在一定范围内可以等概率无重复遍历所有状态，算法在解决任务的过程中，其他粒子会因为种群中极少数最优粒子的引导向最优粒子迅速靠近，如果此粒子并没有达到全局最优，则有可能导致算法陷入局部最优。混沌对粒子初始值敏感，能够依据混沌的内部规则，随机地遍历所有的粒子。所以为了避免粒子陷入“早熟”时，需要加入一个外部扰动，让粒子可以打破局部最优。

当粒子发生早熟时要存在一个外部扰动机制使粒子群跳出“早熟”。本文采用的混沌扰动公式为：

算法实现流程如图1所示。

图 1 算法的实现流程图

3 实验仿真与分析

本实验使用云计算工具Cloudsim-3.0作为实验平台，MyEclipse为开发工具，Java为开发语言。实验基本流程为：搭建实验环境，初始化Cloudsim，创建数据中心、服务代理，设置虚拟机资源及任务的参数，扩展并调用任务调度算法，启动Cloudsim，最后进行实验结果分析。

3.1 仿真实验过程

用Cloudsim部署实验环境，在DatacenterBroker中扩展新算法，将任务数分别设置为50，100,200,500，实验将改进后的算法与标准粒子群算法（SPSO）进行实验仿真，并对这两个算法在任务完成时迭代次数的情况进行分析对比。文中提出的算法的参数设置如表1所示。

表1 SPSO和改进后算法的参数设置

3.2 实验结果比较及讨论

根据表1设置实验参数，为保证实验的准确性，每组实验进行20次，最后取20次实验的平均值进行比较分析。实验比较两种算法在任务数不同时，完成时间最短时的迭代次数的情况，实验结果对比如图2~5所示。

图 2 任务数为50时的任务总完成时间

图 3 任务数为100时的任务总完成时间

图 4 任务数为200时的任务总完成时间

图 5 任务数为500时的任务总完成时间

通过上述实验结果对比可以得出，在迭代前期NPSO算法比SPSO算法收敛能力更强，但是在任务数相同时NPSO算法比NPSO算法完成任务所用的总时间有所减少，且后期的收敛性较强，通过对比可知，改进后的算法有更好的执行效率，在实际应用中能更好地改善用户的使用体验。

4 结论

许多研究人员针对任务调度算法开展了许多相关研究，本文在前人的基础上对标准粒子群算法进行进一步进行改进。通过优化惯性权重，并且在粒子群算法的过程中加入混沌扰动，遍历粒子状态，根据给出的适应度函数，对新算法的性能与其他任务调度算法进行对比。实验结果表明，本文方案有效地降低了任务执行时间，降低了资源消耗成本，具有可行性。

参考文献

［1］ 汤可宗, 柳炳祥, 杨静宇,等. 双中心粒子群优化算法［J］. 计算机研究与发展, 2012, 49(5):1086-1094.

［2］ Wang Yue, Liu Yaqiu, Guo Jifeng,et al.QoS scheduling algorithm in cloud computing based on discrete particle swarm optimization［J］.Computer Engineering,2017,43(6) : 111-117.

［3］ 杜艳明,肖建华.云环境中基于混合多目标粒子群的科学工作流调度算法［J］.计算机科学,2017,44(8):252-259.

［4］ 夏学文,刘经南,高柯夫,等.具备反向学习和局部学习能力的粒子群算法［J］.计算机学报,2015,38(7):1397-1407.

［5］ 任圆圆，刘培玉，薛素芝. 一种新的自适应动态文化粒子群优化算法［J］. 计算机应用研究，2013, 30(11):3240-3243.

［6］ 王波,张晓磊.基于粒子群遗传算法的云计算任务调度研究［J］.计算机工程与应用,2015,51(6):84-88.

［7］ 王登科,李忠.基于粒子群优化与蚁群优化的云计算任务调度算法［J］.计算机应用与软件,2013,30(1):290-293.

［8］ KENNEDY J, EBERHART R C. Particle swarm optimization［C］//Proceedings of IEEE Conference on Neural Networks, Perth, Australia, 1995:1942-1948.

［9］ SHI Y, EBERHART R. Modified particle swarm optimizer［C］// Proceedings of IEEE ICEC Conference, Anchorage, 1998:69-73.

［10］ EBERHART R C, SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization［C］// Proceedings of the 2000 Congress on Evolutionary Computation, 2000. IEEE, 2002:84-88.

（收稿日期：2018-04-14）

作者简介：

许向阳（1967-），男，硕士，副教授，主要研究方向：信息网络管理。

张芳磊（1990-），女，硕士研究生，主要研究方向：信息网络管理。