多目标猫群优化算法支持下的云计算任务调度

丁岳伟,窦飞飞

(1.上海理工大学 光电信息与计算机工程学院,上海　200093;2.上海理工大学 计算机软件技术研究所,上海　200093)



多目标猫群优化算法支持下的云计算任务调度

丁岳伟1,窦飞飞2

(1.上海理工大学 光电信息与计算机工程学院,上海200093;2.上海理工大学 计算机软件技术研究所,上海200093)

摘要针对云环境下任务调度易出现多目标冲突的问题,提出一种改进的基于猫群的多目标优化算法。该算法模拟猫的行为模式,采用基于线性混合比率的猫行为选择方式来提高全局搜索和局部寻优能力;并在迭代过程中结合任务完成时间和任务费用支出,引入一个可调节的多目标集成效用函数,实现了资源与任务的智能调度。实验结果表明,所提算法不仅求解质量高,且在求解速度和调度消耗方面均优于多目标遗传算法和多目标粒子群算法。

关键词多目标猫群算法;线性混合比率;多目标集成效用函数;智能调度

云计算作为一种新技术,近年来成为信息领域的研究热点,其将通过Internet连接的各类资源整合,构成共享虚拟资源池,为用户提供便捷、优质的服务[1-2]。在这种模式下,如何快速实现资源与用户需求的智能匹配和多目标优化调度尤为重要[3]。

目前,云计算调度中多目标优化问题通常采用启发式算法,其中较典型的有多目标遗传算法、多目标粒子群法等。但多目标遗传算法具有参数复杂、局部搜索能力不足、搜索速度慢等缺点[4];多目标粒子群收敛速度快,但由于自身机制更新的限制,求解离散问题时易陷入局部最优[5]。

猫群算法(Cat Swarm Optimization,CSO)是由Shu-Chuan Chu等人在2006年提出的一种基于猫的群体智能算法[6]。在猫群算法应用方面,Santosa[7]提出利用猫群算法来解决聚类问题;刘琼等人[8]提出利用多目标猫群算法来求解混流装配线排序问题。虽然猫群算法在众多问题上取得了较好的应用,但在云计算任务调度方面的研究并不多,其具有较强的研究意义。

本文在研究了云计算任务调度和猫群算法的基础上提出了一种多目标猫群调度方案(MO-CSO),使用加权方法定义了一个基于Makespan和Total Cost的多目标模型并针对目前CSO算法进化过程中一般采用固定的混合比率,而不能根据进化程度有效分配全局猫和局部猫的问题,提出了一种基于线性混合比率的猫行为模式选择方法。MO-CSO算法能够同时进行全局搜索和局部寻优,不但解决了多目标遗传算法局部搜索能力不足以及多目标粒子群算法在解决离散问题时易陷入局部最优的问题,而且具有良好的收敛速度。

1相关模型

1.1任务调度模型

云环境下使用加权有向无环图(Directed Acyclic Graph,DAG)来描述任务调度算法,节点表示任务,边表示任务之间的数据依赖关系。其各参数的描述如下:

(1)任务列表。定义G(T,E),T(x)={T1,T2,…,Tx}为n个任务序列,E代表任务之间的数据相关性;

(2)虚拟机资源列表。定义VM(y)={VM1,VM2,…,VMy}为存储于数据中心的虚拟机资源,这些资源要跟来自网络的用户的任务需求进行映射;

(3)定义可利用资源间的数据传输开销为d_cost(mn),m,n分别表示任务Tm和任务Tn,其中m

图1　任务调度结构模型

假定每项任务对应所有资源的执行时间和开销均已知,其取值均在一些价格策略的规定范围之内。同样,任务之间数据传递的开销也是已知的。

1.2多目标调度模型

为实现基于Makespan和资源有效利用的多目标任务调度算法,本文使用加权方法定义了一个衡量开销的多目标函数,即运行时间和所需计算资源费用的加权之和[9],而系统调度的目的即满足

min(wc×T_cost(VMi)+wt×T_time(VMi))

(1)

定义T_cost(VMi)为可用资源VMi上的所有开销,包括对应所有任务的执行开销,以及这些任务与其相互依赖的任务间进行数据传输的开销。e_cost(mi)是指任务Tm使用资源VMi的开销,d_cost(mn)表示处于不同虚拟机资源上的任务Tm和Tn进行数据传输的开支,则有

(2)

定义T_time(VMi)虚拟机资源VMi上的所有任务的执行时间,etmi表示在资源VMi的任务Tm的执行时间,则有

(3)

基于之前的描述,本文将目标函数定义为

(4)

其中,权重因子wm,wt∈[0,1],且wm+wt=1。wm表示费用的权重;wt表示运行时间的权重;权重是一个偏好参数,用户可根据需要加以改变。

2CSO算法

