基于云计算任务调度的遗传粒子群优化算法

Genetic and Particle Swarm Optimization Algorithm Based on Cloud Task Scheduling

摘要: 云平台的任务调度算法是云计算领域研究的热点。如何在满足不陷入局部最优解的同时有更快的收敛速度，一直是研究者追求的目标之一。为此，本文提出将改进随机因子和惯性权重的增强型粒子群算法(EPSO)引入到遗传算法(GA)变异操作中的增强型遗传粒子群混合算法(GA_EPSO)。通过EPSO算法中的当前最优解和全局最优解重构变异算子，探索提升GA_EPSO算法在不陷入局部最优解的条件下，有更快的收敛速度。仿真实验表明，相同条件下，与遗传算法(GA)，改进后的遗传算法(IGA)，粒子群算法(PSO),增强型粒子群算法(EPSO)以及遗传粒子群算法(GA_PSO)相比，本文提出的改进算法不仅收敛速度快，而且任务调度效率也有明显提升。

Abstract: The task scheduling algorithm of cloud platform is a hot topic in the field of cloud computing. How to achieve faster convergence speed while not meeting the local optimal solution has always been one of the goals pursued by researchers. To this end, this paper proposes an enhanced genetic and particle swarm optimization algorithm (GA_EPSO) that introduces an enhanced particle swarm optimization algorithm (EPSO) with improved random factors and inertia weights into mutation operations in genetic algorithm (GA). Reconstructing the mutation operator by the current optimal solution and the global optimal solution in enhanced particle swarm optimization algorithm, the enhanced genetic and particle swarm optimization algorithm has a faster convergence speed without falling into the local optimal solution. Simulation experiments show that under the same conditions, compared with genetic algorithm (GA), improved genetic algorithm (IGA), particle swarm optimization (PSO), enhanced particle swarm optimization (EPSO) and genetic particle swarm optimization (GA_PSO), the algorithm not only accelerates the convergence speed, but also has a significant improvement in task scheduling efficiency.

1. 引言

云计算作为当今IT界的热点技术，从产生便受到各领域学者的广泛关注，它拥有强大的处理能力，其中关键技术就是基于云计算任务调度算法的设计与应用。如何合理地分配和利用云环境中的资源、有效地调度用户提交的海量任务且保证云系统的负载均衡成为云计算研究的重点。探究在云计算环境中的优秀调度算法已成为专家学者们研究的重点内容之一 [1]。因此，具有简单、通用、鲁棒性强、适于并行处理等优点的智能算法很快成了云计算任务调度领域的研究热点，例如通过模拟自然界进化过程，从而得到最优解决方案 [2][3][4]的遗传算法(GA) [5]、粒子群算法(PSO)以及蚁群算法(ACO)等等，以求解最小化任务完成时间和代价的最优解，但忽略了在进行任务调度时，智能优化算法本身缺点对调度工作的影响。基于此，本文将提出一种混合优化算法，算法的目标除了确保任务完成时间最小化，还将改善任务调度算法存在的缺点。

2. 相关工作

任务调度策略直接影响用户应用任务的服务质量和云计算系统的运行效率，同时还需考虑到云计算系统的负载平衡、资源利用率、系统能耗以及运营成本等诸多因素，因此单一的智能算法难以较好的满足需求，例如蚁群算法搜索时间长、收敛速度慢，易陷入局部最优解；粒子群算法易陷入局部最优解；遗传算法收敛速度慢 [6]。为了更好地解决云计算任务调度问题，混合智能优化算法应运而生。

混合算法，即利用一种算法的优点弥补另一种算法的缺点，使结果更优。张雨等人 [7]针对蚁群算法初期信息素缺乏导致求解速度慢的问题，提出利用遗传算法生成的优化解初始化蚁群信息素分布，结果表明改进后的算法在考虑负载均衡的情况下提高了求解速度，是一种云计算环境下有效的任务调度算法。徐洁等人 [8]为了满足云计算平台庞大用户群的不同服务需求，提出一种基于双适应度遗传退火的云任务调度算法，结果表明混合后的算法能兼顾云计算平台总任务执行时间和用户需求，更好地满足用户需求，提升服务的多样性。王波等人 [9]为解决PSO算法易陷入局部最优解的问题，提出在PSO算法中加入GA算法的交叉、变异操作，结果表明与传统PSO和GA算法相比，混合后算法减少了任务的完成时间。陈璐璐等人 [10]为解决GA算法计算时间长和PSO算法易陷入局部最优解的问题，提出将粒子群思想引入变异算子，结果表明该算法在收敛性和运算速度等方面具有优越性。刘露等人 [11]为同时满足全局优化能力强且收敛速度快，提出在GA算法的变异、交叉、淘汰环节引入PSO算法，结果表明相对于普通GA或者PSO算法，该算法收敛能力有所提高。刘春燕等人 [12]针对GA算法迭代过程反馈信息不够引起最优解质量不高的问题，提出在在变异操作中引入PSO算法，结果表明改进后的算法在总体性能上优于GA算法和PSO算法。王登科等人 [13]为了使系统更加高效的完成任务，提出将粒子群与蚁群结合的任务调度优化算法，结果表明改进后的算法具有较好的实时性和寻优能力。赵莉等人 [14]为了提高智能优化算法的性能，将其更好地应用于各个领域，提出在改进的量子遗传算法基础上，进一步结合粒子群算法，结果表明改进后的算法在性能上有所提高。秦军等人 [15]针对蚁群算法在任务调度中存在收敛速度慢、局部搜索能力差和易于陷入局部最优的问题，提出将蚁群算法和模拟退火算法相结合，结果表明改进后的算法在减少任务的完成时间和计算资源负载均衡等方面明显优于先来先服务和标准蚁群优化算法。

