artificial life

Chapter 5: Genetic Algorithms

5.1 Genetic Algorithms

John Holland, a computer scientist at the University of Michigan, felt that nature’s mechanism for evolution could be modeled in computers to find successful solutions for difficult problems. By taking a population of possible answers and evaluating them against the best possible solution the fittest individuals of the population are determined. After evaluation, combining and mutating, the members of the current generation generate a new population. This new generation is then evaluated and the process is repeated, until an optimal solution is found [Levy, 1992].

Genetic algorithms take advantage of natural selection to cull weaker solutions from a population. By allowing successful solutions to produce the next generation they are rewarded, while weaker solutions are less likely to pass their unsuccessful “genes” to the next generation.

New populations are created from old populations using three techniques: cloning, crossover and mutation.

Cloning is simply the copying of one genotype from one generation to the next. This is usually reserved for only the strongest candidates, and it is used to ensure that, at worst, a population’s strongest candidate is no weaker than that of the population before it.

Mutation simply changes the value of one part of a solution to another random value. In the case of a bit vector representation of a solution, the bit is simply flipped.

Crossover is the heart of a genetic algorithm, and the driving mechanism behind evolution itself. Crossover takes two genotypes and combines them by copying part of one genotype, then crossing over to the other genotype at some point and copying that genotype. There may be more than one crossover point during the creation of a new genotype..