| The first person who proposed genetic algorithms (GAs) as computer programs that mimic the evolutionary process in nature is John Holland, in early 1970s. Holland's book "Adaptation in Natural and Artificial Systems" published in 1975. His genetic algorithm is commonly called the Simple Genetic Algorithm or SGA. When David Goldberg present “Steady state and transient optimization of gas pipeline using genetic algorithm, 1983” named thesis, GAs became more popular. In the 1950s and the 1960s several computer scientists independently studied evolutionary systems with the idea that evolution could be used as an optimization tool for engineering problems (Mitchell, 1996). Genetic algorithms (GAs) are optimization techniques based on the concepts of natural selection and genetics. Genetic algorithms are inspired by Darwin's theory of evolution. In this approach, the variables are represented as genes on a chromosome. Solution to a problem solved by genetic algorithms uses an evolutionary process (it is evolved). GAs features a group of candidate solutions (population) on the response surface. Through natural selection and the genetic operators, mutation and recombination, chromosomes with better fitness are found. Natural selection guarantees that chromosomes with the best fitness will propagate in future populations. Using the recombination operator, the GA combines genes from two parent chromosomes to form two new chromosomes (children) that have a high probability of having better fitness than their parents. Mutation allows new areas of the response surface to be explored. This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied. | | Simple Genetic Algorithm The mechanics of a simple genetic algorithm are surprisingly simple, involving nothing more complex than copying strings and swapping partial strings (Goldberg, 1989). Given a clearly defined problem to be solved and a bit string representation for candidate solutions, a simple GA works as follows (Mitchell, 1996): 1. Start with a randomly generated population of n l-bit chromosomes (candidate solutions to a problem). 2. Calculate the fitness f(x) of each chromosome x in the population. 3. Repeat the following steps until n offspring have been created: a. Select a pair of parent chromosomes from the current population, the probability of selection being an increasing function of fitness. Selection is done "with replacement," meaning that the same chromosome can be selected more than once to become a parent. b. With probability Pc (the "crossover probability" or "crossover rate"), cross over the pair at a randomly chosen point (chosen with uniform probability) to form two offspring. If no crossover takes place, form two offspring that are exact copies of their respective parents. (Note that here the crossover rate is defined to be the probability that two parents will cross over in a single point. There are also "multi-point crossover'' versions of the GA in which the crossover rate for a pair of parents is the number of points at which a crossover takes place.) c. Mutate the two offspring at each locus with probability pm (the mutation probability or mutation rate), and place the resulting chromosomes in the new population. If n is odd, one new population member can be discarded at random. 4. Replace the current population with the new population 5. Go to step2 | |
