云环境下基于DPSO的任务调度算法

云计算环境下的并行计算与任务调度第一章：引言云计算作为一种新兴的计算模式，已经广泛应用于各个领域。

云计算环境为用户提供了强大的计算和存储资源，使得并行计算成为可能。

而在云计算环境下，如何进行合理的任务调度和并行计算，是提高计算效率和资源利用率的关键。

本文将探讨云计算环境下的并行计算与任务调度的问题，并提出一些解决方案。

第二章：云计算环境下的并行计算在云计算环境下，由于云服务提供商通常拥有庞大的计算和存储资源，可以为用户提供高性能的并行计算服务。

并行计算是指将一个大问题划分成若干个小问题，通过同时处理这些小问题来提高计算效率。

在云计算环境下，用户可以通过虚拟机实例或容器来创建并行计算任务，并通过云服务提供商提供的调度系统来管理和执行这些任务。

并行计算的核心是任务的划分和调度。

任务划分是将一个大的计算任务划分成若干个小任务，每个小任务可以由一个或多个计算节点并行执行。

任务调度是将这些小任务分配给可用的计算节点，以实现最佳的性能和资源利用率。

在云计算环境下，由于计算和存储资源的虚拟化和动态分配的特点，任务调度变得更为复杂。

第三章：云计算环境下的任务调度算法在云计算环境下，有许多任务调度算法可供选择。

常用的任务调度算法包括最小任务时间（Minimum Task Time，MTT）、最早完成时间（Earliest Finish Time，EFT）、最小平均完成时间（Minimum Mean Finish Time，MMFT）等。

这些算法主要根据任务的属性（如任务的计算量、输入输出数据的大小等）来进行调度决策。

另外，还有一些优化的任务调度算法，如遗传算法、蚁群算法等。

这些算法通常采用启发式的方法，通过模拟生物的行为或人的思维方式来寻找最优解。

这些算法可以有效地提高任务调度的性能和效率。

第四章：云计算环境下的并行计算框架在云计算环境下，为了更好地支持并行计算，还涌现出了一些并行计算框架。

其中最著名的是Apache Hadoop和Apache Spark。

云计算环境下的网络资源调度算法云计算作为一种高效、灵活的计算模式，已经广泛应用于各个领域。

在云计算环境下，网络资源调度算法的优化是提高系统性能和资源利用率的关键。

本文将介绍云计算环境下常用的网络资源调度算法，并讨论它们的优点和缺点。

一、任务调度算法在云计算环境下，任务调度是一项复杂而关键的任务。

任务调度算法的主要目标是实现任务的高效执行和资源的均衡利用。

目前常用的任务调度算法包括负载均衡调度算法、遗传算法和蚁群算法等。

1. 负载均衡调度算法负载均衡调度算法旨在实现任务在云计算环境下的均衡分配。

它通过监测和评估服务器的负载情况，将任务分配给负载较低的服务器，以实现资源的合理利用。

常用的负载均衡调度算法有轮询算法、最短作业优先算法和最小连接数算法。

轮询算法按照服务器的顺序依次分配任务，实现了资源的均衡分配。

最短作业优先算法将任务分配给需要最少时间的服务器，以减少任务的执行时间。

最小连接数算法则根据服务器当前的连接数来进行任务分配，以实现连接数的均衡。

2. 遗传算法遗传算法是一种模拟自然进化过程的优化算法。

在任务调度中，遗传算法通过定义任务分配的染色体编码和适应度函数来进行任务调度的优化。

遗传算法的优点是可以在复杂的环境下找到较优解，但其缺点是算法的计算复杂度较高，对较大规模的任务调度问题不一定适用。

3. 蚁群算法蚁群算法是模拟蚂蚁觅食行为的一种启发式算法，通过蚂蚁在环境中寻找最优路径来进行任务调度。

蚁群算法的优点是可以在不完全信息的情况下找到相对较优解，并且具有较好的鲁棒性。

但其缺点是算法的收敛速度较慢，需要较长时间来得到较优的结果。

二、资源分配算法在云计算环境下，资源分配算法的目标是实现用户请求的高效响应和资源的合理利用。

常用的资源分配算法包括最大最小公平算法、权重平衡算法和动态调整算法等。

1. 最大最小公平算法最大最小公平算法是一种基于公平性原则的资源分配算法。

它通过将资源分配给当前需求最大的用户，以满足用户的需求，并保证资源的合理分配。

