改进蛙跳算法的网格任务调度优化模型

杨永强, 李淑红

(河南财经政法大学 计算机与信息工程学院, 郑州 450002)

0　引　言

随信息技术的不断发展, 每天的数据呈海量式增长, 而单一计算机无法适应海量数据处理的要求, 该背景下出现了网格系统[1]。网格系统包括了大量异构资源, 它们通过网络协同工作方式形成一台超级虚拟计算机, 实现各种资源的共享。网格系统通过分配资源完成用户提交的任务, 如何对资源进行有效管理, 以最短时间完成用户提交任务显得十分重要, 因此网格任务调度与优化一直是学术界关注的热点[2,3]。

根据网格任务调度策略, 网格任务调度算法可划分为： 静态调度算法和动态调度算法, 其中静态调度算法实现简单, 但由于资源节点的负载具有动态变化特点, 找到的网格任务调度方案往往不是最佳, 调度结果无法令用户满意[4]。相对于静态的网格任务调度算法, 动态调度算法可更好的适应用户任务动态变化特点, 使资源节点的利用更加充分, 但实现比较复杂, 影响网格任务调度的效率, 因此当前网格任务调度算法融合了静态调度和动态调度的优点, 属于混合调度算法[5,6]。网格任务调度是一个NP(Non-deterministic Polynomial)问题, 随人工智能理论研究的不断深入, 出现了基于粒子群算法、 遗传算法以及其改进算法的网格任务调度模型[7-9], 其具有较好的求解速度, 得到了良好的网格任务调度方案[10]。然而这些算法均存在局部最小值缺陷, 难以获得理想的网格任务调度方案, 不能满足网络任务调度的要求[11]。

蛙跳算法(SFLA： Shuffled Frog Leaping Algorithm)是一种参数少, 速度快的人工智能算法, 适合于NP问题的求解[12]。为获得更加理想的网格任务调度方案, 结合网格任务调度问题的特点, 笔者提出了改进蛙跳算法(MSFLA： Modified SFLA)的网格任务调度优化模型, 并通过仿真测试验证该模型的性能。结果表明, MSFLA获得了比其他算法更好的网格任务调度优化方案, 加快了任务完成的速度, 且提高了资源利用率, 具有更好的实际应用价值。

1　网格任务调度问题

网格任务调度是将用户提交的任务分到最合理的资源上, 在保证满足用户满意的条件下, 使任务完成的时间最短, 同时使资源的利用率最高。设用户任务和资源集合分别为：T={t1,t2,…,tn}和P={p1,p2,…,pm}, 任务估计完成时间为E{t1,pj},T和P之间形成一个矩阵：En×m=E{ti,pj}, 1≤i≤n, 1≤j≤m, 任务ti在资源pj上的完成时间为

tfinish(ti,pj)=tbegin(pj)+E(ti,pj)

(1)

其中tbegin(pj)表示任务开始时间。

在网格任务调度方案A的条件下,pj完成最后一个子任务所需的时间为CAp(j), 则所有任务完成的总时间为

C(A)=max(cAp(j)∀1

(2)

网格任务调度优化目标就是找到一个使C(A)最小的调度方案, 笔者采用改进蛙跳算法对最优解进行求解。

2　改进蛙跳算法

2.1　标准蛙跳算法

SFLA是基于群体理论的人工智能算法, 较好地克服其他算法如粒子群优化算法的不足, 模拟蛙群觅食行为对问题进行求解, 其工作步骤如下。

1) 随机产生包含F只青蛙的初始种群：P={X1,X2,…,XF}, 它们与问题的解对应, 第k只青蛙的位置向量可表示为：Xk={xk1,xk2,…,xkn}, 其适应度值为f[Xk], 将这些青蛙划分M个族群, 第j个族群Ej可描述为

Ej={Sj+m(l-1)∈Pt|1≤l≤N}

(3)

其中N表示每一个簇的青蛙数。

2) 在问题的求解过程, 更新最差青蛙Xw的位置, 即有

(4)

其中D表示青蛙移动的距离；Xb表示最佳青蛙的位置；r为0～1之间的随机数。

若f[Xnew]>f[XW], 则每个族群重复上述步骤, 当满足算法终止条件为止。

3) 当全部簇群完成局部搜索后, 产生一个新的种群, 采用最优适应度值个体更新全局最优位置Xg。

4) 不断实现族的划分和局部搜索和更新, 当达到最大迭代次数终止算法。

2.2　改进蛙跳算法(MSFLA)

由于SFLA的局部搜索范围小, 易找到局部小值, 为此采用如下方式对青蛙个体进行更新,扩大青蛙的搜索范围。

D=rc(Xb-Xw)+W

(5)

W=[r1w1,max,r2w2,max,…,rnwn,max]T

(6)

(7)

