混沌粒子群鸡群融合算法的云计算资源调度

隋占丽

(仰恩大学 工程技术学院，福建 泉州 362014)

云计算是全球信息通讯技术行业的发展核心。随着技术的发展，云服务慢慢发展成为“自来水”式的服务，个人或企业无需关心计算存储资源从何而来，只需按需付费，就可以获得想要的数据存储处理资源[1]。但是，云资源的有限性和云计算需求的快速增长是当前云计算急需解决的问题，云资源不同的分配调度方法，使云服务的质量也大相径庭。因此，挖掘更优的云资源调度方法，对于提高云服务质量、提高用户云服务体验具有重要意义。

云计算资源调度的方法有很多，开始出现先进先出调度方法；尔后以此为基础，出现了计算资源调度方法，考虑了资源饥饿度，也就是资源与任务的比值；公平调度策略[2]当前仍在使用，此方法照顾到小用户的感受，以用户为单位分配资源，只是分配资源的多少按用户任务量分派；当前研究最多的智能调度算法[3-5]，就是使用智能算法寻求最优的资源调度方法。当前的优化目标大都比较单一，实现某方面优化的同时，其他没有考虑的方面表现较差，本文研究了实现多方面优化的资源调度方法。

粒子群算法原理简单、收敛较快，但是容易陷入局部最优。本文使用混沌系统的遍历性和鸡群算法的多组群优势对粒子群算法进行优化，使算法容易摆脱局部极值，快速收敛至最优点，使任务能够在适合的虚拟机上执行，同时实现云资源调度完成时间、负载均衡和消耗成本的优化。

1 粒子群算法分析

粒子群算法是受鸟群觅食行为启发得到的群智能算法[6-7]。当前许多群智能算法在资源调度中取得了成功应用，包括遗传算法、粒子群算法、蚁群算法等。其中，遗传算法具有汉明悬崖问题，遗传算法中二进制编码比十进制编码搜索能力强，但是，二进制之间的汉明悬崖使交叉和突变都难以跨越；蚁群算法适合路径搜索问题，但是计算开销大、调度时间长；粒子群算法规则简单、收敛速度快，最适用于全局搜索，本文云资源调度算法以粒子群算法为基础算法。

1.1 粒子群算法原理

在粒子群算法中，影响粒子运动的因素有三个：一是自身运动速度；二是自身记忆；三是群体影响[8]。记第i个D维的粒子的位置为xi=(xi1,xi2,…,xiD)，速度为vi=(vi1,vi2,…,viD)，则粒子下一时刻的速度位置更新为：

(1)

式中d∈[1,D]为粒子维数，k代表时刻，w为惯性因子代表自身速度的惯性，c1、c2为自身学习因子和群体学习因子，分别牵引粒子朝自身历史最优和群体最优运动，r1、r2为(0,1)间的随机数，pbest、gbest分别表示个体历史最优和群体最优。

从式中可以看出，粒子运动的第一项为自身运动惯性，为粒子搜索提供动力；第二项为自身历史最优影响，牵引粒子朝自身最优点运动；第三项为群体最优影响，牵引粒子朝群体发现的最优点运动。

1.2 粒子群算法参数分析及粒子编码

在粒子群算法中，重要的参数包括种群规模C、粒子最大速度Vmax、学习因子c1和c2、惯性因子w。

种群规模C的影响。在粒子群中，每个粒子代表一个可行解，种群规模越大越容易探寻到最优解，但是运算量很大；种群规模越小，则越不容易找到最优解，但是，此时运算量较小。因此，要适当选择种群规模，一般问题种群规模为20～40，困难问题种群规模为100～200。

粒子最大速度Vmax的影响。最大速度代表速度的分辨率，若最大速度较小，粒子速度分辨率高，能够找到最优解，但是难以摆脱局部最优解，若最大速度较大，摆脱局部最优能力强，但是很容易错过最优解。

学习因子c1和c2的影响。学习因子代表历史最优和群体最优对粒子运动的牵引程度，代表算法设置时对自身历史最优和群体最优的重视程度。

惯性因子w的影响。惯性因子代表粒子自身运动对粒子运动影响的大小，惯性因子越大则算法全局搜索能力越强，但是却放弃了参考自身最优和群体最优；惯性因子越小，能够更加趋向于自身最优和历史最优，但是算法变成了局部搜索算法。

