基于改进PSO的网格调度算法

1、基于改进PSO的网格调度算法胡金，杨长兴作者简介：胡金（1984-），男，硕士研究生，网格计算. E-mail: 1*|*技术报告*|*Fangpeng Dong, Selim G. Akl. Scheduling algorithms for grid computing: state of the art and open problemsD. technical report. School of computing, Queens University. Kingston, Ontario, January, 20062*|*期刊*|*贺晓雨. 一种用于任务调度的广义遗传算法J.计算机

2、工程,2010,36(17):184-1863*|*技术报告*|*H Aghdam, S Payvar. A Modified Simulated Annealing Algorithm for Static Task Scheduling in Grid ComputingC/International Conference on Computer Science and Information Technology 2008:623-6274*|*期刊*|*Lei Zhang, Yuehui Chen, Bo Yang. Task Scheduling Based on PSO Algor

3、ithm in Computational GridM. Intelligent System Design and Applications. 2006:696-7045*|*期刊*|*魏东，吴良杰，佐丹，刘刚. 基于混合蚁群算法的网格任务调度J. 计算机工程, 2010,36(3): 215-2176*|*技术报告*|*Kennedy J, Eberhart R. Particle Swarm Op-timizationA. In proc. IEEE Int Conf on Neural NetworksC. Perth, 19957*|*期刊*|*李兵, 蒋慰孙. 混沌优化方法及其应用

4、J. 控制理论与应用, 1997, 14(4):613-615*|1|胡金|Hu Jin|中南大学信息科学与工程学院|School of Information Science and Technology,Central South University,Changsha 410083|胡金（1984-），男，硕士研究生，网格计算|长沙市中南大学校本部10舍126室|410083|2|杨长兴|Yang Changxing|中南大学信息科学与工程学院|School of Information Science and Technology,Central South University, C

5、hangsha 410083|基于改进PSO的网格调度算法|A Grid Scheduling Algorithm based on the improved PSO|（中南大学信息科学与工程学院）摘要：任务调度是网格计算的一个重要组成部分，其性能直接影响到网格的服务质量。为了降低网格任务的完成时间，有效保持网格资源的负载均衡，提出一种独立任务模型下的改进PSO网格任务调度算法（CPSO）。该算法结合粒子群算法和混沌机制，不仅保持了粒子群算法的全局收敛能力，而且通过对每个粒子进行混沌优化增强了粒子跳出局部最优的能力。实验结果表明：该算法不仅缩短了任务调度的完成时间，而且有效的提高了网格的负载均

6、衡性能。关键词：任务调度；独立任务；PSO；混沌优化中图分类号：TP393A Grid Scheduling Algorithm based on the improved PSOHu Jin1, Yang Changxing2(1. School of Information Science and Technology,Central South University,Changsha 410083;2. School of Information Science and Technology,Central South University, Changsha 410083)Abstra

7、ct: Task Scheduling is an important part of Grid Computation. The performance of task scheduling directly affects the quality of service of grid. CPSO(An improved PSO of grid task scheduling algorithm under the meta task model) is proposed for shortening the completion time of task scheduling and ef

8、ficiently balancing the workload. The algorithm combines PSO and the mechanism of Chaos optimization. It not only maintains the global convergence of PSO, but also enhances the ability of getting away from the local optimum by employing chaos optimization to every particle in the swarm. The experime

9、ntal results show that the proposed algorithm in this paper can shorten the completion time of task scheduling and efficiently improve the performance of grid workload. Key words: Task scheduling; Meta task; PSO; Chaos optimization0 概述在网格计算中，任务管理、任务调度和资源管理是网格必须具备的三个基本功能。任务调度是网格系统的一个关键问题，已被证明是一个NP完全问

10、题1。得到一个最优的调度方案或是在有限的时间里找出(任务,资源)的匹配方案是不可能的，因而，一般采用启发式调度算法获得近似最优的时间跨度makespan。近年来，将启发式算法应用于网格任务调度中引起许多学者的关注，并取得了较好的研究成果2,3,4,5，6。其中，PSO算法（粒子群算法）是解决此类问题比较常用而有效的启发式算法，具有搜索速度快、操作简单、效率高等特点。但是粒子群算法容易陷入局部极值，搜索精度不高。针对以上情况，实现最小化makespan，本文基于独立任务调度提出了一种混沌粒子群优化算法的网格任务调度算法CPSO(An improved PSO of grid task sched

11、uling algorithm under the meta task model)。其特点是：利用混沌运动7的遍历性、随机性，在初始化粒子群时采用混沌赋值的方式；在粒子群算法的执行过程中，随机产生一个混沌优化得到的粒子，然后和每个迭代的粒子比较，如果优于此粒子则替换，引导粒子群进行混沌更新，有利于跳出局部最优点，寻找最优点。实验表明，该算法可缩短makespan，有效提高网格任务调度的性能。1 网格任务调度数学模型网格任务分为相互独立的任务和相互关联的任务两种。本文将研究相互独立的任务调度。目前多数研究也是基于此展开的。网格任务调度的实质是将网格环境下的m个需要调度的任务合理分配到n个可用资

