Genetic Algorithms

Genetic algorithms use a population of points to search for good solutions. It is hoped that using a population will help solve the problem of local optima. It is based on an analogy with the evolution in the natural world

Darwin’s Principles #

Darwin proposed that natural evolution was driven by the following principles

• Children tend to inherit characteristics from parents
• There is some variation in those characteristics
• Some characteristics are “better” (at creating more children)

It is now known that such characteristics are encoded genetically (in DNA molecules) which are subject to variation which are introduced by

• Mutation - small errors in copying
• Crossover - genes transferred between chromosomes

Biologists call the propensity to have children the “fitness” of an individual.

To create a genetic algorithm, we have a population of points in the search space. We encourage “good” points (as measured by the objective function) to make copies of themselves with some variation. It is hoped that better and better solutions will evolve.

Steady State Genetic Algorithm #

1. Create a random population of points X
2. Select a member of the population (based on objective value)
3. Create a copy of this point, with some variation
4. Place it in the population, replacing some individual
5. Go to 2

Population Size #

The population size is typically found by trial and error but usually smaller is better (e.g. try 10, 20, 30)

Selection #

A simple common approach is tournament selection which works by picking two individuals at random and keeping the best one

Mutation #

We can mutate a point by applying a local search operator (e.g. flip a bit). More commonly, for bit strings, each bit has a probability μ of being changed. For a bit string of length L, it is usual to set μ = 1/L

Crossover #

We first select another point in the population (e.g. by using tournament selection) and then we exchange “DNA” between them. In uniform crossover, the final string has bits randomly chosen from parents.

Replacement #

There are several ways of placing the new parent in the population:

• The new point replaces a randomly chosen population member
• Replace an individual with probability related to objective value, so worse individuals are more likely to be replaced
• Replace the worst point in the population
• Replace the worst point if the new one is better

Diversity #

To make sure not all individuals end up in the same local optimum, we can try to force some diversity in the population. One way to do this is to penalise the objective value of point if there are similar points in the population. We could also have crossover producing two children which replace their parents if they are better. Finally, we can replace the point most similar to the new point.