混合粒子群算法和爬山算法优化云环境下任务调度

⃝=⃝可在www.sciencedirect.com上在线ScienceDirectICT Express 4（2018）199www.elsevier.com/locate/icte一种混合粒子群算法和爬山算法在云环境Negar Dordaie，Nima JafariNavimipour伊朗大不里士伊斯兰阿扎德大学大不里士分校计算机工程系接收日期：2017年3月12日;接收日期：2017年6月7日;接受日期：2017年8月3日2017年9月20日在线发布摘要任务调度是异构环境中要求高效率的重要问题之一由于任务调度问题是一个NP难问题，许多进化算法被用来解决这个问题。由于基于种群的算法的解的收敛速度慢，它们与局部搜索算法相结合因此，本文提出了一种混合粒子群算法和爬山算法来优化任务调度的最大完工时间在随机和科学有向无环图（DAG）上的实验结果表明，与现有的启发式算法和粒子群优化算法相比，该算法在最大完工时间上具有更好的性能.c2017年韩国通信与信息科学研究所（KICS）。Elsevier B.V.的出版服务。这是一个开放获取CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：云计算;有向无环图;爬山法;粒子群算法;任务调度1. 介绍云计算是一种流行的平台，用于商业资源供应，并允许消费者使用多个服务提供商来利用计算资源[1在分布式环境中提供具有高可扩展性和可用性的按需服务是云背后的主要思想[4在云环境中，用户付出的代价是这与他们所能负担的预算有关[7云由各种资源和服务组成，如存储，处理，内存和虚拟机[12任务调度问题是一个NP难问题[16因此，许多启发式算法被提出来获得相对最优的解。然而，它们可能会陷入局部最优。为了解决这个问题，元启发式技术被用来解决调度问题[19]。最近，进化算法（EAs），即，粒子群算法（Particle Swarm）*通讯作者。电子邮件地址：jafari@iaut.ac.ir（新泽西州）Navimipour）。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2017.08.001优化（PSO）与局部搜索算法（如爬山）相结合，以加速搜索功能[20]。该算法的目的是通过最大化并行化来优化最大完工时间。该算法首先随机产生初始种群。然后，粒子群算法和局部搜索算子被用来优化解决方案。2. 该方法本节介绍了所提出的算法。首先，描述了所使用的应用程序和系统模型。然后，混合PSO爬山的阶段描绘。最后给出了一个算例2.1. 应用程序和系统模型应用程序被分解为子任务，如G（V， E）所示。V表示子任务，E表示子任务之间的依赖关系[21]。有向无环图（DAG）上的任务之间的关系被标记为通信成本，如图1所示。每个任务都必须执行 在一个资源上，所有任务都必须执行。子任务t02405-9595/c2017韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。i（xi（ t）+vi（t+1）北纬200度。新泽西州多尔代 Navimipour/ICT Express 4（2018）199-202图二. 粒子的结构表1Fig. 1. 有11个子任务的DAG。(1) 粒子群优化阶段PSO由Kennedy和Eberhart提出[23]。该算法的灵感来自鸟和鱼的群集模型[24我们使用PSO算法作为初始种群技术的第一阶段。初始种群由随机解生成，其中每个候选解被称为粒子[27]。颗粒的结构如图2所示。在每次迭代中，每个粒子的下一个位置使用两个参数确定：最佳位置[命名为个人最佳（pbest）]，粒子在其探索期间具有;以及粒子在所有粒子中的最佳位置，由全局最佳（gbest）显示。每个的下一个位置图中子任务的计算成本。1 .一、粒子由Eq. （1）Eq.其中vi（t）是质点i在时间单位t内的速度。w被称为C1和C2是正加速常数，分别用于衡量认知和社会成分的贡献[28]。此外，r1和r2是在0和1之间选择的两个随机变量。项xi（t）表示粒子i在时间t的位置。该技术的PSO阶段如算法3所示。vi（t+1）=w.vi（t）+c1r1（pbest（ t）−xi（ t））（1）Xt+1 =+c2r2（gbest（ t）−xi（ t））（2）表示入口节点，t9表示出口节点。表1列出了子任务的计算成本。在表1中，P表示资源，w是计算成本的平均值。2.2. 混合PSO-爬山算法该算法首先用粒子群算法随机初始化种群。然后，使用算法2通过异构最早完成时间（HEFT）处理器映射方法[22]对每个粒子进行评估和排序。然后将爬山算法应用于一些选定的粒子。所提出的算法被重复，直到终止条件得到满足。所提出的算法的主要功能在算法1中描述。(2) 爬坡阶段在基于种群的进化算法中，解的收敛速度较慢。为此，它们与本地搜索算法合作。因此，为了优化解决方案，在使用PSO优化算法之后，使用爬山技术[29]。(3) 终止条件进化算法中的复杂问题必须在某个点停止。因此，我们需要故意停止生命周期过程[30]。该算法在50代之后或当粒子的精细度连续10代不改变时终止。）任务均p0p1p2W的t091089t112111312t21581011t361088t415131113t5791410t613171515t712101412t818131716的t971078N. Dordaie，N.J. Navimipour / ICT Express 4（2018）199-202201图三. 50个不同的随机DAG的跨度（子任务= 20，资源数量= 8，PopSize =100）3. 实验结果在这一节中，所提出的算法的行为的最大完工时间进行了分析。根据工作负载的类型，应用程序是不同的，为了公平地比较所提出的算法与PSO [31]和HEFT-B算法。该算法在C#和云Azure环境下进行了仿真3.1. 随机生成的应用程序图为了评估不同的应用程序，根据工作[32]生成DAG。在不同的子任务数下，我们将所提出的算法与现有的算法进行了比较.随机DAG中生成的子任务的数量被选择为20、50和100个子任务。图3显示了通过HEFT-B、PSO和所提出的算法从调度算法获得的具有20个子任务的50个不同随机生成的DAG的最大完工时间。实验结果表明，该算法的性能优于传统的混合算法.为了在具有50个子任务的图上运行算法，算法被调度用于50个不同的随机生成的DAG。从图4中得到的结果表明，在这种情况下，所提出的算法在最大完工时间方面优于HEFT-B和PSO算法。图5显示了PSO和所提出的算法的执行时间。实验结果表明，该方法比HEFT-B和PSO算法更有效3.2. 科学工作流程的实验结果此外，所提出的算法的最大完工时间的科学表观基因组学工作流应用程序获得和评估见图4。50个不同随机DAG的跨度（子任务= 100，资源数量=8，PopSize= 100）图五. 假设图的迭代算法。其他算法。表观基因组学工作流程应用程序计划有20、24、46和100个节点。工作流从Pegasus工作流生成器获得。图6给出了调度算法的最大完工时间结果。在所有由不同节点组成的图中，结果表明，该算法在最大完工时间方面优化了上述算法。1 https：//confluence。我们的国家。伊斯岛edu/display/394pegas/WorkflowGenerator。北纬202号新泽西州多尔代 Navimipour/ICT Express 4（2018）199-202见图6。表观基因组学（Epigenomics）4. 结论和未来趋势所提出的技术采用PSO以及局部搜索算法，即，爬山，将子任务分配给可用资源。通过对不同规模和不同科学工作流程的随机DAG的实验结果表明，该混合算法在最大完工时间方面明显优于启发式HEFT-B和PSO算法.在未来，我们将测试所提出的算法在更多的现实世界的DAG考虑负载均衡的资源。引用[1] W.- C.金河，澳-地Jo，大型云系统计算实例的成本优化配置，ICTExpress。[2] S. Asghari，N. Jafari Navimipour，使用反向蚁群优化算法的云服务组合，Int. J. Bio-Inspired Comput. （2017年）。[3] F. Aznoli，N.J. Navimipour，云服务推荐：回顾最近的进展并提出未来的研究方向，J。网络Comput. 77（2017）73-86。[4] B. Rimini，A.Jukan，D.Katsaros，Y.Goeleven，云计算系统的架构要求：企业云方法，J.网格计算。9（2011）3-26。[5] R. 哈吉扎德Navimipour，一种在云环境中使用行为图和服务分组进行信任评估的方法，Kybernetes（2017）。[6] S. Hazratzadeh，N. Jafari Navimipour，使用特征矩阵的专家云中的同事推荐系统，Kybernetes（2017）。[7] L. 曾 湾 ， 澳 - 地 Veeravalli ， X.Li， SABA ： A security-aware andautomatic-awareworkflow scheduling strategy in clouds ， J. ParallelDistrib. Comput. 75（2015）141-151。[8] A.S. Milani，N.J. Navimipour，云环境中的负载平衡机制和技术：系统文献综述和未来趋势，J. Netw。Comput. Appl. （2016年）。[9] S.Z. Mohammadi，J.N. Navimipour，使用支持向量机识别无效云提供商，Int. J. 下一代。Comput. （2017年）。[10] F.谢科莱斯拉米Navimipour，基于拥挤距离的多目标粒子群优化算法在云环境中的服务分配，Swarm Evol. Comput. （2017年）。[11] S. Tabagchi Milan，N. Jafari Navimipour，《自然》启发了解决云中负载平衡问题的元计算算法环境：系统性文献综述和未来趋势，J. Netw。系统管理。（2017年）。[12] N. Jafari Navimipour，A. Habibizad Navin，A.M. Rahmani，M.Hosseinzadeh，基于云的框架的行为建模和自动验证，以共享人力资源的知识和技能，Comput。Ind.68（2015）65[13] P. Fouladi，J.N. Navimipour，使用质量控制标准的基于云的知识共享框架中的人力资源排名，Kybernetes 46（2017）。[14] B.A. Milani，N.J. Navimipour，《云环境中数据复制技术的全面回顾：主要趋势和未来方向》，J. Netw。Comput. Appl·64（2016）229-238。[15] 新泽西Navimipour，专家云中可信赖人力资源发现机制的规范和验证的正式方法，专家系统应用42（2015）6112-6131。[16] M. Ashouraie，N. Jafari Navimipour，基于优先级的专家云异构资源任务调度，Kybernetes 44（2015）1455-1471。[17] P. Azad，J.N. Navimipour，使用混合文化和蚁群优化算法的云计算中的能量感知任务调度，Int. J. Cloud Appl. Comput. 7（2017）。[18] N.J. Navimipour，F.S. Milani，基于布谷鸟搜索算法的云计算任务调度，Int.J.Model。44.第44条。[19] M. Akbari，H. Rashidi，一种基于布谷鸟优化的多目标调度算法，用于异构系统中编译时的任务分配问题，专家系统应用60（2016）234-248。[20] S. Padmavathi，S. MohitGolchha，A. SeeniMohamed，基于Memetic算法的概率局部搜索任务调度，在：B.K. 帕尼格拉希，S. Das ，P.N. 苏甘丹峰Nanda （Eds. ），Swarm，Evolutionary ，andMemetic Computing：Third International Conference，SEMCCO2012，Bhubaneswar，India，December（2012）20-22 Proceedings，SpringerBerlin Heidelberg，Berlin，Heidelberg，2012. 224-231[21] Z.唐湖，澳-地齐，Z. Cheng，K. Li，S. Khan，K. Li，一种支持DVFS的云环境中的节能任务调度算法，J. GridComput.（2015）1-20。[22] H. Topcuoglu，S. Hariri，W.李敏友，异构计算中的性能有效和低复杂度任务调度，IEEE Trans. 平行分布13（2002）260-274。[23] 肯 尼 迪 河 王 文 ， 粒 子 群 算 法 ， 高 等 教 育 出 版 社 ， 1995.Proceedings，IEEE International Conference on，vol. 4，1995，pp.1942-1948年。[24] S.N. Sivanandam，S.N. Deepa，Introduction to Genetic Algorithms，Springer，Berlin; New York，2007。[25] A. Mahor，S. 应用自适应惯性权重粒子群算法求解梯级水电站短期发电调度问题。J. 电力能源系统34（2012）1-9。[26] S.莫汉蒂A. Mishra，B.K. Nanda，B.C. Kazara，使用响应曲面法和粒子群优化的AlSiCp纳米粉末混合电火花加工的多目标参数优化，Alexandria Eng. J.[27] F.马里尼湾Walczak，粒子群优化（PSO）。教程，化学计量学和智能实验室系统，2015。[28] A.P. Engelbrecht ， Computational Intelligence ： An Introduction ，WileyPublishing，2007。[29] B. Keshanchi，N. Jafari Navimipour，基于优先级的云计算环境中的任务调度使用模因算法，J。电路系统Comput. （2015年）。[30] B. Ong，M.福岛，自动终止和搜索空间旋转的遗传算法，模因计算。3（2011）111-127。[31] D.S.P. Kumari，K.王文，王文，王文，等.基于遗传算法和多目标粒子群算法的云计算任务调度.北京：计算机科学出版社，2000，21（1）：117 - 118. Hum. 7（2017）1260-1271。[32] B. Keshanchi，A.新泽西州苏里Navimipour，一种改进的遗传算法在云环境中使用优先级队列进行任务调度：形式验证，模拟和统计测试，J。系统软件 124（2017）1-21.