12、源上去，得到尽可能短的makespan。如图1，任务组由相互独立的任务T1、T2、Tn组成，任务间相互独立不受影响。网格任务调度策略也就网格任务调度策略图3独立任务的网格调度模型是相应的网格任务调度算法，将任务映射到相应的网格资源上执行。R1、R2、Rm为网格系统中的网格资源。现假定一虚拟组织VO中某用户提交N个任务，网格系统中有M个节点（网格资源），各个任务相互独立。在调度过程中，一个节点在同一时刻只能处理一个任务，而一个任务不能同时在两个节点上执行，任务一旦开始，执行该任务的节点被独占，直到任务完成后才能执行其他任务。基于以上，任务调度数学模型定义如下：定义1 n个相互独立任务的集合，T=

13、t1,t2,tn。定义2 n个任务的任务量集合，Cost=cost1,cost2,costn。 定义3 m个节点（计算资源）集合，R=r1,r2,rm。定义4 m个节点任务处理能力集合，C=c1,c2,cm。定义5 n个任务映射到m个节点的映射方案集合，Map=map1,map2,mapn。mapi表示第i个任务映射到的节点mapi上执行。任务调度的目标是在网格系统中实现网格任务组在网格资源组上的最优分配。具体来说就是实现：1 时间跨度(makespan)最小2 负载均衡3 经济原则为评价网格任务调度算法的性能，本文将采用以下性能指标：最优跨度，负载均衡度。跨度makespan是指任务组T中第

14、一个任务开始执行到最后一个任务完成的时间。 (1)最优跨度=min(makespan)。 负载均衡度表示计算资源负载差异程度。按下式计算，其数值越接近1，网格系统的负载越均衡。 (2)(3)其中，为理论最优跨度值，由式(3)计算可得，为实际跨度值。 适应值函数Fitness(i,k)=makespan (4)其中，i为第i个粒子，k为算法的迭代次数。2 改进PSO的网格调度算法2.1 标准PSO算法粒子群优化算法（Particle Swarm Optimization, PSO）是由Eberhart和Kennedy于1995年发明的一种全局迭代优化算法。在粒子群算法中，每个个体称为一个“粒子”

15、，每个粒子代表着一个潜在的可行解，并以一定速度飞行。通过对环境的学习与适应，每个粒子根据自身经验及同伴飞行经验来动态调整自身飞行速度。粒子每次速度和位置更新公式如下： (5) (6) 其中：下标“j”表示微粒的第j维，“i”表示微粒i，t表示第t代，w称为惯性因子，c1、c2为加速常数，通常在02间取值，r1 U(0,1)，r2 U(0,1)为两个相互独立的随机函数，。为微粒i的当前位置；为微粒i的当前飞行速度；为微粒i所经历的最好位置，也就是微粒i所经历过的具有最好适应值的位置，称为个体最好位置。为群体中所有微粒所经历过的最好位置，称为全局最好位置。2.2 混沌优化由确定的运动方程得到的具有

16、随机性的运动状态称为混沌运动。混沌是自然界中一种常见的现象，其变化过程看似杂乱无章，但不是完全混乱，而是有一定的规律性在里面。将方程中呈混沌状态的变量称为混沌变量，混沌变量对初值十分敏感。混沌变量具有从任意点（除不动点）出发，按确定公式遍历所有状态的特点，即确定性、遍历性，表现形式如同随机变量。一个典型的混沌系统是Logistic方程，其表达式为：（7）式中：混沌搜索的主要思想是通过混沌系统如式(7)产生混沌序列，然后通过载波的方式 将其映射到优化空间中，就是将混沌变量的值域“放大”到优化变量的取值范围内。2.3 改进PSO的网格任务调度算法(CPSO)由于混沌变量的遍历性、随机性使算法具有一

