A genetic algorithm searches a (potentially) vast solution space for an optimal (or near optimal) solution to the problem at hand.

- Solutions are encoded as strings over a finite alphabet (often 0 and 1).
- A
*fitness function*(or*objective function*) is used to evaluate each string (solution). - Bits and pieces of the fittest strings (solutions) are used to generate new strings (solutions).

Each time step (or generation) of the algorithm produces a population of possible solutions based on the population from the previous time step (or generation).

- Natural selection:
strings with a good fitness value survive from one generation
to the next with high probability; strings with a poor fitness
value perish with high probability.
- Reproduction: two strings chosen via natural selection
mate (via crossover, which picks a position within the strings
at random and exchanges the upper halves of the two strings)
to produce new strings.
- Mutation: strings can undergo spontaneous changes (with small probability) to produce new strings in a different part of the solution space.

- Randomly initialize the population of solutions
Use a population sufficiently large to be representative of the search space as a whole.

- Evaluate the fitness of each individual
That is, evaluate the fitness function for each solution in the population to see if the termination criteria for optimality are met.

- While termination condition does not hold
- Replicate individuals based on their fitness
Use a weighted roulette wheel to reproduce strings in the next generation in proportion to their fitness.

- Transform the individuals in the population
- Randomly pick two parents from the population
- Crossover the parents (pick a random point in the
strings and exchange their top parts) to produce offspring
- Mutate each offspring (randomly decide whether to flip each bit in the string) optionally flip each bit)

- Randomly pick two parents from the population
- Evaluate the fitness of each new individual

- Replicate individuals based on their fitness

/* Select an individual for the next generation in proportion to its contribution to the total fitness of the population */ /* Assumes fitness values in global array fitness */ /* Returns a single selected individual */ int select (real sum_of_fitness_values) int index; index = 0; sum = 0.0; /* Random number between 0 and fitness total */ r = drand48() * sum_of_fitness_values; do index++; sum = sum + fitness[index]; while (index < SIZE-1) and (sum < r); return index;

A GA can be expected to produce good solutions, but might never find a perfect solution. When is a good solution 'good enough'?

When should a GA terminate?

- after a prespecified number of generations.
- when an individual solution reaches a prespecified level of fitness.
- when the variation of individuals from one generation to the next reaches a prespecified level of stability.