云计算环境中基于分布估计蛙跳算法的资源调度

宁菲菲，王建玺

云计算环境中基于分布估计蛙跳算法的资源调度

宁菲菲，王建玺

针对云计算环境下的资源调度问题，提出了一种基于分布估计蛙跳算法的云资源调度策略。在运用混合蛙跳算法（SFLA）搜索全局最优解的同时，在SFLA的局部搜索环节引入基于群体的增量学习算法（PBILA），通过建立反映优质解分布的概率模型，增加子群间的协作、增强群体的全面学习能力。仿真实验结果表明：该资源调度策略不仅能够有效地避免陷入局部最优，而且较好地提升了全局收敛性能。

云计算；资源调度；蛙跳算法；分布估计算法；基于群体的增量学习算法

0 引言

近年来，随着互联网规模的不断扩大和电子商务、在线视频等新型互联网应用的迅猛发展，海量的数据存储、业务的快速增长以及企业运维成本的不断提高对互联网的发展提出了新的挑战。为了给用户提供更为方便、快捷的高质量网络服务，云计算作为一种新型的服务计算模型在2006年一经提出便得到了广泛关注。根据美国国家标准与技术研究院（NIST）的定义：云计算是一种通过互联网以按需的方式随时随地对一个可配置的共享资源池（包括计算设施、存储设备、应用和服务等）进行访问的服务模式[1]。资源调度作为云计算中的一个重要问题，其性能优劣直接影响到云计算资源的利用率、用户满意度以及企业的运营成本。

由于云计算环境下的资源调度是一个NP完全问题，因此，许多学者提出了大量的基于启发式智能算法的云资源调度策略。例如，刘卫宁等[2]提出了基于改进二进制编码的量子遗传算法的云资源调度策略，使其适用于实数编码并有效避免了在量子编码的空间内陷入局部最优。左利云[3]等提出了基于多目标集成蚁群优化算法，用于解决资源调度问题。刘万军[4]等提出了一种基于粒子群优化算法的云资源调度策略，尽量避免资源调度过程中负载失衡问题的产生。金伟健[5]等提出了基于蝙蝠算法的云资源分配策略，以有效兼顾任务完成时间和成本。

本文提出一种基于分布估计蛙跳算法的资源调度策略，将混合蛙跳算法和分布估计算法有效结合。通过在CloudSim平台上进行仿真实验测试算法性能，仿真结果表明：分布估计蛙跳算法不仅能够有效避免在资源调度过程中陷入局部最优，而且较好地提升了算法的全局收敛性能。

1 云资源调度模型

[6]对云计算环境中的资源调度问题建模表示为由s个虚拟机资源和t个用户任务所组成的云资源调度模型，可将该模型表示为四元组SM＝(R, M, F, θ)。其中，R为由s个虚拟机资源所组成的资源集合；M为由t个用户任务所组成任务集合；F表示云资源调度模型的优化目标函数；θ则表示解决云资源调度问题所采用的优化算法。云资源调度模型的主要特征详细描述如下：

（1）资源集合R＝{rc1, rc2, …, rcs}，虚拟机资源rcj(1≤j≤s)负责处理分配到该资源上的子任务。

（2）任务集合M＝{m1, m2, ..., mt}，第mx(1≤x≤t)个用户任务可以划分为Nx个子任务，且子任务间相互独立。

（3）任务mx的执行时间可以表示为公式（1）：

其中，W(k, n, rcj)表示任务mx的第n个子任务所在的虚拟机资源rcj在处理分配到该资源上的第k个子任务时所使用的时间；pos表示任务mx的第n个子任务在虚拟机资源rcj的计算队列中所处的位置则表示虚拟机资源rcj按照其计算队列中子任务的排序依次执行各子任务直至完成任务mx的第n个子任务为止所用的时间。

（4）用ETC(i, rcj)表示第i 个子任务在虚拟机资源rcj上的执行时间，则执行完成任务集合M内所有任务需要的总时间T可以表示为公式（2）：

其中：cnt(rcj)表示分配到rcj资源上的子任务总量。

（5）用户任务的平均完成时间AVG可以表示为公式（3）：

2 分布估计蛙跳算法

2.1 混合蛙跳算法

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）是由Eusuff和Lansey等人[7]提出的一种基于群体智能的进化算法，通过模拟青蛙群体觅食过程用于解决多目标优化问题。由于SFLA概念简单、参数少，而且具有计算速度快、全局搜索寻优能力强以及易于实现等特点，因此，该算法在水资源分配、车间作业流程安排等众多领域都有着广泛应用[8]。SFLA的主要思想是：将整个青蛙群体划分为若干个子群体，每个子群体具有自己的文化，子群体中的每只青蛙也具有自己的文化，在与其他青蛙个体相互作用的同时，还伴随着子群体的进化而进化。首先在各子群体内部分别执行局部搜索，当局部搜索迭代结束后，将所有的子群体进行混合并进行文化交流，即执行全局信息交换。子群体的局部搜索和全局信息交换交替进行，直到终止条件满足为止。接下来简要介绍SFLA的主要步骤。