以上各种混合智能算法虽然同时结合二者的优点，在一定程度上加快收敛速度且降低任务完成时间，提高了任务调度效率，但还有进一步提升的空间。针对该问题，本文以最小完成时间、最快收敛速度为目的，提出增强型遗传粒子群混合算法(GA_EPSO)，算法的特点是在对惯性权重和随机因子改进的同时，将粒子间信息传递的特性引入GA算法，较好的满足了云平台对任务调度算法的需求。

3. 云计算任务调度问题分析

任务调度是保证用户能够及时得到云服务器响应和处理的关键，高效的调度策略可以提高系统对用户请求的响应速度和服务质量。因此，如何针对现有资源对云任务进行合理的分配与调度，提高云计算资源的利用率，并极大程度地满足用户需求是资源分配亟待解决的问题。

云计算平台中包含两个层面的任务调度 [16]，第一层是任务集合到虚拟机集合的调度，第二层是虚拟机集合到物理机集合的调度，本文主要研究第一层调度，调度对象是任务集合，任务调度策略就是寻找该任务集合和云平台可用虚拟资源集合之间的映射关系。

4. 基于增强型遗传粒子群混合算法(GA_EPSO)的任务调度

4.1. 算法建模

为了明确云计算环境下的任务调度问题，作如下假设：

1) 任务的长度在一定范围内随机选取；

2) 所有云计算资源被映射成虚拟机，且虚拟机的性能在一定范围内随机选取；

3) 提交的任务数量远远大于虚拟机数量。

因此，云任务调度问题可描述为：如何将m个长度不同的任务合理地映射到n个性能不同的虚拟机运行，使任务完成时间最短。

4.2. 遗传编码

遗传算法往往根据实际问题设置个体编码方案，常见的GA编码方式有二进制编码和实数编码。对于信息量较大的问题，使用二进制编码会使编码过于冗长，增加算法的计算量，影响算法性能。因此，本文采用实数编码，该方法适用于表示取值范围较大的数，并且对染色体处理的复杂度大大降低，提高了算法的精度。

4.3. 算法设计思想

为了得到总任务完成时间最小且收敛速度最快的调度结果，在任务调度过程中，先利用遗传算法全局搜索能力强的优势，通过选择、交叉、变异等操作找到任务分配的较优解，然后在变异操作中引入PSO算法，更有效地产生接近目标的新个体。

4.4. 适应度函数

本文以任务的总完成时间为目标，因此将所有任务的完成时间作为适应度函数。具体公式如下所示：

$\text{fitness}=\max \left({\text{time}}_i\right),i\in \left\{0,1,2,\cdots ,n-1\right\}$ (1)

其中，time_i表示在虚拟机i上完成所有任务的时间，n表示虚拟机的数量。根据适应度函数可知，当代种群中个体适应度越低，表示所有任务完成时间越短，越不容易被淘汰。

4.5. 遗传操作

遗传算法主要通过选择、交叉以及变异三个遗传操作不断产生新个体，从而选出最优解。

选择操作使用轮盘赌法。在选择过程中，通过个体适应度值确定个体被选择的概率，具体计算方法如公式(2)所示。

$p_i=1/\left(f\left(i\right)\ast \theta \right)i\in \left(1,2,3,\cdots ,n\right)$ (2)

$\theta ={\displaystyle {\sum }_{i=1}^{n}f\left(i\right)},i\in \left(0,1,2,\cdots ,n\right)$ (3)

其中，n表示种群中所有个体数量， $f\left(i\right)$ 表示个体适应度值，θ表示所有个体适应度值倒数之和，p_i表示第i个个体被选中的概率。

交叉操作采用双点交叉法，左右交叉点随机选取。

变异操作引入增强型粒子群算法(EPSO)。传统变异既不考虑历史状态，也不考虑变异算子的优良性，从而影响算法的收敛性。本文通过PSO算法中的当前最优解和全局最优解重构变异算子。

$v_{id}\left(t+1\right)=\omega v_{id}\left(t\right)+c_1{r}_1\left(t\right)\left(p_{id}\left(t\right)-x_{id}\left(t\right)\right)+c_2{r}_2\left(t\right)\left(p_{gd}\left(t\right)-x_{id}\left(t\right)\right)$ (4)

$x_{id}\left(t+1\right)=x_{id}\left(t\right)+v_{id}\left(t+1\right)$ (5)

