The Application Of Genetic Algorithm In Distributed System

As a new kind of parallel optimization algorithm, Genetic Algorithm has been used to solve many kinds of NP-hard problems. Applying GA to scheduling problem and resource mapping problem is an important research subject in distributed system field.In this paper, we divide resources into two kinds. One is computation resources (machines) and the other is non-compute resources. The tasks we study are a set of independent tasks with priorities. We combine task scheduling and resource mapping, and then establish a task scheduling model with the function of resource mapping. On the basis of this model, we design a Modified General Genetic Algorithm, MGGA, and apply it to the static scheduling algorithm in order to obtain an optimal scheduling strategy before executing all tasks, then use a dynamic algorithm to improve the performance of the scheduling plan by adapting to run-time changes..In MGGA, we use one-dimensional structure coding which tallies with biology chromosome in nature. This coding manner, which is different from the traditional matrix coding manner, makes GA more convenient and clear. To collaborate with this coding manner, the basal unit in crossover and mutation operator in our algorithm is not just a bit but gene snippet. In this paper, we also establish a Markov model to analyze the astringency of MGGA. And we draw the same conclusion as General genetic algorithm.The simulation results show that our algorithm can get a better solution than the static mapping algorithm without using GA to optimize.