All great innovations have been inspired by observation from nature. Even Newton's laws came into being when Newton observed the falling apple. Likewise genetic algorithms were derived from the "Survival of the fittest" theory. For those who don't know the theory, I will give a brief description here.
The theory suggests that in a population of individuals, some individuals have better characteristics than others. These characteristics allow those individuals to better adapt to their environment. These individuals are said to be
fitter than the rest
. Due to the environmental conditions, these
fit individuals survive while those that are
unfit perish away. The fit individuals reproduce and pass on the characteristics to their offspring. Thus, over successive generations, the individuals become fitter and better suited to survive in their environment.
The
characteristics described above are encoded in what is known as
a gene, which are present in every organism's DNA. It is from these
genes that the term "genetic algorithms" was coined.
Genetic algorithms are basically search algorithms that employ the concepts of natural selection and survival of the fittest to find the optimal solution to a problem.
A typical genetic algorithm has the following stages:
- Encoding of characteristics on a chromosome.
- Generation of a random population of chromosomes.
- Evaluating the fitness of each individual on the basis of a fitness function.
- Selecting the individuals that would act as parents for next generation.
- Forming a new generation through recombination and/or variation.
- Repeating steps 3-5 until the population converges to an optimum solution.
In a real-life scenario, the fit individuals are selected on the basis of ability to survive in the environment. Similarly, in a genetic algorithm the factors that simulate this
environment are:
- the encoding of chromosomes.
- the fitness function.
Other factors that that are important are:
- the criterion for selecting parents for next generation.
- the techniques used for recombination and variation.
These are quite important in that if they are too strict we might end up converging to a local maximum, and if they are too lenient, it might take a long time to get the population to converge to an optimal solution. So, the optimal genetic algorithm should be balanced enough to explore new regions in the solution space and yet be able to achieve convergence in reasonable time.
Genetic algorithms have been employed in a wide variety of problems, ranging from biology to chemistry to finance. One of the major applications is to use genetic algorithms to evolve neural networks. For more info, you may want to follow these links:
