基于改进遗传算法的云计算任务调度方法

王宏杰,徐胜超

(广州华商学院 数据科学学院,广东 广州 511300)

0 引 言

云计算是一种基于互联网的计算方式,通过网络提供可扩展、灵活、可靠的计算资源和服务。云计算可以帮助用户在不需要购买和维护自己的硬件和软件的情况下,使用云服务商提供的虚拟资源进行计算和存储。云计算任务调度是指将多个任务分配给云计算中心的不同计算节点进行执行,以最大化资源利用率并满足任务的执行需求。由于计算机节点、任务规模、数量都有很大差异,在此过程中需要处理大量的资源,因此如何高效完成云计算任务调度是一个巨大的挑战[1-2]。

文献[3]建立了一个感知任务调度模型,通过求解模型的最优解,获取最优任务调度方案。实验结果表明,该方法可以在系统平均代价方面提供近似最优的性能,但是其存在任务调度完成时间较长的问题。文献[4]将AHP,VIKOR和TOPSIS方法应用至任务调度中,并重点对任务调度负载问题进行了优化,避免了任务之间的调度冲突。结果表明该方法不仅可以保障用户的服务质量,而且能够降低网络运营成本的开销,但是其存在能耗较大的问题,实用价值不高。文献[5]主要通过多路径传输控制协议提出一种全新的传输调度方法,以此完成任务调度处理。结果表明该方法能够有效解决任务调度中数据包的乱序问题,提高链路利用率,但是同样存在任务调度能耗较大的问题。除此之外,国内相关专家也展开了大量研究,例如文献[6]设定一个由时延以及能耗等组成的加权代价函数,以此为依据建立任务调度模型,通过对模型求解得到合适的任务调度方案。

在上述几种调度方法的基础上,该文通过改进遗传算法对云计算任务调度问题进行深入研究,遗传算法凭借其全局优化搜索的优势被引入到云计算任务调度中,通过交叉、变异等操作可以有效提高算法的搜索能力和收敛速度,缩短任务调度时间,更好地满足不同用户对云服务质量的需求。经实验测试结果证明,该方法可以实现任务的及时调度,同时还可以有效减少能耗,获取更加满意的调度方案。

1 云计算任务调度模型构建

为了提升云计算任务调度的效果,对不同的任务属性进行结合,重新设定各个云计算节点的任务属性,对应的计算式如下:

α(w)=[θn+1]·ts

(1)

式中,α(w)代表云计算节点的任务属性;θn代表后续节点总数;ts代表节点子任务的完成时间。

进一步计算节点的综合属性值:

(2)

式中,H(x,y,z)代表云计算节点综合属性;F(u,v)代表云计算节点度值。

通过上述分析,建立目标函数,即全部任务完成时间最小化,构建云计算任务调度模型[7],如公式3所示:

(3)

式中,tmin代表完成全部任务的最短时间。

2 云计算任务调度实现

(4)

式中,df代表个体的适应度取值;ttotal代表任务执行时间总和。

在改进遗传算法过程中,对种群中全部个体的优劣程度展开分级处理是十分必要的,在每次选择操作过程中,需要保留当代种群的最优个体,对其它个体的优劣程度分级处理,个体适应度取值小于平均值,则说明该个体为优秀个体,将其保留下来,否则需要将个体淘汰。另外,交叉操作主要模拟的是生物的遗传特性,该步骤中既可能出现变异,又有一定概率可以获取更加优秀的个体。

在经典遗传算法中[12-13],初始种群的形成是完全随机的,如果在实际计算过程中没有充分考虑解空间的分布情况,则会导致大量的个体全部集中在一个区域内,不利于最优解的搜索。为了有效解决上述问题,需要确保每个个体均匀分布在解空间内。在设定资源数量以及染色体长度的情况下,计算随机两个染色体之间的相似度Similar(i,j):

(5)

式中,L(i,j)代表随机两个染色体之间的距离长度;K代表种群的规模。

采取上述方式能够确保初始种群随机形成的两个个体之间具有差异性,使其可以均匀分布在对应的解空间上,初始种群还包含比较丰富的模式,有效提升了搜索全局最优解的可能性。

虽然通过上述操作可以确保个体是随机且均匀分布的,但是获取的最优解质量比较低,随着不断的进化处理,种群中解的质量才得到有效提升。经过改进处理后的遗传算法示意图如图1所示[14-15]。

图1 改进遗传算法下起始进化点选择

为了实现改进遗传算法的初始种群选择性构建问题[16-17],引入历史表结构存储不同任务的描述以及对应的调度方案。其中,云计算节点中随机两个向量之间的相似性计算可以通过公式5得到。

通过适应度函数评价遗传算法不同解的优劣性,适应度的计算过于简单或者过于复杂均会影响算法的应用效果,因此,计算时需要考虑实际环境问题[18-19],在设定目标函数的条件下计算该值:

(6)

式中,f(x)代表适应度函数;M代表对适应度产生影响的因素总数。

改进的遗传算法需要考虑三个方面的因素[20-21],分别为:

