CHAPTER 15

GENETIC ALGORITHM

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
General Introduction to GAs
 Genetic algorithms (GAs) are a technique to solve problems which
need optimization.

 GAs are a subclass of Evolutionary Computing and are random

search algorithms.

 GAs are based on Darwin’s theory of evolution.

 History of GAs:
• Evolutionary computing evolved in the 1960s.
• GAs were created by John Holland in the mid-1970s.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Biological Background (1) – The Cell
 Every cell is a complex of many small “factories”
 working together.
 The center of this all is the cell nucleus.
 The nucleus contains the genetic information.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Biological Background (2) – Chromosomes
 Genetic information is stored in the chromosomes.

 Each chromosome is build of DNA.

 Chromosomes in humans form pairs.

 There are 23 pairs.

 The chromosome is divided in parts: genes.

 Genes code for properties.

 The posibilities of the genes for one property is called: allele.

 Every gene has an unique position on the chromosome: locus.

“Principles of Soft Computing, 2nd Edition”
by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Biological Background (3) – Genetics
 The entire combination of genes is called genotype.
 A genotype develops into a phenotype.
 Alleles can be either dominant or recessive.
 Dominant alleles will always express from the genotype to the
fenotype.
 Recessive alleles can survive in the population for many
generations without being expressed.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Biological Background (4) – Reproduction
 Reproduction of genetical
information:
• Mitosis,
• Meiosis.

 Mitosis is copying the same

genetic information to new
offspring: there is no
exchange of information.

 Mitosis is the normal way of

growing of multicell structures,
like organs.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Biological Background (5) – Reproduction
 Meiosis is the basis of sexual
reproduction.

 After meiotic division 2 gametes

appear in the process.

 In reproduction two gametes

conjugate to a zygote wich will
become the new individual.

 Hence genetic information is

shared between the parents in
order to create new offspring.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Biological Background (6) – Natural Selection
 The origin of species: “Preservation of favorable variations and
rejection of unfavorable variations.”

 There are more individuals born than can survive, so there is a

continuous struggle for life.

 Individuals with an advantage have a greater chance for survive:

survival of the fittest. For example, Giraffes with long necks.

 Genetic variations due to crossover and mutation.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm (1) – Search Space
 Most often one is looking for the
best solution in a specific subset
of solutions. 2.5

 This subset is called the search

space (or state space). 2

 Every point in the search space is 1.5

a possible solution.
 Therefore every point has a
1

fitness value, depending on the 0.5

problem definition.
 GAs are used to search the search
0
0 100 200 300 400 500 600 700 800 900 1000

space for the best solution, e.g. a

minimum.
 Difficulties are the local minima
and the starting point of the
“Principles of Soft Computing, 2nd Edition”
search. by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm (2) – Basic Algorithm
 Starting with a subset of n randomly chosen solutions from the
search space (i.e. chromosomes).
This is the population.

 This population is used to produce a next generation of

individuals by reproduction.

 Individuals with a higher fitness have more chance to reproduce

(i.e. natural selection).

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Comparison of Natural and GA Terminology

Natural Genetic Algorithm

Chromosome String
Gene Feature or character
Allele Feature value
Locus String position
Genotype Structure
Phenotype Parameter set, a decoded structure

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm (3) – Basic Algorithm

Outline of the basic algorithm

0 START : Create random population of n chromosomes

1 FITNESS : Evaluate fitness f(x) of each chromosome in the
population
2 NEW POPULATION
1 REPRODUCTION/SELECTION : Based on f(x)
2 CROSS OVER : Cross-over chromosomes
3 MUTATION : Mutate chromosomes

3 REPLACE : Replace old with new population: the new generation

4 TEST : Test problem criterium
5 LOOP : Continue step 1 – 4 untill criterium is satisfied

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
 • All individuals in population
evaluated by fitness function.

• Individuals allowed to
reproduce (selection),
crossover, mutate.

Flowchart of GA
“Principles of Soft Computing, 2nd Edition”
by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
“Principles of Soft Computing, 2nd Edition”
by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Reproduction Cycle
1. Select parents for the mating pool
(size of mating pool = population size).

2. Shuffle the mating pool.

