The Convergence Analysis Of Genetic Algorithm Based On Space Mating

Genetic Algorithm is based on Darwin's theory of evolution and Mendel's genetics optimized search algorithm. It expressed as "chromosomes" (usually binary code), in the role of various genetic operators, through the continuous evolution of groups, so that groups converge to the optimal solution or better solution. Professor Holland in GA theory and methods research made a lot of creatively work. The algorithm is simple, universal, robust. It has given rise to general concern of artificial intelligence and extensive application, Some of relevant research is also becoming computer science, information science and optimization hotspot increasingly.In contrast to the great success of genetic algorithm in the practical application: the genetic algorithm is lagging behind the basic theoretical research, lacking of a broad and complete theory of convergence of genetic algorithms in particularly. The convergence of genetic algorithms is the key issues that the algorithm can be achieved whether or not. To avoid premature convergence, convergence slowly or even non-convergence, a large number of scholars conduct research and put forward a number of improvement measures to enhance the convergence speed of genetic algorithm. These improved methods improve the algorithm performance significantly. However, most of these algorithms are verified by experimental methods and lack of corresponding theoretical analysis and proof.Zheng proposed Genetic Algorithm Based on Space Mating (GASM) added space mating operator, through space mating, the whole search space is divided into disjoint sub-space, it is not only optimize the space of the individual, but also be optimized and reduced itself as an operation object sub-space. Algorithms maintain a very low crossover probability, so it is not diversity groups at one moment, but groups maintain diversity at all times, while accumulate useful information and make the algorithm converges to the global optimum solution ultimately, and the individuals of sub-groups exchange probability very low that resolve the system of parallel genetic algorithm great communication overhead problem.To this end, this paper analysis and proof the convergence of GASM, at the same time, put forward another improved genetic algorithm. Its main tasks are the following two aspects:First, the genetic algorithm based on space mating (GASM) with space mating operator can overcome the premature convergence effectively, but is lack of theoretical analysis. In this paper , we analyze the convergent properties of the genetic algorithm based on space mating by homogeneous finite Markov chain. It is proved that the GASM with the elitist mechanism can converge to the global optimum, and the GASM can converge with probability one on the condition of no mutation operator. By comparing the experimental results of four test problems (three of them are multi-peak complex issues), it is shown that the convergence of GASM is better than the genetic algorithm with the elitist mechanism (elitist genetic algorithm, EGA) in solving the multi-peak complex problems. And compared with the algorithm of fast marriage in honey bees optimization.Second, aimed at the problems of single population getting into premature convergence easily, A new multi-population evolutionary algorithm is proposed in this paper. Using multi-threaded parallel processing methods to achieve the population evolve synchronized. The research results show that this algorithm can overcome the premature convergence effectively, Compared with the simple genetic algorithm, the new algorithm can not only convergence speed rapidly, but also evidently improve convergence efficiency.