The Genetic Algorithm*
How Genetic Algorithms Work
Based on natural phenomenon called “the survival of the fittest”, only the fittest individuals survive and reproduce. The reproduction process happens in the gene pool. New combinations of genes are generated from previous ones by exchanging segments of genetic material among chromosomes (known as “crossover”). Then a new gene pool is created. Repeated selection and crossover cause the continuous evolution of the gene pool and the generation of individuals that survive better in a competitive environment.
A Simple genetic algorithm
The Genetic Algorithm cycle
GA operates on encoded representations of the solutions, equivalent to those chromosomes of the individuals in nature. It is assumed that a potential solution to a problem may be represented as set of parameters and encoded as a chromosome.
A fitness function must be provided for evaluating each string. Each solution is associated with a fitness value, based on the fitness function, to reflect how good it is.
Selection models nature` s survival of the fittest mechanism. In principle, individuals from the population are copied to a “mating pool”, with highly fit individuals being more likely to receive more than one copy, and unfit individuals being more likely to receive no copies.
The reproduction phase of GA is simulated through a crossover mechanism. The simplest method of crossover is to cut the chromosomes of the two individuals of some randomly chosen position and then exchange their “head” and “tail” segments, known as 1-point crossover.
Another operation, called mutation, causes sporadic and random alteration of the bits of strings, which is a direct analogy from the nature and plays the role of regenerating lost genetic materials.
Convergence is the progression towards increasing uniformity in the gene pool.
Schema and Schema theorem
While GA has been applied for large number of optimization problems, there is no accepted “general theory” which explains why GA has the properties they do. Although a very clear picture of the workings of GA has yet emerged, there are several hypotheses having been put forward which can partially capture the essence of GA mechanics. One of these hypotheses is the schema theorem.
A schema is a similarity template describing a subset of strings with similarities at certain positions. They are building blocks of good solutions from diverse strings. The concept of schema can be explained with an example. If we consider a string and a schema of length 5, then the schema *0000 will match two strings namely, 00000 and 10000 (with the assumptions that each digit in the string is a binary taking values of either 0 or 1). The symbol * in the schema represents a “don` t care” status. If the rest of the string matches with the schema then it is a member of the schema. The idea of a schema gives a powerful and compact way to discuss all the well defined similarities among finite length strings.
The schema theorem says that a schema occurring in strings with above average evaluations will tend to occur less frequently. This feature of GA has been described as intrinsic parallelism, in that the algorithm is manipulating a large number of schema in parallel.
* This is a part of the Literature Review for my undergraduate thesis on Optimal Capacitor Allocation. Bibliography can be found HERE