3. For each consecutive pair apply crossover.

4. For each offspring apply mutation (bit-flip independently for each

bit).

5. Replace the whole population with the resulting offspring.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Coding
 Chromosomes are encoded by bitstrings.

 Every bitstring therefore is a solution but not necessarily the best

solution.

 The way bitstrings can code differs from problem to problem.

1
Either sequence of
0 on/off or the
0 number 9

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Crossover (Single Point)
 Choose a random point on the two parents.

 Split parents at this crossover point.

 Create children by exchanging tails.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Crossover (n Points)
 Choose n random crossover points.

 Split along those points.

 Glue parts, alternating between parents.

 Generalization of 1 point.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Uniform Crossover
Generate uniformly random number.

X1 = 0110001010
X2 = 1100000111
Uniformly generated = 1 0 0 0 0 0 1 0 0 0
As a result, the new population becomes,

X1 = 1110000010

X2 = 0100001111

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Mutation
 Alter each gene independently with a probability pm
 pm is called the mutation rate
• Typically between 1/pop_size and 1/ chromosome_length

00010101 0011001 01111000 00000000 00001000 00000010

00100100 10111010 11110000 10000010 00000010 00000000
11000101 01011000 01101010 00000000 00010000 00000000
11000101 01011000 01101010 00010000 00000000 01000000

00010101 00110001 01111010

10100110 10111000 11110000
11000101 01111000 01101010
11010101 01011000 00101010
“Principles of Soft Computing, 2nd Edition”
by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – Selection
 Main idea: Better individuals get higher chance:

• Chances are proportional to fitness.

• Implementation: Roulette wheel technique
» Assign to each individual a part of the roulette wheel.
» Spin the wheel n times to select n individuals.

1/6 = 17%
fitness(A) = 3

A B fitness(B) = 1
C
3/6 = 50% 2/6 = 33% fitness(C) = 2

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Genetic Algorithm – An Example
 Simple problem: max x2 over {0, 1, …, 31}

 GA approach:
• Representation: binary code, e.g. 01101  13
• Population size: 4
• 1-point xover, bitwise mutation
• Roulette wheel selection
• Random initialisation

 One generational cycle performed manually is shown here.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Example : Selection

4 1
31% 14%

5% 3
49%
2 “Principles of Soft Computing, 2nd Edition”
by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Example : Crossover

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Example : Mutation

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Simple Genetic Algorithm
 Has been subject of many (early) studies

• still often used as benchmark for novel Gas.

 Shows many shortcomings, e.g.

• Representation is too restrictive.

• Mutation & crossovers only applicable for bit-string & integer
representations.
• Selection mechanism sensitive for converging populations with
close fitness values.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Comparison of GA with Traditional Optimization
Techniques
 GA works with the coding of solution set and not with the solution
itself.

 GA uses population of solutions rather than a single solution for

searching.

 GA uses fitness function for evaluation rather the derivatives.

 GA uses probabilistic transition and not deterministic rules.

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
References
 Holland, J. (1992), Adaptation in natural and artificial systems ,
2nd Ed. Cambridge: MIT Press.

 Davis, L. (Ed.) (1991), Handbook of genetic algorithms. New York:

Van Nostrand Reinhold.

 Goldberg, D. (1989), Genetic algorithms in search, optimization

and machine learning. Addison-Wesley.

 Fogel, D. (1995), Evolutionary computation: Towards a new

philosophy of machine intelligence. Piscataway: IEEE Press.

 Bäck, T., Hammel, U., and Schwefel, H. (1997), ‘Evolutionary

computation: Comments on the history and the current state’, IEEE
Trans. On Evol. Comp. 1, (1)
“Principles of Soft Computing, 2nd Edition”
by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.
Online Resources

 http://www.spectroscopynow.com

 http://www.cs.bris.ac.uk/~colin/evollect1/evollect0/index.htm\

 IlliGAL (http://www-illigal.ge.uiuc.edu/index.php3)

 GAlib (http://lancet.mit.edu/ga/)

“Principles of Soft Computing, 2nd Edition”

by S.N. Sivanandam & SN Deepa
Copyright  2011 Wiley India Pvt. Ltd. All rights reserved.