Abstract:
Evolutionary algorithms tend to get stagnated on local optima and lose alternative solutions. It is due to genetic drift caused by selection pressure, sampling error and gene recombination of crossover. In this paper, homogeneous Markov chain of selection operator is modeled. By demonstrating the existence of absorption states and analyzing absorption probabilities, it is strictly proved that simple selection such as proportional reproduction and rank-based selection must cause uniform convergence of the population, and the makeup of the final population depends not only on selection pressure, but also on distribution of peaks of fitness function, thus planting the curse of premature convergence. In respect of the problems with two candidate solutions, the dynamic characteristics of drift from various selection methods are analyzed by calculating expected value of population diversity. By experimentally measuring the average drifting time and counting the number of premature convergence, the impacts of various sampling methods on genetic drift are compared and analyzed. The results of this paper provide theoretic references and empirical data for implementing and improving evolutionary algorithms.