许向阳，张芳磊

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

0 引 言

云计算是一种将人们所需的数据资源任务分布在计算机构成的资源池上，使使用者能够根据自身需求来获取资源的服务[1]。在大数据时代，云计算是处理数据的一种手段，对数据的处理有很高的要求。所以，云计算在任务调度过程中，算法执行的效率至关重要。多数传统的优化算法已经不能满足现在的需求，为此许多学者在不断的研究中提出了很多启发类的智能群算法。本文以参数少、易编程的粒子群算法融合鸡群优化算法，改进粒子群算法在应用过程中的不足，使新算法能够更好地满足云计算任务调度的需求。

1 基本算法介绍

1.1 标准粒子群算法基本原理

标准粒子群（SPSO）算法是由James Kennedy和Russel Eberhart提出粒子群（PSO）算法后，由Shi和Eberhart等研究人员不断完善、发展得来的[2-4]。在取得个体和全局最优位置前，粒子位置和速度更新公式分别为：

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

该算法由于参数少、计算效率高、快速搜索、容易编程等优点，被应用于许多方面的研究与优化，如解决多目标问题、动态优化、参数优化和组合优化等各类优化问题中，以及模糊系统控制、电力分配系统、神经网络、流水车间调度和生物医学等领域。

1.2 鸡群优化算法基本原理

鸡群优化（CSO）算法在2014年由Xianbing Meng提出，是模拟鸡群等级的一种仿生学算法[5]。

介绍算法前，首先将鸡群的活动与任务调度相关联。鸡群中，鸡的种类不同，遵循的活动规则也将不同。在鸡群的等级制度下，鸡之间也是存在竞争关系的[6-9]。

（1）鸡群分为几个组，每组都包含一只领头的公鸡、几只母鸡和若干小鸡。（2）通过适应值的优劣将鸡群分为若干组，且区分每组中个体的种类。鸡群中适应值最优的若干个体作为每组中的头鸡，并带领适应值最差的小鸡和剩余的母鸡。母子之间的关系是随机确定的，母鸡归属哪组也是随机的。（3）每隔相同的时间，组内的支配关系和母子关系会更新一次。（4）母鸡依据公鸡的足迹寻找食物，小鸡跟随母鸡。鸡会随机偷取别人发现的食物，占主导地位的鸡对食物的获取具有优先权。

假设整个鸡群个体为N，其中公鸡、母鸡、小鸡和妈妈母鸡的个数分别为Nr、Nh、Nc和Nm。每个个体的位置表示为xidk，整个鸡群的位置更新公式分为三种。

公鸡在整个群体中适应度值最优，搜索空间最大，对应的位置更新公式为：

randn(0,σ2)是高斯分布函数，f为适应度函数，r为公鸡中去除i的任一公鸡个体。

母鸡位置更新公式为：

其中，randn是0～1的随机数。C1、C2为学习因子：

j1为第i只母鸡所在小组中的公鸡，j2为整个鸡群中公鸡和母鸡任意选取的个体，且j1≠j2。

小鸡的位置更新公式为：

其中，m为第i只小鸡对应的母鸡妈妈，F为[0，2]的任意数。

2 SPSO算法与CSO算法的融合算法

SPSO算法容易陷入局部最优，整个种群在搜索过程中趋于单一性，降低了种群多样性，使算法“早熟”；而CSO算法在种群多样性方面占有优势。因此，提出在粒子群算法基础上加入CSO算法形成新算法（C-SPSO），避免粒子陷入局部最优的同时，提高算法全局搜索能力，更好地完成云计算环境下的任务调度，降低任务完成时间与成本，提高用户服务质量。

2.1 C-SPSO算法的改进

算法容易陷入早熟，导致出现局部最优的问题。因此，本文在粒子初始化时加入混沌扰动，利用扰动遍历粒子群，降低局部最优问题的出现概率[10]。混沌扰动公式如下：

