基于改进蚁群算法的云环境任务调度研究(2)

1204 计算机测量与控制 第19卷

ij:表示t时刻蚂蚁由城市i转移到城市j的启发信息,一般取 ij=;

dij

k

pij(t):表示t时刻蚂蚁由城市i转移到城市j的概率,计算公式为:

[ ij(t) [ ij]

,j tabuk

[ t ikik

pk(1)ij(t)=k tabu

间的距离来表示,而在云环境中需要用资源的计算和通讯能力

等相关系数来表示信息素。

(3)启发信息也起着非常重要的作用,在云环境中,需要以资源固有的属性(如计算和通讯能力等),来表示在蚁群算法中的启发信息。

基于以上3点,蚂蚁根据当前的资源信息量,决定分配给云计算环境现有资源的下一个任务的概率的计算方法也作相应改变如下:p(t)=

ijk

k

0,j tauk

, 分别代表留信息的重要程度和启发信息的重要程度。

(1)初始化。将每条边上的信息素初始化为一个很小的常数值,将m只蚂蚁随机地放置到n个城市,并将出发点城市设置到禁忌表tabuk中。

(2)蚂蚁根据式(1)选择下一个城市,并修改禁忌表。(3),(2)更新该边信息素。

& ijk(2) ijt+1=(1- ) ijt+

Q/lp,当蚂蚁k走过城市ij时

ijk=

0,其它

其中,ljb是蚂蚁k从开始城市到当前城市已走过的路径长度。 表示信息的持久性。

(4)计算最佳路径。当全部蚂蚁走完所有城市后,按式(3)计算最优路径长度并保留。

lmin=minlk,k=1,2,...,m(3)

lk第k只蚂蚁所走路径长度。

(5)当所有蚂蚁走完全部城市以后,仅对最优路径上的信息素按式(4)进行更新。

new ij=(1- ) old k(4)ij+ ij

式中, 为全局信息素挥发系数,lk为最优路径长度。

(6)如果设置的迭代次数未完,则清空禁忌表,重复上述过程。

k

( kt

,j,k 云计算现有资源

其它

(5)

0,

式中, j(t)是t时刻资源的信息素浓度; j表示资源的固有属性, j= j(0); 表示信息素的重要程度; 表示资源固有属性的重要程度。

蚂蚁路径变异的个数可由随机数产生,产生随机数可以通过Integer.parsedouble(Math.random()*10)Java代码实现。

本文中云环境资源调度的目标是:在云环境下将M个任务分配到N个资源上,通过改进的蚁群优化算法计算任务在各个资源上执行的平均最短时间,实现系统的资源最优化。即求下面函数的最小值[7]。

minF(mi)=

式中,

mifi(mi)

,i=1,2,...,N

M

(6)

i

mi=M,M是在给定时间段内提交给云计算环境的

总的任务数量,mi表示在资源i上分配mi个任务,0 mi Mmax,Mmax表示在资源i上所能执行的最大任务并行数,可以ii

用实验确定。

云环境下,基于蚁群优化算法的任务调度算法执行流程图如下。

2 改进的蚁群优化算法与云环境下的任务调度

蚁群优化算法有很多优点。目前,提出的蚁群改进的优化算法多种多样,取得了非常好的效果。但是由于算法随机性很大,在解决大规模优化问题时容易限于局部最优解、收敛速度慢的缺陷。本文引入遗传算法,结合它快速随机的全局搜索能力,将遗传算法融入到蚁群优化算法的每一次迭代中,提高了收敛的速度,还保证了原算法的求解精确性。同时引入了逆转变异策略[5],避免了陷入局部最优的风险,维持和增加了种群的多样性。基于这种改进的蚁群优化算法,云计算服务集群可以快速实现资源发现、资源匹配、调度产生、任务执行以及蚂蚁路径的逆转变异。

对于每个资源请求者,云环境服务集群必须推荐出一个较优的任务与资源的组合。采用改进的蚁群优化算法来搜索当前分配策略中的最佳策略,在同一时间内,影响资源状态的因素都可以由信息素来描述,那么调度就能简单、快速获得预测的结果。由于云环境的独特性质,我们需要对TSP问题与云环境资源调度问题的特征差异进行关联,以供改进的蚁群优化算法使用[6]。这些差异主要表现在以下3个方面:

(1)在TSP问题中,城市之间有边相连且这些边是可达的并有不同的距离,而在云环境中,资源没有固定的网络拓扑结构。故在云环境中要利用资源活动的相互作用来模拟拓扑关系。

(2)在TSP问题中,城市与城市之间的信息素用城市之

图1 改进算法的任务调度流程图

3 仿真实验结果

本文扩展了云计算仿真平台CloudSim2 1[8],重写了Dat

(下转第1211页)