一种改进的PSO网格调度算法
2011-02-28杨长兴
网络安全与数据管理 2011年12期
关键词:优化
杨长兴,胡 金
(中南大学 信息科学与工程学院,湖南 长沙410083)
在网格计算中,任务管理、任务调度和资源管理是网格的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]序列初始化粒子的位置,并在产生的大量粒子中择优选出初始种群;然后在粒子更新时引入混沌搜索,随机产生若干混沌序列并把最优混沌序列得到的位置和当前粒子最优位置比较,如果优于当前粒子,则更新当前粒子的最优位置,引导当前粒子跳出局部最优点,快速寻找最优解。……
登录APP查看全文