其中，GA算法中第i位上的最优解代替式(4)中的 $p_{id}\left(t\right)$ ；GA算法中的历史最优解代替式(4)中的 $p_{gd}\left(t\right)$ 。r₁和r₂是相互关联且服从均匀分布的随机因子。ω是自适应惯性权重，具体采用式(6)计算。

$\omega \left(t\right)=\left({\omega }_{\max }-{\omega }_{\min }\right)p_s\left(t\right)+{\omega }_{\min }0\le {\omega }_{\min }\le {\omega }_{\max }$ (6)

其中， $p_s\left(t\right)$ 表示粒子群在第t次迭代时的成功率，计算方法如公式(7)所示。

$p_s\left(t\right)={\displaystyle {\sum }_{i=1}^{n}S\left(i,t\right)}/n$ (7)

其中，n表示粒子个数， $S\left(i,t\right)$ 表示粒子i在第t次迭代过程中的成功值，计算方法如公式(8)所示。

其中， ${\text{pbest}}_i^t$ 表示粒子i在第t次迭代时的最优位置， ${\text{globalbest}}^t$ 表示全局最优值， $\text{fitness}\left({\text{pbest}}_i^t\right)$ 表示粒子i在第t次迭代时最优位置的适应度值。

引入PSO算法的变异操作能够根据历史最优解和个体最优解影响变异的方向和幅度。

$S\left(i,t\right)=\{\begin{array}{c}1,\text{fitness}\left({\text{pbest}}_i^t\right)<\text{fitness}\left({\text{pbest}}_i^{t-1}\right)\\ 且\text{fitness}\left({\text{pbest}}_i^t\right)<{\text{globalbest}}^t;\\ 0.5,\text{fitness}\left({\text{pbest}}_i^t\right)<\text{fitness}\left({\text{pbest}}_i^{t-1}\right)\\ 且\text{fitness}({\text{pbest}}_i^t)\ge {\text{globalbest}}^t;\\ 0,\text{fitness}\left({\text{pbest}}_i^t\right)=\text{fitness}\left({\text{pbest}}_i^{t-1}\right)\end{array}$ (8)

5. 仿真试验与分析

5.1. 实验环境及参数设置

本文利用CloudSim构建云环境任务调度模拟平台，Eclipse作为开发平台，将本文提出的GA_EPSO算法与PSO算法、EPSO算法 [17]、GA算法、IGA算法 [18]以及GA_PSO算法 [12]进行对比分析。其中，算法参数见表1。

5.2. 实验结果分析

为了验证GA_EPSO算法的有效性，本文主要从任务完成时间和算法收敛性两个方面与其他算法进行比较。实验设置任务数从50到500变化，迭代200次的时间结果对比图，如图1所示。

其中，横坐标代表任务数量，纵坐标代表所有任务完成时间。从图1可以看出，GA_EPSO算法进行任务调度所用时间明显低于PSO算法和EPSO算法。当任务数量小于等于150时，GA_EPSO算法的总任务完成时间略低于GA，IGA和GA_PSO三种算法，但差距不明显。随着云任务数量的不断增加，GA_EPSO算法的效果明显优于其他三种算法。总而言之，进行任务调度时，GA_EPSO算法的效率高于其他几个算法，且任务数量越多，该算法的优势越明显。

图2是基于200个任务时，六种算法收敛性的比较。

其中，横坐标代表迭代次数，纵坐标代表适应度值。从图2可以看出，GA_EPSO算法的适应度最小，换句话说也就是任务完成时间最短。随着迭代次数的增加，PSO、EPSO、GA、IGA以及GA_PSO五种算法大概从迭代100次开始收敛，适应度值逐渐趋于稳定，但GA_EPSO算法不仅在GA算法中引入PSO算法影响变异操作，而且改进了PSO算法中的随机因子和惯性权重，因此GA_EPSO算法大概从迭代50次开始收敛，收敛速度明显提升。

Table 1. Algorithm parameter setting

表1. 算法参数设置

Figure 1. Comparison of time

图1. 时间比较

Figure 2. Comparison of convergence

图2. 收敛性比较

6. 结束语

本文研究基于云计算任务调度问题时，针对单一算法无法在考虑最小任务完成时间的同时满足较高质量最优解和较快收敛速度的问题，提出将EPSO算法引入到GA算法变异操作的GA_EPSO算法。仿真实验证明，相比于其他五个算法，GA_EPSO算法既加快了收敛速度，又使算法在最短时间内找到最优解。但本实验目前仅优化了任务完成时间，真实的云环境还需考虑其他因素，因此有必要进一步改进和完善该算法。

基金项目

国家自然科学基金(61363016, 61063004)；内蒙古自然科学基金(No. 2015MS0605, No. 2015MS0626, No. 2015MS0627, No. 2017MS0605)；内蒙古教育厅高校研究项目(NJZC059)；内蒙古自治区高等学校科学研究重点项目(NJZZ14100)；教育部留学人员基金([2014]1685)；内蒙古自治区科技计划项目：穿透降水量GSM网络在线监测与数据传输系统。

NOTES

^*通讯作者。