Transcript A simple EA and Common Search Operators

A simple EA and Common
Search Operators
Temi avanzati di Intelligenza Artificiale - Lecture 2
Prof. Vincenzo Cutello
Department of Mathematics and Computer Science
University of Catania
Evolutionary Computation



...is the study of computational systems which use
ideas and get inspirations from natural evolution and
other biological systems
Evolutionary Algorithms (EAs) are closely linked to
AI techniques, especially search techniques. EAs can
be regarded as population-based stochastic
generate-and-test algorithms.
Evolutionary Computation (EC) techniques are used
in optimization, machine learning and automatic
design.
A simple EA and Common Search Operators Lecture 2
2
A simple Evolutionary Algorithm



1 Generate initial Population P(0) at random, and set i=0;
2 repeat
 3 Evaluate the fitness of each individual in P(i)
 4 Select parents from P(i) based on their fitness in P(i)
 5 Apply crossover to create offspring from parents
 6 Apply mutation to the offspring
 7 Select generation P(i+1) from current offspring O(i) and
parents P(i)
8 until finished
A simple EA and Common Search Operators Lecture 2
3
Example (Part 1)

Example Problem



Preparation: Decide Encoding



Binary Encoding
6 bit genotype length
Step 1: Create initial Population


Use EA to find the maximum of an unknown function
f(x,y)
With x,y integers between 0 and 8
Randomly assemble binary strings of length 6
Step 2: Enter loop
A simple EA and Common Search Operators Lecture 2
4
Example (part 2):

Step 3: Calculate Fitness



Decode genotypes into integer values
Compute fitness value from objective function
Step 4: Select n Parents



Randomly select m members of P(i) (e.g. m=2)
The best of these is the first parent
Repeat until all parents selected
(so-called "Tournament Selection")
A simple EA and Common Search Operators Lecture 2
5
Example (part 3)

Step 5: Perform Crossover




For each pair of 2 parents:
Select a random crossover point
Create two offspring from genotype segments of
parents
(so-called 'One-point Crossover')
Step 6: Perform Mutation



For each offspring:
Randomly select one bit
Flip this bit
(so-called 'Bitflip Mutation')
A simple EA and Common Search Operators Lecture 2
6
Example (part 4)

Step 7: Select next generation


E.g. keep the best 6 from current generation
and offspring
Step 8: Continue loop or terminate

E.g. Terminate after n loops without change in
the population
(So-called convergence)
A simple EA and Common Search Operators Lecture 2
7
Remarks

There is no restriction on the fitness (objective) function.


There is no need to know the exact form of the objective
function.



Simulation can be used to derive a fitness value
The initial population does not have to be generated randomly


It can be non-differentiable or even discontinuous
You can use existing knowledge to seed population
The representation does not have to be binary
There are alternative options for all steps of the algorithm

Genetic operators, selection, termination
A simple EA and Common Search Operators Lecture 2
8
Recombination / Crossover Operators





One-Point Crossover
K-Point Crossover
Uniform Crossover
Crossover rate: the probability of applying
crossover
Other operators for nonlinear representations
A simple EA and Common Search Operators Lecture 2
9
Mutation Operators





Bit-Flipping
Random bit assignment
Multiple bit mutations
Per-chromosome mutation rate vs. per-gene
(bit) mutation rate
Other operators for non-binary representations
A simple EA and Common Search Operators Lecture 2
10
Selection





Roulette wheel selection
Fitness proportional selection
Rank-based selection
Tournament selection
More complex operators
A simple EA and Common Search Operators Lecture 2
11
Search Bias


Some offspring tend to be more likely to be
generated than others. This is called a bias
Depends on representation and operators


Crossover bias, e.g. one-point vs. uniform
Mutation bias, e.g. 1-bit-flip vs. k-bit-flip
A simple EA and Common Search Operators Lecture 2
12
Sumary



EC is a field of study that includes EAs and other
areas. EAs include many different types of
algorithms.
Search Operators generate new offspring from
parents. There is no limiation on what operators can
be used.
Search operators are applied to individuals. It is very
important to realize the interdependency between
operators and the representation of individuals.
A simple EA and Common Search Operators Lecture 2
13
Recommended Books
Title
Author(s)
Publisher
Comments
Handbook on Evolutionary
Computation
T. Baeck, D. B. Fogel,
and Z. Michalewicz
(eds.)
IOP Press, 1997.
Very good reference to evolutionary
computation. Should read relevant
sections after each lecture.
Genetic Algorithms + Data
Structures = Evolution
Programs (3rd edition)
Z Michalewicz
Springer-Verlag,
Berlin, 1996
Recommended reference book for this
module. It is more up-to-date than
Goldberg's book.
Addison-Wesley,
1989
Good introductory book on genetic
algorithms and classifier systems, but
no other topics. Somewhat out of date.
Genetic Algorithms in
Search, Optimisation &
Machine Learning
D E Goldberg
Genetic Programming: An
Introduction
W Banzhaf, P Nordin,
R E Keller & Frank D
Francone
Morgan Kaufmann,
1999
A good introductory book on genetic
programming.
Evolutionary Computation:
Theory and Applications
X. Yao (ed)
World Scientific
Publ. Co.,
Singapore, 1999.
Good reference for more advanced
topics.
Various articles in journals
and conference
proceedings
A list of papers will be specified as the
module progresses.
A simple EA and Common Search Operators Lecture 2
14
References and Resources for this
Lecture

Books


(see previous page)
Web Resources



EvoNet Flying Circus Lots of material on
evolutionary computation
The Hitch-Hiker's Guide to Evolutionary
Computation
Introduction to evolutionary computation
Ricardo Poli's lecture notes for this course
A simple EA and Common Search Operators Lecture 2
15