基于MGA-PSO的云计算多目标任务调度

孙长亚 王向文

1(上海电力大学计算机科学与技术学院 上海 200090)2(上海电力大学电子与信息工程学院 上海 200090)

0 引 言

云计算的基础设施规模比单一的物理设备大很多，但是其提供的虚拟资源仍然有限，面对庞大的云任务，如何高效地将子任务分配给虚拟资源，进行合理的任务调度已成为一项必不可缺的研究课题[1-4]。先前解决云计算任务调度问题的各种努力主要针对完工时间[5-6]。随着按需付费模式的普及，用户也会重点关注执行成本，对云服务提供商而言，还需要考虑虚拟机的负载均衡。几种经典的调度算法虽然实现简单，但是缺点很明显，如Min-Min算法[7]、Max-Min算法[8]和先进先出(First In First Out，FIFO)算法[9]。前两个算法未能有效利用资源，从而容易导致负载不均衡的问题；FIFO算法按任务提交顺序安排资源，如果较早提交的任务占用大量计算资源，则后面较小的任务必须等待很长时间。许多研究者使用启发式算法解决云计算任务调度的问题。例如:文献[10]提出了一种基于粒子群算法(PSO)的云任务调度方案，用于减少总执行时间和任务传输时间，并且证明了PSO比遗传算法运行的更快，有效减少了任务的执行时间，但是PSO可能会陷入局部最优解，容易导致求解精度下降，进而增加任务的完工时间和执行成本；文献[11]使用改进的蚁群算法进行云计算资源调度，通过信息素的累积和更新寻找较精确的解决方案，但是由于求解初期信息素匮乏，导致求解速率较慢，这样可能会占用用户大量时间，不能很好地满足用户的服务质量需求；文献[12]提出了一种基于最早完成时间和PSO的自适应参数遗传算法，交叉概率的参数根据当前的演化状态进行自适应，以促进进化并找到更好的解决方案，缺点是只考虑了最小化完工时间，优化的目标过于单一；文献[13]将遗传算法和蚁群算法融合用于云计算任务调度，提高了云计算资源调度的效率，但是参数较多，编程实现较为复杂，且没有考虑云系统的负载均衡，任务过大或过多时，容易导致云系统运行异常。

为了弥补传统算法用于与计算任务调度的不足，本文综合考虑任务完工时间、执行成本、云系统负载均衡三个目标，提出了一种混合微生物遗传粒子群算法(MGA-PSO)用于云计算任务调度。该算法结合微生物遗传算法(MGA)和PSO的长处，在任务调度前期使用MGA缩小求解空间以提升寻优速度；在任务调度后期使用动态惯性权重的PSO进一步寻找并快速收敛到最优解。实验结果表明，MGA-PSO算法可有效减少完工时间、降低执行成本并平衡云数据中心虚拟机的负载。

1 云计算多目标任务调度

云计算利用并行化技术处理大量任务，在数据中心利用虚拟化技术建立一定数量的虚拟机，根据用户需求，将子任务分配到合适的虚拟机上执行。通常采用Map/Reduce编程模型，通过Map(映射)和 Reduce(化简)两个阶段， 将一个较大的任务分割成为很多较小的子任务，然后分配给若干个虚拟机并行执行，最后返回运行结果。该模型具有良好的扩展性和容错性，一台机器宕机时，可以迅速将任务转移到另外一个节点运行。本文只考虑子任务相互独立的情况，整个任务调度框架可简化为图1。

假设有t个相互独立的任务，如：A={α1,α2,…,αt},其中αi(0≤i≤t)表示第i个任务, 每个任务的大小为SIZEi；另假设云系统由p个高速互联的虚拟机组成，如：B={β1,β2,…,βp}，其中βj(0≤j≤p)代表第j个虚拟机，每个虚拟机具备一定的处理能力MIPSj，使用MGA-PSO算法将个任务调度到p个虚拟机上以非抢占方式执行(t>p)。

任务i在虚拟机j上执行时间的计算公式如下：

Tij=SIZEi/MIPSj

(1)

虚拟机j的释放时间RTj初始化为0，当有任务执行时其更新公式如下：

RTj=RTj+Tij

(2)

任务i是虚拟机j上的第一个任务时，其开始执行时间定义为0，否则定义为虚拟机j的释放时间RTj。

