Genetic Algorithms

The evolution process consists of successive generations. At each generation, individuals with high fitness are selected, the chromosomes of selected individuals are recombined and subjected to small mutations. Formally, the scheme of GA can be represented as follows (The population at t-th generation is designated by {S_k(t)}):

• Step 0. Create a random initial population {S_k(0)}.
• Step 1. Evaluate the fitness f(S_k) of each individual S_k in the population {S_k(t)}.
• Step 2. Selecting the individuals S_k according to their fitness f(S_k) and applying genetic operators (recombinations and point mutations) to selected chromosomes, generate the offspring population {S_k(t+1)}.
• Step 3. Repeat the steps 1,2 for t = 0, 1, 2, ... , until some convergence criteria (the maximum fitness in the population ceases to increase, t reaches the certain value) is satisfied.

There are a number of particular GA schemes, which differ in methods of selection, recombination, chromosome representation, etc.

A traditional GA works on the binary string (symbols S_ki take the values 0 or1) of fixed length (N = const) and applies fitness-proportionate selection, one-point crossovers, and one-flip mutations.

The fitness-proportionate selection means that during the Step 2 the parents S_k of individuals of the new population are selected with probabilities, which are proportional to their fitness f(S_k). Another example of a selection is the ranking one: a certain number of best the individuals of the population {S_k(t)}are used as parents of a new generation.

The one-point crossover is organized analogously to the biological one: if we have two parents S₁ = (S₁₁, S₁₂,...,S_1N) and S₂ = (S₂₁, S₂₂,..., S_2N), their children are (S₁₁,..., S_1m, S_2,m+1,...,S_2N) and (S₂₁,..., S_2m, S_1,m+1,...,S_1N); that is a head and a tail of an offspring chromosome are taken from different parents. Two-point and several point crossovers can be organized in similar manner. Such crossovers are sometimes supplemented by inversions (which are reverses of the symbol order in a part of a chromosome) in order to find the essential combinations of symbols in the strings. Some GAs use a uniform recombination, that is, the symbols of the chromosome of the first offspring are taken from either of the parents (S₁ or S₂) randomly for any symbol position, whereas the second offspring has remainder symbols; e.g., two children of S₁ and S₂ can have the following chromosomes: (S₁₁, S₂₂, S₁₃, S₁₄,...,S_2N) and (S₂₁, S₁₂, S₂₃, S₂₄,...,S_1N).

As optimization technique, the GAs possess an implicit parallelism: different partial effective gene combinations (they are called “schemata”) are searched in parallel manner, simultaneously for all searched combinations. Note, that the smaller is a combination, the quicker it can be found.

The GA scheme is very similar to that of quasispecies. The main difference is that recombinations do not included in the quasispecies model, whereas namely recombinations play the main role to find the new good solutions in GAs (mutation intensity is usually very small in GAs).

Conclusion. GAs are computer program models, which are based on a general understanding of the genetic evolution. GAs are rather universal heuristic optimization methods, which require little knowledge about a problem to be solved. They are also effective methods of combinatorial optimization.

References:

1. Holland, J.H. (1975) Adaptation in Natural and Artificial Systems, Ann Arbor, MI: The University of Michigan Press. 2^nd edn. (1992) Boston, MA: MIT Press.

2. Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley.

3. Mitchell, M. (1996) An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA.