Evolutionary algorithms
Download
Report
Transcript Evolutionary algorithms
Prepared by
Barış GÖKÇE
1
Search Methods
Evolutionary Algorithms (EA)
Characteristics of EAs
Genetic Programming (GP)
Evolutionary Programming (EP)
Genetic Algorithms (GA)
Evolutionary Strategies (ES)
Summary
References
2
Search is very comman problem which is
included nearly all types of problems.
It is as difficult for computers as for humans.
In general, domain space is very huge, and it is
impossible to make a search by trying all
possible configurations.
There are many search methods which use
different heuristics.
3
4
A type of Guided Random Search
Used for optimization problems
Based on the idea of biological evolution
The power of the evolutionary algorithms is
limited by the lack of a clear genotypephenotype distinction.
It has its own parameters.
EAs are known as global optimization methods
which work well on ‘noisy’ functions which
have many local optima
5
Parameters of EAs may differ from one type to
another. Main parameters:
Population size
Maximum number of generations
Elitism factor
Mutation rate
Cross-over rate
There are six main characteristics of EAs
Representation
Selection
Recombination
Mutation
Fitness Function
Survivor Decision
6
t:=0;
InitPopulation(P,t);
EvaluateFitness(P,t);
while not terminate(P,t)
begin
t:=t+1;
SelectParents(P,Ps);
Recombine(Ps);
Mutate(Ps);
EvaluateFitness(Ps,t);
Survive(P,Ps);
end;
7
Representation:
How to define an individual
The way to store the optimization parameters.
Determined according to the problem.
Different types:
Binary representation
Real-valued representation
Lisp-S expression representation
Selection
Used to determine parents used to generation of next
population
Some types:
Truncation selection
Roulette wheel selection
Tournament selection
Neighborhood selection
8
Recombination
Determines how to combine the genes of selected parents
Types is determined according to the representation. These types:
Bits of the genes
Values of the genes
Mutation
Change on a single gene of the individual
Types is determined according to the representation. These types:
Switching bits
Updating the value of the gene
Fitness Function
Gives an intuition about how good the individual is.
Depends on directly to the problem
Survivor Decision
Idea of survival of the best individuals. It is about Elitism factor.
Usage of it is not advised. In general, overall best individual is
stored as a different individual not to loose reached best parameter
set, but they are not used during other operations.
9
It is used to find the proper program for given
problem.
It requires very high computation power, so it
is suitable for only simple problems.
There is no comman representation. But the
most famous representation is the Lisp
expression.
While the main operator is the cross-over,
mutation is used as secondary operator.
10
Cross-over method is to replace a gene of the
individual with that of another individual.
Individual pairs are selected randomly.
Mutation can be applied to only one of the
genes or to whole individual.
Meta-Genetic Programming is like to find the
program which finds the program. Even the
GP is suitable for simple problems, MetaGenetic Programming is suitable for simpler
problems
11
Because genetic programming and metagenetic programming are suitable relatively
simpler problems, there are not enough
samples for this type of algorithm.
Especially meta-genetic algorithm is a new
research area, so documentation on this
method is very sparse.
A good sample for genetic programming is:
http://alphard.ethz.ch/gerber/approx/default.html
12
There is no fixed structure for representation.
There is only mutation operation, and crossover is not used in this method.
Each child is determined by its parent in a way
of mutation.
So, we can conclude that there are three steps:
Initialize population and calculate fitness values for
initial population
Mutate the parents and generate new population
Calculate fitness values of new generation and
continue from the second step.
13
Mutation is at a very critical point, because it is
the only method which leads to the variation.
Main application areas:
Cellular design problems.
Constraint optimization
Testing students’ code
......
Not a widely used evolutionary algorithm,
because the variation between individuals is
very small and the convergence speed is not
enough.
14
It is used to find an optimum parameter set by
using the randomness.
It can be classified as global search heuristics,
because it uses many evolutionary biology
techniques, and randomness helps it to find
optimum parameter set.
Individuals are represented by byte arrays. So,
it is not feasible for real-valued application.
Gray coding is a very popular representation.
Genetic representation of solution domain and
fitness function are the two requirements of the
GA.
15
Main operator of the GA is the cross-over. Crossover method:
a pool is constructed from the parents.
During the generation of next population, pairs are
selected from that pool
Children are generated by the application of cross-over.
Mutation is the background operation. It is applied
to the children which are generated by cross-over.
Methods of the mutation are as follows:
One point
Two point
Cut and splice
16
Most popular selection algorithms for GA are
roulette wheel selection and tournament
selection.
Fitness function of GA is the scaled fitness
function.
GA is not effective in problems which the
fitness values of individuals are calculated as 1
or 0.
Samples:
http://homepage.sunrise.ch/homepage/pglaus/gentore.htm
http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html
17
This method is used for nearly all types of
problems. Some of them are:
Scheduling
Timetabling
Face recognition
NLP
Distributed computer network topologies
Learning robot behavior
Molecular structure optimizationGait
Software Engineering
Traveling Salesman Problem
18
Main property of ES is the usage of the realvectors as coding representation.
ES uses many operands which are based on
randomness; selection, cross-over and
mutation.
ES is a very flexible technique in the view of
the operands. Functionality of operands are
determined according to the problem
definition.
19
Representation: It allows us to represent
floating. By this way, search is done on the
continuous domain space. In addition to the
floating point representation, real-vector
representation can be used.
Selection: In selection, neighborhood method is
applied. There are two different types of ES
according to the selection set*:
plus selection (both parent and child)
comma selection (only parent)
Fitness function: Not scaled. It is calculated as
objective function values.
20
Recombination & Mutation: These operands
are very similar to the those of GA. The main
difference is that mutation amount is not
constant in ES. There are additional
parameters, sigma, which are used as the
mutation amount of the original mutation
amount. So, the mutation amount also gets
closer to the optimum value.
As recombination function, three main
functions can be used:
Arithmetic mean of the parents
Geometric mean of the parents
Discrete cross-over method.
21
Pseudocode of the ES is as follows:
generationNumber = 0;
initialization (β0 );
while ( !stoppig_criteria )
for ( l = 0; l< λ ; l++)
Ώl = reproduction ( βg , ρ );
sl = s_recombination ( Ώl, ρ );
sl' = s_mutation ( sl );
yl = y_recombination ( Ώl, ρ );
yl' = y_mutation ( yl );
Fl = F(yl');
βg' = { yl', sl', Fl };
switch selection_type
case comma-selection:
βg+1' = selection( βg' );
break;
case plus-selection:
βg+1' = selection( βg', βg );
break;
g = g + 1;
22
where βn represents the parents of nth population,
βn' represents the offsprings of nth population,
Ώl represents the offsprings after cross over process,
sl represents the sigma values of the offspring l,
sl' represents the mutated sigma values of the
offspring l,
yl represents the genes of the offspring l,
yl' represents the mutated genes of the offspring l.
g represents the generation number.
23
There are many application areas of the ES.
Some of them:
The Quadruped Gait parameter optimization
Optimization of Road Networks
Local Minority Game
Multi-Criterion Optimization
Optical Fibre Design
.....
24
25
Informed Search Algorithms slayts of the course CmpE 540.
http://en.wikipedia.org/wiki/Evolutionary_algorithm
http://www.cs.sandia.gov/opt/survey/ea.html
http://www.faqs.org/faqs/ai-faq/genetic/part2/section-3.html
http://en.wikipedia.org/wiki/Genetic_programming
http://alphard.ethz.ch/gerber/approx/default.html
http://en.wikipedia.org/wiki/Evolutionary_programming
http://en.wikipedia.org/wiki/Genetic_algorithm
http://homepage.sunrise.ch/homepage/pglaus/gentore.htm
http://www.ads.tuwien.ac.at/raidl/tspga/TSPGA.html
http://en.wikipedia.org/wiki/Evolution_strategy
26
?
27