猫群算法是一种建立在猫行为模式和群体智能基础上的新型仿生算法。该算法模拟猫的追踪过程来搜索优化问题的全局最优解,再通过猫的搜寻模式来确定局部最优解,猫的位置信息即为待求优化问题的最优解或可能解。该算法具有较好的收敛速度,在迭代过程中淘汰自适应性较差的个体,减少了无效搜索的开销。

3MO-CSO算法描述

云计算任务调度是一个任务和虚拟机资源进行相互寻找,动态匹配的过程。因此,在该算法中,可将任务和虚拟机资源分别模拟为目标所在的维度空间和猫群。猫群执行MO-CSO算法寻找到目标所在位置并进行追捕,直至输出最优解,即找到最佳调度方案。

标准CSO算法采用固定比率(MR)来分配整个猫群在执行搜寻模式和追踪模式上的数量,但这种分配方式不能根据算法的进化程度调整全局搜索和局部搜索的比重。研究发现,算法前期追踪猫的比率增大可提高的全局搜索能力,促进算法收敛到Pareto前沿的速度;后期若加大搜索猫的比率则会提高局部搜索能力,有效搜索出非支配解,保证算法的收敛性[10]。本文针对此问题提出一种基于线性混合比率的猫行为模式分配公式

(5)

其中,算法采取的最大混合比率为MRmax,最小混合比率MRmin。n为当前运行代数;IT_max为最大迭代次数。

MO-CSO算法具体过程如下:

输入猫群数量和D维坐标

输出猫的位置与任务调度方案

1./*initial N,D*/ //初始化猫群数量和D维坐标;

2.Assess FV of all cats and store non-dominated cats;

3.Divide all cats into SM and TM by MR;

