基于多目标免疫系统算法的云任务调度策略

doi:10.11772/j.issn.1001-9081.2016.02.0324

计算机应用 ›› 2016, Vol. 36 ›› Issue (2): 324-329.DOI: 10.11772/j.issn.1001-9081.2016.02.0324

• 第三届CCF大数据学术会议(CCF BigData 2015) • 上一篇下一篇

基于多目标免疫系统算法的云任务调度策略

段凯蓉, 张功萱

南京理工大学计算机科学与工程学院, 南京 210094

收稿日期:2015-08-29 修回日期:2015-09-07 出版日期:2016-02-10 发布日期:2016-02-03
通讯作者: 段凯蓉(1990-),女,陕西西安人,硕士研究生,主要研究方向:Web服务、分布式计算。
作者简介:张功萱(1961-),男,江西景德镇人,教授,博士生导师,博士,CCF会员,主要研究方向:Web服务、信息安全、分布式计算系统。
基金资助:
国家自然科学基金资助项目(61272420)。

Multi-objective immune system algorithm for task scheduling in cloud computing

DUAN Kairong, ZHANG Gongxuan

School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing Jiangsu 210094, China

Received:2015-08-29 Revised:2015-09-07 Online:2016-02-10 Published:2016-02-03

摘要/Abstract

摘要： 针对云计算环境下任务调度问题,为减少任务完工时间,同时降低任务执行费用,提出一种改进的基于多目标免疫系统的任务调度算法IMISA来寻找较优的可行分配方案。与传统分配适应度值不同,该算法将抗体群划分为非支配解集和支配解集,分别将非支配解的独立支配区域面积、支配解与所有非支配解所围成的多边形面积作为相应的抗体-抗原亲和力,根据相应亲和度计算克隆比例后克隆变异生成子代。在CloudSim平台上进行仿真实验,结果表明,与NSGA-Ⅱ及多目标免疫系统算法(MISA)相比,IMISA能够找到具有更短完工时间及更小的执行费用的调度方案,同时获得的Pareto解集也具有更好的分布性。

关键词: 云计算, 任务调度, 免疫系统算法, 多目标优化, Pareto解集

Abstract: To address the task scheduling problem in cloud, a new multi-objective immune system algorithm named IMISA (Improved Multi-objective Immune System Algorithm) was proposed to optimize completion time and monetary cost simultaneously. In this work, the assignment of the fitness value was different from the traditional way, the antibodies were divided into non-dominated antibodies and dominated antibodies. The exclusive dominated area was regarded as the antigen affinity, and the polygonal area surrounded by all the non-dominated solutions and a selection of the dominated antibody were treated as the corresponding antibody-antigen affinity. After that, clonal probability was calculated according to these affinities and new offspring was generated by cloning and mutation. Simulation experiments on CloudSim indicate that, compared with NSGA-Ⅱ and Multi-objective Immune System Algorithm (MISA), the proposed algorithm can produce schemes with shorter completion time and lower monetary cost, and it also can achieve Pareto fronts with better quality in both convergence and diversity.

Key words: cloud computing, task scheduling, Immune System Algorithm(ISA), multi-objective optimization, Pareto solution set

中图分类号:

TP301.6

段凯蓉, 张功萱. 基于多目标免疫系统算法的云任务调度策略[J]. 计算机应用, 2016, 36(2): 324-329.

DUAN Kairong, ZHANG Gongxuan. Multi-objective immune system algorithm for task scheduling in cloud computing[J]. Journal of Computer Applications, 2016, 36(2): 324-329.

参考文献

