The underlying ideas for genetic algorithms were inspired by Charles Darwin's notion of biological evolution through natural selection. The basic idea is to solve an optimization problem by evolving the best solution from an initial set of completely random guesses. The theoretical model provides the framework within which evolution takes place, and the individual parameters controlling it serve as the genetic building blocks. Observations provide the selection pressure.
Parallel Genetic Algorithm Chart
Initially, the parameter space is filled uniformly with trials consisting of randomly chosen values for each parameter, within a range based on the physics the parameter is supposed to describe. The model is evaluated for each trial, and the result is compared to the observed data and assigned a fitness inversely proportional to the variance. A new generation of trials is created by selecting from this population at random, weighted by fitness.
In order to apply genetic operations to the new generation of trials, their characteristics must be encoded in some manner. The most straightforward way of encoding is to convert the numerical values of the parameters into a long string of numbers. This string is analogous to a chromosome, and each number represents a gene. For example, a two-parameter trial with numerical values x1=1.234 and y1=5.678 would be encoded into the single string of numbers 12345678.
Next, the encoded trials are paired up and modified in order to explore new regions of parameter space. Without this step, the final solution could ultimately be no better than the single best trial contained in the initial population. The two basic operations are crossover which emulates sexual reproduction and mutation which emulates happenstance and cosmic rays.
As an example, suppose the encoded trial above is paired up with another trial having x2=2.468 and y2=3.579, which encodes to the string 24683579. The crossover procedure chooses a random position between two numbers along the string and swaps the two strings from that position to the end. So, if the third position is chosen, the strings become
123|45678 -> 123|83579 246|83579 -> 246|45678Although a high probability of crossover exists, this operation is not applied to all of the pairs; this helps keep favorable characteristics from being eliminated or corrupted too hastily. To this same end, the rate of mutation is assigned a relatively low probability. This operation allows for spontaneous transformation of any particular position on the string into a new randomly chosen value. So if the mutation operation were applied to the sixth position of the second trial, the result might be:
24645|6|78 -> 24645|0|78After these operations have been applied, the strings are decoded back into sets of numerical values for the parameters. In this example, the new first string 12383579 becomes x1=1.238 and y1=3.579 and the new second string 24645078 becomes x2=2.464 and y2=5.078. This new generation replaces the old one, and the process begins again. The evolution continues until one region of parameter space remains populated while other regions become essentially empty.
It works far better than we had expected before trying it.