17、定的突跳能力，易跳出局部极值点。而PSO算法具有算法简单、运算速度快，搜索能力强等。本文结合这两种机制，用混沌变量初始化粒子的位置，既不改变粒子群算法初始化时所具有的随机性本质，又能提高粒子群的多样性和遍历性，在大量产生初始群体的基础上，择优选出初始群体；同时在每次粒子更新时，随机生成混沌变量并映射到解空间中。如果优于原粒子则进行替换，这样可以提高种群的多样性，有效减少收敛于局部极值现象。算法流程如下：步骤1 初始化参数。设定最大迭代次数，惯性权值，学习因子，最大速度，位置最大值等。步骤2 混沌初始化种群。(1)随机产生一个n维每个分量数值在0,1上的向量，n为种群的大小，根据式（6），得n个

18、向量。(2)将分量载波到相应变量的取值区间，选出较优的POPSIZE个粒子作为初始粒子群。步骤3随机初始化各个粒子的初始速度并计算各个粒子的适应值，设置其初始极值，然后计算种群极值。步骤4 根据式（5）、（6）更新粒子位置和速度。步骤5 启动混沌优化。随机产生一个0,1上的数值，根据式(7)得一个向量(t=1,2,)，把产生混沌变量序列通过逆映射到解空间。步骤6 计算和两个粒子的适应值，如果优于，则用替换掉。步骤7 若粒子的适应值优于原来的极值，设置当前适应值为粒子极值。若粒子极值优于群体极值，设置当前粒子为全局最优粒子并更新全局极值。步骤8 跳至步骤4直到算法到达最大迭代次数。步骤9 输出全

19、局最优值和全局最优粒子，最优跨度，负载平衡度。3 实验与性能分析实验以GridSim工具包为基础构建网格仿真环境，将本文提出的CPSO算法与PSO算法进行对比分析。PSO算法参数设置如下：种群大小为20，学习因子=2.05，惯性因子为0.729，算法最大迭代次数为1000，每个测试运行50次。混沌控制参数为4。实验中从调度方案的makespan、负载平衡度两个方面比较两种算法的性能。任务执行时间如图2所示，对于每种不同场景重复进行50次，取50次实验的平均结果作为实验结果。负载平衡度如图3所示，同样取50次实验的平均结果作为实验结果。1 makespan图2 CPSO和PSO算法的执行效果负载

20、均衡度图3 CPSO和PSO算法的执行效果由图2和图3可见，混沌优化粒子群算法CPSO和基本粒子群算法PSO在50次相同实验下，相同的迭代次数对两种算法在独立任务网格任务调度模型上的makespan和负载均衡度进行了比较。显然，无论是在makespan还是负载均衡度上， CPSO算法都较PSO更优越。通过实验可以看出，基本粒子群能快速的找到较优解，但是后期逐渐收敛于该解，而处于“停滞”状态，很难得到更优解。而引入混沌机制的CPSO算法，拥有了基本粒子群算法的快速收敛的特性，同时在未得到最优解的情况下，仍不断向最优接靠近，不断得到更优解甚至最优解。4 结束语为了改善网格任务调度性能，本文提出了基

21、于独立任务的混沌优化PSO任务调度算法。该算法是在独立任务模型下，以时间跨度makespan为效用函数(适应度函数)，结合粒子群算法和混沌优化原理，在任务调度中首先通过混沌初始化得到较优的初始粒子群，有效减少了粒子飞向较优点的迭代次数；同时在每个粒子更新位置和飞行速度时，以概率1产生一个混沌序列并映射到解空间，如果此位置优于该粒子当前位置，则粒子更新到该位置。这样以使粒子摆脱“惰性”，向最优解靠近。实验表明，与基本粒子群算法PSO相比， CPSO算法有效的减少了网格任务的完成时间makespan，从而提高了计算节点的负载平衡性能和资源的利用率。下一步的研究工作是在相互关联的任务调度模型下，如何

22、利用该算法有效提高任务调度的效率，以及如何让算法在当网格系统中用户的实际需求多样化时仍然有效。参考文献 (References)1 Fangpeng Dong, Selim G. Akl. Scheduling algorithms for grid computing: state of the art and open problemsD. technical report. School of computing, Queens University. Kingston, Ontario, January, 20062 贺晓雨. 一种用于任务调度的广义遗传算法J.计算机工程,2010,36(17):184-1863 H Aghdam, S Payvar. A Modified Simulated Annealing Algorithm for Static Task Scheduling in Grid ComputingC/International Conference on Computer Science and Information Te