Analysis And Suppressing Methods Of Genetic Drift In Evolutionary Computation

This study analyzes the phenomena of genetic drift in evolutionary computation, investigates the methods of suppressing genetic drift and accelerating evolutionary search.Markov chain of selection operator is modeled. It is proved that stochastic selection based on fitness bias causes inevitable genetic drift and possible premature convergence by analyzing the absorption states and absorption probabilities of Markov chain. The extent, dynamic behavior, and controllability of genetic drift from various selection strategies are probed and compared by calculating and analyzing the average drift velocity and population diversity. The experiments investigating the effects of noise of stochastic sample methods on genetic drift and search performances are conducted and analyzed.The common crossover or recombination methods in evolutionary algorithms are generalized as two types of multi-parent recombination operators, that is, diagonal crossover and scan crossover. By analyzing the frequency of dominant allele, it is strictly proved that diagonal crossover and uniform scanning crossover do not cause genetic drift, but occurrence-based scanning crossover induces severe genetic drift that augments as the number of parents increases. Experimental results show that genetic drift induced by occurrence-based scanning crossover reduces both convergence rate and genotypic diversity, thus causing pure performance deterioration of evolutionary search.The existing niching methods are reviewed systematically, with focus on presenting the major strength and weakness of the representative niching methods. Equivalence class model describing the structure of search space of multi-modal functions is introduced. Genetic drift in deterministic crowding (DC) niching method is analyzed, it is due to the judging and replacing errors of similar individuals. Probabilistic crowding (PC) is proved to have the capacity maintaining multiple stable classes in a single population, by analytically and numerically solving expected proportion equation.Considering the respective strength and weakness of DC and PC, a kind of clustering probabilistic crowding (CPC) niching method is proposed. CPC judges the similarity of two individuals from the whole population, and applies valley function to further analyze their class memberships. The class memberships and relative fitness of two similar individuals are used to determine whether or not to employ deterministic or probabilistic replacement.Number of effective classes, average peak ratio and global optimum ratio are proposed as three performance criterions measuring class maintenance capacity, parallel local andglobal convergence velocity of niching evolutionary algorithms. The test results on share, DC, PC, and CPC show that all performances of CPC are statistically superior to those of the other niching methods.By investigating the techniques of improving convergence velocity and reliability of standard genetic algorithms, this study proposes a kind of hybrid niching evolutionary algorithms HNE based on parallel local search. HNE adopts the framework of CPC, introduces real-coded representation, adaptive Gaussian mutation, discrete recombination, and parallel local search operator PLS. PLS partitions the population into a group of disjoint subpopulations by cluster analysis, then uses simplex method to search local optima in each subpopulation in parallel.According to a large number of optimization results on artificial multi-modal functions with various topological structure and hardness, it is concluded that HNE is a kind of cost-effective, robust, and self-adaptive niching algorithm with powerful capacity of suppressing genetic drift, it can search out quickly and maintain in parallel various optima in a single population.This study also discusses the further improving measures of HNE, and presents future research directions.