其中ri表示随机数；c为常数。

-xw+rc(Xb-Xw)+W

(8)

其中R表示权重因子；r2,r3为随机数[13]。

算法的工作后期时, 青蛙不断接近问题最优解对应的位置Xg, 此时种群的多样性消失, 搜索会出现停滞, 为避免该现象, 引入混沌理论对最差青蛙进行扰动, 具体如下

1) Logistic混沌映射为

xn+1=μxn(1-xn)0

(9)

其中μ表示混沌变量。

2) 设Xg=(Xg1,Xg2,…,Xgd), 则Xgi映射的取值范围内为

zi=xL(xu-xL)xgi

(10)

其中xL,xu为最小和最大值。

(11)

4) 混沌处理后个体更新Pg, 则有

(12)

q=lnt/(1+lnt)

(13)

其中CR表示随机数。

2.3　MSFLA的性能测试

为测试MSFLA的优越性, 采用测试实验与SFLA进行对比分析, 选择智能优算法当前最常用的4个标准测试函数作为研究对象, 其有单峰和多峰函数, 测试结果公平, 说服力强, 具体如下

(14)

(15)

(16)

(17)

所有函数的适应度值进化曲线如图1所示。对图1的适应度值进化曲线进行对比和分析可发现, MSFLA的收敛精度更高, 且收敛速度也更快, 通过更少的迭代次数找到函数的最优解, 而且算法的稳定性更强。

a　f1函数　　　　　　　　　　　　　　　　　　　　　　　b　f2函数

c　f3函数　　　　　　　　　　　　　　　　　　　　　　　　d　f4函数图1　f1～f4的适应度进化曲线Fig.1　Fitness evolution curve of f1～f4

3　基于MSFLA的网格任务调度问题求解

3.1　个体的编码

不同的编码方式, 得到问题不同的求解效率, 笔者采用分层方式进行编码, 具体如图2所示。

图2　任务的编码Fig.2　Encoding of tasks

3.2　网格任务调度模型的工作步骤

Step1设置MSFLA的相关参数, 如局部迭代次数、全局迭代次数等, 根据具体的网格任务调度问题初始MSFLA的初始种群, 并根据个体进行编码操作。

Step2计算每只青蛙的适应度值, 笔者选择任务完成的总时间的倒数作为适应度函数, 并根据适应度值对青蛙进行排序。

Step3根据度适应值将每只青蛙划分到相应和簇群中。

Step4更新每个簇群的最优青蛙位置Xb、 最差位置Xw以及整个种群的最优位置Xg。

Step5青蛙移动步长对青蛙位置进行更新操作, 并计算其适应度值, 根据适应值对Xw进行更新操作。

Step6当达到局部迭代次数后, 所有青蛙进行混合和簇群的重新划分。

Step7若达到最大迭代次数, 输出Xg。

Step8根据Xg得到任务的最佳调度解。

综合上述可知, 网格任务求解问题的MSFLA工作流程如图3所示。

图3　基于MSFLA的网格任务求解流程Fig.3　Grid task solving process based on MSFLA

4　验证性测试

在GridSim仿真平台进行验证性测试, 采用标准SFLA、 遗传算法(GA: Genetic Algorithm)在相同条件进行对照测试, 共有50个任务, 4个网格节点, 每种算法同时执行10次测试实验, 所有算法的网格任务调度优化仿真实验结果如图4和图5所示。对网格任务调度优化结果进行对比分析可发现, 在相同迭代次数下, MSFLA获得更加理想的网格任务调度解, 且网格任务调度效率更高, 这主要是由于MSFLA较好的避免了对比算法存在的局部最优, 早熟缺陷, 找到了更优的网格任务调度方案。

图4　算法的搜索性能　　　　　　　　　 　　　图5　算法的时间开销　　　 　Fig.4　Search performance of algorithms　　　　　　Fig.5　Time overhead of algorithms

5　结　语

任务调度优化问题是网格系统应用中的一个关键问题, 为克服当前网格任务调度算法存在的缺陷, 笔者设计了基于MSFLA的网格任务调度优化模型, 在GridSim仿真平台上的测试结果表明, MSFLA加快了网格任务调度优化问题求解的速度, 在更短时间内可以到最优的网格任务调度优化方案, 同时获得更加理想的网格任务调度优化方案, 提高网格系统资源的利用率, 为网格任务调度优化问题求解提供了一种新的研究工具。

参考文献：

[1]罗红, 慕德俊, 邓智群, 等. 网格计算中任务调度研究综述 [J]. 计算机应用研究, 2005, 22(5): 16-19.

LUO Hong, MU Dejun, DENG Zhiqun, et al. A Review of Job Scheduling for Grid Computing [J]. Application Research of Computers, 2005, 22(5): 16-19.

