Crossover and Mutating Genetic Algorithm

A genetic algorithm differs from the simpler search techniques (random walks, hill climbing, etc.) because it is population-based. Rather than moving from one solution to another solution, a genetic algorithm keeps track of multiple solutions at the same time and uses this combination to cover more of the search space.

A genetic algorithm, as its name suggests, uses the idea of genetics from biology. In the natural world, life is governed by the environment, where the problem to solve is how to live long enough to reproduce effectively. The solutions to this problem are organisms, which are defined by their genes. Each gene makes up part of the solution, and they combine together in arbitrarily complicated ways to make each organism.

Although genes are safely tucked away in the nuclei of cells, they are implicitly competing with each other; this is because the most dangerous force in the environment is usually other organisms (large or microscopic). This, in incredibly loose terms, is survival of the "fittest".*

In a genetic algorithm, these ideas are implemented literally in the code: full solutions are made out of a collection of partial solutions; the worst solutions are constantly being discarded, whilst those that remain are used as templates for new solutions. This exactly mirrors an idealised model of genetics, however the fitness is specified explicitly which directs the solutions to a desirable area.

In the genetic algorithm on this page, I've included the two commonly used solution generators: "mutation" and "crossover". Mutation randomly changes some of the genes, and is a good source of diversity for the algorithm. Crossover chops up two solutions and swaps sections between them, which allows new solutions to be formed without throwing away the genes that have evolved so far (they just get recombined in different patterns). Together these rules make a more sophisticated model of sexual reproduction than crossover alone. To start the simulation, click on the playfield (the box showing the greyscale fitness function).

Current fitness: