Genetic Algorithms
Created | Updated Jan 6, 2003
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.