根据式（8）小鸡的位置更新公式可知，小鸡只向自己的妈妈学习。文献[11]为了克服小鸡在鸡群算法中的不足，也对小鸡的位置状态更新进行了优化。本文由SPSO算法和文献[7]的启示，基于CSO算法，对小鸡的位置更新公式进行改进。小鸡在运动过程中除了向自己的妈妈学习外，还会自我学习。因此，小鸡的位置更新公式可改进为：

式中，ω为小鸡自身学习的系数。根据SPSO算法中惯性权重的取值，本文ω的计算公式如下：

2.2 C-SPSO算法适应度函数

C-SPSO算法中整个群体分为若干小组，组之间存在竞争关系，组内同种个体也存在竞争关系。这个竞争是由适应度值决定的。适应度值的优劣决定了种群的搜索方向，影响整个任务的执行时间和任务调度系统的资源利用率。因此，本文的适应度函数是以总任务完成时间和任务总执行成本为基础进行定义的。

适应度函数如下：

2.3 C-SPSO算法执行基本流程

C-SPSO算法解决云计算环境下任务调度的基本流程如下。

步骤1：建立规模为N的粒子群，根据混沌扰动公式，对粒子的速度和位置进行初始化，筛选粒子，并定义相关参数；

步骤2：计算粒子的初始适应值，找到粒子当前个体与全局的最优距离，并对种群所有粒子的适应度值进行排序；

步骤3：判别种群是否满足鸡群的等级分配，满足则对种群进行分配并继续执行，否则分别根据式（3）、式（5）和式（10）对公鸡、母鸡和小鸡的位置进行更新；

步骤4：对满足鸡群等级的种群进行分配，确定公鸡、母鸡、小鸡的等级，同时确立公鸡的领导地位和母鸡与小鸡的母子关系；

步骤5：种群进行迭代及位置更新，计算更新后粒子的适应度值，并与之前适应度值进行比较，更新至鸡群个体和全局最好的位置；

步骤6：种群进行迭代，若种群达到最大迭代次数，算法停止；否则，返回步骤3。

3 实验与结果分析

本文通过Cloudsim-3.0进行实验，将SPSO算法、CSO算法和C-SPSO算法在此平台经过扩展，基于总任务完成时间和任务总执行成本两方面进行对比分析，每组实验分别进行20次，计算平均值作为最终结果。

3.1 实验过程

首先新建Cloudsim的数据中心，设置平台实验的带宽、主机数、任务数量及长度等参数，创建虚拟机，在DatacenterBroker中扩展算法，最后开始仿真，并在实验结束后停止仿真。3种算法中，最大迭代次数Kmax=1 000。实验中算法所需参数设置如表1所示。

表1 实验中算法参数设置

3.2 实验结果对比及讨论

根据表1参数进行实验设置，任务数设置为10～80。为降低实验结果的误差，本文每组实验进行20次，最后取实验结果的平均值。

在任务数不同的情况下，总任务的执行时间情况如图1所示。

由图1可知，在任务数较少时，3种算法完成任务的时间相差不大，但随着任务数的增加，任务完成时间有显著差异。通过对比任务完成时间发现，本文提出的C-SPSO算法时间明显缩短。

图1 任务完成时间

在任务数不同的情况下，任务总的执行成本情况如图2所示。

图2 任务执行成本

由图2分析可得，3种算法随着任务数的增多，执行成本都在上升。但是，SPSO算法、CSO算法与C-SPSO算法相比，后者的增长速度慢，且任务数越多越明显。

4 结 语

本文为了解决标准粒子群算法在任务调度时的缺点，首先对标准粒子群算法的惯性权重进行指数形式改进，以提高粒子群后期局部搜索能力；其次融合鸡群优化算法，增强群体的多样性，并对小鸡位置更新部分引入小鸡的自我学习参数，提高算法的收敛速度，并在粒子的选取上加入了混沌扰动；最后，通过实验结果分析可以直观看出，新算法在任务完成时间和任务总执行成本上的优势，验证了算法的可行性。