The Genetic Algorithm*
|
Components of GA Representation Scheme GA was derived from a study of biological systems. In biological systems evolution takes place on chromosomes-organic devices for encoding the structure of living things. A living being is only a decoded structure of the chromosomes. Natural selection is the link between chromosomes and the performance of the decoded structures. In GA, the design variables or features that characterize an individual are represented in ordered list called string. Each design variable corresponds to gene and the string of the design variables corresponds to chromosomes in biological systems. Bit strings- lists of 0` s and 1` s, have been found to be effective in representing a wide variety of information in the problem domains involving function optimization. A drawback of bit string representation is the presence of hamming cliffs –the hamming distances between the binary codes of adjacent integers. For example, 01111 and 10000 are the integer representation of 15 and 16 respectively, but have a hamming distance of 5. Gray codes suggested alleviating the problem by ensuring that the codes for adjacent integers always have a hamming distance of 1.
GA operates with a set of strings instead of a single string. This set or population of strings goes through the process of evolution to produce new individual strings. To begin with, the initial population could be seeded with heuristically chosen strings or at random. In either case, the initial population should contain a wide variety of structures. Evaluation Function The evaluation function is a procedure to determine the fitness of each string in the population and is very much application oriented. Since GA proceeds in the direction of evolving better fit strings and the fitness values is the only information available to GA, the performance of the algorithm is highly sensitive to the fitness values. In case of optimization routines, the fitness is the value of the objective function to be optimized. GA is basically unconstrained search procedures in the given problem domain. Any constraints associated with the problem could be incorporated into the objective function as penalty function. Parent Selection Techniques When breeding new chromosomes, we need to decide which chromosomes to use as parents. The selected parents must be the fittest individuals from the population but we also want sometimes to select less fit individuals so that more of the search space is explored and to increase the chance of producing promising offspring. The disadvantage of always using, the top few chromosomes is that the population quickly converges to one of these individuals and produces sub-optimal solution known as premature convergence. Two common selection techniques are listed below; - Roulette Wheel Selection. The idea behind the roulette wheel selection parent selection technique is that each individual is given a chance to become a parent in proportion to its fitness evaluation. It is called roulette wheel selection as the chances of selecting a parent can be seen as spinning a roulette wheel with the size of the slot for each parent being proportional to its fitness. Obviously those with the largest fitness (and slot sizes) have more chance of being chosen. The problem with roulette wheel selection is that one member can dominate all the others and get selected a high proportion of times. The reverse is also true. If the evaluation of all the members is very close to one another then they will have an almost equal chance of being selected. - Tournament Selection. In tournament selection, potential parents are selected and a tournament is held to decide which of the individuals will be the parent. Using the evaluation to choose parents can lead to problems. For example, if one individual has an evaluation that is higher than all the other members of the population then that chromosome will get chosen a lot and will dominate the population. Similarly, if the population has almost identical evaluations then they have an almost equal chance of being selected, which will lead to an almost random search. In order to solve this problem, each chromosome is sometimes given two values, an evaluation and a fitness. The fitness is a normalized evaluation so that parent selection is done more fairly. Some of the methods for calculating fitness are described below. - Windowing. The windowing evaluation technique takes the lowest evaluation and assigns each chromosome a fitness equal to the amount it exceeds this minimum. - Fitness ranking, individuals are sorted in order of raw fitness, and then new fitness values are assigned according to rank. This may be done either linearly or exponentially. Fitness ranking can cease over-compression problem.
The Genetic Algorithm * This is a part of the Literature Review for my undergraduate thesis on Optimal Capacitor Allocation. Bibliography can be found HERE |