Transcript Chap7

Genetic Algorithms
Underlying Concept
 Charles Darwin outlined the principle of
natural selection.
 Natural Selection is the process by which
evolution occurs.
 The fittest members of a species will survive
and propagate more than those less fit.
Development of GAs
 In 1975 John Holland developed the idea of
Genetic Algorithms
 These are algorithms that mimic the principles
of natural selection to solve problems.
 Often used for Optimization problems, and for
biological simulations.
The Basic Idea
 Possible solutions to a problem are labelled
“Chromosomes”
 An initial population of these chromosomes is
created and mated via crossover and mutation
algorithms to create 'offspring'
 This process is repeated until the optimal
solution is found.
Step-By-Step GAs
 Step 1: Choose an initial population of
chromosomes
 Step 2: Create an offspring population from the
parent population
 Step 3:the offspring undergo a crossover
 Step 4: mutations occur in the offspring population
(this is based on a probability algorithm)
 Step 5: evaluate the fitness of each offspring
 Step 6: replace parents with offspring, and repeat 25 until the optimal solution is reached
Psuedocode!
Choose an initial population of chromosomes
while (termination condition not satisfied) do
repeat
if(crossover condition satisfied) then{
select parent chromosomes;
choose crossover parameters;
perform crossover;
}
if(mutation condition satisfied) then{
select chromosome for mutation;
choose mutation point;
perform mutation;
}
Evaluate fitness of offspring;
until sufficient offspring created;
select new population;
end while
Courtesy of Reves, Colin R. Genetic Algorithms
– Principles and Perspectives : a Guide to GA
Theory.
Step 1 – The Initial Population
 These will be randomly generated strings in
the problem set
 The number of members in the initial
population is determined on a case by case
basis, but it is usually reliable in most cases to
use lg(string length) initial chromosomes.
Step 2 & 3 – Create Offspring and
Crossover
 Two parents are chosen from the set, and an
offspring is created.
 The parent's chromosomes are then combined
into the offspring through a process called
“crossover”, in which certain genes from each
parent are mixed together.
Crossover Schemes
 Linear Crossovers:

single-point crossover
A 'crossover point' is randomly chosen
 All of the genes (alleles) after the crossover point from
one parent are copied into their corresponding location
on the other.
 (a,b,c,d,e,f,g) and (1,2,3,4,5,6,7)
 Crossover point is 3
 (a,b,3,4,5,6,7) and (1,2,c,d,e,f,g) are created
 These are the offspring of the 2 parents

 There are many other crossover techniques, most involving the same
concept, but multiple crossover points
N-Point Crossover Algorithm
Choose a random integer n;
choose n cross points;
generate random permutation ð of (1...,n+1) for segment order;
designate one parent for copying;
k <-- 1;
repeat
copy all compatible alleles of segment ðk from designated parent;
swap parent designations;
k++;
until k = n+1;
if child incomplete then insert legal alleles at required position, using random tie
breaking if necessary.
Step 4 - Mutations?
 An important event for the evolution of any species is mutation. A
new trait is developed, and if it is beneficial, often it will be
propagated.
 The same must be true for GAs
 Mutation is not always required in all matings. So a probability of
mutation equation should be set up (this will vary depending on the
problem).
 Each time a new child is created a random number is generated and
checked by this mutation equation to see if a mutation should occur.
Step 5: Evaluate the Fitness
 In order to decide which traits are beneficial
and should be passed on, a fitness algorithm
must be performed on the children.
 These fitness algorithms are completely
problem specific
 There are 2 basic types of algorithm


Probability dependent
Rank Dependent
Probability Dependent Selection
 Each one of the offspring is analysed using
some problem specific algorithm to determine
the probability that it will lead to a successful
solution
 Roulette wheel type:


Each offspring is assigned a segment of the
roulette wheel based on its probability.
A random number is then generated, and
whichever section of the wheel it fall into is the
offspring that is chosen for reproduction
Rank Dependent Selection
 Each offspring is analysed by a ranking
algorithm and its fitness is returned as some
number.
 The greater the number the greater the fitness
 All of these ranks are ordered, and the best fit
offspring are chosen for reproduction.
Other Selection Methods
 Scaling
 Generational
 Hierarchical
Step 6
 The chosen offspring are then made the
parents for the next iteration of the process
 The algorithm repeats until some specified
condition (Problem Specific) is met.
Analysis of GAs
 Strengths

GAs are ‘parallel’

Can examine multiple solutions at once
 Limitations



Deceptive fitness functions
Can be time consuming
Only deal with one trait at a time