A Comparative Analysis of Selection Schemes Used in Genetic Algorithms

A Comparative Analysis of Selection Schemes Used in Genetic Algorithms

| David E. Goldberg and Kalyanmoy Deb
This paper compares four commonly used selection schemes in genetic algorithms: proportionate reproduction, ranking selection, tournament selection, and Genitor (or "steady state") selection. The analysis is based on deterministic difference or differential equations, which are verified through computer simulations. The paper provides approximate and exact solutions, as well as convergence time and growth ratio estimates. Proportionate reproduction is found to be less effective in maintaining steady pressure toward convergence without scaling. Ranking selection and tournament selection maintain strong growth under normal conditions, while Genitor achieves an unusually high growth ratio, leading to premature convergence. The paper recommends practical application of the analyses and suggests further detailed stochastic analyses to understand the $k$-armed bandit problem and its implications for selection techniques. The analysis also highlights the importance of balancing exploration and exploitation in genetic algorithms, with potential solutions such as slow growth ratios to prevent premature convergence and high growth ratios to capture building blocks quickly.This paper compares four commonly used selection schemes in genetic algorithms: proportionate reproduction, ranking selection, tournament selection, and Genitor (or "steady state") selection. The analysis is based on deterministic difference or differential equations, which are verified through computer simulations. The paper provides approximate and exact solutions, as well as convergence time and growth ratio estimates. Proportionate reproduction is found to be less effective in maintaining steady pressure toward convergence without scaling. Ranking selection and tournament selection maintain strong growth under normal conditions, while Genitor achieves an unusually high growth ratio, leading to premature convergence. The paper recommends practical application of the analyses and suggests further detailed stochastic analyses to understand the $k$-armed bandit problem and its implications for selection techniques. The analysis also highlights the importance of balancing exploration and exploitation in genetic algorithms, with potential solutions such as slow growth ratios to prevent premature convergence and high growth ratios to capture building blocks quickly.
Reach us at info@study.space