粒子编码方式。若存在N个用户，M个资源，第t个用户的任务数量为TaskNum(t)，则总任务数TaskNum为：

(2)

对N个用户提交的任务进行编号，第i个用户提交的第j个任务编号m为：

(3)

通过以上分析可知，染色体长度为TaskNum，每个任务所在的基因位为m，基因的可取值为[1,M]，基因的取值代表该位置上的任务由此资源执行。

2 混沌粒子群算法

在粒子群算法中，粒子的初始化和进化都具有很强的随机性，粒子搜索过程的随机性使算法可能难以搜索到最优位置，容易陷入局部最优。为了解决这些问题，使用混沌系统的遍历特性，肯定比粒子群算法无顺序无目的搜索表现出色，而且一定能够跳出局部最优。

2.1 混沌特性

混沌系统在自然和社会系统中存在较多，是复杂、随机而又具有精确内部规则的系统[9]。Logistics方程是典型的混沌系统，以此为例对混沌系统进行介绍，即：

Sk+1=μSk(1-Sk)，

(4)

式中μ为管制变量，取值为4。S0取值为0～1间的任意值，就可以得到确定的序列S1,S2,…，此系统即为一个混沌系统。

2.2 混沌粒子群算法

使用混沌特性对粒子群算法的优化主要体现在3点：一是对粒子最初位置和速度使用混沌序列设置，此设置使算法具有种群多样性和遍历性，同时不改变初始设置随机化的特性；二是以当前种群此刻找到的最佳位置为基础形成混沌序列，使用混沌序列中的最佳位置代替种群中的一个个体位置，此措施可以使惰性个体摆脱局部极值，同时迅速找到全局最优。

由以上分析，给出混沌粒子群算法的步骤为：

(1)给出算法最大循环次数和参数赋值；

(2)对粒子群所有粒子的初始位置和初始速度进行混沌设置；

(3)若粒子i当前状态好于此粒子历史最优点，则更新粒子历史最优pbesti；若某粒子当前状态好于群体最优值，则更新群体最优值gbest；

(4)按照式(1)对粒子速度和位置进行更新；

(5)对个体历史最优pbesti进行混沌优化，计算适应度值，找出最佳个体P*；

(6)使用最佳个体替换粒子群中的惰性个体；

(7)若满足算法结束条件则算法结束并输出群体最优值gbest；否则转至Step3。

3 混沌粒子群鸡群融合算法

粒子群算法原理简单、搜索速度快，但是容易陷入局部最优；鸡群算法是典型的多种群算法，可以有效避免粒子陷入局部最优和早熟问题。将混沌粒子群算法和鸡群算法相融合，提出了混沌粒子群鸡群融合算法。此算法继承了粒子群算法收敛速度快和鸡群算法有效避免局部最优的优势，可以使粒子在解空间中实现更加充分的搜索，使云任务在更加适合的虚拟机上执行。

3.1 鸡群算法

鸡群算法是模拟鸡群觅食行为的群智能算法，主要模拟鸡群的等级制度和行为习惯[10]。将鸡群进行理想化的描述：(1)将鸡群分成若干组，每组都由一只公鸡、几只母鸡和小鸡组成；(2)公鸡数量和组数一致，种群中适应度好的鸡被指定为公鸡，适应度差的鸡指定为小鸡，其余为母鸡，母鸡分到哪个组是随机产生的，小鸡和母鸡的母子关系也是随机产生的；(3)在等级制度下，一个组内的支配关系不变，但是每经历数代步骤更新一次；(4)每组鸡群在头公鸡的引导下寻觅食物，小鸡在母亲鸡周围寻觅食物，同时鸡会偷取其他组发现的优质食物。

记种群中公鸡、母鸡、小鸡、母亲鸡的数量分别为RN、HN、CN、MN。

在鸡群中，公鸡的适应度越高，则在获得食物方面越具有优先权，也就是其食物搜索范围越广，即：

(5)

式中k为公鸡编号且k≠i，Rand(0,σ2)为均值为0、方差为σ2的高斯分布，f为适应度函数值。

母鸡在寻觅食物时受公鸡和小鸡的约束，即：

(6)

