一种改进的遗传算法在云计算中的应用

陈晓燕，姚高伟，张 鲲，王海丰

(1. 琼州学院 计算机工程学院，海南 三亚 572022；2. 信阳师范学院 城市与环境科学学院，河南 信阳 464000)

0 引言

随着计算机的发展，人们对其存储和传输能力的要求也随之变高，云计算应运而生.云计算是一种大规模的分布式计算模型，它把存储于个人电脑、移动电话和其他设备上的大量信息和处理器资源集中在一起，协同工作.它充分利用虚化技术，将用户从软件、硬件和资源的管理中解放出来，并将这些负担转移给云计算服务供应商[1].

为了充分利用云计算的各种优势，将人们从繁重的资源管理中解脱出来，人们已经将所有的任务放在了云环境下执行.大量的任务放在云环境下，使得云计算系统每时每刻都处在海量任务之中[2-3].因此，对用户提交的海量任务进行有效的调度，使得用户提交的任务处理时间短，所需的费用低，并且保证云系统负载均衡，是云计算技术中研究的重点问题.

目前解决云环境下的任务调度问题主要是从任务执行所花费的时间以及执行任务所需的费用方面展开的，国内外对于云环境下任务调度问题的算法研究成果还比较少.文献[4]提出了基于蚁群算法的云计算资源调度算法，在算法的设计中，只考虑了对任务执行时间进行优化，没有考虑到任务调度中其他的问题.文献[5-6]提出了多目标遗传算法，算法中涉及的任务调度优化目标过多，在遗传算法下，优化目标过多，会造成局部收敛，而难以达到全局优化.本文将任务调度中执行任务所需时间和执行任务所需费用这两个重要的因素作为优化目标，提出了改进的遗传算法，仿真实验验证了其良好的性能.

1 任务调度与遗传算法

1.1 任务调度概述

目前云计算中的调度方式大多采用的是预分配机制下的静态资源调度方法，这种方式下的任务调度，没有体现“按需分配”的思想，会出现小任务调用大资源的情况，造成资源的不必要浪费[7].在云计算中，任务调度的核心技术在于所采用的调度算法.国内外的很多专家、学者针对云计算中的任务调度，提出了一些算法，如蚁群算法、粒子群算法、遗传算法，其中用得最为广泛的是遗传算法.但是传统的遗传算法自身有缺陷，如迭代次数多，算法运行耗时长，这样大大降低了整个云计算环境的性能.云计算中的任务调度如图1所示.

图1 云计算中任务调度图

云计算的任务调度过程分三个阶段，其中最重要的阶段就是调度技术所处的阶段，调度技术的优劣直接关系到任务调度的结果.云计算中所采用的任务调度技术，就是把不同的任务分配到合适的虚拟机上的方式，具体的过程如下：(1)给所有的任务开始分配虚拟机；(2)任务分配结束后，虚拟机开始执行任务；(3)任务执行出相应的结果(即调度结果).所得出的调度结果就是评价这个调度技术优劣的标准.

1.2 遗传算法

遗传算法(Genetic Algorithm，简称GA)起源于20世纪60年代，借鉴生物学中进化论的思想，从中提取的一种进化算法，借助计算机模拟在种群的繁殖过程中，父代遗传基因的重组和优胜劣汰，主要用来解决科学研究中的复杂问题[8].遗传算法的步骤如图2所示.

对于云计算中的资源，最完美的状态是用户的请求得到满足，并且处理速度快，所花的费用少，所用的资源管理代价最小.这对云计算中的任务调度来说，是一个NP难问题[9].遗传算法是一种仿生型优化算法，通过生物学中的优胜劣汰原理，将最优的个体遗传到下一代，这种算法思想使得算法的并行性和全局寻优能力得到了最大的体现，也使得遗传算法在解决NP难问题中有绝对的优势[10].

云环境下的任务调度是保证用户服务质量，提高云环境下资源利用率的关键.因此，针对传统遗传算法存在的问题，本文结合遗传算法的全局寻优能力，提出了一种改进的遗传算法，将其应用于云计算中的任务调度，主要从执行时间以及执行任务所需的费用这两个方面来进行优化，用此算法去求解云环境下的任务调度问题.

图2 遗传算法流程图

2 改进的遗传算法在云计算中的设计

