Simulation of Natural Evolution

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