[2]王浩, 李飞. 基于Qos约束的网格任务调度算法[J]. 四川理工学院学报: 自然科学版, 2013, 26(1): 25-28.

WANG Hao, LI Fei. Grid Task Scheduling Algorithm Based on QoS Dimensions [J]. Journal of Sichuan University of Science & Engineering: Natural Science Edition, 2013, 26(1): 25-28.

[3]王成昌, 陈闳中, 方钰, 等. 基于混合粒子群算法的网格任务调度 [J]. 计算机科学, 2012, 39(2): 18-21.

WANG Chengchang, CHEN Hongzhong, FANG Yu, et al. Task Scheduling in Grid Environment Based on Hybrid PSO Algorithm [J]. Computer Science, 2012, 39(2): 18-21.

[4]孙瑞志, 杨璐, 欧阳娅. 基于改进遗传算法的网格任务调度 [J]. 解放军理工大学学报: 自然科学版, 2012, 13(4): 388-392.

SUN Ruizhi, YANG Lu, OUYANG Ya. On Grid Task Scheduling Based on Modified Genetic Algorithm [J]. Journal of PLA University of Science and Technology: Natural Science Edition, 2012, 13(4): 388-392.

[5]张京军, 刘文娟, 刘光远. 基于改进免疫遗传算法的网格任务调度 [J]. 河北工程大学学报: 自然科学版, 2013, 30(2): 81-84.

ZHANG Jingjun, LIU Wenjuan, LIU Guangyuan. Task Scheduling in Grid Computing Based on Improved Immune Genetic Algorithm [J]. Journal of Hebei University of Engineering: Natural Science Edition, 2013, 30(2): 81-84.

[6]杨明, 薛胜军, 陈亮, 等. 自适应邻域的多目标网格任务调度算法 [J]. 计算机应用, 2012, 32(3): 599-602.

YANG Ming, XUE Shengjun, CHEN Liang, et al. Multi-Objective Evolutionary Algorithm for Grid Job Scheduling Based on Adaptive Neighborhood [J]. Journal of Computer Applications, 2012, 32(3): 599-602.

[7]肖海蓉, 李惠先. 基于自适应遗传算法的网格任务调度优化 [J]. 吉林大学学报: 理学版, 2015, 53(2): 297-302.

XIAO Hairong, LI Huixian. Grid Task Scheduling Optimization Based on Adaptive Genetic Algorithm [J]. Journal of Jilin University: Science Edition, 2015, 53(2): 297-302.

[8]朱海, 王宇平. 融合安全的网格依赖任务调度双目标优化模型及算法 [J]. 软件学报, 2011, 22(11): 2729-2748.

ZHU Hai, WANG Yuping. Integration of Security Grid Dependent Tasks Scheduling Double-Objective Optimization Model and Algorithm [J]. Journal of Software, 2011, 22(11): 2729-2748.

[9]乔楠楠, 尤佳莉. 一种面向网络边缘任务调度问题的多方向粒子群优化算法 [J]. 计算机应用与软件, 2017, 34(4): 309-314.

QIAO Nannan, YOU Jiali. A Multi-Directional Particle Swarm Optimization Algorithm for Network Edge Task Scheduling [J]. Computer Applications and Software, 2017, 34(4): 309-314.

[10]张忠平, 冯玉鹏, 张雪楠. 基于标准差及二次分配的启发式网格资源调度算法 [J]. 小型微型计算机系统, 2016, 37(2): 259-263.

ZHANG Zhongping, FENG Yupeng, ZHANG Xuenan. Heuristic Grid Resource Scheduling Algorithm Based on Standard Deviations and Secondary Distribution [J]. Journal of Chinese Computer Systems, 2016, 37(2): 259-263.

[11]蒲汛, 彭喜化, 于显平, 等. 基于均匀离散PSO算法的多QoS网格任务调度策略 [J]. 控制与决策, 2013, 8(6): 808-814.

PU Xun, PENG Xihua, YU Xianping, et al. Jobs Scheduling Policy for Gird with Multi-QoS Constraints Using Uniform-Design Discrete Particle Swarm Optimization [J]. Control and Decision, 2013, 8(6): 808-814.

[12]LEI D, GUO X. A Shuffled Frog-Leaping Algorithm for Job Shop Scheduling with Outsourcing Options [J]. International Journal of Production Research, 2016, 54(16): 1-12.

[13]于晓鹏, 曹春红. 一种新的改进的混合蛙跳算法 [J]. 吉林大学学报: 信息科学版, 2012, 30(2): 203-206.

YU Xiaopeng, CAO Chunhong. Geometric Constraint Solving Based on Shuffled Frog Leaping Algorithm and Particle Swarm Optimization [J]. Journal of Jilin University: Information Science Editions, 2012, 30(2): 203-206.