Transcript Document

A Generic Parallel Genetic
Algorithm
By Roderick Murphy
under the supervision of Mr Dermot Frost
What Are Genetic Algorithms?
• Search or optimisation procedures based on
the mechanisms of natural selection and
natural genetics.
i.e. the thoeries of this man
What Are Genetic Algorithms?
• They are ‘weak’ optimisation techniques – They
don’t use domain specific knowledge in their
search procedure.
• They generally involve evolving a population of
candidate solutions to a given problem.
• Evolution is carried out using operations inspired
by natural genetic variation and natural selection.
Search Spaces and Fitness
Landscapes
A Typical GA
• Random ‘guesses’ of the solution to the
problem – An initial population.
• A means of calculating how good a guess
solution is – A fitness function.
• A method of mixing good solutions to
produce better ones – Crossover.
• An operator to introduce diversity within
the population – Mutation.
GA Terminology
Chromosome / Genome
Gene
Allele
Locus
Phenotype / Organism
Generation
String of characters
Characters used (eg binary)
1 or 0 (for binary)
Position of gene in string
Candidate solution
Iteration
GA Operators
There are 3 main operators for a serial GA:
Selection
Crossover
Mutation
Selection
• The method by which
population members
(candidate solutions) are choosen.
• The chosen individuals will be combined
with each other to form offspring.
Selection methods
Common selection methods used in GAs are
• Fitness Proportionate Selection
• Rank Selection
• Tournament Selection
Fitness proportionate Selection
• Can be achieved using the roulette wheel
algorithm.
– Construct a roulette wheel with a marker
proportional to the fitness of each
individual as shown.
– When the arrow is spun the
probability of selecting an
individual is thus propotional
to the fitness of that individual.
Rank Selection
• All individuals are sorted according to their
fitness.
• Each individual is then assigned a
probability of being selected from some
prior probability density.
Tournament
Selection
• Select a group of N
(N>1) members.
• Select the fittest member of this group and
discard the rest.
Other Selection Techniques
• To overcome some of the problems associated
with selection (e.g. stagnation and premature
convergence), the following can be used
• Fitness scaling
– Ensures that extremely fit members are not selected too
often during fitness proportionate selection methods.
• Elitism
– A small number of the best individuals are retained so
that they will survive into the next generation.
Crossover
• The means by which individuals are
combined to form offspring.
Mutation
• The Mutation operator ensures
the gene pool does not become
too restricted.
• In GAs it is carried out by randomly
changing one or more of the alleles (bits) in
an individual’s chromosome.
• The probability of mutating a particular bit
is typically very small (~ 0.001).
Parallelising a Genetic Algorithm
• Genetic Algorithms are highly parallelisable
since most of the operators can be caried
out on individual members independently of
other members.
Parallelisation Methods
Common parallel GA prototypes:
• Master Slave prototype.
• Distributed, Asychronous Concurrent
prototype.
• Network model.
• Island model.
Master Slave prototype
Genetic
Algorithm
Master
Function
Evaluation
Function
Evaluation
Function
Evaluation
Local Search
Local Search
Local Search
Distributed, Asychronous
Concurrent prototype.
Concurrent
Process
Concurrent
Process
Concurrent
Process
Concurrent
Process
Shared
Memory
Concurrent
Process
Concurrent
Process
Concurrent
Process
Concurrent
Process
Network Model
GA
GA
GA
GA
GA
GA
Island Model
Island 1
Island 3
Island 2
Island 5
Island 4
Applications of GAs
• Optimisation tasks
• Immune Systems
• Automatic
Programming
• Ecology
• Population genetics
• Machine Learning
• Social Systems
• Economics
Generic Parallel GA Function
Population ParallelGeneticAlgorithm(
int nislands, int ngenerations,
int nmembers, int string_length,
GA_Op select_type, double select_arg,
int nelite, GA_Op cross_type,
double cross_prob, int ncross_points,
int *gene_lengths, double mut_prob,
GA_Op scaling_type, double scale_arg,
GA_Op mig_type, double *mig_prob,
double (*ObjectiveValueFunction)
(Population *, int, int, int)
);