STij=RTj

(3)

任务i的完成时间为任务i在虚拟机j上的开始执行时间与执行时间之和，其公式如下：

FTij=STij+Tij

(4)

任务的最大完工时间为所有虚拟机释放时间的最大值，其更新公式如下：

Makespan=max{RTj|∀βj∈B}

(5)

云环境的负载均衡定义为所有虚拟机释放时间的标准差，其公式表示如下：

(6)

给云数据中心的内存、带宽、处理器和存储空间设置一定的单位价格，通过统计任务调度过程中各资源的使用量计算执行成本Cost。

云任务的调度过程是多目标优化问题，所以本文定义适应度函数为任务完工时间、执行成本及云环境负载均衡的加权和，用于衡量云计算任务调度的性能，其公式表示如下：

fitness=λ1×Makespan+λ2×LB+λ3×Cost

(7)

式中：λ1+λ2+λ3=1，可以根据任务需求灵活地调整各权重的值。任务调度的最终目标是最小化适应度函数的值。

2 混合微生物遗传粒子群算法

2.1 微生物遗传算法

John Holland教授于1975年提出了基于种群进化机制的遗传算法(GA)，该算法提出了一个自然选择的过程，随着时间的推移会产生更好的解决方案，具有并行搜索、群体寻优的特点，适用于大型空间的求解问题。

GA存在无法保留“好父母”的缺点：无论父母染色体多么优秀，都不会保留，只能进行交叉变异操作生成新的个体，但是新个体并不一定优于父母，容易导致解的精度不够。为克服此缺点，借鉴微生物遗传算法(MGA)[14]的思想，在种群每次迭代过程中，随机抽取两个染色体作为父染色体并比较其适应度，适应度好的父染色体不做任何处理，只对适应度差的父染色体进行改进的交叉操作和变异操作。如果变异后的子染色体适应度优于其父染色体，则将其与适应度好的父染色体作为下一代置于新种群上，否则，保留原种群。这样，可以有效保留种群中适应度好的父代染色体，大大提高了求解的精度。

MGA流程如图2所示。首先，通过随机创建染色体对种群进行初始化；其次，根据适应度值进行选择操作，选择一些染色体以创建新的种群；接着，随机选择两个父代染色体进行改进的交叉操作，在适应度好的父染色体上随机截取一个基因交叉点i，将第1到i个基因片段替代适应度差的父染色体对应位置；然后，对改进的交叉操作产生的子染色体进行基本位变异操作，即随机选择一个新基因去替换原有基因；最后，计算染色体的适应度，如果变异后的子染色体适应度更好，则将其取代适应度差的父染色体置于新种群上，否则，两个父代染色体仍置于新种群上。整个过程持续进行，直到满足终止条件，选择适应度最好的染色体作为最优解。

图2 MGA流程

2.2 改进的粒子群算法

2.2.1标准粒子群算法

粒子群算法(PSO)[15]是一种基于群体智能的优化算法，算法中的粒子类似于搜寻食物过程中飞行的鸟群，各个鸟群信息共享，它们总是搜索目前离食物最近鸟的周围区域，根据飞行经验去寻找食物。PSO的设计思想就是基于这种信息共享机制，任意时刻每个粒子位置都受个体最佳位置和问题空间中全局最佳位置的影响。PSO中粒子的性能可通过适应度函数来测量，根据适应度值判断粒子的好坏在每一次迭代中对粒子进行优化。为描述粒子群算法，相关参数定义见表1，算法中粒子速度和位置的更新公式如下：

表1 粒子群算法相关参数定义

(8)

(9)

式(8)右侧可以拆分为三部分：1) “惯性”，即粒子前一次迭代时速度的经验；2) “自我认知”，表示粒子当前位置与自身最佳位置的距离；3) “群体经验”，表示粒子当前位置与种群整体最佳位置的距离。PSO没有MGA的交叉、变异操作，需要设置的参数较少，编程实现简单且收敛速度快，可以用来加快求解速度。

2.2.2动态惯性权重的粒子群算法

惯性权重ω的取值影响PSO的性能。ω的值较大，有利于全局搜索，可以加快求解速度；ω的值较小，有利于局部搜索，能够提高解的精度。标准PSO中惯性权重ω的取值固定，不利于在算法运行过程中实现全局搜索和局部搜索的平衡。

