As we know, evolution of creatures on the Earth started from a one-cell creature. Natural Evolution
was difficult to understand before Charles Darwin’s Theory of evolution.
Genetic Algorithm can be used to simulate the Natural Evolution. In fact this algorithm itself is based
on the Theory of Evolution.
Before we discuss what is Genetic Algorithm, Let us think ‘Why Dinosaurs disappeared?’
Answer is explained by Genetic Algorithm, Which is based on Charles Darwin’s Theory of evolution
(also known as theory of natural selection or Survival of the Fittest )
ABSTRACT
As we know, evolution of creatures on the Earth started from a one-cell creature. Natural Evolution
was difficult to understand before Charles Darwin’s Theory of evolution.
Genetic Algorithm can be used to simulate the Natural Evolution. In fact this algorithm itself is based on the Theory of Evolution.
Before we discuss what is Genetic Algorithm, Let us think ‘Why Dinosaurs disappeared?’ Answer is explained by Genetic Algorithm, Which is based on Charles Darwin’s Theory of evolution (also known as theory of natural selection or Survival of the Fittest ).
GENETIC ALGORITHM
The terminology associated with genetic algorithms comes from the field of Genetics, hence the name. The idea is to simulate the natural process of evolution.
Genetic Algorithm is not the gene coding. It is a Computer algorithm that resides on the principles of genetics and evolution.
Genetic Algorithm is supposed to do, what nature does. The fittest chromosomes are selected as parents. Crossover and Mutation is performed over them. As a result, children are produced. Then children become parents and this process continues forever till some candidate chromosomes are sufficiently fit. Dinosaurs lost their fitness with time. That’s why, they disappeared.
Abbildung in dieser Leseprobe nicht enthalten
Figure - Process of Natural Evolution
SELECTION
Selection models the principle of “survival of the fittest”. Nature always selects the best. For simulation, fitness of a chromosome is expressed through a fitness function. Fitness of the gene is calculated and the two chromosomes with best fitness value are selected as parents.
FITNESS FUNCTION
Fitness function is an evaluation function that determines what solutions are better than others.
Fitness is computed for each individual.For example, f(x) = 15 x + 3
Small samples of chromosomes are taken and one chromosome with the best fitness in each sample is
selected. These are the chromosomes with local maximum.
Abbildung in dieser Leseprobe nicht enthalten
Figure - Local maximum: chromosome locations on the surface of the peak function
Two best chromosomes are selected out of the chromosomes on the local maximum for being the parents.
Abbildung in dieser Leseprobe nicht enthalten
Figure - global maximum : Chromosome locations on the surface of the peak function
REPRESENTATION OF CHROMOSOME
A chromosome consists of a number of genes, and each gene is represented by 0 or 1.
Abbildung in dieser Leseprobe nicht enthalten
CROSSOVER
Crossover is sexual reproduction. It combines genetic material from two parents, in order to produce superior offspring. First, the crossover operator randomly chooses a crossover point where two parent chromosomes break, and then exchanges the chromosome parts after that point. As a result, two new offspring are created.
Abbildung in dieser Leseprobe nicht enthalten
Figure – Crossover of the chromosomes
MUTATION
Mutation is a genetic operator that alters one or more gene values in a chromosome from its initial state. It introduces randomness into the population. Mutation is performed in order to avoid entering unstable state.
Abbildung in dieser Leseprobe nicht enthalten
Figure - Mutation of a chromosome
SIMULATION OF NATURAL EVOLUTION
In the early 1970s, John Holland introduced the concept of genetic algorithms. His aim was to make computers do what nature does.
Nature has an ability to adapt and learn without being told what to do. In other words, nature finds good chromosomes blindly. Genetic Algorithm do the same.
The Genetic Algorithm uses a measure of fitness of individual chromosomes to carry out reproduction. As reproduction takes place, the crossover operator exchanges parts of two single chromosomes, and the mutation operator changes the gene value in some randomly chosen location of the chromosome.
BASIC SIMULATION STEPS
Step 1: Represent the problem variable domain as a chromosome of a fixed length, choose the size of a chromosome population, the crossover probability and the mutation probability.
Step 2: Define a fitness function to measure the performance, or fitness, of an individual chromosome in the problem domain. The fitness function establishes the basis for selecting chromosomes that will be mated during reproduction.
Step 3: Randomly generate an initial population of chromosomes of size N- x1, x2, . . . , xN.
Step 4: Calculate the fitness of each individual chromosome- f (x1), f (x2), . . . , f (xN).
Step 5: Select a pair of chromosomes for mating from the current population. Parent chromosomes are selected with a probability related to their fitness.
Step 6: Create a pair of offspring chromosomes by applying the genetic operators - crossover and mutation.
Step 7: Place the created offspring chromosomes in the new population.
Step 8: Repeat Step 5 until the size of the new chromosome population becomes equal to the size of the initial population, N.
Step 9: Replace the initial (parent) chromosome population with the new (offspring) population.
Step 10: Go to Step 4, and repeat the process until the termination criterion is satisfied.
Abbildung in dieser Leseprobe nicht enthalten
Figure – Reproduction Steps
CONCLUSION
Natural Evolution can be simulated using Genetic Algorithm. Chromosomes can be represented as group of Genes , which are represented as 0 or 1. The fittest chromosomes are selected as parents. Crossover and Mutation is performed over them. As a result, children are produced. Then children become parents and this process continues.
REFERENCES
http://www.biologyinmotion.com/evol/index.html http://www.obitko.com/tutorials/genetic-algorithms/ http://www.aaai.org/AITopics/pmwiki/pmwiki.php/AITopics/GeneticAlgorithms