Research Of Genetic Algorithms On The Muti-modal Optimization Problems

How to apply genetic algorithms to solve multi-modal optimization problems has been a focus in the research community of genetic algorithm and evolutionary computation. It is also fundamental to the basic theory and industrial applications of genetic algorithms. There have been many successful cases in real world, but the existing theoretic analyses are far from perfect. The influence of the external parameters on the efficiency of genetic algorithms is especially investigated, and the theoretic analyses are made and extended corollaries are derived. The theoretical achievements are used to the design of high-efficiency genetic algorithms for solving multi-modal optimization problems. The main contents of the dissertation are as follows:1. The development of the multi-modal optimization and genetic algorithms is summarized, and the current literatures of the application of genetic algorithms to the multi-modal optimization problems are reviewed. The basic theories of genetic algorithms are introduced, and the development trends of genetic algorithms are evaluated.2. The infinite population model of the gene pool genetic algorithm (GPGA) is built based on the Walsh transform, and the relation between the fitness difference of local optima of the BINEEDLE fitness function and the efficiency of GPGA is defined. The application scope of the theoretical corollaries are analyzed and proved via simulation tests. According to the theoretical propositions, we invent the two-step genetic algorithm for the multi-modal optimization problems, and get satisfactory empirical results. It also proves the theoretic corollaries indirectly.3. Both the influence of the attraction basins of the local optima on the convergence of genetic algorithms and the influence of the solution space spectrum on the efficiency of GPGA are investigated, which illustrates the significance of partition of the solution space. According to the orthogonal design, we propose a new genetic algorithm based on the rational partition of the solution space. The simulation experiments show that the improved algorithm converges to the global optimum more quickly, and can find more local optima than traditional methods on multi-modal optimization problems.4. Two complex evolution systems are analyzed based on infinite population model of the genetic algorithm. According to the analytical results, two new evolution systems are constructed, and the iterative equations of the dynamical system models of both evolution systems is derived in one-bit case. The complex behaviors of both systems in steady state are investigated by phase portraits, bifurcation diagrams and Lyapunov-exponent spectrums, which show that the first evolution system is a chaotic system and the second evolution system contains complex periodic behaviors. According to these conclusions, we present the method to keep the diversity of the population of the genetic algorithm, which is good for finding more useful solutions of multi-modal optimization problems.