Parallel Genetic Algorithm And Its Distributed Application On The Combination Optimum Problem

This thesis is motivated by the fact that parallel computing on a network of computers using commodity components has received increased attention recently, and noticeable progress towards usable systems has been made. Genetic Algorithms (GAs) are powerful search techniques. Parallel genetic algorithm(PGA) is one of the main research fields of genetic algorithms. It can efficiently satisfy the multiple needs of large-scale computing on a network of workstation clusters. An overview on the composing principles and typical application of existing PGA is presented in this thesis. The future research work which must give more attention has been also mentioned. Then a hybrid parallel genetic algorithm developed by the author for combination optimum problem is presented.Chapter one introduces the content and significance of the research. Several success solutions based on large-scale parallel computing will be introduced.Chapter two explains some basic knowledge of parallel computing.GA and PGA are introduced in chapter three. Factors influencing the performance of PGA are also discussed.A hybrid algorithm using distributed PGA based on the DDs model and heuristic method (2opt) for rapid solution of Travelling Salesperson Problem(TSP) is presented in chapter 4. A c program based on this algorithm in Parallel Virtual Machine(PVM) environment is developed. In this hybrid method, the mutation is provided by the 2opt method which is one of the most well-known local search algorithms among TSP solving algorithms. It improves the TSP tour and reverses the order of the sub-tour. The DDs method is a combination of global parallelism with coarse grained PGA. There is however no migration operator as such, because the whole population is treated during the evolution as a single collection of individuals. The main idea of this model is to cut down waiting time for the last(slowest) individuals, by dynamic splitting the population into demes, which can then be processed without delay. It gives more efficiency in terms of processing speed. The algorithm is fully scalable. The proposed method is used to solve TSP on PC clustering computing system , the experiment results demonstrates that the new method is effective and valid.