式中Rand为(0,1)间的随机数，r1为公鸡编号，r2为小鸡编号。

小鸡在母亲鸡附近寻找食物，即：

(7)

3.2 混沌粒子群鸡群速度和位置更新方法

混沌粒子群鸡群算法核心思想是：(1)粒子群算法依靠个体的合作与竞争寻优，加入鸡群算法后，组群之间的信息交流可以使算法以更大概率逃出局部最优；(2)从粒子群中选取适应度大的粒子引导整个种群的搜索方向，增强全局搜索能力，使云任务在更合适的虚拟机上执行。

参照鸡群算法的等级制度，将所有粒子分为3类：A粒子、B粒子、C粒子，分别对应鸡群算法中的公鸡、母鸡和小鸡。A粒子作为粒子群中的优秀个体，其位置和速度的更新方式与式(1)保持不变。

粒子群的每个子群除了具有独立性特点外，还要有相互的合作，也就是相互交流。基于此思想，B粒子的位置和速度更新方式为：

(8)

式中pbestid、gbestid分别表示粒子个体历史最优和本组群的群体最优，xf为其他组群的最优位置，c3为组群间学习因子，一般取值为[0,4]，在此取值为2，r3为(0,1)间的随机数。

C粒子在B粒子周围搜寻食物，其位置更新方法为：

(9)

3.3 混沌粒子群鸡群算法流程

根据以上分析，给出混沌粒子群鸡群融合算法流程为：

(1)建立一个粒子种群并对相关变量赋值，对粒子初始位置和速度进行混沌设置；

(2)计算粒子的个体适应度值和组群适应度值；

(3)将粒子群进行分组，在A粒子和B粒子间确定隶属关系，在B粒子和C粒子间确定母子关系；

(4)按照粒子分类进行速度和位置更新；

(5)若更新后的全局适应度值高则位置更新，否则不更新；

(6)迭代次数是否达到上限，若是则算法结束输出全局最优值，否则依据适应度值判断是否对等级进行重新划分，如需要则更新等级，否则转至(3)。

3.4 评价函数

本文作出以下假设：(1)任务是由若干大任务分解成的一批小任务，且子任务划分粒度相同；(2)任务量远远超过虚拟机数量。记N为任务总数，Ti为第i个子任务，M为虚拟机数量，VMj代表第j个虚拟机，RCU(VMj)为虚拟机VMj运行单元时间的成本。第j个虚拟机完成系统交给的所有子任务时间记为vmTime(VMj)，则：

(10)

式中Time(Ti,VMj)表示子任务Ti在虚拟机VMj上的执行时间，n为分派到VMj上的子任务数量。

总任务执行时间评价函数定义为所有虚拟机所用时间最长的一个，即：

completeTime=max(vmTime(VMj))j∈[1,M] ，

(11)

负载均衡度DLB评价函数使用完成时间的比值来度量，即：

(12)

此式的含义是：各虚拟机完成任务所用时间与总任务完成时间越相近则负载越均衡，那么DLB值越大则负载均衡度越高。

使用每个虚拟机完成任务的时间和单位时间的成本消耗，可以给出所有任务完成的总成本为：

3.5 基于融合算法的云资源调度流程

通过以上分析，给出混沌粒子群鸡群融合算法的云资源调度流程如图1所示。

图1 基于融合算法的云资源调度流程图

4 实验验证

使用CloudSim云计算平台仿真模拟器对本文提出的优化算法进行调度效果验证。模拟器参数为：1个数据中心(包含两台主机)，虚拟机数量为5，虚拟机大小为2048MB，带宽为1000bit，1个虚拟机只有1个PE，PE处理能力为100-300MIPS；任务总量设置为10-50，任务长度为15000-50000MI。

为了与本文提出的混沌粒子群鸡群融合算法进行对比，本文分别使用轮询算法、粒子群算法、混沌粒子群算法和混沌粒子群鸡群融合算法对云计算资源进行分配，统计各调度策略的任务执行时间、负载均衡度、消耗成本，结果分别如图2、图3、图4所示。

图2 各调度策略任务完成时间

图3 各调度策略负载均衡度

图4 各调度策略资源消耗对比