2022年5月第43卷 第5期计算机工程与设计C OM P U T E RE N G I N E E R I N G A N DDE S I G NM a y2022V o l .43 N o .5云环境下改进S O S 的多目标任务调度算法陈 艺1,江芝蒙2,张 渝3(1.四川文理学院智能制造学院,四川达州635000;2.四川文理学院信息化建设与服务中心,四川达州635000;3.西南大学计算机与信息科学学院,重庆400715)摘 要:为有效获取云计算中多目标任务调度求解算法的全局最优解,提出一种云环境下基于改进期望服务质量(Q o S )的多目标任务调度算法㊂设计多目标任务调度框架,提出相应的目标函数与约束条件㊂利用准反射学习构建初始种群以改进共生生物搜索(S O S )算法,加入自适应变异率以提高全局搜索能力㊂通过设定坐标进行任务分配,利用改进后S O S 算法实现多目标任务优化调度㊂云计算仿真结果表明,所提算法相比于其它算法,有效改善了能源利用率㊁能耗和时间成本,具有较好的Q o S 传输性能㊂关键词:云环境;多目标任务调度;改进S O S 算法;准反射学习;自适应变异率;云计算仿真软件中图法分类号:T P 391 文献标识号:A 文章编号:1000-7024(2022)05-1214-10d o i :10.16208/j.i s s n 1000-7024.2022.05.003收稿日期:2020-09-29;修订日期:2021-03-31基金项目:重庆市科委科技计划基金项目(c s t c 2018j s c x -m s yb X 0089)作者简介:陈艺(1980),女,四川平昌人,硕士,副研究员,研究方向为计算机应用㊁大数据等;江芝蒙(1981),男,四川达州人,硕士,实验师,研究方向为计算机应用㊁大数据㊁云计算;张渝(1979),男,重庆人,博士,副教授,研究方向为人工智能㊁软件工程㊁通信网络㊂E -m a i l :v i v i yi c h e n @126.c o m M u l t i o b j e c t i v e t a s ks c h e d u l i n g a l g o r i t h mb a s e do n i m pr o v e dS O S i n c l o u d e n v i r o n m e n tC H E N Y i 1,J I A N GZ h i -m e n g 2,Z H A N G Y u 3(1.S c h o o l o f I n t e l l i g e n tM a n u f a c t u r i n g ,S i c h u a nU n i v e r s i t y o fA r t s a n dS c i e n c e ,D a z h o u635000,C h i n a ;2.C e n t e r o f I n f o r m a t i o nC o n s t r u c t i o na n dS e r v i c e ,S i c h u a nU n i v e r s i t y o fA r t s a n dS c i e n c e ,D a z h o u635000,C h i n a ;3.S c h o o l o fC o m p u t e r a n d I n f o r m a t i o nS c i e n c e ,S o u t h w e s tU n i v e r s i t y ,C h o n g q i n g 400715,C h i n a )A b s t r a c t :T o e f f e c t i v e l y o b t a i n t h e g l o b a l o p t i m a l s o l u t i o no f t h em u l t i -o b j e c t i v e t a s k s c h e d u l i n g a l g o r i t h mi n c l o u d c o m p u t i n g ,a m u l t i -o b j e c t i v e t a s k s c h e d u l i n g a l g o r i t h m b a s e do n i m p r o v e de x p e c t e d q u a l i t y of s e r v i c e (Q o S )i nc l o u de n v i r o n m e n tw a s p r o -p o s e d .A m u l t i -o b j e c t i v e t a s k s c h e d u l i ng f r a m e w o r kw a s d e s i g n e d ,a n d th e c o r r e s p o n di n g o bj e c t i v e f u n c t i o n a n d c o n s t r a i n t c o n d i -t i o n sw e r e p r o p o s e d .T h e q u a s i -r e f l e c t i o n l e a r n i n g w a su s e d t oc o n s t r u c t t h e i n i t i a l p o p u l a t i o n t o i m p r o v e t h eS ym b i o s i sS e a r c h (S O S )a l g o r i t h m ,a n d t h e a d a p t i v em u t a t i o n r a t ew a s a d d e d t o i m p r o v e t h e g l o b a l s e a r c h a b i l i t y .T h e t a s kw a s a l l o c a t e db y s e t -t i n g t h e c o o r d i n a t e s ,a n d t h e o p t i m i z e dS O Sa l g o r i t h m w a s u s e d t o r e a l i z e t h e o p t i m a l s c h e d u l i n g o fm u l t i -o b j e c t i v e t a s k s .C l o u d c o m p u t i n g s i m u l a t i o ne x p e r i m e n t r e s u l t s s h o wt h a t c o m p a r e dw i t h o t h e r a l g o r i t h m s ,t h e p r o p o s e d a l g o r i t h me f f e c t i v e l y i m p r o v e s e n e r g y u t i l i z a t i o n ,r e d u c e e n e r g y c o n s u m p t i o na n d t i m e c o s t ,a n dh a s b e t t e rQ o S t r a n s m i s s i o n p e r f o r m a n c e .K e y wo r d s :c l o u de n v i r o n m e n t ;m u l t i -o b j e c t i v et a s ks c h e d u l i n g ;i m p r o v e dS O Sa l g o r i t h m ;q u a s i r e f l e c t i o nl e a r n i n g ;a d a p t i v e m u t a t i o n r a t e ;C l o u d S i m0 引 言分布式计算是当前信息技术领域最具影响力的发展方向,将并行的思想和技术连接起来,为个人计算机和其它机器提供资源㊁设备㊁软件和数据等内容的实时共享[1]㊂但云计算普遍都面临安全问题,在云设置中存在巨大挑战,尽管该领域已有部分研究,但任务规划仍然有较大改善空间[2]㊂任务规划算法效率的提高有助于提升系统的整体效率,以便提供更好的服务质量㊂任务规划应侧重于在适当的框第43卷第5期陈艺,江芝蒙,张渝:云环境下改进S O S的多目标任务调度算法架中对计算任务进行合理的规划,使计算资源最大化利用的情况下完成计算任务[3]㊂多目标任务调度优化旨在构建出一个用于指导任务分配的分配表[4]㊂近年来,在操作系统进程与线程之间㊁流水作业之间和工业生产环境之间或者是在分布式计算系统中的任务调度中多目标调度技术都是值得进行探究的方向[5,6]㊂因此,数值计算对于确定最优解来规划云计算中各种功能而言至关重要㊂在云计算模型中大规模问题实例带来的巨大搜索空间,现有多目标任务调度方法容易陷入局部最优解,无法快速有效地获得全局最优解[7]㊂因此,提出了一种云环境下基于改进S O S的多目标任务调度算法㊂首先对目前云环境下多目标任务调度算法的研究现状进行了分析,然后提出多目标任务调度算法整体架构,分析了调度算法框架和目标函数;再者介绍共生生物搜索算法的各个阶段,对于任务调度给出了相应的改进方案,最后进行实验分析,论证所提算法的可行性㊂1相关研究对于云环境下多任务流多目标优化调度,一般的启发式算法㊁元启发式算法㊁博弈论调度以及帕累托优化等方法都是被广泛使用的优化算法,并且在相关研究中已取得了一定的进展[8]㊂由于启发式方法依赖于一个特定问题域的信息学习的特性,通常被用来制定针对特定类型问题的解决方案[9]㊂通过对启发式算法进行改进后,生成了一种新的算法称为元启发式算法,该算法也将局部搜索算法和随机算法进行了融合㊂其中蚁群优化㊁遗传算法以及粒子群优化算法等都属于典型元启发式算法[10]㊂在任务调度问题领域,通常包括独立任务调度㊁列表调度以及基于集群和复制的调度3种启发式算法㊂文献[11]提出了一种基于元启发式的任务调度方法,以优化异构M P S o C的寿命可靠性㊁性能和功耗㊂寿命可靠性受几种具有不同行为的故障机制的影响,这些机制主要取决于温度及其变化模式㊂为了提高多处理器系统的生命周期可靠性,需要在优化过程中考虑所有潜在故障的影响㊂实验结果表明,所提方法可靠性和功耗平均分别提高30%和3.6%㊂因此,它可以用于云计算问题的研究和实践应用,以优化工作计划㊂文献[12]提出了一种空间任务调度和资源优化(s p a t i a l t a s ks c h e d u l i n g a n d r e s o u r c e o p t i m i z a t i o n,S T S R O)方法,通过经济高效地调度异构应用程序的所有到达任务来满足任务的延迟约束,从而最小化其提供者的总成本㊂S T S R O很好地利用了分布式绿云数据中心(d i s t r i b u t e d g r e e n c l o u d d a t ac e n t e r s, D G C D C)中的空间多样性㊂在每个时隙中,将D G C D C的成本最小化问题表述为约束优化之一,并通过提出的基于模拟退火的蝙蝠算法(S B A)加以解决[13]㊂实验结果表明,与两种典型的调度方法相比,S T S R O实现了更低的总成本和更高的吞吐量㊂文献[14]提出了一种负载均衡资源集群(L B-R C)负载均衡机制㊂应用元启发式蝙蝠算法来获得最佳资源聚类及其聚类中心,以实现更快的收敛㊂采用新的动态任务分配策略,以在给定的限制内实现最小的制造时间和执行成本㊂在各种综合数据集和性能矩阵上的实验结果表明,该方法在计算资源利用率和计算成本方面有一定改进,但还有可提升的空间㊂文献[15]提出了使用两个禁忌列表的禁忌元启发式算法,将机器分为两组,以减少生成的邻居数量,然后通过保持相同质量的解决方案来最大程度地减少计算时间㊂禁忌搜索与最佳启发式方法的比较结果表明,禁忌搜索调度方案在计算时间方面具有更好的表现㊂对于博弈算法而言,为使分布式计算的整体性能更佳,因此侧重于对系统级的负载均衡以及资源分配方面进行深入的探究[16]㊂文献[17]通过运用演化博弈论研究了3种策略的分工演化㊂根据回报矩阵中的参数设置所出现4种特定情况,通过计算提供平衡点的相应稳定性㊂数值计算结果直观描述了策略的演变状态㊂结果表明,更大的协同收益有助于系统中的有效分工,从而为多主体系统提供高收益㊂在实际应用中,由于高时间复杂度,该算法的可行性是还有待进一步验证㊂针对多目标优化问题的解决方法,帕累托优化方法是被广泛使用的一种方法,同时它还能对多个目标之间进行合理的权衡,因此当多个目标间有冲突时该方法的效果更佳[18,19]㊂满足帕累托优化准则的通常存在多个解,一般将该多个解集合称为帕累托边际㊂尽管上述调度方法都是有效的,但部分方法在实际应用中的可行性较差,且任务调度优化结果还有进一步提升的可能㊂为了处理多目标问题,调度计划所需的时间会大幅度增加㊂因此,文献[20]侧重提出一种混沌共生生物搜索(c h a o s s y m b i o s i ss e a r c h,C S O S)算法,用于任务调度问题中降低搜索的代价和时间跨度㊂结果表明,C S O S在任务规划中对成本降低和时间限制方面有着显著的改进,但对于数据量大㊁任务复杂度高的云环境下的可行性还有待验证㊂针对上述问题,例如不适用于多目标任务优化㊁搜索时间长㊁计算复杂㊁易陷入局部最优等,提出了一种云环境下基于改进S O S的多目标任务调度算法㊂所提算法的创新点总结如下:(1)为了更合理地实现多目标任务调度,所提算法设计了相应的调度框架,其中包括云平台㊁数据中心㊁处理单元和任务管理器等,并且提出了与之对应的目标函数与约束条件㊂(2)由于传统的共生生物搜索(s y m b i o t i co r g a n i s m s s e a r c h,S O S)算法收敛速度慢,易陷入局部最优,所提算㊃5121㊃计算机工程与设计2022年法对其进行改进,即利用准反射学习构建初始种群,在偏利共生阶段中加入扰动项,并且在寄生阶段中加入自适应变异率,以提高全局搜索能力㊂(3)为了将改进S O S算法应用于多目标任务调度问题,所提算法将生物坐标转换为任务时间表,通过设定坐标即可实现任务分配,缩短了完成时间且提高了算法各方面的性能㊂2多目标任务调度算法整体架构2.1问题描述多目标任务调度是通过调度算法将接收到的任务分配到合适的执行虚拟机(v i r t u a lm a c h i n e s,VM)列表中,在满足多目标约束下实现任务完成时间最短㊂单目标调度算法存在一个问题,例如,具有高优先级的任务拥有优先分配的机会,如果高优先级任务未分配完成,低优先级任务将无法分配,如此便降低了系统处理任务的效率㊂因此需要一个有效的调度算法,在各种情况下均能提供最佳效率㊂在调度器中充分应用调度算法,在不破坏服务层契约的情况下提高信息中心的效率㊂此外,任务提交和VM会影响完成工作的时间,相应的成本效益也会受到服务供应商规划的影响,因此,在此情况下,应有效地对任务进行调度,以减少执行成本和时间㊂2.2调度算法框架在整个任务执行过程中,如果调度方案降低了工作效率,并且影响了客户的活动,那么客户可以通过任务调度器进行任务数据管理㊂任务调度器具有接受和管理任务信息的功能,将满足预算㊁成本㊁存储限制的任务数据上传至调度中心,然后由调度中心根据成本㊁时间等约束完成任务分配㊂所提的多目标任务调度算法框架如图1所示㊂图1云环境下的任务调度框架其中,云平台由多个数据中心组成,这些数据中心可以通过使用各地的互联网进行访问,具备计算㊁存储等数据处理功能,并且调度中心利用改进的S O S算法来解决云模式中任务调度的问题㊂在每个服务器集群中,处理单元(p r o c e s s i n g e l e m e n t s,P E)通过高带宽连接网络[21],因此需要考虑通信延迟㊂在任务调度模块中,有效地将用户任务分配给各种可用的P E,以优化用电量和时间㊂在调度过程中,用户任务将分配给数据中心C(C1, C2, ,C m),每个数据中心都配备了多个处理单元{P E1, P E2, ,P E m}来执行用户任务㊂数据中心之间会通过一组信息<v,p>来相互交流,其中v㊁p分别表示处理单元的执行速率和功耗㊂用户的任务流可以建模为一个有向无环图(d i r e c t e da c y c l i c g r a p h,D A G),记为G r N,H㊂节点集N={T1, ,T n},在任务对{T i,T j}ɪH中,父任务称为T i,子任务称为T j㊂T j使用T i生成的信息,子任务在其所有父任务完成之前被假定为无法执行㊂在某个任务图表中,没有父任务的任务称为进入任务,而没有子任务的任务称为退出任务㊂该模型只考虑一个输入输出任务节点㊂因此,在D A G开始和结束时,添加了两个假任务T e t和T e x,运行时间为零㊂D A G中每N个顶点上都有长度为l的任务㊂由于所有P E都是有顺序的且标准化的,但调度是随时发生的,因此不利于任务的快速的处理㊂所提算法通过使用改进的S O S为云环境中提供了任务调度和资源使用方案㊂2.3多目标调度的目标函数所提模型中将云接口视为在复杂计算任务中使用云资源执行的一组用户功能㊂根据任务㊁资源㊁成本的定义以及规划优化模型的表示,云计算的效率会有所不同㊂在N 个任务T的调度问题中,存在两个目标函数和各种限制㊂目标一为在v m j分配中减少任务i的预期任务往返时间(R T i j);目标二为降低v m j中的总预期成本(E C i j)㊂利用加权和策略构建两个目标函数的加权集合,以解决向量显著减少的多目标问题㊂其中预期往返时间R T i j包括传输㊁确认和执行操作在内的整个过程的完整时间R T i j=(S i/b i)+d i+(k i/n j)+d i(1)式中:S i为任务i的大小,b为带宽,d为延迟,k i为执行任务i所需的指令数目,n j为每秒执行的指令数E C i j=(l i/n j)*R C+(f i/b j)*C/b jR C=R*(C/m)+S*C/s t(2)式中:R C为资源成本,f i为文件大小,C为执行任务i的成本,R为虚拟机的R AM,S为虚拟机的大小,s t为存储量㊂对于一个虚拟机来说,其容量小于或等于数据中心的数据量㊂因此多目标任务调度的优化目标为m i n P= 1*ðn i=0ðm j=0R T i j*z i j+ 2*ðn i=0ðm j=0E C i j*z i j(3)㊃6121㊃第43卷第5期陈艺,江芝蒙,张渝:云环境下改进S O S的多目标任务调度算法S u b j e c t t oðm j=0z i j=1∀iz i jȡ0∀i,j ðm j=0c jɤt c ðm j=0m jɤt m (4)式中:z i j是在v m j中分配任务i的决策变量,c j是分配给v m j的C P U,m j是分配给v m j的内存,t c是数据中心的总C P U,t m是数据中心的总内存, 1㊁ 2为权重因子㊂适应度值为f i t n e s s=m i n P(5) 3提出的改进共生生物搜索算法对于云环境下多目标任务优化调度,通常使用的算法包括元启发式算法㊁博弈论调度以及帕累托优化等,其中元启发算法中的S O S算法潜在的解由一组经过连续迭代进化而来的生物表示,每个生物代表一个优化问题的解,并且通过互利㊁共栖和寄生3个阶段进行解决方案优化[22]㊂相比于其它搜索算法,S O S算法的全局搜索能力更强,得到的优化结果更加合理有效㊂3.1共生生物搜索算法S O S算法的互利阶段是两种不同生物之间的一种关系,两种生物都从这种相互作用中受益㊂在共栖关系中,一个生物从相互作用中受益,而另一个生物不受伤害㊂在寄生关系中,一个生物引发一种有益于自身的关系,而另一个生物则受到伤害[23]㊂在S O S算法进化中,适者生物被允许进入下一代潜在解,而不适者生物被丢弃㊂在二维搜索空间中创建生物种群,并根据S O S的3个阶段(互利㊁共栖和寄生)的模型改变每个生物的位置㊂假设第i个生物在解决方案搜索空间中的位置为X i=(X i1,X i2,X i3, ,X i g)(6)式中:X i pɪ[L p,U p],pɪ[1,g],搜索空间第p维数的上下界分别由L p和U p进行表示㊂并且每次进行迭代的过程中,生物的位置都会根据生物的3个阶段进行更新㊂3.1.1互利阶段假设X i是生态系统的第i个成员㊂在此阶段,从生物群中随机选择一个生物个体X j,与另一个个体X i(iʂj)相互作用,以实现互利㊂这种相互作用的实质是提高生态系统中X i和X j的生存程度㊂根据下式得到了X i和X j的新候选解,而这些候选解的质量受互惠互利因素的影响X'i=X i+U(0,1)*(X b e s t-C o*β1)X'j=X j+U(0,1)*(X b e s t-C o*β2)C o=12(X i+X j)(7)式中:C o为X i和X j之间的相互关系向量,X b e s t为具有最佳适应值的生物,β1和β2代表生物X i和X j之间的利益因子, U(0,1)是0和1之间均匀分布的随机数向量;i=1,2, 3, ,e c o s i z e;jɪ{1,2,3, ,e c o s i z e|jʂi},其中e c o s i z e是搜索空间中的生物数㊂在相互关系中,一个生物在与一个共同伙伴进行互动时,可能会从中获得重大或轻微的利益㊂因此,随机获得的β1和β2是1或2,1和2分别表示轻效益和重效益㊂通过X b e s t分别与X i和X j进行交互,如果新的候选解的适应度值优于传统的解,则新的候选解将取代传统的解㊂在这种情况下,X'i和X'j在下一代生态系统中分别取代X i和X j㊂否则,X'i和X'j将被丢弃,而X i和X j将存活到下一代生态系统中㊂迭代表示为X i=X'i i f f(X'i)>f(X i)X i i f f(X'i)ɤf(X i)(8) X j=X'j i f f(X'j)>f(X j)X j i f f(X'j)ɤf(X j)(9)式中:f(.)为适应度评估函数㊂3.1.2共栖阶段在共栖阶段,生态系统的第i个成员随机选择一个生物X j与X i(iʂj)相互作用㊂在这种情况下,X i打算从X j中受益,X j既不从交互中获得收益也不从交互中损失㊂通过与X j和X b e s t的交互,分别提高了设计向量X i的适应度质量和算法的寻优能力㊂相互作用表示如下X'i=X i+U(-1,1)*(X b e s t-X j)(10)式中:X b e s t为最佳适应值的生物,U(-1,1)是-1和1之间均匀分布随机数的向量,i=1,2,3, ,e c o s i z e,jɪ{1,2, 3, ,e c o s i z e|jʂi},e c o s i z e为搜索空间中的生物数㊂X i根据式(8)进行更新㊂3.1.3寄生阶段在寄生阶段,通过克隆第i个生物X i,并使用随机生成的数字对其进行修改,产生了一种称为寄生虫载体的人工寄生虫㊂然后,从生态系统中随机选取X j,计算寄生虫载体和X j的适应度值㊂如果寄生物载体比X j更适合,那么X j被寄生物载体所代替,否则X j将存活到下一代生态系统中,寄生物载体则被丢弃㊂X j根据下式关系进行更新X j=P V i f f(P V)>f(X j)X j i f f(P V)ɤf(X j)(11)式中:P V为寄生虫载体㊂该阶段通过随机剔除非活性解,引入活性解,增加了算法的探索能力㊂从而避免了早熟收敛,提高了收敛速度㊂S O S算法的流程如图2所示㊂3.2提出的改进方案传统S O S算法存在3个明显的不足:①初始种群随机㊃7121㊃计算机工程与设计2022年图2 S O S 算法的流程构建,降低全局搜索能力;②早熟㊁收敛速度慢;③有可能陷入局部最优㊂为此,所提算法针对这3个方面提出了改进措施:①利用准反射学习来构建初始种群;②共栖阶段中加入扰动项;③寄生阶段中加入自适应变异率㊂3.2.1 采用准反射学习机制的种群初始化随机初始化生物种群方法是标准S O S 算法中的常用方法,但该方法存在一定的局限性,它对算法的全局搜索能力进行了一定的削弱,从而导致该方法的收敛精度大大降低,以致常常会出现早熟的现象㊂因此,为了更好解决该问题,通过采用准反射学习(qu a s i -r e f l e c t i o n -b a s e dl e a r -n i n g ,Q R B L )机制对该算法的求解质量和收敛速度进行强化㊂假设x 为实数且x ɪ[p ,q ],则x 的准反射数x -R表示为:x -R=r a n d ((p +q )/2,x )㊂其中r a n d ((p +q )/2,x )表示在(p +q )/2和x 之间均匀分布的随机数㊂假设=(x 1,x 2, ,x n )为一个n 维向量空间的点,其中x 1,x 2, ,x n 都属于实数且x i ɪ[p i ,q i ],∀i ɪ{1,2, ,n }㊂则的准反射点,其中-R=(x -R1,x -R 2, ,x -R n),其中x -R i=r a n d ((p i +qi )/2,x i )(12)假设=(x 1,x 2, ,x n )是n 维向量空间中的点(假设其中代表的是候选解),候选解的目标函数值由f (㊃)进行表示,除此之外,的准反射点还可以根据准反射点的定义来获得-R=(x -R 1,x -R 2, ,x -Rn )(13)若f (-R)ɤf (),这说明与相比,-R的目标函数值相对更优,这时选择使用-R来替代;反之,保持不变㊂为了进一步的对S O S 算法的寻优性能进行提高,给出了一种优化的方法,该方法主要是在标准S O S 算法的种群初始化阶段中将准反射学习机制进行引入㊂经过对它初始解的思考,以及评估它的准反射解,选取更优的进行使用,如此一来,采用准反射学习机制对搜索空间的搜索会更加全面和充分,从而使得算法的收敛速度更快,同时又更可能找到近似全局最优解的候选解,算法的精度也得到了较大的提高㊂3.2.2 共栖阶段中引入扰动项共栖最主要的作用就是能够在最优解的引导下,实现对生物体的快速寻优㊂然而,该措施存在的缺陷就是收敛的精度较低,并且收敛的速度相对较慢㊂针对此问题本文采取了新的改进措施,通过在共栖阶段中,基于原搜索方程引入扰动项,其中加入的扰动项是X b e s t 和X i 的差向量,并且线性递减的惯性权重ω也被引入,具体如下所示X i n e w =X i +ω(X b e s t -X i )+(1-ω)(X b e s t -X j )ω=ωm a x -(ωm a x -ωm i n )t t m a x(14)其中,在[0,1]区间范围内的惯性权重由ω进行表示;惯性权重的最大值记作ωm a x ;惯性权重的最小值记作ωm i n ;算法的最大迭代次数由t m a x 来表示;t 表示的是当前的迭代次数㊂在此阶段中,为维护个体间存在的差异,采取对差分扰动项进行增加的方法;此外,由于在算法迭代的初始阶段中ω的值相对较大,算法的全局搜索能力也相对较强,为了尽可能避免陷入局部最优,所以还将线性递减的惯性权重ω进行了引入㊂在算法不断迭代后,ω的值也会不断减小,并且在较优解的邻域内,算法中个体的搜索能力也会得到加强,收敛的精度也会随之提高,并且收敛的速度也会变快㊂3.2.3 寄生阶段中加入自适应变异在进行寄生操作时,通常情况下,传统S O S 算法选取的变异率是固定值,其中存在一个较大的缺陷就是这使得算法陷入局部最优的概率较大,以致收敛的精度也会大大降低㊂针对该问题本文所提的算法做出了相应的改进,基于传统S O S 算法,将其中的固定变异率由适应值进行动态调整的变异率来替代,详细的公式过程如下pv =f m ax (X i )-f (X i )f m ax (X i )-f a v e (X i )d 1,f (X i )ȡf a v e (X i )d 2,f (X i )<f a v e (X i )(15)式中:p v 为动态变异率;生物体的平均适应值用f a v e (X i )进行表示,其中,选取f (X i )作为生物体适应值来进行寄生操作;种群中的最大适应值记作f m a x (X i );d 1㊁d 2表示的是随机数㊂鉴于适应值动态调整的变异率,采取寄生的操作方式,这可以使具有较高适应值的生物体变异率尽可能的变低,㊃8121㊃第43卷 第5期陈艺,江芝蒙,张渝:云环境下改进S O S 的多目标任务调度算法具有较低适应值的生物体变异率尽可能的变高,让优质生物体的数量得到增加,从而进一步实现对算法收敛速度以及精度的提高[24]㊂3.3 任务调度问题中的生物编码在该算法中,生物的种群结构被表示为一组实例类型,每个生物是种群中的一个个体,代表了搜索空间的一部分㊂生物坐标系中的每个坐标(每个字段)都是云环境中的实例类型㊂在d 维解决方案搜索空间中,n 个生物的搜索种群表示为X ={X 1,X 2,X 3, ,X n }㊂第i 个生物的位置表示为X i ={x i 1,x i 2,x i 3, ,x i d }㊂为了定义问题的解决方案,每个生物代表一个完整的任务时间表㊂实数值表示要选择的备用实际类型[25]㊂该确定生物在解决方案搜索空间中位置的坐标系取决于生物的维数㊂举个例子说明,生物的7个任务时间表如图3所示,其中生物是一个7维的生物,它在搜索空间上的位置由坐标1到7定义㊂图3 生物编码及其与VM 映射的对应任务生物的移动范围由执行任务的可用实例数决定,因此,生物搜索空间的坐标值可以是一个或多个可用实例㊂由于所选VM 的适应度值是离散的,因此生物位置中每个坐标的最近整数值对应的就是执行该坐标定义任务的实例类型㊂由图3中的示例可知,资源池中有3个实例,因此每个坐标值的范围为0~3㊂坐标1的值0.6表示任务1已分配给实例类型2㊂坐标2的值2.7表示任务2已分配给实例类型3㊂其余的坐标遵循相同的逻辑㊂其中将生物坐标转换为任务时间表的算式如下s i=xii =1,2,3, ,n (16)4 仿真及分析实验基于C l o u d S i m 仿真平台进行,测试中使用一个数据中心㊁5个VM 和300个c l o u d l e t 执行㊂云环境的模拟参数见表1㊂改进S O S 算法中,种群规模是100,个体维数是5,最小权重ωm i n 和最大权重ωm a x 分别是0和1,最大迭代步数是100㊂表1 模拟参数参数值最大迭代次数100虚拟机数量5虚拟机容量9000m b ~10000m b虚拟机处理能力1000m i ps 主机存储1000000m b O S 结构W i n d o w s 7x 86任务数或c l o u d l e t 数50~3504.1 性能指标所提算法使用相应的指标评估能量㊁时间㊁成本㊁资源利用率和服务水平协议(s e r v i c e l e v e l a g r e e m e n t ,S L A )违反情况㊂(1)能耗:所有响应或服务的能量消耗E k =ðni =1(ρiˑq i)(17)(2)时间:任务在传输㊁确认和执行操作中整个过程的时间,计算如式(1)㊂(3)成本:虚拟机上任务执行所需的总成本,包括资源成本和执行成本,计算如式(2)㊂(4)资源利用:资源应得到均衡利用,即分配给v m j的C P U 不能超过数据中心的总C P U ,以及分配给v m j 的内存不能超过数据中心的总内存㊂数学表达如下ðm j =0cj ɤt c ,ðmj =0m j ɤt m (18)(5)S L A 违反情况:当云提供商的处理器数量小于所需的任务或C l o u d l e t 的数量时,就会发生S L A 冲突,因此处理的任务数不能超过上限S L A =t c <i(19)4.2 调度性能评估4.2.1 不同迭代次数下的收敛曲线为了论证所提算法的收敛特性,将其与文献[11]㊁文献[14]㊁文献[17]进行对比分析,其中不同算法的总执行时间和成本随着迭代次数的收敛性如图4所示㊂由图可知,迭代次数在30~40时,算法基本上都完成了任务的执行㊂从图4(a )可以看出,所提算法完工时间约为2.9m s ,优于文献[11]㊁文献[14]㊁文献[17]所提方法所需要的4.9m s ㊁4.5m s 和3.5m s ㊂从图4(b )可以看出,在成本开销方面,所提方法相较于文献[11]方法大约节省50%的成本开销;相较于较为节省成本的文献[17],也能节省约15%的成本开销㊂在最开始时,算法分配任务都是根据站点处理速度以及性价比来进行相应的分配,因此成本低且耗时长㊂在之后时间和成本的收敛速度开始变快,这主要是由于每个任务包都会根据自身利益㊃9121㊃。

云计算环境下基于改进遗传算法的任务调度算法摘要：在当前的互联网时代，云计算技术已经成为了IT行业的一个重要发展方向。

随着云服务市场的不断扩大和用户需求的日益增长，任务调度问题也成为了一个备受关注的问题。

传统的任务调度方法往往存在效率低下、资源浪费等问题，因此需要寻找一种更加高效的方法来解决这些问题。

本研究提出了基于改进遗传算法的任务调度算法，该算法能够有效地优化任务分配方案以提高系统的整体性能。

关键词：云计算环境；遗传算法；任务调度；算法引言：近年来，云计算作为一种新型的信息科技架构模式逐渐成为人们关注的一个热点话题。

云计算通过将计算资源与网络连接相结合的方式，为企业提供了一种全新的数据处理方式。

然而，由于云计算中涉及到大量的计算资源和复杂的计算流程，如何合理地处理任务调度问题就显得尤为重要。

传统任务调度方法虽然有一定的应用价值，但是它们存在着效率低下、资源浪费等问题。

为了解决这些问题，本文提出了基于改进遗传算法的任务调度算法。

一、云计算任务调度概述（一）云计算概述云计算是一种通过互联网提供计算资源和服务的方式，它可以为用户提供灵活的计算能力。

在传统的计算机系统中，用户需要自己购买并维护硬件设备才能进行数据存储和处理，而云计算则提供了一种更加高效、便捷的方法来解决这个问题。

云计算的核心是虚拟化技术，即将物理服务器划分成多个虚拟服务器，每个虚拟服务器都可以独立运行应用程序。

这种方式不仅提高了系统的利用率，还可以降低成本，因为只有使用到的虚拟服务器才会被付费。

此外，云平台还支持多层次的访问控制，使得不同的用户可以在安全的基础上共享资源。

（二）云计算任务调度特点在云端计算环境中，任务调度是一项非常重要的工作。

随着云计算技术的不断发展和应用范围的扩大，任务调度问题也变得越来越复杂。

因此，研究如何有效地解决任务调度问题是一个重要的课题。

首先，云计算环境的特点决定了任务调度需要考虑多方面的因素。

例如，资源分配、负载均衡、性能优化等方面都需要得到充分的关注。

云计算环境下基于 ABC-QPSO 算法的资源调度模型温聪源;徐守萍;曾致远【摘要】In order to improve the utilisation rate of cloud resource scheduling and guarantee load balance of nodes, we propose a cloud computing resource scheduling method which combines the quantum particle swarm optimisation algorithm with artificial bee colony algorithm. Firstly, the search operator of artificial bee colony algorithm is introduced to QPSO algorithm as the mutation operator to solve its defect of premature convergence, and then the shortest scheduling time is taken as the fitness function of the QPSO algorithm to optimise the cloud resource scheduling, finally, the performance test of ABC-QPSO is carried out on CloudSim platform.Results show that the ABC-QPSO overcomes the shortcomings of QPSO algorithm, and effectively shortens the task completion time as well, as well as improves the utilisation rate of cloud resource scheduling, it is suitable for cloud computing resource scheduling of large-scale tasks.%为了提高云计算资源的利用率,保证节点负载均衡,提出一种人工蜂群算法和量子粒子群算法相融合的云计算资源调度模型( ABC-QPSO). 首先将人工蜂群算法的搜索算子作为变异算子引入到量子粒子群算法中,以解决量子粒子群算法早熟收敛缺陷,然后以任务完成时间最短作为量子粒子群的适应度函数对云计算资源调度进行优化,最后在CloudSim 平台上对ABC-QPSO的性能进行测试. 结果表明,ABC-QPSO算法不仅克服了QPSO算法的不足,而且有效缩短了任务的完成时间,提高了云计算资源利用率,适合于进行大规模任务的云计算资源调度.【期刊名称】《计算机应用与软件》【年(卷),期】2015(032)005【总页数】4页(P30-32,64)【关键词】云计算;资源调度;人工蜂群算法;量子粒子群算法;任务分配【作者】温聪源;徐守萍;曾致远【作者单位】广东金融学院广东广州510520;广东金融学院广东广州510520;广东金融学院广东广州510520【正文语种】中文【中图分类】TP393云环境任务数量以海量形式存在，而云计算资源具有动态、异构特性，因此如何对云资源进行有效管理，提高资源利用率，成为云计算研究中的重点问题[1,2]。

云计算环境下的动态任务调度技术随着云计算技术的不断发展，大规模计算资源的互联和共享已成为当前云计算环境下的重要特征。

然而，云计算环境下的动态任务调度问题是一个挑战性问题，其核心是动态任务调度问题。

为了解决这一问题，研究人员们提出了各种各样的动态任务调度技术。

一、背景介绍云计算环境下的动态任务调度技术是一种优化计算资源利用率、提高系统性能的重要手段。

一般来说，动态任务调度技术主要包括任务调度算法、任务调度策略、任务分配机制等三个方面。

这些技术的目标是使计算资源的利用率尽可能高、任务的执行时间尽可能短，从而提高系统的运行效率和性能。

二、动态任务调度技术1. 任务调度算法任务调度算法是动态任务调度技术的核心内容，它直接影响了任务调度效果和系统性能。

常见的任务调度算法有最优调度算法、负载平衡算法、遗传算法、蚁群算法等。

最优调度算法是一种以最小化任务调度时间为目标的动态任务调度算法。

负载平衡算法则是基于负载均衡原理进行任务调度的一种算法。

遗传算法则是模仿生物进化的过程，将调度问题变成一个优化问题，并通过良好的优化策略进行求解。

蚁群算法是一种基于蚁群的贪婪求解算法，本质上是一种分布式启发式算法，可用于解决任务调度问题。

2. 任务调度策略任务调度策略是实现任务调度算法的具体方案，通常包括贪心策略、混合策略、分层策略、多目标策略等。

具体的策略要根据不同的应用环境确定。

贪心策略是指在任务调度过程中根据当前状态选择最优的任务，而不考虑长远的效益。

混合策略则是将不同的任务调度算法和策略合并使用，从而取得更好的调度效果。

分层策略是指根据任务的不同特征将任务划分成不同的层次，并采用不同的调度策略。

多目标策略则是同时优化多个指标，如任务完成时间、计算资源利用率、能耗等。

3. 任务分配机制任务分配机制主要是针对多节点的分布式系统中任务分配问题，其目标是合理地分配任务到各个节点上，以达到最优的调度效果。

任务分配机制通常包括贪心分配、随机分配、最优分配、自适应分配等。

云计算中的资源调度与任务调度算法云计算是指通过网络将计算机资源（包括计算、存储、网络等）提供给用户使用的一种计算模式。

其中，资源调度和任务调度算法是云计算系统中非常重要的一部分，对于提高系统性能和资源利用率具有关键作用。

本文将探讨云计算中资源调度和任务调度算法的相关概念、挑战以及解决方案。

一、资源调度算法1. 资源调度算法的定义资源调度算法是指根据用户需求和系统资源情况，将任务分配到合适的计算节点上，以达到提高系统性能和资源利用率的目的。

在云计算环境中，资源调度算法需要考虑以下几个方面的因素：任务特征、资源特征、用户需求和系统性能指标等。

2. 资源调度算法的挑战资源调度算法面临着以下挑战：（1）系统规模庞大：云计算系统通常包含大量的计算节点和任务，如何高效地进行资源调度是一个巨大的挑战。

（2）任务类型多样：云计算系统中的任务具有不同的类型和特征，如何根据任务特征进行合理的调度，是资源调度算法需要解决的问题。

（3）资源利用率最大化：资源调度算法需要考虑如何使系统中的资源得到充分利用，达到资源利用率最大化的目标。

3. 资源调度算法的解决方案为了解决资源调度算法面临的挑战，研究者们提出了多种解决方案，包括但不限于以下几种：（1）基于负载均衡的资源调度算法：通过合理地分配任务，将系统中的负载均衡地分布在各个计算节点上，达到资源利用率最大化的目标。

（2）基于优先级的资源调度算法：根据任务的优先级，将高优先级的任务分配到合适的计算节点上，提高任务执行效率，提升系统性能。

（3）基于预测的资源调度算法：通过对任务的执行时间进行预测，将任务分配到最适合的计算节点上，减少任务的执行时间，提高系统响应速度。

二、任务调度算法1. 任务调度算法的定义任务调度算法是指根据任务的特征和系统资源情况，将任务合理地分配到计算节点上，以达到系统性能和用户需求的要求。

任务调度算法需要考虑任务的特点、资源的利用情况、系统负载等因素。

2. 任务调度算法的挑战任务调度算法面临着以下挑战：（1）任务执行时间的不确定性：由于任务执行的环境和资源的不确定性，任务执行时间无法准确预测，任务调度算法需要考虑这种不确定性。

云计算环境下的网络资源调度算法随着云计算发展的迅猛，网络资源调度算法成为了保障云环境稳定性和性能优化的关键技术。

本文将介绍云计算环境下的网络资源调度算法的概念、原理及其应用，并进一步讨论其存在的挑战和未来发展方向。

一、引言随着云计算技术的不断成熟和普及，云环境中大规模的虚拟机和网络资源需求得到满足。

然而，在这个复杂的网络环境中，如何高效地调度和分配网络资源，成为了一个重要的问题。

网络资源调度算法的设计和优化可以帮助提高系统的性能和资源利用率，降低成本。

二、云计算环境下的网络资源调度算法概述1. 定义网络资源调度算法是指根据系统需求和资源特点，通过合理的调度策略和算法分配云环境中的网络资源，以满足系统性能、负载均衡、资源利用率等要求。

2. 原理网络资源调度算法主要基于以下原理：- 资源感知：算法需要能够感知云环境中的各种网络资源状态，包括带宽、延迟、负载等指标。

- 资源调度：根据当前系统的需求和资源状态，算法能够动态地调整资源的分配和调度策略。

- 均衡优化：资源调度算法需要考虑负载均衡的原则，尽可能避免资源过载或负载不均衡的情况。

- 效率优化：算法需要追求资源利用率的最大化，以减少资源浪费和降低成本。

三、常见的网络资源调度算法1. 静态调度算法静态调度算法是根据事先设定的策略和规则对网络资源进行静态分配和调度。

这种算法的优点是简单、稳定，但缺点是不能适应网络环境的实时变化，无法实现动态调度和负载均衡。

2. 动态调度算法动态调度算法是根据当前系统的需求和资源状态进行实时的资源分配和调度。

常见的动态调度算法包括最短作业优先（SJF）、最早截止时间优先（EDF）、最小剩余时间优先（SRTF）等。

这些算法可以根据任务的优先级和资源需求进行动态调度，以实现资源的高效利用和负载均衡。

3. 智能调度算法智能调度算法基于人工智能和机器学习的技术，能够根据历史数据和实时监测数据进行资源调度的决策。

这种算法可以通过学习和适应网络环境的变化，进一步优化资源调度策略，提高系统的性能和稳定性。

基于云计算的调度算法随着云计算技术的快速发展，越来越多的企业开始将自己的业务和数据迁移到云端进行处理和存储。

云计算的出现为企业提供了更加灵活和高效的计算资源，极大地提高了企业的运营效率和成本效益。

云计算资源的调度成为了一个关键的问题，如何能够高效地利用云计算资源，提高资源的利用率，成为了云计算领域需要解决的重要问题之一。

为了解决资源调度的问题，研究人员提出了很多云计算的调度算法，这些算法通过对资源的合理分配和任务的调度，来提高云计算资源的利用率。

本文将针对基于云计算的调度算法进行详细的介绍和分析。

静态调度算法是指在任务到达之前，就已经确定了资源的分配和任务的调度。

这种算法一般能够在任务到达之前就完成资源的分配和任务的调度，但是对于任务到达时间和任务量的变化并不敏感，很难适应动态的云计算环境。

动态调度算法是指在任务到达后，根据实时的系统状态和任务的需求，实时地对资源进行分配和任务进行调度。

这种算法能够更好地适应动态的云计算环境，但是在实际应用中也更加复杂和困难。

二、基于云计算的调度算法的研究进展随着云计算技术的不断发展和完善，基于云计算的调度算法的研究也取得了很大的进展。

目前，关于基于云计算的调度算法的研究主要集中在以下几个方面：1. 资源的动态分配2. 任务的智能调度3. 负载均衡和资源利用率优化4. 数据中心的能耗管理5. 容错处理和故障恢复在资源的动态分配方面，研究人员提出了很多优化算法，如基于遗传算法的资源分配算法、基于贪心算法的资源调度算法等。

这些算法能够在任务到达时，根据任务的需求和系统的状态，选择合适的资源进行分配，从而提高系统的利用率和性能。

在数据中心的能耗管理方面，研究人员提出了很多能耗管理算法，如基于预测模型的能耗管理算法、基于动态调节的能耗管理算法等。

这些算法能够根据系统的负载和需求，实时地调节数据中心的能耗，从而降低能耗成本并保证系统的性能。

在容错处理和故障恢复方面，研究人员提出了很多容错处理算法和故障恢复算法，如基于备份和恢复的容错处理算法、基于重试和重传的故障恢复算法等。

云计算环境下的大规模任务调度算法随着信息技术的不断发展，计算机应用已经成为各行各业不可或缺的一部分。

云计算技术作为目前最受瞩目的计算机应用技术之一，已经成为各大企业和科研机构重点关注的对象。

云计算环境下，如何高效的完成大规模任务调度是云计算技术研究的一个热点问题。

本文将从大规模任务调度算法的角度，探讨云计算环境下的大规模任务调度算法。

一、大规模任务调度算法的研究现状近年来，大规模任务调度算法在云计算环境下的研究受到了广泛关注。

在传统的大规模任务调度算法中，主要是采用贪心算法、遗传算法、粒子群算法等方法来解决。

但随着云计算环境的出现，这些传统算法已经不能完全符合云计算环境下任务调度的需求。

因此，学者们开始探索新的大规模任务调度算法。

目前，云计算环境下大规模任务调度算法的研究主要包括基于遗传算法的任务调度、基于蚁群算法的任务调度、基于模拟退火算法的任务调度等。

以基于遗传算法的任务调度为例，传统的遗传算法主要是通过模拟生物进化的过程，寻找出任务的最优调度方案。

但在云计算环境下，传统的遗传算法往往难以解决任务调度问题。

为此，学者们提出了一系列针对云计算环境下的遗传算法，如动态遗传算法、变异遗传算法等。

二、大规模任务调度算法的关键技术在云计算环境下，大规模任务调度算法的研究面临着众多难题。

其中，算法的优化和任务分配是两个关键环节。

1.算法的优化优化算法是提高任务调度效率的关键。

在云计算环境下，由于网络传输速度的限制和数据传输的开销，传统的算法难以满足云计算环境下任务调度的需求。

因此，需要寻找一种更适合云计算环境的算法。

例如，可以引入深度学习等人工智能技术，利用深度学习对任务调度进行预测，从而提高任务调度的效率。

2.任务分配任务分配是任务调度的一个重要环节。

在云计算环境下，由于资源分布不平衡和任务需求差别较大，任务分配难度加大。

为了解决这个问题，可以采用动态任务分配和负载均衡等技术。

动态任务分配可以根据任务的实时需求，将任务分配到最适合的虚拟机上。