在云环境下，将任务执行所花费的时间以及所需的费用作为适应度函数，充分考虑了云环境的弹性功能，避免了在无限资源的云环境下，将初始问题变成单一标准问题或单一约束问题.本文选取的时间函数和费用函数虽然忽略了云环境下的能量消耗、网络可靠性，但从总的来说，是从用户的角度来看待问题的，考虑的是用户最关心的问题，让用户得到了更好的体验，体现了云计算面向服务的宗旨.

2.1 任务调度模型设计

对于云环境中的任务、虚拟机以及任务与虚拟机之间的关系进行数学描述如下.

(1)任务序列为task={t1,t2,…，tm},其中t1代表第1个任务，依次类推，tm代表第m个任务.

(2)虚拟机序列为vm={vm1,vm2,…,vmn},其中vm1代表第1个虚拟机，依次类推，vmn代表第n个虚拟机.

(3)任务与虚拟机的关联,vm(ti)表示执行任务(ti)的虚拟机.

2.2 染色体编码

在遗传算法中用染色体编码表示种群中的个体，在云环境下的任务需要分配到虚拟资源上，一个染色体表示一种任务分配方案.每个染色体中，基因数目和任务数量相等，基因的值最高为虚拟机数量.本文使用二维串的方法作为调度方案：一维表示任务到资源当中的映射,另一维则表示任务的执行顺序.编码前，先对任务建立一个关系矩阵JZ,用JZij来表示任务ti和tj之间的关系.如果JZij=1，ti是tj的父任务；如果JZij=0，则表示任务ti与任务tj没有关系.

先对任务到资源当中的映射进行编码，然后再对第二维进行编码，具体的操作步骤如下：

(1)初始化.假定集合set为空，存放始任务(即没有父任务的任务).

(2)依据关系矩阵JZ，将父任务已经调度完的任务，或者是没有父任务的任务放入集合set中，通过JZij的值来判断任务的调度情况.

(3)对二维串上第一个没有被调度的任务进行判断，如果它在集合set中，就把它放进调度序列中去.

(4)将步骤(3)中被调度的任务从集合set中除去.

(5)重复步骤(2)至步骤(4)，直到调度完所有的任务.

2.3 适应度函数设计

在遗传算法中，各个解的优劣是通过适应度函数来衡量的，适应度值高的个体将会遗传到下一代中去，而适应度值低的个体则在遗传的过程中被淘汰掉.因此，适应度函数其实就是目标优化函数.然而，传统的遗传算法一般是以单个目标来设计适应度函数的，而云环境比较复杂，所要考虑的目标不再是单一的，因此，传统的遗传算法不适用于云环境中的任务调度.

本文主要考虑的是云环境下任务调度中两个重要的优化目标：时间目标和费用目标.

本文改进的遗传算法用在云计算中，使得云环境下任务调度完成任务的时间最短，所需的费用最低，因此，约束函数由两个组成:一个是时间目标函数，一个是费用目标函数.

(1)时间目标函数

最早开始执行时间设为ts,最早结束时间设为tf,进入系统的任务设定为tinput,对于ts和tf,可建立如下的关系式：

ts(tinput)=0,

(1)

tf(tinput)=ts(tinput)+te(ti,vmj),

(2)

其中：te为任务执行时间，vmj表示在虚拟机上执行的第j个任务.

对于其他任务来说，ts和tf的值可以通过递归的方式进行计算得出，式子如下：

tf(ti)=ts(ti)+te(ti,vm(ti)),

(3)

(4)

其中：set(ti)是任务ti父结点的集合，一个任务可以有很多个父节点，子节点执行任务，必须等到所有父节点执行完之后，子任务开始执行的时间为集合set(ti)中数据最晚到达子任务的时间；tt为传输时间.

(2)费用目标函数

云环境下执行任务的费用由两部分组成：数据传输所需的费用、虚拟机执行任务所需的费用.费用目标函数表示如下：

(5)

其中：ec为单个任务执行的费用，vm(ti)表示执行任务(ti)的虚拟机，tc表示在虚拟机vm(ti)上执行的任务(ti)产生的数据传输给在虚拟机vm(tp)上执行的任务(tp)所产生的费用.

2.4 界限函数

对于时间目标函数和费用目标函数，关键在于求其下限，下限的求解方法如下：

