A Parallel Genetic Algorithm Based On Adaptive Migration Strategy

Genetic Algorithm, a modern artificial intelligence algorithm, results from the process of simulation biological evolutionary. It has natural parallelism and has high performance in solving complex, large-scale, non-linear, non-differentiable optimization problems. Currently, the single-core computers are being phased out, the price of multi-core machine is rapidly declining and computer architecture has been going in the multi-core direction, all of which provide the basis for implementation and application of the Parallel Genetic Algorithm. Thus, Parallel Genetic Algorithm is being researched by more and more researchers. Based on this tendency, a Parallel Genetic Algorithm based on adaptive migration strategy (AMPGA) is proposed in this thesis, through theoretical analysis and experiment. AMPGA could be achieved on the current computers architecture, and could obtain good results, which could improve the performance of traditional Parallel Genetic Algorithm to some degree.The major work and innovations in the thesis are as follows:(1) An improved Parallel Genetic Algorithm, which is suitable for running on the current multi-core computers, is proposed. This Implementation combines the Genetic Algorithm and current computer architecture, which makes the Parallel Genetic Algorithm execute on the mainstream computer concurrently and improve the convergence speed, fully tap the computer's computing capability.(2) An adaptive migration strategy, which is according to the current evolution state to migrate dynamically and conditionally, is proposed. It reduces the communication and synchronization consumption which is caused by useless migration, ensures the better individuals which are migrated effectively between the sub-populations, sufficiently exerts the oriented effect of the better individuals, avoid the blind and fixed migration of traditional Parallel Genetic Algorithm, and improves the capability of solving global optimization, accuracy and convergence speed of the traditional Parallel Genetic Algorithm.(3) Migration Operator and Acceptance Operator are proposed. By executing these tow operators, a better individual is accepted from other sub-populations to exert the oriented effect of the better individual to enhance the precision and convergent speed, when the difference between individuals are large and the individuals are far from the global optimization. An individual which could increase the diversity of the individuals is accepted to prevent from trapping into local optimal value and to avoid premature convergence effectively when the difference between individuals are little and easy to trapping into local optimal value.(4) AMPGA is applied to a number of problems of Benchmark function optimization to test the performance of AMPGA and to compare with the traditional Parallel Genetic Algorithm. The results show AMPGA has not only faster convergent speed but also has more accurate precision as well as higher parallel efficiency.