Home

Generic Genetic Algorithm

Description

There are numerous variants of the genetic algorithm. We attempt to make our implementation as generic as possible. Our implementation is based on the GA described in "Evolutionary algorithms in theory and practice". It is also very similar to the GA described in "Evolution in time and space", but we use tournament selection instead of proportional selection, and we use elitism.
@book{back1996evolutionary,
  title={Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms},
  author={Back, T.},
  year={1996},
  publisher={Oxford University Press, USA}
}
@INPROCEEDINGS{Muhlenbein91evolutionin,
    author = {Heinz Muhlenbein},
    title = {Evolution in time and space - the parallel genetic algorithm},
    booktitle = {Foundations of Genetic Algorithms},
    year = {1991},
    pages = {316--337},
    publisher = {Morgan Kaufmann}
}
One generation of our GA runs as follows: Tournament selection with replacement chooses two individuals from the current population. These individuals cross over with probability equal to the crossover rate. The resulting children, or the parents if no cross occurred, are mutated. The two mutants are added to the next generation. This process is repeated until the next generation has been filled up to the population size. Finally, elitism checks to see if the best individual seen so far is in the population, if not, then the worst fitness individual in the population is replaced by the best.

Pseudo code

P <- generate a population of individuals randomly
while stopping criterion has not been met:
	while size(P') < pop_size
		parent1 <- tournament_selection(P)
		parent2 <- tournament_selection(P)
		child1, child2 <- with probability cross_rate crossover parent1, parent2
		child1 <- mutate child1
		child2 <- mutate child2
		add child1 and child 2 to population P'

	elitism: if the best fitness individual is not in P'', replace the worst individual in P'' with this best one

	P <- P'
	P' <- ()

Python

Code for this algorithm can be found in ga_modules/classicGA.py in any of the tarballs available here. In the earliest tarball, the GA is in classicGA2.py