文档介绍：重庆理工大学
硕士学位论文
基于改进混合蛙跳算法的网格任务调度算法研究
姓名:孙元姝
申请学位级别:硕士
专业:计算机应用技术
指导教师:杨武
2011-06
摘要
摘要
网格是分布式计算领域中的一个新兴研究方向,在未来社会中发挥着越来越重
要的作用,吸引了大批专家致力于网格的研究。网格是一个集成的计算与信息服务
环境,它借助网络连接地理上分布的计算资源,并将它们转变成便利、经济、可靠
的计算能力,以实现资源的共享。网格资源具有动态性、异构性、自治性等特点,
如何合理匹配网格任务与资源,使网格系统达到最佳性能,成为网格研究的重点之
一,这也是本文研究的主要内容。
网格任务调度是一类组合优化问题,围绕网格任务调度算法,网格学者作了大
量的研究工作,已将遗传算法、粒子群算法、Min-Min 算法等经典组合优化算法,
成功应用于求解网格任务调度问题。混合蛙跳算法 SFLA(Shuffled Frog Leaping
Algorithm)是一种新兴的启发式算法,它兼具了粒子群算法和模因算法的优点,在
求解网格任务调度问题上取得不错的效果。
基于对 SFLA 算法和网格任务调度问题的深入分析,论文针对 SFLA 算法自身
存在的易陷入局部最优以及信息共享不足等缺陷,进行了如下几个方面的研究:首
先,考虑到“虎父无犬子”的自然进化规律,鉴于 Min-Min 算法思路简单、能在较
短时间内获得较高质量解等优点,提出 Min-Min 与随机算法相结合的种群初始化策
略,既改善初始种群的质量,又不失其多样性,使种群快速收敛到全局最优;其次,
基于种群进化对局部极值的依赖性,对局部极值添加了遗传算子,扩大了局部搜索
范围,降低陷入局部最优的几率。同时,借鉴 PSO 算法中粒子更新思想,优化 SFLA
算法中最差青蛙个体步长移动公式;最后,在混合过程中,对各族群局部极值添加
遗传算子,加强个体间的信息共享,提高种群的多样性,加快算法的收敛速度。
为了评估改进 SFLA 的性能,论文利用 Gridsim 模拟器,结合 JCreator IDE 环
境,对基于改进 SFLA 算法的网格任务调度进行仿真实验。实验结果表明,论文改
进的 SFLA 算法是可行的,提高了网格调度系统的吞吐量。
论文从种群初始化、个体矢量更新以及混合操作等方面,对 SFLA 算法进行了
改进,并通过 Gridsim 模拟器对改进的算法进行了仿真。仿真结果表明,论文提出
的改进方法是有效的,对网格任务调度算法领域的研究提供一定的帮助。

关键词:网格;网格任务调度;混合蛙跳算法;局部搜索;混洗过程
I
Abstract
Abstract
The grid is a new research direction in the filed of puting, will be
playing an increasingly vital role in the future, attracting a large number of experts to
devote to the grid. Grid is an enviroment that puting and information
services, which link geographically puting resources work and
transform them into a convenient, economical and puting power to achieve
resource sharing. Owing to the characters of dynamic, heterogeneousness, self-ruling of a
grid, how to match grid tasks and resources to achieve the best performance is one of the
key research fileds of grid, whic is also the main content of this paper.
Grid task scheduling is a kind binatorial optimization problem, the grid
scholar has done a lot of research. Many binatorial optimization algorithm,
such as ic algorithm, Particle swarm