Skip to main content
Article
Generalized Crowding for Genetic Algorithms
Genetic and Evolutionary Computation Conference 2010 (GECCO-10) (2010)
  • Ole J Mengshoel, Carnegie Mellon University
  • Severino F Galan
Abstract
Crowding is a technique used in genetic algorithms to preserve diversity in the population and to prevent premature convergence to local optima. It consists of pairing each offspring with a similar individual in the current population (pairing phase) and deciding which of the two will remain in the population (replacement phase). The present work focuses on the replacement phase of crowding, which usually has been carried out by one of the following three approaches: Deterministic, Probabilistic, and Simulated Annealing. These approaches present some limitations regarding the way replacement is conducted. On the one hand, the first two apply the same selective pressure regardless of the problem being solved or the stage of the genetic algorithm. On the other hand, the third does not apply a uniform selective pressure over all the individuals in the population, which makes the control of selective pressure over the generations somewhat difficult. This work presents a Generalized Crowding approach that allows selective pressure to be controlled in a simple way in the replacement phase of crowding, thus overcoming limitations of the other approaches. Furthermore, the understanding of existing approaches is greatly improved, since both Deterministic and Probabilistic Crowding turn out to be special cases of Generalized Crowding. In addition, the temperature parameter used in Simulated Annealing is replaced by a parameter called scaling factor that controls the selective pressure applied. Theoretical analysis using Markov chains and empirical evaluation using Bayesian networks demonstrate the potential of this novel Generalized Crowding approach.
Keywords
  • Genetic algorithms,
  • niching,
  • deterministic crowding,
  • probabilistic crowding,
  • Markov chain analysis,
  • Bayesian networks,
  • experiments
Publication Date
July, 2010
Citation Information
Ole J Mengshoel and Severino F Galan. "Generalized Crowding for Genetic Algorithms" Genetic and Evolutionary Computation Conference 2010 (GECCO-10) (2010)
Available at: http://works.bepress.com/ole_mengshoel/20/