基于入侵肿瘤生长优化的云计算调度算法  

Task Scheduling Algorithm in Cloud Computing Based on Invasive Tumor Growth Optimization

作　　者：周静[1] 董守斌[1] 唐德玉 ZHOU Jing;DONG Shou-Bin;TANG De - Yu(Department of Computer Science and Technology,South China University of Technology,Guangzhou 510641;Department of Medical Information Engineering,Guangdong Pharmaceutical University,Guangzhou 510006)

机构地区：[1]华南理工大学计算机科学与工程学院,广州510641 [2]广东药科大学医药信息工程学院,广州510006

出　　处：《计算机学报》2018年第6期1360-1375,共16页Chinese Journal of Computers

基　　金：广东省自然科学基金(2015A030308017;2016A030310300)资助~~

摘　　要：随着云计算应用的发展,云计算任务调度的要求越来越复杂.群智能算法能在满足多种约束限制下,实现复杂的云计算任务调度问题,因而得到广泛应用.入侵肿瘤生长优化算法ITGO(Invasive Tumor Growth Optimization)是一种新型的启发式群智能算法,该算法通过模拟肿瘤的生长和入侵行为,在解空间中搜寻最优解,具有较高的准确性和较快的收敛速度.该文将入侵肿瘤生长优化算法离散化,提出了一种离散化的入侵肿瘤生长调度算法D-ITGO,通过将云计算任务调度方式的可行解即任务—虚拟机对应关系映射成为肿瘤细胞的坐标,使之可以应用于云计算任务调度问题;并针对云计算调度问题进行优化设计,包括:(1)设计生长细胞到入侵细胞的转换策略,使得更容易和更快地跳出局部最优解;(2)设计死亡细胞到入侵细胞转换策略,以避免浪费资源,并提高搜索效率;(3)调整生长细胞的生长步长,在逼近最优解时放慢生长速度,以避免跳过最优解.该文基于CloudSim仿真环境对D-ITGO算法以及优化策略进行了实验测试,并且使用非参数假设检验,对实验结果进行了评估和分析.实验结果和分析结果表明,这些策略均能提高收敛速率和搜索效率,其中,生长细胞到入侵细胞的转换策略和死亡细胞到入侵细胞转换策略在一定程度上减少了计算时间,生长细胞的生长步长调整策略能强化D-ITGO的搜索效率.同时,D-ITGO算法比目前应用于云计算任务调度的算法,在云任务执行时间上有7.1%~11.2%的提升,在调度开销上也有一定的优势.With the development of cloud computing,there are more and more complex requirements raised by cloud task schedule and then the corresponding schedule methods need to solve more and more problems.Swarm intelligence algorithms are widely used in this field（task schedule in cloud environment）because they can solve these complex problems effectively,and at the same time satisfy a lot of constraints.Invasive Tumor Growth Optimization is a new meta-heuristic algorithm of swarm intelligence.This algorithm can effectively find out the optimal solution（s）in the solution space,and obtain high convergence rate and accuracy by imitating the behavior of tumor cells,including the growth behavior and invasive behavior.In this paper,we proposed a Discrete Invasive Tumor Growth Optimization（D-ITGO）,which is to make the original Invasive Tumor Growth Optimization to be discretized,to solve the task scheduling problem in cloudenvironment.The main schedule strategy of D-ITGO is to make a correspondence between cloud tasks and virtual machines,then map this kind of correspondence into the coordinates of a tumor cell,finally solve the problem by improving some search strategies of original ITGO.We proposed three new strategies for this problem,including：（1）the design of a new transformation strategy,which transforms the growing cells into invasive cells by the criteria of Life_span,to make the D-ITGO to be easier and faster to get away from local optima;（2）a re-design of the transformation strategy between the death cells and invasive cells to improve the search efficiency;The new strategy make death cells transform into invasive cells directly,which can maximize the release of memory space,and at the same time save the computational resource;（3）an adjustment of growth step-size of the growing cells,which can slow down the growth of the growing cells when they approach to the optima values,to avoid skipping the optimal solutions.In the experiment,we used CloudSim toolkit for testing,and used the non-parametr

关 键 词：云计算 群智能算法 入侵肿瘤生长优化算法 任务调度 时间开销 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]