|
|
|
Genetic algorithms were invented by Holland to mimic some of the processes of natural
evolution and selection. In nature, each species needs to adapt to a complicated
and changing environment in order to maximize the likelihood of its survival. The knowledge that each species gains is encoded in its chromosomes, which undergo transformations when reproduction occurs. Over a period of time, these changes to the chromosomes give rise to species that are more likely to survive, and so have a greater chance of passing their improved characteristics on to future generations. Of course, not all changes will be beneficial but those that are not tend to die out. Holland's genetic algorithm attempts to simulate nature's genetic algorithm in the following manner. The first step is to represent a legal solution to the problem you are solving by a string of genes that can take on some value from a specified finite range or alphabet. This string of genes, which represents a solution, is known as a chromosome. Then an initial population of legal chromosomes is constructed at random. At each generation, the fitness of each chromosome in the population is measured. The fitter chromosomes are then selected to produce offspring for the next generation, which inherit the best characteristics of both the parents. After many generations of selection for the fitter chromosomes, the result is hopefully a population that is substantially fitter than the original. All genetic algorithms consist of the following main components: Chromosomal Representation Each chromosome represents a legal solution to the problem and is composed of a string of genes. The binary alphabet {0,1} is often used to represent these genes but sometimes, depending on the application, integers or real numbers are used. In fact, almost any representation can be used that enables a solution to be encoded as a finite length string. Initial Population Once a suitable representation has been decided upon for the chromosomes, it is necessary to create an initial population to serve as the starting point for the genetic algorithm. This initial population is usually created randomly. From empirical studies, over a wide range of function optimization problems, a population size of between 30 and 100 is usually recommended. Fitness Evaluation Fitness evaluation involves defining an objective or fitness function against which each chromosome is tested for suitability for the environment under consideration. As the algorithm proceeds we would expect the individual fitness of the "best" chromosome to increase as well as the total fitness of the population as a whole. Selection We need to select chromosomes from the current population for reproduction. If we have a population of size 2N, the selection procedure picks out two parent chromosomes, based on their fitness values, which are then used by the crossover and mutation operators (described below) to produce two offspring for the new population. This selection/crossover/mutation cycle is repeated until the new population contains 2N chromosomes i.e. after cycles. The higher the fitness value the higher the probability of that chromosome being selected for reproduction. Crossover and Mutation Once a pair of chromosomes has been selected, crossover can take place to produce offspring. A crossover probability of 1.0 indicates that all the selected chromosomes are used in reproduction i.e. there are no survivors. However, empirical studies have shown that better results are achieved by a crossover probability of between 0.65 and 0.85, which implies that the probability of a selected chromosome surviving to the next generation unchanged (apart from any changes arising from mutation) ranges from 0.35 to 0.15. If we only use the crossover operator to produce offspring, one potential problem that may arise is that if all the chromosomes in the initial population have the same value at a particular position then all future offspring will have this same value at this position. For example, if all the chromosomes have a 0 in position two then all future offspring will have a 0 at position two. To combat this undesirable situation a mutation operator is used. This attempts to introduce some random alteration of the genes e.g. 0 becomes 1 and vice versa. Typically this occurs infrequently so mutation is of the order of about one bit changed in a thousand tested. Each bit in each chromosome is checked for possible mutation by generating a random number between zero and one and if this number is less than or equal to the given mutation probability e.g. 0.001 then the bit value is changed. This completes one cycle of the simple genetic algorithm. The fitness of each chromosome in the new population is evaluated and the whole procedure repeated, i.e. Generate random population REPEAT evaluate fitness of current population select chromosomes, based on fitness, for reproduction perform crossover and mutation to give new improved population UNTIL finished Where finished indicates either an optimal or suitable sub optimal has been found or the maximum number of generations has been exceeded. |