Study On Genetic Algorithms Based On Knowledge And Multi-population Evolution

Genetic Algorithms (GAs), based on the'survival of the fittest'principle of natural selection and information inheritance during evolution process, are global stochastic search techniques for optimization problems, and have properties of robustness, global convergence and connotative parallel. However, conventional genetic algorithms had no definite knowledge system, and failed to use local spatial information to guide searching, thus resulted in problems such as poor local searching capacity, premature convergence, and slow convergence. Fortunately, the introduction of relevant knowledge of problems may improve the searching ability of the genetic algorithm, and the application of experience of genetic algorithm and prior knowledge about evolution nature may guide the evolution process correct and thus improve the effect of optimization and the efficiency of the algorithm. In this paper, the relevant knowledge of problem, the information of evolution and multi-species evolution algorithm are introduced into genetic algorithm to establish an improved genetic algorithm based on prior knowledge and multi-population evolution. The main work and results of the paper are the following:(1) The effect of prior knowledge of problem on algorithm through introducing correlative problem's solution in GA are tested. Results show that the higher the correlation between the introduced problem and the problem to be solved, the better it is helpful to solve the problem. In combination with relative lore of problem presentation, a Self-Adaptive Genetic Algorithm is established based on individual similarity. It decreases the crossover rate of similar paired individual, maintains population diversity, improves global search capacity, saves the compute resource, and accelerates the convergence.(2) After a detailed analysis of population diversity, a dynamic size genetic algorithm based on population diversity is proposed. The algorithm decreases the population size during evolution process, and increases remarkably the population size when the population lacks diversity. The new algorithm is an algorithm with strong local and global search capacities. Results show that the method seldom converges at local optimum and has high convergence speed.(3) Draw lessons from the phenomenon of community cooperation in species, a new multi population genetic algorithm is proposed. Different evolution mechanisms are used in different subpopulations, thus the local and global search capacities of the algorithm are balanced. Results show that this multi-species evolution is useful for GA to get the fitter individual and restrain prematurity. (4) Draw lessons from that evolution of species is reflected by environmental adaptation of the species, a parallel Genetic Algorithm based on clustering is proposed. The algorithm cluster analysis is carried out on all the individuals, and different evolution mechanisms are used in different subpopulations. The convergence of the algorithm is theoretically proved. Results show that the algorithm greatly increases the possibility for achieving global optimum, and meanwhile maintains the population diversity.(5) An in-depth study is carried out on the genetic algorithm in noise environment. It is found that the proposed computing method for object function value can lower the effect of noise on individual fitness evaluation. Two new evaluation indexes are proposed. Test results show that the evaluation indexes can effectively reflect the optimal performance in noise environment. CBPGA is applied in the problem in noise environment, and the results show that CBPGA can effectively hinder the noise influence.