从图2可以看出，在任务量为10～50的情况下，混沌粒子群鸡群融合算法的任务完成时间最少，而且随着任务量的增加，耗时上的差距越来越明显，使用外推的思想，若任务量继续增大则混沌粒子群鸡群算法的用时优势会更加明显；从图3可以看出，基于混沌粒子群鸡群算法的调度策略资源分配最公平，负载均衡度最高(接近于1)，说明各虚拟机时间消耗相近，分配最为合理；从图4可以看出，基于混沌粒子群鸡群算法的能量消耗最少，而且随着任务量增加，耗能差别也在拉大。

综合图2、图3、图4，可以发现以下规律：(1)三种评价策略下，调度算法优异程度排序为：混沌粒子群鸡群算法、混沌粒子群算法、粒子群算法和轮询算法，这是因为使用混沌系统优化粒子群算法时，混沌系统具有遍历性，可以促进粒子群算法摆脱局部极值而搜索全局最优；而在混沌粒子群算法基础上融入鸡群算法，就实现了将粒子群进行分组，每个组群作为一个小团队在搜索最优位置，而且团队之间具有最优位置的信息交流，不仅使粒子群算法尽快摆脱局部极值，而且能够在解空间实现充分细致的搜索，使云任务能够找到最合适的虚拟机执行；(2)在耗时和耗能上，任务量越大，耗时和耗能优势越明显，这是因为在任务量较小的情况下，虚拟机计算能力与云任务计算需求之间的矛盾较小，劣质的调度策略就能够在一定程度上满足调度要求，使得优质调度策略的优势不是很明显；而当任务量较大时，所有虚拟机都在执行任务，此时计算资源供应和需求之间的矛盾突出，使用优质算法进行合理的资源调度优势就会凸显出来。

综上所述，混沌粒子群鸡群融合算法在任务耗时、负载均衡度和消耗成本上均具有优势，且任务量越大，耗时和耗能的优势越明显。

5 结语

本文以云计算资源调度中的耗时、负载均衡、耗能为优化目标，提出了混沌粒子群鸡群融合算法，具体工作为：

(1)使用混沌系统的遍历性和鸡群算法的多组群性优化粒子群算法，使粒子群算法能够摆脱局部最优，在全局范围内细致搜索；

(2)鸡群算法作为多组群算法，融入到混沌粒子群算法中，将粒子群进行分组，组内粒子又分等级，组群在搜索最优位置的同时，也实现了组群间的最优位置交流；

(3)使用CloudSim软件对算法进行验证，结果表明混沌粒子群鸡群算法在耗能、负载均衡度和耗能上均具有优势。

参考文献：

[1] 杜伟. 分布式结构化存储调度服务器的设计与实现[D]. 成都：电子科技大学, 2013.

[2] 杨洋. 基于资源状况的延时等待公平调度算法的研究[D]. 沈阳：东北大学, 2014.

[3] 卓涛, 詹颖. 改进人工蜂群算法的云计算资源调度模型[J]. 微电子学与计算机, 2014(7):147-150.

[4] 袁浩, 李昌兵. 基于社会力群智能优化算法的云计算资源调度[J]. 计算机科学, 2015, 42(4):206-208.

[5] 嵇可可. 基于动态趋势预测蚁群算法的云计算资源调度优化研究[J]. 科技通报, 2016, 32(1):187-190.

[6] 李擎, 张超, 陈鹏,等. 一种基于粒子群参数优化的改进蚁群算法[J]. 控制与决策, 2013(6):873-878.

[7] 王东风, 孟丽, 赵文杰. 基于自适应搜索中心的骨干粒子群算法[J]. 计算机学报, 2016, 39(12):2652-2667.

[8] Mehdinejad M, Mohammadi-Ivatloo B, Dadashzadeh-Bonab R, et al. Solution of optimal reactive power dispatch of power systems using hybrid particle swarm optimization and imperialist competitive algorithms [J]. International Journal of Electrical Power & Energy Systems, 2016, (83):104-116.

[9] Cai P, Yuan Z Z. Hopf bifurcation and chaos control in a new chaotic system via hybrid control strategy [J]. Chinese Journal of Physics, 2017, 55(1):64-70.

[10] 李振璧, 王康, 姜媛媛. 基于模拟退火的改进鸡群优化算法[J]. 微电子学与计算机, 2017, 34(2):30-33.