高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

基于逆向学习行为粒子群算法的云计算大规模任务调度

    作者简介: 赖兆林(1986-),男,博士生,主要研究方向为人工智能、演化计算。E-mail: lzl_education@163.com;
    通讯作者: 冯翔, xfeng@ecust.edu.cn
  • 中图分类号: TP18

A Reverse Learning Behavior Particle Swarm Optimization for Large-Scale Task Scheduling in Cloud Computing Environment

    Corresponding author: Xiang FENG, xfeng@ecust.edu.cn ;
  • CLC number: TP18

  • 摘要: 针对传统智能优化算法在解决云计算任务调度时, 存在易陷入局部最优和过早收敛的问题,提出了一种逆向学习行为粒子群算法(RLPSO)。首先,采用分群策略对种群内个体进行群划分,使得整个种群具有搜索行为多样性,增强算法的搜索能力;其次,引入逆向学习机制及繁殖机制,避免算法陷入局部最优,并在理论上证明了RLPSO算法的收敛性;最后,通过实验进行有效性验证,并与4个经典智能优化算法进行了比较。实验结果表明,在大规模任务调度总完成时间寻优问题上,RLPSO算法表现出比4个对比算法更优的搜索性能。
  • 图 1  粒子编码解码示例图

    Figure 1.  Example of particle coding and decoding

    图 2  粒子分群机制

    Figure 2.  Grouping mechanism of particles

    图 3  个体的搜索方式及学习方向

    Figure 3.  Search mode and learning direction of individual

    图 4  种群内个体繁殖行为

    Figure 4.  Reproductive behavior of individual

    图 5  基准测试函数三维空间分布图

    Figure 5.  Visualization of benchmark functions in three-dimensional space

    图 6  5种算法在不同任务数下的收敛曲线

    Figure 6.  Convergence curves of five algorithms under different number of tasks

    图 7  3种不同任务数的完成时间

    Figure 7.  Completion time of five algorithms on three different number of tasks

    表 1  基准测试函数

    Table 1.  Benchmark functions

    NameEquationBoundMinimumD
    Sphere${f_1}(x) = \displaystyle\sum\limits_{i = 1}^D {x_i^2} $[−100, 100]030
    Schwefel 1.2${f_2}(x) = \displaystyle\sum\limits_{i = 1}^D {{{\left(\sum\limits_{j = 1}^i {{x_j}} \right)}^2}} $[−100, 100]030
    Rosenbrock${f_3}(x) = \displaystyle\sum\limits_{i = 1}^{D - 1} {[100{{({x_{i + 1}} - x_i^2)}^2} + {{({x_i} - 1)}^2}]} $[−30, 30]030
    Sum of Squares${f_4}(x) = \displaystyle\sum\limits_{i = 1}^D {i \cdot x} _i^2$[−10, 10]030
    Rastrigin${f_5}(x) = \displaystyle\sum\limits_{i = 1}^D {[x_i^2 - 10 \cos (2{\text{π}} {x_i}) + 10]} $[−5.12, 5.12]030
    F4${f_6}(x) = 418.982\; 9 D + \displaystyle\sum\limits_{i = 1}^D {( - {x_i}\sin (\sqrt {\left| {{x_i}} \right|} ))} $[−100, 100]030
    Ackley$\begin{aligned} {f_7}(x) =& - 20\exp \left( - 0.2\sqrt {\displaystyle\frac{1}{D} \displaystyle\sum\limits_{i = 1}^D {x_i^2} } \right) -\\& \exp \left[\displaystyle\frac{1}{D} \sum\limits_{i = 1}^D {\cos (2{\text{π}} {x_i})} \right] + 20 + \exp (1) \\ \end{aligned} $[−32, 32]030
    Griewank${f_8}(x) = \displaystyle\frac{1}{{4\; 000}}\displaystyle\sum\limits_{i = 1}^D {x_i^2 - \prod\limits_{i = 1}^D {\cos \left(\displaystyle\frac{{{x_i}}}{{\sqrt i }}\right) + 1} } $[−600, 600]030
    下载: 导出CSV

    表 2  不同的μ取值时RLPSO算法的目标函数值

    Table 2.  Objective function values of RLPSO algorothm with different μ

    μf1f2f3f4
    MeanStdMeanStdMeanStdMeanStd
    0.19.92×10−11.53×10−24.75×10−14.61×10−22.38×1026.50×1019.76×1013.87
    0.27.38×10−12.35×10−21.72×10−15.26×10−21.94×1027.16×1015.01×1014.27
    0.34.81×10−19.62×10−26.50×10−29.19×10−31.65×1022.96×1011.28×1017.52
    0.45.73×10−22.87×10−34.27×10−23.40×10−31.02×1025.84×1019.392.18×10−1
    0.51.68×10−21.12×10−33.91×10−25.18×10−36.42×1012.57×1014.889.01×10−1
    0.61.59×10−33.87×10−43.47×10−22.31×10−33.57×1011.082.241.43×10−1
    0.74.92×10−38.72×10−43.04×10−21.97×10−34.29×1018.514.13×1015.65
    0.87.16×10−23.22×10−33.68×10−29.85×10−35.85×1013.426.74×1012.91
    0.93.24×10−21.53×10−38.95×10−25.72×10−36.91×1015.387.15×1012.62
    μf5f6f7f8
    MeanStdMeanStdMeanStdMeanStd
    0.18.25×1023.52×1012.36×10−15.67×10−21.92×1013.209.351.71×10−1
    0.27.93×1029.51×1011.45×10−12.38×10−21.07×1019.891.147.93×10−1
    0.36.04×1028.97×1018.28×10−24.12×10−35.331.85×10−17.80×10−16.24×10−2
    0.41.13×1021.37×1016.17×10−25.50×10−39.65×10−14.01×10−24.54×10−11.97×10−2
    0.59.18×1014.035.09×10−28.11×10−33.42×10−11.70×10−27.26×10−25.41×10−2
    0.66.62×1012.824.85×10−22.36×10−38.04×10−15.62×10−21.09×10−22.53×10−3
    0.78.49×1013.515.63×10−26.70×10−32.161.37×10−15.18×10−22.99×10−3
    0.82.71×1024.50×1017.04×10−23.64×10−34.987.45×10−19.24×10−28.37×10−3
    0.95.25×1029.43×1012.59×10−17.23×10−26.209.13×10−13.48×10−13.25×10−2
    下载: 导出CSV

    表 3  3种不同任务数的完成时间

    Table 3.  Completion time of five algorithms under the different number of tasks

    AlgorithmCompletion time
    Tn=100Tn=500Tn=1 000
    RLPSOBest11.5460.95145.42
    Worst13.1863.82158.17
    Mean12.3662.50149.34
    Std2.451.9812.63
    GABest28.07106.04195.11
    Worst30.25110.52224.62
    Mean29.41108.93217.19
    Std5.369.8420.04
    ACOBest17.9493.26183.06
    Worst20.8798.41208.48
    Mean19.0596.18195.13
    Std4.273.3114.71
    LSABest15.1368.32151.35
    Worst17.5873.44174.20
    Mean16.2470.61166.12
    Std3.483.8718.47
    PSOBest20.2486.71169.21
    Worst22.6590.12198.34
    Mean21.7988.97181.72
    Std3.224.2616.05
    下载: 导出CSV

    表 4  5个优化算法Wilcoxon's test的p值

    Table 4.  p-values of Wilcoxon's test of five algorithms

    Algorithmp
    Tn =100Tn =500Tn =1 000
    RLPSO
    GA2.46×10−22.51×10−22.49×10−2
    ACO1.38×10−21.44×10−21.26×10−2
    LSA4.52×10−24.60×10−24.85×10−2
    PSO2.95×10−22.87×10−23.18×10−2
    下载: 导出CSV

    表 5  5个优化算法的Friedman test排名结果

    Table 5.  Ranking results of Friedman test of five algorithms

    TnRLPSOGAACOLSAPSO
    1001.003.504.752.253.50
    5001.005.003.252.253.50
    1 0001.005.004.002.252.75
    下载: 导出CSV
  • [1] 李飞标, 虞慧群, 范贵生. 基于能耗降低的虚拟机动态迁移算法[J]. 华东理工大学学报(自然科学版), 2017, 43(5): 102-107.
    [2] VOUK M A. Cloud computing —— Issues, research and implementations[C]// International Conference on Information Technology Interfaces. USA: IEEE, 2008: 31-40.
    [3] DINH H T, LEE C, NIYATO D, et al. A survey of mobile cloud computing: Architecture, applications and approaches[J]. Wireless Communications and Mobile Computing, 2013, 13(18): 1587-1611. doi: 10.1002/wcm.v13.18
    [4] 陈全, 邓倩妮. 云计算及其关键技术[J]. 计算机应用, 2009, 29(9): 2562-2567.
    [5] ARFEEN M A, PAWLIKOWSKI K, WILLIG A. A framework for resource allocation strategies in cloud computing environment[C]// 2011 IEEE 35th Annual Computer Software and Applications Conference Workshops.USA: IEEE, 2011: 261-266.
    [6] 汪定伟, 王俊伟, 王洪峰, 等. 智能优化方法[M]. 北京: 高等教育出版社, 2007.
    [7] ZHAO Chenhong, ZHANG Shanshan, LIU Qingfeng, et al.Independent tasks scheduling based on genetic algorithm in cloud computing[C] //Proceedings of IEEE 5th International Conference on Wireless Communications, Networking and Mobile Computing. Beijing, China: IEEE, 2009: 1-4.
    [8] LI Jianfeng, PENG Jian, CAO Xiaoyang, et al. A task scheduling algorithm based on improved ant colony optimization in cloud computing environment[J]. Energy Procedia, 2011, 13: 6833-6840. doi: 10.1016/S1876-6102(14)00454-8
    [9] GUO Lizheng, ZHAO Shuguang, SHEN Shigen, et al. Task scheduling optimization in cloud computing based on heuristic algorithm[J]. Journal of Networks, 2012, 7(3): 547-553.
    [10] AGARWAL M, SRIVASTAVA G M S. A cuckoo search algorithm-based task scheduling in cloud computing[C]//Advances in Computer and Computational Sciences. Singapore : Springer, 2018: 293-299.
    [11] DAOUD M I, KHARMA N N. A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks[J]. Journal of Parallel and Distributed Computing, 2011, 71(11): 1518-1531. doi: 10.1016/j.jpdc.2011.05.005
    [12] SIM K M, SUN W H. Ant colony optimization for routing and load-balancing: Survey and new directions[J]. IEEE Transactions on Systems, Man, and Cybernetics : Part A. Systems and Humans, 2003, 33(5): 560-572. doi: 10.1109/TSMCA.2003.817391
    [13] KENNEDY J, SPEARS W. Matching algorithms to problems: An experimental test of the particle swarm and some genetic algorithms on the multimodal problem generator[C]// Proceedings of IEEE International Conference on Evolutionary Computation. USA: IEEE, 1998: 78-83.
    [14] 李荣雨, 刘洋. 基于梯度的自适应快速布谷鸟搜索算法[J]. 运筹学学报, 2016, 20(3): 45-56.
    [15] 张垚, 曹萃文, 顾幸生. 基于一种遗传邻域万有引力算法的作业车间调度[J]. 华东理工大学学报(自然科学版), 2018, 44(4): 573-580.
    [16] WOLPERT D H, MACREADY W G. No free lunch theorems for optimization[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82. doi: 10.1109/4235.585893
    [17] LI X, ZHANG J, YIN M. Animal migration optimization: An optimization algorithm inspired by animal migration behavior[J]. Neural Computing and Applications, 2013, 24(7/8): 1867-1877.
    [18] ZHANG H, ZHU Y, CHEN H. Root growth model: A novel approach to numerical function optimization and simulation of plant root system[J]. Soft Computing, 2014, 18(3): 521-537. doi: 10.1007/s00500-013-1073-z
    [19] FENG X, WANG Y, YU H, et al. A novel intelligence algorithm based on the social group optimization behaviors[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2017, 48(1): 65-76.
    [20] ZHAN Z H, ZHANG J, LI Y, et al. Orthogonal learning particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(6): 832-847. doi: 10.1109/TEVC.2010.2052054
    [21] CHEN W N, ZHANG J, LIN Y, et al. Particle swarm optimization with an aging leader and challengers[J]. IEEE Transactions on Evolutionary Computation, 2013, 17(2): 241-258. doi: 10.1109/TEVC.2011.2173577
    [22] QIN Q, CHENG S, ZHANG Q, et al. Particle swarm optimization with interswarm interactive learning strategy[J]. IEEE Transactions on Cybernetics, 2015, 46(10): 2238-2251.
    [23] DONG W, ZHOU M C. A supervised learning and control method to improve particle swarm optimization algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 47(7): 1135-1148.
    [24] GONG Y J, LI J J, ZHOU Y, et al. Genetic learning particle swarm optimization[J]. IEEE Transactions on Cybernetics, 2017, 46(10): 2277-2290.
    [25] LIN Q, LIU S, ZHU Q, et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 32-46. doi: 10.1109/TEVC.2016.2631279
    [26] LEITHEN K.M’Gonigle, RUPERT Mazzucco, et al. Sexual selection enables long-term coexistence despite ecological equivalence[J]. Nature, 2012, 484: 506-509. doi: 10.1038/nature10971
    [27] DYER A G, DORIN A, REINHARDT V, et al. Bee reverse-learning behavior and intra-colony differences: Simulations based on behavioral experiments reveal benefits of diversity[J]. Ecological Modelling, 2014, 277: 119-131. doi: 10.1016/j.ecolmodel.2014.01.009
    [28] KENNEDY J, EBERHART R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks. USA: IEEE, 1995: 1942-1948.
    [29] BRATTON D, KENNEDY J. Defining a standard for particle swarm optimization[C]// Proceedings of the IEEE Swarm Intelligence Symposium.Honolulu, USA: IEEE, 2007: 120-127.
    [30] LIU B, WANG L, JIN Y H. An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Transactions on Systems Man & Cybernetics, 2007, 37(1): 18-27.
    [31] SHAREEF H, IBRAHIM A A, MUTLAG A H. Lightning search algorithm[J]. Applied Soft Computing, 2015, 36: 315-333.
    [32] FOONG, KUAN W, MAIER H R, Simpson A R. Ant colony optimization for power plant maintenance scheduling optimization[J]. Annals of Operations Research, 2008, 159(1): 433-450. doi: 10.1007/s10479-007-0277-y
    [33] GE Y, WEI G. GA-based task scheduler for the cloud computing systems[C]// International Conference on Web Information Systems and Mining. USA: IEEE, 2010: 181-186.
    [34] GARCÍA S, MOLINA D, LOZANO M, et al. A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behavior: A case study on the CEC’2005 special session on real parameter optimization[J]. Journal of Heuristics, 2009, 15(6): 617-644. doi: 10.1007/s10732-008-9080-4
  • [1] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180321005
    [2] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416001
    [3] 赵倩倩赵均徐祖华陈曦邵之江秦海中 . 空分装置群的设备启停及变负荷调度策略. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181015005
    [4] 王德勋虞慧群范贵生 . 基于深度学习的面部动作单元识别算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190107003
    [5] 徐震浩周畅张凌波顾幸生 . 柔性作业车间的成套订单调度问题. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181109001
    [6] 罗雪莉郎美东 . 聚合物前药载药性能的计算机模拟. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190514001
    [7] 赵剑沈阳曹旭妮 . 基于铁蛋白的溶栓蛋白纳米粒子的构建及活性分析. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180601001
    [8] 马振伟何高奇袁玉波 . 基于小样本深度学习的通风柜橱窗状态识别方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190412004
    [9] 陈剑挺叶贞成程辉 . 基于p阶Welsch损失的鲁棒极限学习机. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181209001
    [10] 张雪芹魏一凡 . 基于深度学习的驾驶场景关键目标检测与提取. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181023002
    [11] 张习习顾幸生 . 基于集成学习概率神经网络的电机轴承故障诊断. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181206001
    [12] 宋振振陈兰岚娄晓光 . 基于时序卷积网络的情感识别算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190508001
    [13] 赵菡诸葛晶晶林家骏 . 飞行状态敏感的关联门调节算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180622003
    [14] 吉祥虞慧群范贵生孙怀英 . 基于蚁群算法的延时感知VANET路由协议. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181116001
    [15] 陈立皇程华房一泉 . 基于注意力机制的DGA域名检测算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180326002
    [16] 王学武夏泽龙顾幸生 . 基于事件触发的自适应邻域多目标进化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181120005
    [17] 常青张天宇赵冰冰 . 基于机器视觉的手机异形主板非标自动化检测算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416006
    [18] 颜建军刘章鹏刘国萍郭睿王忆勤付晶晶钱鹏 . 基于深度森林算法的慢性胃炎中医证候分类. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180410001
    [19] 高炳舒刘士荣 . 基于BoW模型的RGB-D SLAM算法的运动轨迹估计. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180419001
    [20] 曹雅茜黄海燕 . 基于代价敏感大间隔分布机的不平衡数据分类算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180515001
  • 加载中
图(7)表(5)
计量
  • 文章访问数:  2800
  • HTML全文浏览量:  1332
  • PDF下载量:  10
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-02-26
  • 网络出版日期:  2019-05-29

基于逆向学习行为粒子群算法的云计算大规模任务调度

    作者简介:赖兆林(1986-),男,博士生,主要研究方向为人工智能、演化计算。E-mail: lzl_education@163.com
    通讯作者: 冯翔, xfeng@ecust.edu.cn
  • 华东理工大学计算机科学与工程系,上海 200237

摘要: 针对传统智能优化算法在解决云计算任务调度时, 存在易陷入局部最优和过早收敛的问题,提出了一种逆向学习行为粒子群算法(RLPSO)。首先,采用分群策略对种群内个体进行群划分,使得整个种群具有搜索行为多样性,增强算法的搜索能力;其次,引入逆向学习机制及繁殖机制,避免算法陷入局部最优,并在理论上证明了RLPSO算法的收敛性;最后,通过实验进行有效性验证,并与4个经典智能优化算法进行了比较。实验结果表明,在大规模任务调度总完成时间寻优问题上,RLPSO算法表现出比4个对比算法更优的搜索性能。

English Abstract

  • 云计算是一种新的计算模型和服务模式[1],融合了网络及计算机技术,实现资源共享和按需访问,并为基础设施、平台和软件(应用)服务。当用户应用程序需要服务时,它可动态地提供尽可能多的计算资源。与此同时,应用程序可以选择其数据存储在哪些服务器上,使得用户能更好地掌控自己的数据。云计算的原理为:以网络的方式将较大的计算程序拆分成一系列小的子程序,然后通过服务器集群计算后的结果传给用户[2]。例如Google的Map/Reduce框架就是采用这种技术,TB级的数据可在数秒内被处理完成,从而实现了与超级计算机同样功效的服务[3]

    在商业应用中,可采用离线方式的有数据挖掘和数据存储等,而对于实时性要求较高的应用,例如交易处理及电子商务,都要求系统尽可能在较短时间内处理完提交的任务。然而,通常情况下,用户所请求的服务数量比较大,因此,为了使系统快速响应用户请求,任务调度算法起着至关重要的作用。与此同时,设计有效的调度算法,使得整个系统达到最优,成为云计算研究的难点[4]

    云计算中的任务调度问题属于NP完全问题[5]。智能优化算法,很适合求解此类问题[6],例如遗传算法(GA)、蚁群算法(ACO)、粒子群算法(PSO)和布谷鸟搜索算法(CSA)等,且这些算法已被应用于解决云计算任务调度问题,并取得一定的效果。文献[7]采用GA算法实现了云计算中独立任务的有效调度。文献[8]利用ACO算法优化了云计算的总任务及平均任务完成时间;文献[9]提出了基于PSO的调度算法,使得云计算任务的处理时间及传输时间最小;文献[10]使用布谷鸟搜索算法对云计算任务的总响应时间进行了优化。任何优化算法都有其优点和不足。例如,GA算法的时间开销小及鲁棒性高,而不足之处是容易陷入早熟收敛[11];ACO算法具有较好的搜索能力,但计算量大,收敛速度慢[12];PSO算法实现容易、需要设置的参数少及收敛速度快,但迭代后期局部寻优性能不足[13];CSA算法计算速度快,但存在全局寻优性能与局部寻优性能不平衡的缺陷[14]

    智能优化算法的共同特征在于模拟自然行为,且每一个算法都具有其优缺点[15]。此外,文献[15]指出不存在任何一个算法可以解决所有的优化问题,某一算法可能在某些问题上表现出色,但是在另一问题上其性能不佳。因此,为了提升智能优化算法的优化性能,一些研究者提出了新的优化算法。Li等[16]受动物迁徙行为启发,提出了动物迁徙优化算法(BBO);Zhang等[17]通过模拟自然界中植物根系生长行为,提出了根生算法(RGA);Feng 等[18]以社会群理论为基础,提出了社会群熵优化算法(SGEO)。还有一些学者通过改进已有算法来提升优化算法的性能。Zhan等[19]在PSO算法基础上采用正交学习策略,提出了正交学习粒子群算法(OLPSO);Chen等[20]把衰老机制引入PSO算法中,提出了老化领导者的PSO算法(ALC-PSO);Qin等[21]基于PSO引入群内交互学习策略,提出了群内交互学习PSO算法(IILPSO)。PSO算法作为较为经典的智能优化算法,最近几年依然有不少学者对其进行研究并改进。Dong等[22]受机器学习中的监督学习和控制领域中的预测控制策略启发,提出了一种基于监督学习控制的自适应粒子群优化算法(APSO-SLC);Gong等[23]通过采用遗传算子来生成粒子学习的范例,提出了一种遗传学习粒子群算法(GL-PSO);Lin等[24]通过设计一种平衡适应度估计方法和一种新的粒子速度更新公式,提出了一种新的多目标粒子群算法(NMPSO)。

    本文受文献[25]中生物以性别分群及文献[26]中蜜蜂逆向学习行为的启发,提出了一种逆向学习行为粒子群优化算法(RLPSO),并应用到云计算任务调度问题上。该算法在传统粒子群算法基础上,首先把整个种群划分为雄性群体和雌性群体;然后,引入逆向学习行为。这两种机制有助于提升算法搜索能力,并且可以加快算法收敛速度。在云计算任务调度问题上,与4个经典的智能优化算法相比,RLPSO算法在大规模任务调度时,总任务时间减少,并且提升了任务调度效率。

    • 粒子的编码主要有两种方式,一种是直接编码(即一个粒子代表一个可行解);另一种是间接编码(即一个粒子表示一种任务调度策略), 本文使用间接编码。

      假设云计算下的任务数为Tn,资源数为Rn,子任务总数为Sn。由于每个任务划分为多个子任务,从而有子任务的总数大于任务数。子任务数与每个任务数的关系,如式(1)所示:

      其中,Hn(i)表示第i个任务包含子任务的数目。

      使用顺序法对子任务进行编码,其公式如下:

      其中,D[r, c]表示第c个任务中的第r个子任务。

      假设Tn=3,Rn=3,Sn=10,并且粒子(2, 1, 3, 1, 3, 1, 2, 1, 3, 2)是可行的调度,图1示出了粒子编码及解码示意图。对于编码过程,其任务、子任务对(2, 6)表示第2个任务的第3个子任务编号为6;子任务、资源对(6, 1)表示把子任务6分配给资源1执行。对于解码过程,资源1上执行的子任务是{2, 4, 6, 8},资源2上执行的子任务是{1, 7, 10},资源3上执行的子任务是{3, 5, 9}。

      图  1  粒子编码解码示例图

      Figure 1.  Example of particle coding and decoding

      完成全部任务的总时间如下:

      其中:Utime(k, i)表示第k个资源执行第i个子任务所需的时间开销;m表示分配给该资源的子任务数目。

      从式(3)可知,完成一组任务的可行调度总时间为Otime由于一组任务的可行调度对应于优化算法中的一个解xi(粒子), 因此,完成全部任务的总时间转换为优化问题的目标函数为

    • 粒子群优化算法(PSO)[27]是研究者受鸟群的集体行为启发提出的一种自然启发式算法。该算法模拟了自然界中鸟群捕食行为,从而建立具有群体智能的简单模型。整个群体中的个体共享最优个体信息,其他个体往最优个体方向移动,使得种群逐步趋于最优。

      PSO算法把待优化的目标函数的解看作是搜索空间里的一个粒子,在搜索过程中,通过适应值来评价个体的优劣。每个个体的位置更新由其速度和距离决定。初始状态下,PSO中的个体随机分布在搜索空间内,通过迭代的方式搜索最优解。每次迭代时,个体在更新自己的位置之前,获取群体当前最优个体位置及本身历史最优位置,以此调整自己的飞行方向。随着迭代次数的增加,群体内的其他个体逐渐接近最优个体。当达到终止条件时,整个算法停止搜索,此时,群体内最优个体位置即是该算法得到的最优解。个体位置更新公式如下:

      其中:$x_{k}(t)$为个体k在第t次迭代时的位置;Vk(t)为该个体的速度;pk(t)为个体k搜索到的局部最优位置;G(t)为全局最优位置;w为惯性权重;c1c2表示加速常数;r1r2表示[0, 1]范围的均匀随机数[28]

    • 文献[25]对物种的多样性及雌雄个体之间繁殖后代时的择偶条件等进行了研究,本文以此作为划分粒子群算法的依据,把粒子群中的个体按照生物性别划分为两个群,即雄性子群和雌性子群,不同子群内的个体将执行不同的学习行为。

      定义1 (个体分群)。设M表示雌性,F表示雌性,I表示整个种群个体。对于$\forall i \in \rm{I}$,则有(gender(i)∈M)∧(gender(i)∈F)或者(gender(i) ∈F)∧(gender(i)$ \notin $M)成立。即,个体性别具有唯一性,任意一个个体,或者被划分到雄性子群,或者被划分到雌性子群,不能同时存在于两个不同子群。若整个种群内个体数为N,则雄性子群内个体数Nm=[N/2],雌性子群内个体数Nf=NNm。分群机制如图2所示。

      图  2  粒子分群机制

      Figure 2.  Grouping mechanism of particles

      受文献[26]中逆向学习行为启发,生物个体具有逆向学习能力,因此,RLPSO算法内个体除了正向学习之外,以一定概率进行逆向学习。

      定义2 (个体学习目标) 对于种群内的任意个体i,其搜索行为受学习目标个体影响。雄性个体的学习目标为雄性子群内最优个体Mb及雌性子群内最优个体Fb,而雌性个体的学习目标为雌性子群内最优个体Fb

      定义3 (个体学习方向) 对于种群内的任意个体i,不管是雄性个体还是雌性个体,都有正向学习行为和逆向学习行为两种模式。设μ(0<μ<1)为种群内个体的方向选择概率,rand为产生均匀分布随机数的函数。若rand>μ,个体选择逆向学习方向;反之,个体选择正向学习方向。在搜索空间内,个体搜索方式及学习方向的选择如图3所示。

      图  3  个体的搜索方式及学习方向

      Figure 3.  Search mode and learning direction of individual

      定义4(雄性个体搜索行为)由定义2可知,雄性个体选择个体MbFb作为学习目标,由定义3可知,个体有两种学习方向。从而有,当rand>μ时,个体根据式(7)进行更新位置;当rand≤μ时,个体根据式(8)进行更新位置。

      定义5(雌性个体搜索行为)由定义2可知,雌性个体只选择个体Fb作为学习目标,即学习目标单一性。雌性个体与雄性个体位置更新方式类似,当rand>μ时,个体根据式(9)进行更新位置;当rand≤μ时,个体根据式(10)进行更新位置。

      定义6(繁殖行为)种群内个体繁殖的目的在于通过产生更优的新生个体替换劣解个体,使得整个种群往更优趋势演化。对于每一轮迭代,任意选择一个雄性个体i,与此同时,个体i将等概率地从雌性子群中选择一个雌性个体j作为繁殖对象,通过繁殖操作,将有一个新的个体xnew产生, 繁殖行为如图4所示。

      图  4  种群内个体繁殖行为

      Figure 4.  Reproductive behavior of individual

      假设搜索空间内最小边界为Lb,最大边界为Ub,则新生个体在搜索空间中的位置计算公式如下:

      若新生个体的适应值fobejct(xnew)优于种群内最差个体fobejct(xworst),则淘汰最差个体xworst,并用新生个体xnew替换。反之,若新生个体适应值逊于最差个体,则抛弃新生个体。

      由式(11)可知,新生个体可在搜索空间内任一位置产生。对于具有多个极值的问题(即多峰问题),当算法收敛于某个非最优的极值点附近时,借助于新生个体在搜索空间的其他区域产生的方式,可加强算法跳出局部最优的能力。RLPSO算法的伪代码如下:

      Input:population size N,iterative number Gn, andparameter μ

      Output:The best fitness value and the best task sequence

      (1). Initialization;

      (2). Generate N individuals randomly;

      (3). Set the number of females equal to males;

      (4). Encoding initial task sequences;

      (5). For k=1 to Gn

      (6).  For i=1 to N

      (7).   If xi is a male individual

      (8).    If rand>μ

      (9).     Updating position by Eq. (8);

      (10).   Else

      (11).    Updating position by Eq. (9);

      (12).   End if

      (13).  If xi is a female individual

      (14).   If rand>μ

      (15).    Updating position by Eq. (10);

      (16).   Else

      (17).    Updating position by Eq. (11);

      (18).   End if

      (19).  End For

      (20).  Performing reproductive operation;

      (21). Recording the best fitness value and the best position of individual

      (22). End For

      (23). Decoding the best position;

      (24). Return

    • 式(7)~式(10)中$V_{k}(t+1)$$x_{k}(t+1)$是多维变量,每个维度之间相互独立,故可简化到一维进行证明,并且变量$c_{1} r_{1}$可表示成$K_{1}$, $c_{2} r_{2}$可表示成$K_{2}$

      引理1 当种群内个体往逆向方向学习时,其位置更新公式满足收敛性。

      证明

      式(8)和式(10)可简化为

      当式(12)中的K2Mb都等于0时,式(13)即为简化的式(9)。即通过式(13)来同时代表简化的式(7)和式(9)是合理的。

      根据动力系统理论,式(13)可重写为

      其中:${{y}}(t) = \left[ \begin{array}{l} {V_{id}}(t) \\ {X_{id}}(t) \\ \end{array} \right]$A为动力系统中的状态矩阵,其值为$\left[ {\begin{array}{*{20}{c}}w&{ - \theta }\\w&{1 - \theta }\end{array}} \right]$p为引导粒子往特定位置移动的外部输入;B为控制粒子动力外部效果的输入矩阵,其值为$\left[ \begin{array}{c} \theta \\ \theta \\ \end{array} \right]$

      若存在一个稳定值${{y}}^{*}$,对于任意的t,满足${{y}}^{*}(t+1)={{y}}^{*}(t)$,则${{y}}^{*}$可根据式(12)和式(13)计算得

      从动力学理论可知,其收敛性取决于状态矩阵A的特征值。

      其中,特征值为

      动力系统收敛的充分必要条件是$\left|\lambda_{1}\right|<1$$\left|\lambda_{2}\right|<1$,由$w>0$$c_{1} r_{1}>0$$c_{2} r_{2}>0$,可得$\left|\lambda_{1}\right|<1$$\left|\lambda_{2}\right|<1$。从而可证个体进行逆向学习时,其位置移动公式是收敛的。

      引理2 当种群内个体往正向方向学习,其位置更新公式满足收敛性。

      证明

      与引理1证明过程相似,其状态矩阵的特征值与式(17)相似,不同的是,$\theta $的负值即$\theta '$,如式(19)所示。

      动力系统收敛的充分必要条件是$\left| {{\lambda _1}^\prime } \right| < 1$$\left| {{\lambda _2}^\prime } \right| < 1$,由$w > 0$${c_1}{r_1} > 0$${c_2}{r_2} > 0$,可得$\left| {{\lambda _1}^\prime } \right| < 1$$\left| {{\lambda _2}^\prime } \right| < 1$,即成熟个体位置相斥移动公式是收敛的,从而可证个体进行逆向学习时,其位置移动公式是收敛的。

      定理1 RLPSO算法是收敛的。

      证明 根据引理1和引理2,可得RLPSO算法内所有个体的移动都将收敛于稳定状态点,即算法满足收敛性。

    • 采用云计算仿真通用平台CloudSim,仿真环境中,计算机的配置环境:操作系统为Windows 10, 内存16 GB,硬盘1TB。资源数量Rn为50, 任务数量Tn分别为100、500、1 000。将RLPSO算法分别与闪电搜索算法(LSA)、粒子群算法(PSO)、遗传算法(GA)、蚁群算法(ACO)4个经典智能优化算法进行比较。5种优化算法的种群规模都为50,迭代次数为200,每个算法分别运行25次。其余参数设置为:(1)PSO算法,惯性权重因子w=1.0,c1c2取值为2.0[29];(2)LSA的通道时间设置为10[30];(3)ACO算法的信息素因子为1.0×10−6、启发函数因子为0.9、信息素挥发因子为0.5、信息素常数为20[31];(4)GA算法的交叉概率为0.65,变异概率为0.01[32];(5)为了比较RLPSO与传统的PSO的性能,RLPSO的参数wc1c2设置与PSO的相同。此外,RLPSO的方向选择概率μ设为0.6。为了客观评价本文算法的性能,采用两个非参数统计技术(Wilcoxon's Test和Friedman Test)对5种算法得到的数据进行性能分析,显著性水平为0.05[33]

    • 经典PSO有3个参数(wc1c2),而RLPSO比经典PSO多一个参数(即方向选择概率μ)。RLPSO中wc1c2的设置与文献[29]相同,因此,本文只对参数μ进行择优。选用8个基准测试函数作为案例。为了尽量覆盖不同属性的基准测试函数,选择了4个单模函数(f1~f4)和4个多模函数(f5~f8),即不同属性的测试函数各占一半。这些基准测试函数的详细描述如表1所示。图5示出了8个基准测试函数在三维空间的分布。从图中可以看到,单模函数只有一个最小值,而多模函数有多个极值。

      NameEquationBoundMinimumD
      Sphere${f_1}(x) = \displaystyle\sum\limits_{i = 1}^D {x_i^2} $[−100, 100]030
      Schwefel 1.2${f_2}(x) = \displaystyle\sum\limits_{i = 1}^D {{{\left(\sum\limits_{j = 1}^i {{x_j}} \right)}^2}} $[−100, 100]030
      Rosenbrock${f_3}(x) = \displaystyle\sum\limits_{i = 1}^{D - 1} {[100{{({x_{i + 1}} - x_i^2)}^2} + {{({x_i} - 1)}^2}]} $[−30, 30]030
      Sum of Squares${f_4}(x) = \displaystyle\sum\limits_{i = 1}^D {i \cdot x} _i^2$[−10, 10]030
      Rastrigin${f_5}(x) = \displaystyle\sum\limits_{i = 1}^D {[x_i^2 - 10 \cos (2{\text{π}} {x_i}) + 10]} $[−5.12, 5.12]030
      F4${f_6}(x) = 418.982\; 9 D + \displaystyle\sum\limits_{i = 1}^D {( - {x_i}\sin (\sqrt {\left| {{x_i}} \right|} ))} $[−100, 100]030
      Ackley$\begin{aligned} {f_7}(x) =& - 20\exp \left( - 0.2\sqrt {\displaystyle\frac{1}{D} \displaystyle\sum\limits_{i = 1}^D {x_i^2} } \right) -\\& \exp \left[\displaystyle\frac{1}{D} \sum\limits_{i = 1}^D {\cos (2{\text{π}} {x_i})} \right] + 20 + \exp (1) \\ \end{aligned} $[−32, 32]030
      Griewank${f_8}(x) = \displaystyle\frac{1}{{4\; 000}}\displaystyle\sum\limits_{i = 1}^D {x_i^2 - \prod\limits_{i = 1}^D {\cos \left(\displaystyle\frac{{{x_i}}}{{\sqrt i }}\right) + 1} } $[−600, 600]030

      表 1  基准测试函数

      Table 1.  Benchmark functions

      图  5  基准测试函数三维空间分布图

      Figure 5.  Visualization of benchmark functions in three-dimensional space

      由定义3可知,RLPSO的方向选择概率μ的取值范围为(0,1),因此,在参数择优过程中,把μ分别设成0.1~0.9(间隔大小为0.1)。对于每个不同的μ,RLPSO在基准测试函数上得到的目标函数值如表2所示。可以看到,当μ=0.6时,RLPSO在f1f3f4f5f6f8 6个函数上表现出最佳性能。对于f2函数,μ=0.7时RLPSO搜索到最优值为3.04×10−2,而μ=0.6时RLPSO得到的最优值为3.47 ×10−2,只比3.04 ×10−2稍微逊色一点。对于f7函数,μ=0.5时结果最好,μ=0.6次之。由于μ=0.6时在大部分函数上都能得到最优结果,表明在该参数值下,RLPSO的搜索性能最好,因此,本文将参数μ设成0.6。

      μf1f2f3f4
      MeanStdMeanStdMeanStdMeanStd
      0.19.92×10−11.53×10−24.75×10−14.61×10−22.38×1026.50×1019.76×1013.87
      0.27.38×10−12.35×10−21.72×10−15.26×10−21.94×1027.16×1015.01×1014.27
      0.34.81×10−19.62×10−26.50×10−29.19×10−31.65×1022.96×1011.28×1017.52
      0.45.73×10−22.87×10−34.27×10−23.40×10−31.02×1025.84×1019.392.18×10−1
      0.51.68×10−21.12×10−33.91×10−25.18×10−36.42×1012.57×1014.889.01×10−1
      0.61.59×10−33.87×10−43.47×10−22.31×10−33.57×1011.082.241.43×10−1
      0.74.92×10−38.72×10−43.04×10−21.97×10−34.29×1018.514.13×1015.65
      0.87.16×10−23.22×10−33.68×10−29.85×10−35.85×1013.426.74×1012.91
      0.93.24×10−21.53×10−38.95×10−25.72×10−36.91×1015.387.15×1012.62
      μf5f6f7f8
      MeanStdMeanStdMeanStdMeanStd
      0.18.25×1023.52×1012.36×10−15.67×10−21.92×1013.209.351.71×10−1
      0.27.93×1029.51×1011.45×10−12.38×10−21.07×1019.891.147.93×10−1
      0.36.04×1028.97×1018.28×10−24.12×10−35.331.85×10−17.80×10−16.24×10−2
      0.41.13×1021.37×1016.17×10−25.50×10−39.65×10−14.01×10−24.54×10−11.97×10−2
      0.59.18×1014.035.09×10−28.11×10−33.42×10−11.70×10−27.26×10−25.41×10−2
      0.66.62×1012.824.85×10−22.36×10−38.04×10−15.62×10−21.09×10−22.53×10−3
      0.78.49×1013.515.63×10−26.70×10−32.161.37×10−15.18×10−22.99×10−3
      0.82.71×1024.50×1017.04×10−23.64×10−34.987.45×10−19.24×10−28.37×10−3
      0.95.25×1029.43×1012.59×10−17.23×10−26.209.13×10−13.48×10−13.25×10−2

      表 2  不同的μ取值时RLPSO算法的目标函数值

      Table 2.  Objective function values of RLPSO algorothm with different μ

    • 图5(a)所示任务数为100时5种优化算法的总任务完成时间收敛曲线。从图中可以看到,在50次迭代时RLPSO搜索到的值已经优于其他4个优化算法,直到200次迭代RLPSO都表现出了最优的搜索性能,此时搜索到的最优值为12.36 s。在50~200迭代区间,LSA算法仅次于RLPSO。ACO在100次迭代之后处于收敛状态,无法搜索到更优值,搜索曲线为直线状态,此时搜索到的最优值为19.05 s。此时PSO搜索精度在微细提高,然而搜索到的最优值逊于ACO。GA算法在50~100次迭代范围内无法搜索到更优值,搜索曲线为直线,100~150次迭代时搜索到一次更优值(29.41 s)之后,其搜索精度再也没有发生变化。可以看出,在任务数为100的条件下,5种算法搜索性能按先后次序排名为:RLPSO、LSA、ACO、PSO、GA。

      当任务数为500时,5种优化算法的总任务完成时间收敛曲线如图5(b)所示。由于任务数比较大,在50次迭代时,5种算法的搜索曲线已经表现出比较明显的区别,此时算法搜索到的最优值分别为:RLPSO为62.88 s,LSA为82.37 s,PSO为102.33 s,ACO为105.64 s,GA为134.10 s。在50次迭代之后,RLPSO基本处于收敛状态,当迭代次数为200时,其搜索到的最优值为62.50 s,与其他4个优化算法相比,RLPSO呈现出的是快速收敛的能力。LSA算法搜索性能次于RLPSO,其搜索曲线在100次迭代之后接近于收敛状态。PSO和ACO在整个迭代区间的搜索性能都比较接近,直到迭代结束时,PSO搜索到的最优值为88.97 s,而ACO搜索到的最优值为96.18 s。GA算法50~200次搜索到的最优值都逊于其他4个算法,当迭代结束时,其搜索到的最优值为108.93 s。在任务数为500的条件下,5种算法的搜索性能按先后次序排名为: RLPSO、LSA、PSO、ACO、GA。

      图5(c)可以看到,当任务数增加到1 000时,RLPSO的寻优效果最好,搜索到的总任务完成时间为149.34 s。在经过150次迭代之后,LSA、PSO、ACO、GA算法基本处于早熟收敛状态,而RLPSO的寻优曲线还在略微变化,即随着迭代次数的增加,其搜索到更优的值。5个算法中,GA算法的寻优效果最差,在迭代次数为100时,无法再搜索到更优值,并进入收敛状态,此时,GA搜索到总任务完成时间为217.19 s,约为RLPSO搜索到的值的1.5倍。在任务数为1 000时,5种算法的搜索性能按先后次序排名为: RLPSO、LSA、PSO、ACO、GA。

      图6可知,任务数为100、500、1 000时,RLPSO具有最优的寻优效果,特别是任务数为1 000时,RLPSO明显优于其他4个对比算法。

      图  6  5种算法在不同任务数下的收敛曲线

      Figure 6.  Convergence curves of five algorithms under different number of tasks

      表3为3种不同任务数条件下,5种算法得到的数据结果。可以看出,RLPSO比其他算法能搜索到更优的结果。图7示出了3种不同任务数时总任务完成时间的柱状图,从图中可以直观看到,在Tn=100时,RLPSO搜索到的总任务完成时间最小,LSA次之,GA总任务完成时间最大。在Tn=500和Tn=1 000时,依然是RLPSO的总任务完成时间最小,GA的总任务完成时间最大。

      图  7  3种不同任务数的完成时间

      Figure 7.  Completion time of five algorithms on three different number of tasks

      AlgorithmCompletion time
      Tn=100Tn=500Tn=1 000
      RLPSOBest11.5460.95145.42
      Worst13.1863.82158.17
      Mean12.3662.50149.34
      Std2.451.9812.63
      GABest28.07106.04195.11
      Worst30.25110.52224.62
      Mean29.41108.93217.19
      Std5.369.8420.04
      ACOBest17.9493.26183.06
      Worst20.8798.41208.48
      Mean19.0596.18195.13
      Std4.273.3114.71
      LSABest15.1368.32151.35
      Worst17.5873.44174.20
      Mean16.2470.61166.12
      Std3.483.8718.47
      PSOBest20.2486.71169.21
      Worst22.6590.12198.34
      Mean21.7988.97181.72
      Std3.224.2616.05

      表 3  3种不同任务数的完成时间

      Table 3.  Completion time of five algorithms under the different number of tasks

      RLPSO算法与4个对比算法的Wilcoxon's Test结果如表4所示。从该表中可以看到p值都小于显著性值(0.05),即RLPSO显著优于4个对比算法。表5给出了5个算法的Friedman Test结果,在任务数分别为100、500、1 000时,RLPSO的排名值都是1.00,结果表明本文算法性能最好。

      Algorithmp
      Tn =100Tn =500Tn =1 000
      RLPSO
      GA2.46×10−22.51×10−22.49×10−2
      ACO1.38×10−21.44×10−21.26×10−2
      LSA4.52×10−24.60×10−24.85×10−2
      PSO2.95×10−22.87×10−23.18×10−2

      表 4  5个优化算法Wilcoxon's test的p值

      Table 4.  p-values of Wilcoxon's test of five algorithms

      TnRLPSOGAACOLSAPSO
      1001.003.504.752.253.50
      5001.005.003.252.253.50
      1 0001.005.004.002.252.75

      表 5  5个优化算法的Friedman test排名结果

      Table 5.  Ranking results of Friedman test of five algorithms

      从以上实验结果图分析得到,应用RLPSO算法进行任务调度,可以搜索明显更小的总任务完成时间,从而表明RLPSO算法是一种云计算环境下的有效任务调度算法。

    • 本文提出的RLPSO算法,通过对粒子进行群划分,引入逆向学习行为,并设计繁殖行为,从而提升整个算法的全局搜索能力和局部搜索能力。在云计算环境下,RLPSO算法在任务数分别为100、500、1 000的条件下进行了优化性能测试。实验仿真结果表明,与4个传统优化算法(即GA、PSO、ACO、LSA)相比,本文的算法具有更优的寻优性能,并且能明显提高对总任务调度时间寻优的效率。目前大部分的优化算法,其灵感主要来源于自然界中的动物生存或植物生长行为。下一步工作将在此改进的粒子群算法的基础上引入粒子竞争行为,从而使得优化算法不再是简单的模拟自然界中存在的现象,而是丰富算法的内部机制,以此形成更具有智能性的优化算法;设计并行计算结构,使得算法在求解大规模问题时能加快计算速度;把改进的算法应用于解决实际问题。

(7)  表(5) 参考文献 (34) 相关文章 (20)

目录

    /

    返回文章