[1] 刘鹏.云计算[M].2版.北京:电子工业出版社, 2011: 2-3. (LIU P. Cloud computing[M]. 2nd ed. Beijing: Publishing House of Electronics Industry, 2011: 2-3.)
[2] MING G, LI H. An improved algorithm based on max-min for cloud task scheduling[M]//Recent Advances in Computer Science and Information Engineering. Berlin: Springer, 2012: 217-223.
[3] 李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31(1):184-186. (LI J F, PENG J. Task scheduling algorithm based on improved genetic algorithm in cloud computing environment[J]. Journal of Computer Applications, 2011, 31(1): 184-186.)
[4] SELVARNI S, SADHASIVAM G S. Improved cost-based algorithm for task scheduling in cloud computing[C]//ICCIC 2010: Proceedings of the 2010 IEEE International Conference on Computational Intelligence and Computing Research. Piscataway, NJ: IEEE, 2010: 1-5.
[5] LI K, XU G C, ZHAO G Y, et al. Cloud task scheduling based on load balancing ant colony optimization[C]//ChinaGrid 2011:Proceedings of the 2011 Sixth Annual ChinaGrid Conference. Washington, DC: IEEE Computer Society, 2011: 3-9.
[6] ZHAN S, HUO H. Improved PSO-based task scheduling algorithm in cloud computing[J]. Journal of Information & Computational Science, 2012, 9(13): 3821-3829.
[7] 谢开贵,曾晓晖,李春燕,等.免疫算法与其他随机优化算法的比较分析[J].重庆大学学报(自然科学版),2003,26(11):43-47. (XIE K G, ZENG X H, LI C Y, et al. Comparative analysis between immune algorithm and other random searching algorithms[J]. Journal of Chongqing University (Natural Science Edition), 2003, 26(11): 43-47.)
[8] DEB K, PRATAP A, AGAWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[9] CORTÉS N C, COELLO C A C. Multiobjective optimization using ideas from the clonal selection principle[C]//GECCO '03: Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation: Part I, LNCS 2723. Berlin: Springer, 2003: 158-170.
[10] AICKLIN U, DASGUPTA D, GU F. Artificial immune systems[C]//ICARIS 2004: Proceedings of the Third International Conference on Artificial Immune Systems, LNCS 3239. Berlin: Springer, 2014: 187-211.
[11] ZHAO J, LIU Q L, WANG W, et al. A parallel immune algorithm for traveling salesman problem and its application on cold rolling scheduling[J]. Information Sciences, 2011, 181(7): 1212-1223.
[12] LI B, WU S, YANG J, et al. A three-fold approach for job shop problems: a divide-and-integrate strategy with immune algorithm[J]. Journal of Manufacturing Systems, 2012, 31(2): 195-203.
[13] SZABO A, DE CASTRO L N, DELGADO M R. FaiNet: an immune algorithm for fuzzy clustering[C]//FUZZ-IEEE 2012: Proceedings of the 2012 IEEE International Conference on Fuzzy Systems. Piscataway, NJ: IEEE, 2012: 1-9.
[14] JIAO L C, GONG M G, SHANG R H, et al. Clonal selection with immune dominance and anergy based multiobjective optimization[C]//EMO 2005: Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization, LNCS 3410. Berlin: Springer-Verlag, 2005: 474-489.
[15] 郑金华,李珂,李密青,等.一种基于Hypervolume指标的自适应邻域多目标进化算法[J].计算机研究与发展,2012,49(2):312-326. (ZHENG J, LI K, LI M Q, et al. Adaptive neighbor multi-objective evolutionary algorithm based on hypervolume indicator[J]. Journal of Computer Research and Development, 2012, 49(2): 312-326.)
[16] KNOWELS J D, CORNE D W. Approximating the nondominated front using the Pareto archived evolution strategy[J]. Evolutionary Computation, 2000, 8(2): 149-172.
[17] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice & Experience, 2011, 41(1): 23-50.
[18] ZITZLER E, DEB K, THIELE L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195.
[19] SCHOTT J R. Fault tolerant design using single and multicriteria genetic algorithm optimization [D]. Cambridge, MA: Massachusetts Institute of Technology, 1995: 136.

基于多目标免疫系统算法的云任务调度策略

Multi-objective immune system algorithm for task scheduling in cloud computing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[2]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[3]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[4]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[5]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[6]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[7]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[8]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[9]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[10]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[11]	李二超, 杨蓉蓉. 基于自适应反向学习的多目标分布估计算法[J]. 计算机应用, 2021, 41(1): 15-21.
[12]	王博, 刘连生, 韩绍程, 祝世兴. 基于多策略融合的混合多目标蝗虫优化算法[J]. 计算机应用, 2020, 40(9): 2670-2676.
[13]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[14]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[15]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.