(1)时间界限函数

时间界限函数求解的是在虚拟机上执行任务的时间最小值，计算方法如下：

tt(ti,tj)=et(tj,vm(ti))-et(tj,vm(tj)),

(6)

其中：tt为传输时间，et为单个任务的执行时间，tj表示任务j，vm(ti)表示执行任务(ti)的虚拟机.

(2)费用界限函数

费用界限函数求解的是在虚拟机上执行任务的费用最小值，计算方法如下：

tc(ti,tj)=ec(tj,vm(tj))-ec(ti,vm(ti)),

(7)

其中：tc为传输费用，ec为单个任务执行的费用.

对于云计算环境下的用户来说，任务调度所需的时间和费用是越少越好，综合上文的时间目标函数和费用目标函数，适应度函数如下：

f=ωts(ti)+(1-ω)cost，

(8)

其中：ω为权重系数，其值在0到1之间，任务执行的时间越少，ω越大；任务执行所需的费用越少，ω越小.当ω=1时，则是从时间的角度进行优化；当ω=0时，则是从费用的角度进行优化.

2.5 遗传操作

(1)选择算子

本文改进的遗传算法主要是从时间函数和费用函数这两个角度来考虑的，算子的选择既要维持多样性，又要保证收敛性.在遗传算法中,是通过轮盘赌的方式来表示选择算子，个体的适应度值越大，则被选中遗传到下一代的概率就越大；个体适应度值越小,则被选中的概率越小.

染色体的适应度值为f,选择概率为g，则可建立如下的式子：

(9)

(2)交叉算子

交叉算子是遗传算法中重要的操作，交叉操作在一定程度上克服了遗传算法的早熟收敛问题，可以保证种群中个体多样性.

交叉操作的本质是希望通过组合的方式，产生比较优秀的个体.本文进行交叉操作的具体步骤如下：

(i)从所有的任务资源中随机选取两个任务作为父代个体.

(ii)从(i)中产生的父代个体中选取一个作为交叉点，进行变异的部分即为交叉点之前的任务和处于交叉点的任务.

(iii)根据矩阵JZ，重新分配任务的执行顺序，产生两个新的个体.

(3)变异算子

变异是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体.变异操作的具体步骤如下：

(i)从所有的任务资源中随机的选取一个任务作为父代个体.

(ii)从(i)中产生的父代个体中随机选择变异点，然后将一个可执行的虚拟资源分配给处于这个变异点的任务.

(iii)根据矩阵JZ，重新分配任务的执行顺序，产生两个新的个体.

2.6 算法终止条件

同其他算法一样，云环境下的任务调度算法同样需要有算法终止条件来终止算法.在云环境下的任务调度，时间与花费成反比的关系，本文采用迭代的次数作为算法终止条件，当迭代次数达到一定数量，就是算法预期的结果.

3 仿真实验及结果分析

仿真实验主要目的是将本文的改进遗传算法应用到不同的云计算模拟场景中，对改进的遗传算法与传统的遗传算法进行对比实验，分析实验的结果，以验证该改进的遗传在云计算中的有效性.

3.1 实验设备

本实验用到的设备有：操作系统Windows XP，MyEclipse，云仿真模拟器CloudSim.

3.2 参数设计

云环境下，假设资源是无限的，可以按照实际的需求使用，虚拟机上能执行任何任务.验证算法在云环境中所起到的作用，假设种群的规模为20，任务数为20，虚拟机个数为5，变异概率为0.1，迭代次数为100，在算法结束后，对最后一代中各个解个体的分布情况进行验证.图3和图4是将改进的遗传算法用于任务调度与传统遗传算法的任务调度，所需的平均等待时间以及所需费用的对比图.

从图3中看出，在任务数目同等的情况下，改进的遗传算法下的平均等待时间比传统遗传算法相对来说所需少些.从图4中可以看出，时间相同的情况下，改进的遗传算法下的任务调度所需要的费用要比传统遗传算法下的低.

图3 平均等待时间对比图

图4 执行任务所产生的费用对比图

4 结论

本文提出了改进的遗传算法应用于云计算中的任务调度，并针对任务调度中的执行时间和费用，设计了适应度函数、交叉算子、变异算子.实验结果表明，在云环境下，该算法应用于任务调度有一定的优势.