基于改进GA 的云计算任务调度算法研究

    姜学文

    

    

    

    摘要：在当前的社会当中，随着计算机技术和网络技术的发展，云计算逐渐成为一种主要的计算方式。而在云计算当中，任务调度算法发挥着重要的作用。对此，应当对计算资源进行合理的分配，对任务调度算法进行改进，从而进一步提升云计算的效率。基于此，本文对考虑时间-成本约束的遗传算法的改进GA任务调度算法进行了分析和研究，从而更好发挥出云计算的作用和效果。

    关键词：改进GA；云计算；任务调度算法

    中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）13-0177-02

    云计算是当前网络中一种基于云平台提供的运算服务，其中包含软件、平台、基础设施等服务，通过互联网，拆分处理任务，使之形成若干小任务，然后通过多个服务器系统进行计算分析和搜索，并向用户传递结果。在云计算当中，包括网格计算、并行计算、分布式计算等方面的内容。在云计算中，具有庞大的计算任务，因此任务调度十分重要，对于云计算的效率来说，也有着直接的影响。

    1 任务调度的基本概述

    在当前的云计算领域当中，对Google的Map/Reduce编程模型的应用较为广泛，能够并行计算大规模的数据集。通过对大任务的划分，利用多个计算资源对划分的小任务进行并行执行，最后对最终的计算结果进行汇总。云计算在提供服务的过程中，应当面向多个用户，因此对各个用户的响应时间应加以考虑，并且应当对服务所需成本进行考虑。而在一些传统的调度算法中，往往难以对所有的因素进行考虑，因而难以同时兼顾到时间和成本[1]。在云计算当中，主要有网络、存储器、处理器等资源，在应用过程中，根据用量和需求进行使用和付费。在云计算当中，任务调度算法能够向各个计算资源中更加合理的分配子任务，从而缩短任务执行时间，降低任务执行成本。

    2 几种任务调度算法的比较

    在云计算环境下，基于相同的条件，对考虑成本约束的遗传算法、考虑时间约束的遗传算法、考虑时间-成本约束的遗传算法等进行了比较分析。在实验研究当中，在初期的遗传算法进化阶段，对于总任务完成时间来说，这三种遗传算法都能够得到基本相似的最优子任务调度结果。而在不断增加进化代数的条件下，对于总任务完成时间来说，考虑成本约束的遗传算法、考虑时间-成本约束的遗传算法能够得到更加良好的结果，而考虑时间约束的遗传算法则难以取得较为理想的效果[2]。由此可见，在考虑成本约束的遗传算法中，能够得到最小总任务完成成本的子任务调度结果，但是难以有效的优化任务完成时间。而考虑时间约束的遗传算法，能够得到最短任务完成时间的子任务调度结果，但是难以有效的优化任务执行成本。在考虑时间-成本约束的遗传算法当中，由于同时对任务的时间和成本进行了考虑，因而在任务调度当中，能够取得更为理想的子任务调度结果，更好的提升云计算的效率和效益。

    3 考虑时间-成本约束的遗传算法

    1） 染色体的编码解码

    在编码方式方面，染色体十分丰富，能够对间接编码和直接编码的方式进行应用。子任务的数量，可看作染色体的长度，在染色体当中，根据子任务占用资源的具体编号，对基因取值进行确定。在初始种群的产生过程中，每一个染色体会随机生成资源编号，在变异、较差算子之后，子任务会对任意的可用资源进行占用，因此，在最优解当中，都会有染色体编码与之相对应。在染色体生成之后，应当对其进行解码操作，从而对子任务分布在不同资源中的情况加以了解。根据占用资源的不同，对子任务进行划分，根据资源编号，得到多组子任务的分类序列，然后对相应的染色体进行解码[3]。在解码之后，对于计算资源中分配的子任务，能够对其序列进行了解。通过对ETC矩阵进行应用，对于计算资源中，子任务序列的完成时间，能够进行准确的计算。在云计算当中，计算资源当中都有着并发处理的特点，因而在计算中，根据最大的计算结果，确定为子任务完成的具体时间。在考虑时间-成本约束的遗传算法当中，由于对完成子任务的成本、时间等都要加以考虑，因此可采用贪心算法对子任务完成的最大成本、最大时间等进行计算。

    2） 适应度函数

    在基于改进遗传算法的云计算任务调度算法当中，选择适当的遗传算法适应度函数，能够发挥出良好的效果，对于遗传算法中查找最优解、收敛速度等，都有着直接的影响。如果个体具有较大的适应度，其就有更大的概率向下一代进行遗传。如果个体的适应度较小，则其就有较小的概率向下一代进行遗传。在任务调度的过程中，应当对完成所有子任务需要的时间、成本等问题进行考虑。在定义时间的适应度函数当中，涉及平衡任务负载因子这一参数，能够对不同计算资源的实际利用率进行反映[4]。如果平衡任务负载因子具有较大的数值，则说明计算资源具有较高的利用效率，因而任务完成时间就会相应的较短。在定义成本的适应度函数当中，可根据任务完成时间进行计算。在适应度函数当中，如果只对之间约束进行考虑，在越高的计算资源利用率之下，如果子任务个体需要较短的时间就能够完成子任务，就有较大的适应度。而如果适应度函数只对成本约束进行考虑，子任务个体需要较低的成本就能够完成任务，也会具有较大的适应度。所以，在对考虑时间-成本约束的遗传算法的适应度函数进行定义的过程中，应当对时间、成本等约束进行综合性的考虑，从而得到更加准确的任务调度结果。

    3） 遗传操作

    在遗传操作当中，主要包括选择操作、交叉操作、变异操作等。在选择操作当中，将具有较强适应度的个体在种群中进行选择，从而对新种群的形成过程进行产生。从优胜劣汰的基本原则中，如果个体具有越高的适应度，就会由更大的概率向下一代进行遗传，因而在种群当中，能够连续的优化适应度，从而向最优解进行不断靠近[5]。在考虑时间-成本约束的遗传算法当中，选择操作因子为轮盘赌选择的方式，根据相应的公式对个体被选择概率进行计算。在适应度函数当中，对任务调度的成本约束、时间约束等进行了考虑。经过相应的选择操作，完成任务成本较低、时间较短的个体，都会包含在种群当中。在新个体的产生过程当中，交叉操作发挥着重要的作用，其能够对遗传算法中的全局搜索能力进行确定。在变异操作当中，对于遗传算法的这种局部搜索能力，可以进行相应的优化和完善。通过这种方式，能够对种群的多样性加以保护，从而避免早熟现象的出现。在考虑时间-成本约束的遗传算法当中，通过对自适应遗传算法的应用，优化了变异、交叉概率的计算公式，使其能够对变异操作、较差操作等概率进行自动的适应和调整。在结束遗传操作的时候，考虑时间-成本约束的遗传算法能够对初始算法求得的成本约束、时间约束等，能够和最优子任务调度结果染色体进行比较，而如果算法中没有产生合理的最优子任务调度结果，则重新对算法进行运行，从而得到最优结果。

    4 结论

    在当前的社会中，云计算是一种十分重要的应用形式，在各个领域中都发挥出了良好的效果。而在云计算的执行当中，需要通过一定的任务调度算法，得出完成任务的最优时间和成本。基于此，本文对基于改进遗传算法的云计算任务调度算法进行了研究，极大促进了云计算更加高效的应用。

    参考文献：

    [1]张陶，于炯，杨兴耀，等. 基于改进粒子群算法的云计算任务调度算法[J]. 计算机工程与应用，2013（19）：68-72.

    [2]刘愉，赵志文，李小兰，等. 云计算环境中优化遗传算法的资源调度策略[J]. 北京师范大学学报：自然科学版，2012（4）：378-384.

    [3]刘冬梅. 云计算环境下改进加权轮转任务调度算法研究[J]. 牡丹江师范学院学报：自然科学版，2015（1）：11-12.

    [4]孙凌宇，冷明. 基于不同分配策略的云计算任务调度性能比较与分析[J]. 井冈山大学学报：自然科学版，2016（1）：62-68+74.

    [5]袁恩隆，李飞，唐籍涛，等. 改进蚁群算法的云存储任务调度算法研究[J]. 四川理工学院学报：自然科学版，2014（1）：41-44.