Genetic Algorithms Content from the guide to life, the universe and everything

Genetic Algorithms

3 Conversations

A genetic algorithm (GA) is a process that uses mechanisms analogous to those found in biological evolution to solve multi-constraint (many variable) problems.

The Process

The problem must first be encoded such that it can be concisely described and manipulated. This usually involves concatenating1 place holders for each of the variables in some kind of string or list of objects. An initial population of these strings or lists (genomes) is then generated with completely random values in the place holders (genes).

Each string is then tested against some function to obtain a fitness value. The fitness values of all strings are then compared and some policy for selecting mating couples is brought to bear. This policy can vary from one implementation to another and has a significant impact on the convergence of the population.

Pairs of strings are mated by partitioning them at some random point along their length and swapping, or crossing, half of each string at that point. Whist randomly chosen, the crossover point should be common to both parents to ensure that resulting strings keep the same length.

Crossover is executed one or more times on a mating pair, generating a new child each time.

Randomly selected children may be modified at a randomly chosen point along their length (locus) at birth to simulate mutation.

Newly generated children are then fitness tested and inserted into the population wherever their fitness value is found to be higher than an existing member. Weaker members are deselected in this way.

After fitness testing, crossover and replacement have been executed, the process is repeated on the new population.

As generations advance, fitness values will rise and the strings in a population might eventually converge on a particular set of values. This is not necessarily a good thing as the point at which they converge might be a false peak on the fitness landscape for this problem.

Any multi-constraint problem is a potential target for the application of GAs. Time tabling, route planning and scheduling systems are ideal.

1Concatenating means to bring things together.

Bookmark on your Personal Space

Edited Entry


Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry

Categorised In:

Written by

Edited by

h2g2 Editors


h2g2 Entries

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more