摘 要： 提出了一种基于独立任务的改进PSO网格调度算法(MCPSO)。该算法结合粒子群优化算法和混沌机制，在保证寻优速度的同时又能兼顾“跳出”局部最优的能力。实验结果表明，与基本粒子群优化算法相比，该算法具有更好的收敛速度和求解质量。
关键词： 网格调度；独立任务；PSO；混沌优化
在网格计算中，任务管理、任务调度和资源管理是网格的3个基本功能。任务调度是网格系统的一个关键问题，关系到网格能否高效利用资源、快速完成任务以及实现系统负载均衡。同时它也是一个NP完全问题[1]，即得到一个最优的调度方案或是在有限的时间里找出最优(任务,资源)的匹配方案是不可能的。目前多采用启发式算法解决此类问题。
近年来，很多学者将启发式算法应用于任务调度中，并取得了较好的研究成果[2-5]。其中，GA算法可能找到最优解，但选择过程存在随机性，不能确保得到最优解，同时开销大，运行时间长；AA算法虽然有正反馈机制能避免早熟现象，但容易收敛于局部最优，而且算法复杂，搜索时间长；SA算法能以一定的概率接受差的解而可能跳出局部极小，是一种全局最优算法，但是搜索时间比较长；PSO粒子群优化算法[6]搜索速度快、操作简单、效率高，但是易陷入局部极值，搜索精度不高。
针对PSO易早熟、求解质量不高的问题，为实现最小化任务完成总时间(makespan)，本文提出一种基于独立任务调度的改进PSO网格调度算法MCPSO(An improved PSO of grid scheduling algorithm under the meta task)。该算法的主要思想是：首先采用混沌[7]序列初始化粒子的位置，并在产生的大量粒子中择优选出初始种群；然后在粒子更新时引入混沌搜索，随机产生若干混沌序列并把最优混沌序列得到的位置和当前粒子最优位置比较，如果优于当前粒子，则更新当前粒子的最优位置，引导当前粒子跳出局部最优点，快速寻找最优解。实验表明，该算法改善了PSO算法易陷入局部最优问题，同时兼顾更好的makespan和负载均衡，有效提高网格的性能。
1 问题定义
图1所示是一个简单的任务调度流程图，其中MDS(Monitoring and Discovering Service)是资源监控与发现服务，用于收集和发布系统状态信息。
如图1所示，首先任务划分模块将应用程序划分为若干个子任务，然后调度模块从网格资源中的信息采集模块MDS收集必要信息，最后按一定的策略对任务进行分发。
通常在网格环境下主要考虑一组相互独立、任务之间没有数据和通信依赖的独立任务(metatask)。目前多数研究是基于此展开的。本文将主要研究独立任务调度。
现假定虚拟组织VO中用户提交了若干个任务，这些任务经由图1中的划分模块分成n个独立子任务t1、t2、…、tn组成子任务集合T，网格系统中有m个节点(网格资源)r1、r2、…、rm构成资源集合R。任一任务ti可以在任一节点rj上执行，rj在同一时刻只能处理一个任务，而ti不能同时在两个节点上执行，ti一旦开始，rj被独占，直到ti完成后才能执行其他任务。用一个n维向量(w1，w2，…，wn)表示任务的预计完成时间，其中wi为任务i的预计完成时间。
定义1 (任务映射集)n个任务映射到m个节点的映射方案T→R集合即任务映射集MAP。集合MAP={map1，map2，…，mapn}，其中mapi表示第i个任务在映射到的节点mapi上执行。
定义2 (节点工作时间)节点工作时间RCj是指节点j处理完所有分配给它的任务所花费的时间。如式(1)所示：
式中，μ为控制参数，0≤μ≤4；un∈[0，1]。
混沌搜索的主要思想是通过混沌系统如式(7)产生混沌序列，然后通过载波的方式
xni=ai+uni(bi-ai)(9)
将其映射到优化空间中，也就是将混沌变量的值域“放大”到优化变量的取值范围内。
2.3 改进PSO的网格调度算法(MCPSO)
PSO具有很强的全局搜索能力，但不能保证全局收敛。当粒子自身信息和个体极值信息占优时，往往停滞于局部最优解，且随机初始化的种群质量不高，甚至距离最优解位置较远。而混沌具有良好的遍历性、随机性以及一定的突跳能力，易跳出局部极值点，最终可能得到最优解。
因而可以利用混沌的遍历性，在初始化时产生大量粒子，从中择优选出初始种群。同时在粒子位置和速度更新时，引入混沌搜索，并把最优混沌序列得到的位置与当前粒子最优位置相比较，如果优于当前粒子则进行替换。这样可以有效减少算法收敛于局部极值的现象。算法流程如下：
(1)给定种群大小POPSIZE、最大迭代次数、惯性权值w、学习因子c1、c2及控制参数μ等。
(2)混沌初始化：
①随机产生一个n维每个分量数值在[0，1]上的向量，z1=(z11，z12，…，z1n)，n为种群的大小，根据式(8)，得n个混沌序列z1，z2，…，zn。
②利用式(9)将zi，1≤i≤n分量载波到相应的变量取值区间，选出较优的POPSIZE个粒子作为初始种群。
(3)随机初始化各个粒子的初始速度并计算其适应值，设置各个粒子的初始极值并计算种群极值。
(4)根据式(6)、式(7)更新粒子位置和速度。
(5)启动混沌搜索。随机产生d个[0，1]上的随机数，根据式(8)得到d个混沌序列，并把产生的混沌序列依次载波放大到对应变量的取值范围上，从中选出最优位置xi*。
(6)比较当前粒子的个体极值和xi*的适应值，如果xi*较优则用xi*更新当前粒子的最优位置。
(7)更新个体极值和群体极值。
(8)跳至步骤(4)直到算法到达最大迭代次数。
(9)输出全局最优值和全局最优粒子、最优跨度ω、负载平衡度β。
2.4 问题编码
对于n个任务m个资源的调度，粒子的位置和速度均用n维向量表示，维数和任务数一致。如位置向量(x1，x2，…，xm)中第i维分量xi表示任务ti的权值，是[0，m)之间的一个随机数。当n=10，m=5时，各个节点对应的权值范围如表1。
若某粒子的位置矢量表示如下：
Particle：(2.5, 1. 8,0.6,2.4,4.8,3.2,0.7,1.9,2.5,4.0)
上述粒子即为任务的一个调度方案，由表1可得任务与节点的映射关系如表2所示。
3 实验与性能分析
以GridSim工具包为基础构建网格仿真环境，将本文提出的MCPSO算法与基于独立任务的基本粒子群优化算法MPSO算法进行对比分析。
PSO算法参数设置如下：种群大小POPSIZE=10，学习因子c1=c2=2.05，惯性因子ω=0.729，算法最大迭代次数为1 000，混沌控制参数?滋=4。测试运行50次，取50次实验的平均结果作为实验结果。
实验中有5个节点，10个任务，各个任务的预计完成时间{10, 42, 34, 27, 56, 79, 77, 62, 81, 51}，单位为s。
实验从调度方案的求解质量、makespan、负载平衡度3个方面比较两种算法的性能。
求解质量如表3所示。
比较可知，本文提出的MCPSO算法比MPSO有更好的性能，平均跨度值与最好解的偏差小，最好解的次数明显多于MPSO算法，最差解也明显优于MPSO，MCPSO算法的求解质量更好。
为了观察算法的收敛特性，给出了两种算法1 000次迭代的makespan变化曲线，如图2所示。从图2可以看出，MCPSO算法收敛速度优于MPSO算法的情况，并能得到更好的解，而且改进的PSO算法初始解明显更优。
由图3可知，两种算法的负载均衡度随着迭代次数的增加而减少，即负载均衡性能都有提升。而MCPSO算法的负载均衡性能大大好于MPSO算法。
通过实验可以看出，基本粒子群能快速地找到较优解，但是后期逐渐收敛于该解，并处于“停滞”状态，很难得到更优解。引入混沌机制的MCPSO算法，拥有基本粒子群算法快速收敛的特性，同时在未得到最优解的情况下，逐渐向最优解靠近，不断得到更优解甚至最优解。
为改善网格调度性能，本文提出了基于独立任务的改进PSO任务调度算法。该算法以时间跨度makespan为数学模型，结合粒子群算法和混沌优化原理，首先通过混沌初始化得到较优的初始种群，有效减少粒子飞向较优点的迭代次数；在更新粒子位置和速度时，对粒子的最优位置进行混沌搜索，试图找出更优的位置，使粒子飞向更优位置而避免陷入局部最优位置。实验表明，与基本粒子群算法MPSO相比，MCPSO算法能有效提升任务调度问题的求解质量，缩短了makespan，优化了计算节点的负载均衡性能。下一步的研究工作是在关联任务调度时，如何利用该算法有效提高任务调度的效率，以及如何让算法在当网格系统中用户的实际需求多样化时仍然有效。
参考文献
[1] Dong Fangpeng, SELIM G.Scheduling algorithms for grid computing: state of the art and open problems[D].Technical Report. School of computing, Queen′s University. Kingston, Ontario, January, 2006.
[2] 贺晓雨.一种用于任务调度的广义遗传算法[J].计算机工程,2010,36(17):184-186.
[3] AGHDAM H, PAYVAR S.A Modified simulated annealing algorithm for static task scheduling in grid computing[C]. International Conference on Computer Science and Information Technology，2008:623-627.
[4] Zhang Lei, Chen Yuehui, Yang Bo.Task scheduling based on PSO algorithm in computational grid[M].Intelligent System Design and Applications，2006.
[5] 魏东，吴良杰，佐丹，等.基于混合蚁群算法的网格任务调度[J].计算机工程, 2010,36(3): 215-217.
[6] KENNEDY J, EBERHART R.Particle Swarm Op-timization[C].In proc.IEEE Int Conf on Neural Networks. Perth, 1995.
[7] 李兵, 蒋慰孙.混沌优化方法及其应用[J].控制理论与应用, 1997, 14(4):613-615.