在PSO运行的早期，粒子相对分散，具有较好的多样性，这时应该保持较大的惯性权重值，以增强算法的全局搜索能力；在算法运行的后期，粒子越来越聚集，这时应该保持较小的惯性权重值，以改善算法的局部搜索能力。很多算法将惯性权重设置为随迭代次数的增加线性递减，在一定程度上提高了算法的性能，但是线性递减策略对于动态系统的效果并不理想。因此，提出一种随迭代次数非线性递减的动态惯性权重策略，其数学公式描述为：

(10)

式中：ωmax表示惯性权重的最大值；ωmin表示惯性权重的最小值；n为当前迭代次数；N为最大迭代次数；α1、α2、α3为控制因子，对惯性权重进行调节，保证算法运行前期具有较大的权重值，加强全局搜索，从而加快求解速度，在算法运行后期，使权重值快速减小，加强局部搜索，从而提高解的精度。

2.3 混合微生物遗传粒子群算法

本文将MGA和改进的PSO融合，形成混合微生物遗传粒子群算法(MGA-PSO)用于云计算任务调度。在任务调度前期，使用MGA处理初始种群，因为MGA找到较精确的解需要训练很长的时间，所以本文提出：只迭代较少的次数以缩小求解范围，无须找到较精确的解决方案。在任务调度后期，利用PSO快速收敛到最优解的优点，使用改进的PSO对上一阶段产生的解决方案进一步优化，找到最优的解决方案，这一阶段可以迭代多次，从而提高解的精度。MGA全局搜索能力强的优点，可大大缩小求解范围，提高解的精度，避免PSO在进一步优化解决方案时陷入局部最优解。而PSO快速收敛到最优解的优点，减少了云计算任务调度的时间，弥补了MGA需要较长时间找到精确解的缺点。

MGA-PSO算法用于云计算任务调度之前，需要建立云计算任务调度的解决方案与算法中染色体和粒子的对应关系。假设云系统有8个任务和3个虚拟机，在使用MGA阶段，每个染色体由代表虚拟机的一些基因组成，染色体的长度等于云任务的数量，该阶段可以定义染色体的长度为8，基因的种类为3。在使用改进的PSO阶段，粒子是要分配的任务，粒子的维度是要分配的任务数，分配给粒子的每个维度的值是虚拟机编号，该阶段可以定义粒子的维度为8，每个维度的值只能取0、1或2。

图3展示了这种对应关系，它既可以表示一条染色体，又可以表示一个粒子。当表示一条染色体时，第0个基因的值为1，代表任务0被分配给虚拟机1；第3个基因的值为2，代表任务3被分配给虚拟机2。当表示为一个粒子时，第1维取值为0，代表任务1被分配给虚拟机0；第7维取值为2，代表任务7被分配给虚拟机2。

图3 一条染色体或一个粒子

MGA-PSO算法用于云计算任务调度的流程如图4所示，其执行步骤总结如下。

图4 MGA-PSO算法流程

1) 生成随机种群并指定迭代次数，种群表示任务调度的一系列解决方案，每个解决方案是云任务在可用虚拟机上的分布。

2) 使用MGA缩小求解范围，云计算任务调度的解决方案在这里被称为染色体，通过MGA算子(即选择、交叉、变异)在每次迭代中保留适应度较好的染色体，将得到的染色体传递给改进的PSO。

3) 使用改进的PSO进一步优化解决方案，来自MGA的染色体被称为粒子，在每次迭代中通过式(8)-式(10)逐渐增强粒子。

4) 根据式(7)选择具有最佳适应度的粒子作为云计算任务调度的解决方案。

3 仿真实验与性能分析

3.1 实验环境及参数设置

为了评估MGA-PSO算法的性能，使用墨尔本大学开发的CloudSim[16]云仿真平台进行仿真实验，其运行的硬件环境为Intel i7处理器，16 GB DDR4内存，1 TB硬盘空间，Windows 10系统。CloudSim支持云计算的研究与开发，用户编写的算法可以在此平台上测试运行，减少了搭建云平台的时间和成本。本文的仿真实验将MGA-PSO算法用于云计算任务调度并与现有的云任务调度算法作比较，它们是GA和PSO。另外编写一个和本文算法原理相同的GA-PSO算法，验证对GA和PSO改进的必要性。

