Transcript Genetic Algorithms

Genetic Algorithms





Genetic Algorithms – What are they? And how they are
inspired from evolution.
Operators and Definitions in Genetic Algorithms paradigm.
-chromosomes
-crossover, mutation and selection
-population, fitness and elitism
Applications of Genetic Algorithms.
Real Parameter Genetic Algorithms.
Parent Centric Recombination Operator & G3 model.

Genetic algorithms are search algorithms based
on the mechanics of natural selection and natural
genetics (Goldberg 1989).
 GA s exploit the idea of the survival of the fittest
and an interbreeding population to create a novel
and innovative search strategy.
 In nature weaker members of a species tend to die
away, leaving the stronger and fitter to mate,
create offspring which evolve themselves into
newer species and ensure the continuing survival
of the fittest.
 GA s are a form of randomized search, in that the
way in which solutions are chosen and combined
is a stochastic process rather than traditional
deterministic problem solving techniques.
Operators and Definitions


Chromosome -- A possible solution to a
problem represented traditionally as a
binary string ( e.g. 11000110)
Crossover-- When two individuals mate,
both parents pass their chromosomes onto
their offspring. The two chromosomes
come together and swap genetic material.
In binary GA s crossover is
performed by swapping a part of binary
strings between two solutions at a
randomly chosen cross-site with some
probability. It is a binary operator.
Operators and Definitions


Mutation – Conversion of proteins from one to
another.
In Binary GA s mutation is performed by
converting some random bit of a binary string
into its complementary bit (ie a 1 to a 0 or vice
versa) with some probability. It is a unary
operator.
Mutation will help prevent the population from
stagnating. It adds “fresh blood” to a population
of solutions to a problem. It adds diversity.
Operators and Definitions




Fitness – The measure of goodness of a solution. (e.g.
the function value of a solution in an optimization
problem).
Selection – The Darwinian selection mechanism to
eliminate bad solutions in a population.
Population – A pool of solutions represented as binary
strings (chromosomes) that undergo
-- selection (based on their fitness)
-- crossover (mutually among themselves randomly)
-- mutation (randomly)
Note – crossover and mutation destroy old solutions
Elitism – Some elite (good) solutions are carried onto
the next generation without being destroyed. It is
considered to be a good strategy.
Roulette Wheel Selection
Solutions are selected on the
basis of the percentage that
their fitness contributes to the
cumulative fitness of the whole
population
GA flowchart
GA dynamics
Applications of GA s

GA s are especially useful when
-- The search space is large, complex or poorly understood.
-- Domain knowledge is scarce or expert knowledge is difficult to
encode to narrow the search space.
-- No mathematical analysis is available.
-- Traditional search methods fail.
Typically over the years GA s have been successfully applied to

Function and Structural Optimization

Database Query Optimization

Determination of Protein Structures

Scheduling Problems

Construction and Training of Neural Networks

Engineering Design

Multi-criteria Decision Making (one of the hottest fields for GA s)

Music Composition
Real Parameter Genetic Algorithms

A number of real world applications involve object variables which
are real valued
 In the past few years researchers have tried to simulate the
principles of crossover, mutation and selection in real-valued space
directly.
 A number of Real parameter crossover and mutation operators have
been proposed:
-- Simulated Binary Crossover (SBX) (Deb 1995)
-- Evolution Strategies (ES) (Rechenberg & Schwefel)
-- Unimodal Normal Distribution Crossover (UNDX) (Kita 1997)
-- Simplex Crossover (SPX) (Yamamura 1997)
-- Parent Centric Crossover (PCX) (Deb 2001)
Real Coded Crossovers

UNDX -- It is a generic multi-parent
crossover operator which emphasizes
offspring closer to the geometric centroid of
the parents.
UNDX
SPX

SPX – It is a generic multi-parent crossover
operator which uses a uniform probability to
generate offspring inside a simplex determined
by the parents.

PCX – It is a generic multi-parent crossover PCX
operator which emphasizes offspring closer to
the parents.
Some Test Functions for Real GA s

Schwefel’s Function
n
2
 ( x )
i
j
i 1

Ellipsoidal Function
j 1
n
 i * xi
2
i 1

Gen. Rosenbrock’s Function
n 1
2
2
100 * ( x  x )  ( xi 1)
i
i 1
(
i 1
2
)
Generalized Generation Gap Model (G3 model)
The breeding scheme of Binary GA s is modified as follows
 From Population P, select the best parent and (M-1) other
 1
parents randomly.
 Generate N offspring from the chosen M parents using
some recombination scheme. (UNDX, PCX etc).
 Choose two parents (p1 and p2) at random from the
population P.
 From the combined sub-population of p1, p2 and N
created offspring, choose the best two solutions and replace
p1 and p2 with these two solutions.
 Another modification is to replace only one parent in the
population with best offspring. (Modified G3 model)
Results


Graphically presented are the
number of function evaluations
required to find a solution of
fitness of 1e-20 for Felp as a
function of the pool size (N
here lambda).
A parametric study to find the
optimal population size.
Results

Graphically presented are the
number of function evaluations
required to find a solution of
fitness of 1e-20 for Fsch as a
function of the pool size (N here
lambda).
 A parametric study to find the
optimal population size.
Results

Graphically presented are the
number of function
evaluations required to find a
solution of fitness of 1e-20
for Fros as a function of the
pool size (N here lambda).
 A parametric study to find
the optimal population size.
Results
Best Fitness versus
function evaluations for
Schwefel’s function.
Results
Felp
Fsch
Frose
Comparison of G3 PCX with Differential Evolution
Results
Felp
Fsch
Frose
Scale Up study for G3 PCX
Conclusions




A comprehensive parametric study of Real
Parameter GA s was performed.
Comparisons of PCX with UNDX, SPX, ES, DE
and classical methods were performed.
Superiority of Parent Centric Recombination
Approach was seen.
Future Work.
-- Need to develop a mathematical model for
choosing the best set of parameters for a Real
Parameter GA.
-- Replacing traditional recombination operators in
Multi-objective GA s with PCX and seeing the
effect.