Genetic Algorithm (GA)
Genetic Algorithms (GAs), first proposed and analyzed by John Holland in 1975, are optimization techniques based on natural evolution and adaptation. In a GA, a population of candidate solutions is always maintained. Candidate solutions are sometimes named as Individuals, Chromosomes, etc. Each Individual is an encoded representation of variables of the problems at hand. Each component (variable) in an Individual is termed as Gene.
The sequences of a GA are initial population generation, selection of population for reproduction, creation of new population by using recombination and mutation, evaluation of new population, replacement of old population by new generation. The skeleton of a GA may be as follows:
1.t=0; Generate initial population P(t) at random; 2.Evaluate each individual in P(t); 3.While termination condition not satisfied do begin t=t+1; Select some parents S(t) from P(t-1); Generate offspring Q(t) by applying crossover and mutation on S(t); Evaluate offspring Q(t); Combine old population and new offspring to generate P(t); end;
In many problems, the initial population is generated randomly, crossover and mutation are performed probabilistically; so GAs are somehow stochastic.
Many issues arise in design of a Genetic Algorithm. First of all how to encode the problem, i.e. how to transfer phenotype to genotype and vice versa. Some problems can be solved using binary encoding while some by order encoding (for example, Traveling Salesman Problem (TSP)). Fitness is calculated according to the objective function. For TSP, fitness can be negative of distance of a tour or inverse of distance; so the lower distance, the better fitness. Next comes selection strategy--how to select parents for recombination. Whatever may be the selection method, the better chromosome will have better chance to be selected. Roulette wheel selection, tournament selection and rank-based selection are common selection methods.
Crossover operator is crucial for the success of a GA and it is also problem dependent. If the encoding is binary, the crossover is easier to implement. Consider two parents: A=010101101101 and B=111010 000111. To apply one-point crossover on these parents, first we have to fix the crossover point; usually this is determined randomly. Suppose the crossover point is between position 6 and 7. Performing one point crossover two offspring are produced as C and D. This is illustrated below:
Parents: A:010101101101 B:111010000111 Offspring:C:010101000111 D:111010101101Crossover is applied in the hope the new offspring will be better than its parents. Crossover is applied with higher probability. One point, two points and uniform crossover are widely used. Partially matched crossover (PMX), order crossover, cycle crossover, edge recombination crossover and edge assembly crossover are commonly used crossing techniques for combinatorial optimization like TSP. A practical approach of PMX can be found in details in the implementation of TSP by GA.
Mutation is a genetic operator that is used to alter one or more genes in an individual. This operator is used to prevent GAs from stagnating at local optima. For example, if C of the above example is mutated at position 3 (bit is inverted), the new mutated offspring would be:
Replacement strategy determines which offspring will replace which old individuals. Elitism, steady state replacement and CHC selection are widely used for this purpose. In CHC strategy, if the original population size is N, N offspring are generated, they are combined to get 2N individuals which are then sorted and the best N individuals are accepted for next generation.