Topics
GAs belong to a class of algorithms which imitate the principles of natural
evolution for parameter optimization problems.
Next, a way of measuring the "fitness" of the chromosomes so that good
solutions are selected to be parents is needed. This is analogous to natural
selection, where "survival of the fittest" is said to occur. The fitness
function selected is specific to the particular application, but generally
has a positive value which is large when the solution is good and small when the
solution is bad.
The good chromosomes for the next generation are selected based upon their
fitness function using a mechanism called roulette-wheel selection (Fig. 1).
Each chromosome has a fitness, which can be regarded as a portion of the total
fitness of the population. If this is drawn as a pie chart where the total area
of the pie corresponds to the total fitness of the population, then each individual
has a slice of the pie with a size proportional to its own fitness (Fig. 2).
The pie is spun like a roulette wheel with a pointer at a fixed position. When the
wheel stops spinning, the pointer indicates the individual which is to be selected
as a parent. The probability of the pointer pointing to any individual is proportoinal
to the size of the slice of that individual in the pie. In other words, the
number of times an individual is selected is proportional to its fitness function.
If there are N individuals, the wheel is spun N times.
Crossover and Mutation are the common genetic operators. Offspring
for the next generation are produced by selecting pairs of parent
chromosomes from the selected list and crossing over some of their genetic
material. The number of parents to be selected randomly for crossover is based
on the probability of crossover. The result is two offspring chromosomes
which have the properties of the two parents.
Crossover is done by generating a random number that corresponds to the position
along the chromosome. The binary digits are then swapped between the two parents
at that point for a specified length to create two new individuals.
Introduction
The essential features of a GA are the "chromosomes" that contain the genetic
information. They are the main carriers of hereditary information. Genes, which
represent hereditary factors, are lined up on a chromosome. In a GA, chromosomes
are strings of data that define a particular solution for the problem at hand.
For example, a chromosome representing six genes might be specified as a six digit
binary number, say [110010].A population of these chromosemes, corresponding
to a certain number of individual solutions to the problem is created randomly
initially. Fitness of Chromosomes
Selection of Chromosomes
Genetic Operators - Crossover
| Parent 1 | [1011100110] | Offspring 1 | [1010011110] |
| Parent 2 | [1010011100] | Offspring 2 | [1011100110] |
Mutation is usually defined by the probability of mutation, which
is usually set to a low value eg. 0.001, which means one out of 1000 chromosomes
will undergo mutation. The bits to be mutated are randomly selected. After it
is selected, it is mutated. So if it is 0, it becomes 1 and vice versa.
After the genetic operations, we come up with a new generation of solutions
breeded from their parents. They are supposed to be healthier than their parents.
Genetic Operators - Mutation
This process of breeding and evaluation continues, with the average fitness of
the population in each generation being monitored along with the individual
fitness of the fittest individuals. Usually the process is terminated when the
average fitness value reaches a stable value.
For feed back:
sramachandran@mailcity.com