步骤1：初始化。随机生成N只青蛙组成初始蛙群，每只青蛙都代表着优化问题的一个可行解Y=(y1, y2, ... , yE)，E表示解的维数。

步骤2：排序。计算每只青蛙的适应度F(i)，并按照适应度对所有青蛙进行降序排序。每只青蛙都对应一个序号Si（1≤ i≤N），Si表示排序后该青蛙在序列中的位置。

步骤3：子群划分。将N只青蛙组成的初始蛙群划分为L(L

其中，Gi表示对序号为Si的青蛙所分配子群的群号。根据公式（4）进行子群划分，排序后序号为1的青蛙被分入1号子群，序号为2的青蛙被分入2号子群，… ，序号为L的青蛙被分入L号子群，序号为L+1的青蛙被分入1号子群，序号为L+2的青蛙被分入2号子群，依此类推，直到所有青蛙被分配完毕为止。

步骤4：局部搜索。设Yb为子群中具有最优适应度的可行解，Yw为子群中适应度最差的可行解，Yg为整个蛙群中具有最优适应度的可行解。在各子群内部进行局部搜索，并根据公式（4）用子群内具有最优适应度的可行解Yb来更新适应度最差的可行解Yw。得公式（5）：

其中，rand()函数产生值为0～1之间的随机数。若根据公式(5)更新后得到的解newYw的适应度优于Yw，则Yw=newYw；否则用整个蛙群中具有最优适应度的可行解Yg代替Yb重复执行公式（5）得到newYw，若其适应度仍不优于Yw，则随机产生一个可行解代替Yw。在各子群体内部根据公式（5）重复执行更新Yw的操作，直到迭代次数达到设定的最大局部搜索次数为止。

步骤5：全局信息交换。当所有子群结束一轮的局部搜索之后，将所有子群的青蛙进行混合，执行全局信息交换并记录当前整个蛙群中具有最优适应度的可行解Yg，即全局最优解。

步骤6：计算并判断终止条件。如果终止条件得到满足，则算法结束，否则转到步骤2继续执行。

2.2 分布估计算法

分布估计算法（Estimation of Distribution Algorithms，EDAs）是进化计算领域所提出的一种全新进化模式。分布估计算法的主要思想是运用统计学习的手段建立一个描述群体（即解空间）内个体（即解）分布的概率模型，通过对概率模型随机采样产生新的群体以实现群体的不断进化，重复执行直到满足终止条件为止[9]。

分布估计算法的关键在于建立一个能够精确反映优化问题的概率模型。本文选择运用最早被提出的分布估计算法——基于群体的增量学习算法PBILA[9]的学习规则来建立描述优质解分布的概率模型。具体实现可以归纳为以下3个主要步骤：

步骤1：初始化群体，建立描述解空间的概率模型。

将第z个子群在执行SFLA局部搜索的第q次迭代时，子群内具有最优适应度的可行解表示为每个元素的取值范围为［1, s］上的整数。根据所有子群内最优适应度可行解的信息，得到如公式（6）所示的初始化群体每一列的取值情况，计算得到如公式（7）所示的描述解空间的概率模型上取值为j(1≤j≤m)的概率如公式（6）、（7）：

步骤2：评估种群中的个体，并从中选取适应度较高的个体集合，运用统计学习等方法对概率模型进行更新。

计算群体Yqb中L个个体的适应度，从中选择最优的W(W

2.3 分布估计蛙跳算法

混合蛙跳算法中，通过向子群内具有最优适应度的可行解Yb学习，该子群内适应度最差的可行解Yw得到更新，而只有当更新后得到的可行解newYw的适应度优于Yb时，子群内具有最优适应度的可行解Yb才能得到更新。这不仅造成混合蛙跳算法的全局收敛速度较慢，而且导致其容易陷入局部最优[8]。

本文通过将混合蛙跳算法和分布估计算法相结合，根据所有子群内最优适应度可行解的信息，建立一个描述解空间内优质解分布的概率模型，使适应度最差的可行解的每一次更新信息都来自该概率模型，而不像混合蛙跳算法中适应度最差的可行解只向该子群内的最优适应度可行解学习，从而增进子群间的学习与协作，使算法具有更为全面的学习能力，避免陷入局部最优。此外，在执行局部搜索的每一次迭代时，概率模型和各子群内的最优适应度可行解都将依据种群中的优质个体进行更新，加速子群进化，算法的收敛速度得到提高。

分布估计蛙跳算法(EDSFLA) 的具体步骤如下：

步骤1：初始化。随机生成N只青蛙组成初始蛙群。步骤2：排序。计算每只青蛙的适应度F(i)，对青蛙个体按照适应度进行降序排序。

步骤3：子群划分。将蛙群划分为L个子群。步骤4：在各子群内执行局部搜索：

步骤4-1 设numdd为子群内部进行局部搜索的迭代次数，ddz为设定的局部搜索总次数，初始化numdd=1；

步骤4-2 根据个体的适应度，确定各子群内的最优适应度可行解Yb和最差适应度可行解Yw；

步骤4-5 将W个最优适应度可行解随机放入各个子群内，若新放入的可行解的适应度优于子群内的最优适应度可行解Yb，则Yb被替换，否则保持不变;

步骤4-6 根据公式(5)更新各子群中的最差适应度可行解Yw；若newYw的适应度优于Yw，则用newYw代替Yw，否则就用中适应度最好的可行解代替Yb，根据公式(5)重新更新Yw，如果更新后可行解的适应度仍然没有改进，则随机选择一个可行解来替代Yw；

步骤4-7 若numdd

步骤5：全局信息交换。当所有子群结束一轮的局部搜索之后，将所有子群进行混合，完成全局信息交换并记录全局最优解Yg；

步骤6：计算并检验终止条件。若满足终止条件，则算法结束；否则转到步骤二重新执行排序和子群划分。通常，如果算法在经过连续几次的全局信息交换之后，全局最优解未能得到显著改进则算法强制退出。

3 仿真实验与性能分析

为了测试本文提出的资源调度算法的性能，在云计算仿真平台CloudSim上进行仿真实验，选择混合蛙跳算法和遗传算法与本文算法EDSFLA作对比实验。参数设置如下：种群规模N=300，子群个数L=30，子群内青蛙个数M=10，子群内的局部搜索次数ddz=15。

3.1 不同任务数量下的算法性能对比

在云计算的资源数量固定不变，任务数量不断变化的情况下，SFLA、GA与EDSFLA，3种算法在进行资源调度时的性能变化曲线如图1所示：

图1 不同任务数量下平均完成时间对比

从图1可以看出，3种算法在处理较少数量的任务时，资源调度所表现出的性能非常相近，这主要是因为：相对于数量较少的待处理任务，云资源的数量比较充足，因此，在处理任务时基本上不会出现资源竞争现象。随着云计算任务量的增加，3种算法所需的任务处理时间都在不断增多，其中，任务的平均完成时间增长速度最快是遗传算法GA，混合蛙跳算法SFLA次之，变化最为缓慢的是EDSFLA。因此，相较于SFLA和GA两种算法，在运用同等数量的资源处理较大的任务量时，EDSFLA具有较优的资源调度性能。

3.2 不同资源数量下的算法性能对比

在云计算的任务数量固定不变，资源数量不断变化的情况下，SFLA、GA和EDSFLA，3种算法在进行资源调度时的性能变化曲线如图2所示：

图2 不同资源数量下平均完成时间对比

仿真实验参数设置为：任务数量t=30，每个任务被划分的子任务数Nx=20，重复执行该实验5次取平均结果。

从图2可以看出，随着资源数量的不断增加，任务的平均完成时间逐渐减少，且相较于 SFLA 和 GA两种算法，本文提出的资源调度算法EDSFLA完成任务所需时间最短，资源调度性能最优。由于结合了混合蛙跳算法和分布估计算法，在有效避免陷入局部最优的同时，还加快了算法的收敛速度。

4 总结

基于分布估计蛙跳算法的资源调度策略通过将分布估计算法引入混合蛙跳算法的局部搜索环节，根据所有子群最优适应度可行解的信息建立一个描述优质解分布的概率模型，使适应度最差的可行解的每一次更新信息都来自该概率模型，此外，在执行局部搜索的每一次迭代时，依据种群中优质个体的信息，概率模型和各子群的最优适应度可行解都会得到更新。该算法在通过增强算法的全面学习能力有效避免陷入局部最优的同时，还使得算法的全局收敛性能得到提升。

参考文献

[1] MELL P, GRANCE T. The NIST Definition of Cloud Computing[R]. National Institute of Standards and Technology, 2011.

[2] 刘卫宁,靳洪兵,刘波.基于改进量子遗传算法的云计算资源调度[J].计算机应用,2013,33(8):2151-2153.

[3] 左利云,左利锋.云资源中多目标集成蚁群优化调度算法[J].计算机应用,2012,32(7):1916-1919.

[4] 刘万军,张孟华,郭文越.基于MPSO 算法的云计算资源调度策略[J].计算机工程,2011,37(11):43-48.

[5] 金伟健,王春枝.基于蝙蝠算法的云计算资源分配研究[J].计算机应用研究,2014,32(9):121～124.

[6] 孙大为,常桂然,李凤云等. 一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报,2011,39(8):18 24-1831.

[7] EUSUFF M M, LANSEY K E. Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[C]//Proc of Word Water Congress.2004:111.

[8] 张恒巍,卫波,王晋东等.基于分布估计蛙跳算法的云资源调度方法[J].计算机应用研究,2014,31(11):3225-3228. [9] 周树德,孙增圻.分布估计算法综述[J].自动化学报,2007,33(2):113-124.

TP181

A

2015.01.13）

1007-757X(2015)07-0059-03

宁菲菲（1985-），女，汉族，河南省平顶山人，平顶山学院，软件学院，助教，硕士，研究方向：无线传感器网络与云计算，平顶山，467000

王建玺（1981-），女，汉族，河南社旗人，硕士，平顶山学院，软件学院，讲师，硕士，研究方向：计算机图像处理与模式识别，平顶山，467000