Research Of Grid Task Scheduling Based On Genetic Simulated Annealing Algorithm

With the rapid development of computer technology and Internet, there are a large number of different types of available resources which is generated on the web. Grid task scheduling is one of the core researching items. One of the core tasks is how to rationally allocate the task to different resources to make the entire grid system to perform perfectly. But heterogeneous, dynamic and autonomy of the grid itself make the traditional scheduling algorithm facing new challenges. Therefore, how to optimize the scheduling algorithm based on the existing one to maximize the throughput of the grid system is an important and practical issue.Recently, genetic algorithm GA (Genetic Algorithm) and simulated annealing algorithm SA (Simulated Annealing) are relatively effective to solve the grid task of scheduling algorithm. Both two algorithms are simulated some phenomena of nature to optimize methods for solving problems in a large-scale. Also, neither of them requires the continuity and convexity of the objective function. GA has strong global search performance, but its climbing ability is weak and prone to the premature convergence problem in practical application, and has lower efficiency in the later stage of evolution. The SA is able to cast off local optimal solution and to inhibit premature convergence of genetic algorithms, but its evolution is slow.Since the premature convergence and slow evolution of GA, the paper combined two algorithms'characteristics to improve and design a simulated annealing genetic algorithm GSAA (Genetic Simulated Annealing Algorithm). The basic idea of GSAA is to make full use of the group of GA, global convergence, random, quick search and other advantages of generating the initial solution firstly, which is produced initial solution by the genetic operation of GA; then use the initial solution of SA Metropolis criteria to decide whether to accept transition characteristics of the crossover and mutation to generate new individuals, to accept the high-quality solutions while accepting inferior solutions properly, to ensure the diversity of population. The GSAA uses adaptive crossover and mutation probability; properly improved genetic operations. To obtain the optimal solution of grid task scheduling by GSAA is workable.This paper analysis the basic principles of the genetic algorithm and simulated annealing algorithm SA (Simulated Annealing) thoroughly. According to the characteristics of grid task scheduling, the paper designs the hybrid genetic algorithm in various components, and simulate achieved the GSAA in Gridsim grid simulator. Still, after comparing with GA and SA, the results show that the proposed Genetic Simulated Annealing Algorithm has better search ability.