The Genetic Algorithm*
|
Genetic Operators Crossover - Simple Genetic Algorithm (SGA) uses 1-point crossover, where mating chromosomes are cut once. Other crossover techniques have also been devised, often involving more than one cut point. In 2-point crossover, chromosomes are regarded as loops by connecting the ends together. Two cut points decide a segment, and two chromosomes exchange the segment. It performs the same task as 1-point cross over, but more general.
1-point crossover Uniform crossover involves an average of L/2 crossover points for strings of length L. In uniform crossover, each gene in the offspring is created by copying the corresponding gene from either parents according to a randomly generated crossover mask. Two-Point Crossover vs. Uniform Crossover
- Despite theoretical analysis, however, it appears difficult to predict when a particular crossover form will be optimal for a given problem. Spears [16] provide a theoretical analysis with respect to disruption of sampling distribution between 1-point crossover, 2-point crossover and uniform crossover, although, disruption analysis alone is not sufficient to predict or select the optimal form of crossover. According to [16], 2 point crossover is the least disruptive among crossover operators, while uniform crossover is the most disruptive. However, high disruption rate is not bad at all time during the search process. Since high disruption stress exploration at the expense of exploitation, there are important situations in which minimizing disruption hinders the adaptive search process by overemphasizing exploitation at the expense of needed exploration. One of the clearest examples of this is when the population size is too small to provide the necessary sampling accuracy for complex search spaces and when the population losses diversity when it converge towards a common area of the search space. From this analysis, [16] propose a simple adaptive crossover that adapts the crossover operator from 2-point crossover to uniform crossover during the run. Spears [17] provide an experimental analysis between two point crossover, uniform crossover and a proposed 1 bit adaptation on a 1 peak and 6 peaks objective function. Experimental results [17] showed that uniform crossover performs better than two-point crossover for problems at any level of complexity, for problems with small population size and for problems that involves a longer bits of chromosome. Mutation - Mutation is the process of random modification of the value of a string with small probability. It is not a primary operator but it ensures that the probability of searching any region in the problem space is never zero and prevent s complete loss of genetic material through reproduction and crossover. Elitism - It is sometimes the case that a good solution is found early on in the GA run but gets deleted from the population as the GA progresses. One solution is to “remember” the best solution found so far. Alternatively a technique called elitism can be used. This technique ensures that the best members of the population are carried forward from one generation to the next. Genetic Parameters Population size - Population size affects the efficiency of the algorithm. If we have smaller population, it would only cover a small search space and may results in poor performance. A larger population would cover more space and prevent premature convergence to local solutions. At the same time, a large population needs more evaluation per generations and may slow down the convergence rate. As a general observation of previous works on GA, increase in complexity of the algorithm leads to a need for larger population size. Khan [8] reviews the previous studies done in determination and optimization of population size. Probability of Crossover
- Probability of crossover or crossover rate is the parameter that effects the rate at which the crossover operator is applied. A higher crossover rate introduces new strings more quickly into the into the population. For uniform crossover, a higher probability of contributing ones parents allele lowers the rate of disruption. If the crossover rate is too high, high performance strings are eliminated faster that selection can produce improvements. A low crossover rate may cause stagnation due to the lower exploration rate. Probability of Mutation
- Probability of mutation or mutation rate is the probability with which each bit position of each string in the new population undergoes a random change after a selection process. A low mutation rate helps to prevent any bit positions from getting stuck to a single values, where as a high mutation rate results in essentially random search. Back [3] review the literatures on mutation parameters of genetic algorithm.
The Genetic Algorithm * This is a part of the Literature Review for my undergraduate thesis on Optimal Capacitor Allocation. Bibliography can be found HERE |