实验中四个算法各自运行22次，去除实验结果的最大值和最小值，取剩下20次实验结果的平均值作为有效比较数据。算法中的相关参数设置见表2。

表2 算法的相关参数

续表2

3.2 性能分析

图5显示了四种算法用于云计算任务调度时的寻优效果，任务数设置为500。可以看出，GA和PSO用于云计算任务调度的寻优效果一般，过早的陷入了局部最优。GA-PSO算法和MGA-PSO算法的适应度有一段时间没有变化，可能陷入了局部最优，但是随着迭代次数的增加，都能迅速跳出局部最优，并且能够快速找到最优解。本文MGA-PSO算法最终的适应度最低，寻优效果最好，具有较强的全局搜索能力。

图5 四种算法用于云计算任务调度的寻优曲线

图6和图7显示了小规模任务下四种算法完工时间和执行成本的对比效果，任务数设置为20、40、60、80、100。从图6可以看出，GA和PSO用于云计算任务调度会花费较多的时间，当任务数增加时，GA的完工时间增幅最快。整体上MGA-PSO算法的完工时间低于GA-PSO算法，该结果是因为所提出MGA在迭代过程中保留了适应度好的父代染色体，提高了解的精度，能以更好的方式收敛到解决方案。从图7可以看出，GA的执行成本最高，可能原因是发生了“早熟”收敛；MGA-PSO算法和GA-PSO算法及PSO用于小规模任务调度的执行成本相差不大，这种微小的差异是由于所提出的混合算法主要依赖于PSO将解决方案收敛到最优解，任务规模越小差异越小。

图6 小规模任务四种算法的完工时间

图7 小规模任务四种算法的执行成本

图8和图9显示了大规模云任务下四种算法完工时间和执行成本的对比效果，任务数设置为200、400、600、800、1 000。从图8可以看出，进行大规模云任务调度时， MGA-PSO算法和GA-PSO算法在完工时间方面具有较大优势，随着任务规模的增加，MGA-PSO算法的完工时间明显低于GA-PSO算法。这是由于任务规模变大，生成的初始种群更加随机，在MGA-PSO算法前期能保留较多优秀的父代染色体，大大提高了解的精度。从图9可以看出，在执行成本方面，当任务调度时，任务规模越大，MGA-PSO算法优势越明显。这是因为动态惯性权重的PSO的改进有效平衡了算法的全局搜索能力和局部搜索能力，能够找到更为合适的解决方案。

图8 大规模任务四种算法的完工时间

图9 大规模任务四种算法的执行成本

图10为四种算法用于云计算任务调度时的虚拟机负载均衡对比效果，任务数设置为20、80、200、1 000。可以看出MGA-PSO算法的负载均衡效果比GA和PSO好很多，这是因为MGA-PSO算法将任务完工时间、执行成本、云系统负载均衡三个目标作为任务执行时虚拟机选择的依据，总是选择最合适的虚拟机来执行任务，而不仅仅关注虚拟机的处理能力，这可能会选择处理能力稍弱的虚拟机处理云任务，并减慢云任务的整体执行速度(即增加完工时间)，但是在其他方面会有改善，例如虚拟机负载更加均衡，执行成本更低。灵活地调整适应度函数中各权重的值可以满足不同方面的需求。

图10 虚拟机负载均衡效果对比

无论是在完工时间、执行成本还是虚拟机负载均衡效果方面，MGA-PSO算法的调度性能都优于同种思想的GA-PSO算法，可见对GA和PSO的改进提升了云计算任务调度的性能。

4 结 语

针对GA和PSO各自的优缺点，本文将MGA(“升级版”GA)与改进的PSO组合成MGA-PSO算法用于云计算任务调度。该算法充分考虑了体现用户服务质量的完工时间、执行成本和云系统负载均衡三个目标，并根据这些目标建立适应度函数作为算法运行时虚拟机选择的依据。仿真结果表明，MGA-PSO算法在完工时间、执行成本和负载均衡方面都优于GA、PSO和GA-PSO算法，能够满足用户的服务质量需求，有效提高云计算任务调度的效率。