4.While (FV !=min(OF)) do{

5.Update MR;

6.If(cat ∈ SM){

7.SMP←generate replicas of cat;

8.FV← check all replicas fitness value;}

9.Eles (cat ∈TM){

10.V←get velocity of cat;

11.Update D_location;

12.If (D_location>Max_space){

13. D_location=-D_location;

14.Else;

15.SF← check all replicas fitness value;}

16.Output D_location;}

MO-CSO算法中猫群有两种状态模式,搜寻模式(Seeking Mode(SM))和追踪模式(Tracing Mode(TM))。

3.1猫群搜寻模式

搜寻模式中的猫群处于休息状态,但其却不会放松警惕,会对四周环境进行观察和搜寻。在搜寻模式下涉及到的参数有:

搜寻记忆池(Seeking Memory Pool,SMP):猫群在搜寻过程中,每个个体会进行自身搜寻操作,并复制出新的个体来填充搜寻记忆池。

自适应度值(Fitness Value,FV):根据Pareto前沿来判定猫的自适应度值。

搜寻模式的具体步骤如下:

步骤1每只猫进行自身搜寻,并复制多份当前位置用来填满搜寻记忆池;

步骤2随机的初始化每只猫的维数;

步骤3评估每个副本的自适应值;

步骤4从记忆池非支配解中找出最优复制位置;

步骤5将最优的复制位置替换当前的个体位置。

3.2猫群追踪模式

追踪模式下,猫群会以很快的速度向搜寻模式中发现的目标移动。追踪模式类似粒子群算法,即用个体的位置(D_location)来表示优化问题的解,根据速度-位移模型来更新每一维个体的值。定义第i只猫在D维空间中位置和速度的具体步骤如下:

(1)根据下面的公式计算出第i只猫最新的速度

(6)

(2)根据式(7)计算更新第n只猫的位置

(7)

(3)判断第n只猫的当前位置中的任一维位置是否超出了搜索空间,若超出则将该值作为相应的边界值,触到边界值后反方向进行搜索;

(4)计算每只猫的自适应度值;

(5)用非支配解的猫来更新解集。

图2　MO-CSO 算法流程

4实验结果与分析

本文实验是在CloudSim的仿真平台上完成的,为确保数据的可靠性进行了多组仿真实验,每组运行了10次,将20次实验结果取平均值得到最后效果。

4.1实验参数设置

实验模拟了10个具有相互依赖关系的任务在3个VM资源上的调度,为使实验结果更加直观,省略了描述云任务和虚拟机资源的部分参数,比如处理能力,存储能力、带宽等。可用虚拟机资源与对应任务之间的开销和执行时间值如表1所示。

表1　虚拟机资源与任务之间的执行开销

可用虚拟机资源之间数据传输开销如表2所示。

表2　可用虚拟机资源之间的传输开销

4.2实验结果分析

在保持测试条件和环境相同的情况下,本文分别实现了MO-GA算法、MO-PSO算法、MO-CSO算法,并结合各类算法的总任务平均完成时间Makespan 和总任务平均开销Totalcosts 两大指数进行了对比测试。

图3为Mo-GA算法在应用本文多目标函数后的实验结果。

图3　MO-GA算法实验结果

图4为Mo-PSO算法在应用了本文多目标函数后的实验结果。

图4　MO-PSO算法实验结果

图5为本文所提算法Mo-CSO的实验结果。

图5　MO-CSO算法实验结果

通过对比不同的迭代次数中3种算法的多目函数min(OF)的取值,可得到较直观的优化效果,如图6所示,MO-CSO算法的min(OF)值相比另外两种算法较小,即任务调度的时间和开销均得到了优化,且这种优化效果会随着迭代次数的增大更加明显。

图6　3种算法min(OF)值对比

5结束语

本文算法相对于多目标猫群算法,不再采用固定的比率分配整个猫群在执行搜寻模式和追踪模式上的数量,而是采用一种线性混合比率,这种改进提高了全局搜索和局部寻优的能力。此外,算法设计了一个基于调度时间和费用的多目标集成效用函数作为评价算法优劣的指标。实验分别对MO—CSO 和MO-GA和MO-PSO算法进行测试,通过对比可知本文所提算法MO—CSO在解决云计算任务调度问题中具有良好的性

能,尤其在迭代次数较多时优势更加明显。下一步工作将研究建立更加符合云计算调度中的多目标调度模型,达到高效的优化效果[11]。

参考文献

[1]Stanoevska-Slabeva K,Wozniak T.Cloud basics-an introduction to cloud computing[J].Berlin Heidelberg:Springer,2010,8(4):47-61.

[2]Kwon T,Won Gi Yoo,Won-Ja Lee.Next-generation sequencing data analysis on cloud computing[J].Genes & Genomics,2015,37(3):489-501.

[3]Ghanbari S,Orhman M.A priority based job scheduling algorithm in cloud computing[J].Procedia Engineering,2012,50(9):778-785.

[4]Marjan Abdeyazdan,Amir Masoud Rahmani.Multiprocessor task scheduling using a new prioritizing genetic algorithm based on number of task children[M].New York:Distributed and Parallel Systems,2008.

[5]郭力争,耿永军,姜长源,等.云计算环境下基于粒子群算法的多目标优化[J].计算机工程与设计,2013,33(7):2358-2362.

[6]Chu S C,Tsai P W,Pan J S.Cat swarm optimization[C].Berlin,Germany:9th Pacific Rim International Conference on Artificial Intelligence,Springer Verlag,2006.

[7]Santosa B,Ningrum M K.Cat swarm optimization for clustering[C].Malaysia:IEEE International Conference for Soft Computing and Pattern Recognition(SOCPAR),2009.

[8]刘琼,范正伟,张超勇,等.基于多目标猫群算法的混流装配线排序问题[J].计算机集成制造系统,2014,19(2):333-342.

[9]Wang X,Yeo C S,Buyya R,et al.Optimizing the makespan and reliability for workflow applications with reputation and a look-head genetic algorithm[J].Future Generation Computer Systems,2011,27(8):1124-1134.

[10]Panda Ganapati,Pradhan Pyari Mohan,Majhi Babita.IIR System identification using cat swarm optimization[J].Experiment Systems with Applications,2011,38(10):12671-12683.

[11]Pradhan Pyari Mohan,Panda Ganapati.Solving multi-objective problems using cat swarm optimization[J].Experiment Systems with Applications,2012,39(3):2956-2964.

Task Scheduling in Cloud Computing Based on Optimized Multi-objective Cat Swarm Algorithm

DING Yuewei1,DOU Feifei2

(1.School of Optical-Electrical and Computer Engineering,University of Shanghai for

Science and Technology,Shanghai 200093,China;2.Institute of Computer Software Technology,

University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractConsidering the multi-objective conflict problem for job scheduling in cloud computing environment,this paper proposes an optimized multi-objective cat swarm algorithm (MO-CSO) based on cat behavior using the linear mixture ratio selection method to improve the global search and local optimization ability.The algorithm combines the makespan and total cost to propose an adjustable multi-objective integrated utility function,which implements the intelligent dispatching of resources and task.The experimental results show that the optimized MO-CSO not only has high quality,but also are superior in solving speed and scheduling costs to the multi-objective genetic algorithm (MO-GA) and the multi-objective particle swarm optimization (MO-PSO) algorithm.

Keywordsmulti-objective cat swarm algorithm;linear mixing ratio;a multi-objective integrated utility function;intelligent scheduling

中图分类号TP306.1

文献标识码A

文章编号1007-7820(2016)02-004-05

doi:10.16180/j.cnki.issn1007-7820.2016.02.002

作者简介:丁岳伟(1961—),男,教授,硕士生导师。研究方向:计算机网络应用等。窦飞飞(1990—),女,硕士研究生。研究方向:云计算等。

基金项目:上海市自然科学基金资助项目(14ZR1440100);上海市教委科研创新重点基金资助项目(14ZS167)

收稿日期:2015- 08- 25