(1)云计算任务调度总完成时间跨度;

(2)可利用资源的空间;

(3)用户规定完成时间。

任务时间跨度是适应度函数中一个十分重要的因素,通常情况下,一个任务的期望时间主要是由性能预测系统提供。在改进遗传算法中,参数的选择也是十分重要的,主要包含以下几方面参数的选择:

遗憾的是，批玄风雷声大而振儒学雨点小，到了南朝，世家大族多祖尚清淡，好宴游，“故士大夫子弟，皆以博涉为贵，不肯专儒”[11](P1539)；即使经学名家，“虽好经术，亦以才博擅名”[11](P177)。显然，这里的“博涉”与“专儒”、“才博”与“经术”两两对言，前者皆当首推善谈玄与精通三玄之学。

(1)种群规模。

在遗传算法中需要优先确定不同参数的取值,尤其是种群规模的大小。

(2)交叉率。

遗传算法优化性能的好坏和交叉率取值大小存在密切关联。

(3)变异率。

通过变异率控制各种新型基因的引入比例。

通过上述分析完成对遗传算法的改进,运用改进后的遗传算法求解云计算任务调度模型,具体流程如图2所示。

图2 基于改进遗传算法的云计算任务调度流程

(2)判断算法是否为初始运行,假设是,则通过均匀分布策略形成初始种群;反之,则参考历史任务调度信息形成经过改进处理后的初始种群;

(3)对个体的适应度取值进行计算,以减少任务调度的总执行时间;

(4)根据适应度计算结果,展开下一代个体选择和染色体交叉变异操作;

(5)采用改进的遗传算法对调度模型进行求解,判断获取的解是否满足终止条件,假设是,则直接输出最优云计算任务调度方案;反之,则跳转至步骤2。

3 实验结果与性能分析

通过实验验证所提基于改进遗传算法的云计算任务调度方法的有效性。

3.1 实验环境与参数设置

实验平台为CloudSim5,具体实验环境如表1所示。

表1 实验环境参数

CloudSim是在GridSim模拟器的基础上扩展得来的一种仿真软件,其通过扩展一系列接口,提供基于数据中心的虚拟化云环境,支持云计算资源管理和调度模拟。CloudSim属于一种层次型结构,其从下到上依次为:核心模拟引擎层、仿真层和用户代码层。其中,核心模拟引擎层的作用是实现组件与实体之间的通信;第二层为仿真层,该层的主要作用是为云计算任务调度环境建模,并提供仿真支持,具体包括虚拟机、储存容量以及接口管理等;最上层则是用户代码层,包括用户数量、调度策略接口等。

在上述实验环境下假设存在100个用户,对应500个任务,1 500个子任务,具体包括资源挖掘、数据传输以及用户注册等,总运行时间为120 min。改进遗传算法的种群内个体数为100,交叉概率在0.3～0.9区间内,变异概率小于0.1,最大迭代次数为50。将改进遗传算法的参数输入至CloudSim平台中,通过多次迭代,输出元计算任务调度结果。

3.2 结果及其分析

通过表2分析经典遗传算法和改进遗传算法的自适应度对比结果。

表2 经典遗传算法和改进遗传算法的适应度对比结果

分析表2可知,改进处理后的遗传算法种群适应度平均值和最大适应度取值明显更优越一些,说明其运行效率更高,可以获取更加精准可靠且有效的实验结果。因为文中方法充分考虑了适应度的计算过于简单或者过于复杂会对算法的寻优性能产生不良影响,因此在计算适应度的过程中,考虑实际环境和问题,设定目标函数,以提高适应度的适应性。

继续分析各个方法的任务调度时间变化情况,结果如图3所示。

(a)文中方法

由图3可知,文中方法的任务调度完成时间较低,其调度时间最高值仅为16 min,而文献[3]方法、文献[5-6]方法的调度时间最高值分别为23 min,16.9 min和23 min,证明采用文中方法可以以更快的速度完成任务调度。这是因为文中方法将全部任务最小化完成时间作为目标,构建云计算任务调度模型,然后通过改进遗传算法求解该模型,获取最优解,有效提升了该方法的运行效率。

以下实验测试主要分析不同任务数量下各个方法的能耗变化情况,结果如图4所示。

图4 不同任务数量下各个方法的能耗测试结果对比

由图4中的实验测试结果可知,文中方法的能耗明显更低,验证了该方法的优越性。这是因为在适应度取值计算中,该方法充分考虑了实际环境和问题,避免适应度的计算过于复杂,对算法的寻优性能产生不良影响,从而降低了云计算任务调度能耗。

4 结束语

为了有效解决传统任务调度方法存在的不足,以改进遗传算法为基础,提出一种新的云计算任务调度方法。经过实验测试证明,采用该方法可以获取高效率且低能耗的调度方案,可以更好地完成任务调度。在后续的研究过程中,需要注重云计算网络的实际环境,同时还需要注意数学以及图论等基础学科的学习,在坚实的理论基础上,获取更加满意的调度方法。