【作者】 李力；

【导师】 薛胜军；

【作者基本信息】 武汉理工大学 ， 计算机应用技术， 2008， 硕士

【摘要】 网格是一个集成的计算与资源环境,它能充分吸纳各种计算资源,并将它们转化成一种随处可得的、可靠的、标准的同时还是经济的计算能力,实现资源的全面共享。网格任务调度是网格研究的核心内容之一,如何合理地将任务分配给不同资源,使整个网格系统达到最佳的性能,这是任务调度需要解决的问题。由于网格自身的分布性、异构性、动态性和自治性,使得传统的调度算法面临新的挑战。因此,如何在现有调度算法的基础上提出一个好的调度算法,尽可能提高网格系统的吞吐量,是一个重要而现实的问题。遗传算法是近年兴起的一种用于解决优化问题的启发式算法,被广泛用于解决各类NP问题和任务调度问题。有仿真实验证明:在处理调度问题时,遗传算法与传统调度算法相比更具优越性。由于基本遗传算法SGA(Simple GeneticAlgorithm)本身存在一定的缺陷,比如“早熟”收敛和“欺骗”问题,因此大批学者都致力于改进遗传算法的探索和研究中。本文深入解析了遗传算法和模拟退火算法SA(Simulated Annealing)的基本原理,针对SGA的不足,提出了一种混合遗传算法HGA(Hybrid Genetic Algorithm)。HGA在SGA的基础上,主要改进了以下几个方面:借鉴了模拟退火的思想,根据SA中的Metropolis准则决定是否接受由交叉和变异操作产生的新个体,使得在接受优质解的同时,也有限度的接受劣质解,保证了种群的多样性;采用了自适应交叉和变异概率;适当地改进了遗传操作。根据网格任务调度的特点,本文详细设计了混合遗传算法的各个组成部分。在GridSim网格模拟器中,对混合遗传算法进行了仿真实现,并与SGA和SA进行了对比,结果表明本文提出的混合遗传算法具有更好的搜索能力和收敛速度。更多还原

【Abstract】 Grid is an environment that integrates calculation and resources. It can fully absorb all kinds of computing resources and turns them into a computing capability which is easily available, reliable, standardized and economical. In this way, we can share the resources thoroughly. Task scheduling is one of the most important part in grid research, How allocate tasks to different resources in order to make the grid system obtain the highest performance is the problem which the task scheduling needed to resolve. The features of distribution, heterogeneousness, dynamic and self-ruling of grid challenge the traditional scheduling algorithms. So it is very important and realistic to put forward a better scheduling algorithm based on existing algorithms which can make full use of all kinds of resources and improve the throughput of grid system.Genetic algorithm is a new kind of modern heuristics algorithm, which is often used to solve different kinds of NP-complete problems and complex job scheduling problems. Some simulation experiments have confirmed that genetic algorithm is better than classical scheduling algorithms. Because the simple genetic algorithm (SGA) has some defects, such as prematurely convergence and deceptive problem, many academicians committed themselves to the research of improving the genetic algorithm.This thesis analyzes the basic principle of the genetic algorithm and the simulated annealing algorithm (SA) thoroughly. Aiming at the shortage of simple genetic algorithm, this thesis brings forward a kind of hybrid genetic algorithm (HGA). Some improvement is made on the basis of SGA: It learns the Metropolis rule from SA to determine whether to accept a new individual that generated by the crossover or mutation operation. According to the Metropolis rule, the algorithm can accept not only a premium solution, but also a bad solution in a limited probability, so it makes the population having great variety; its crossover probability and the mutation probability are self-adaptive; its genetic operations are also improved properly. Based on characteristics of task scheduling in Grid, we design all the components of HGA at length. On top of that, we perform an experiment based on GridSim to implement the algorithm, and do comparison with SGA and SA in performance. The experiment results show that the hybrid scheduling algorithm that we put forward has a better ability of search and a higher convergence speed.更多还原