Transcript EC_tutorial 2 - 서울대 : Biointelligence lab

Evolutionary Computation:
A Tutorial
September 2009
Biointelligence Laboratory
School of Computer Sci. & Eng.
Seoul National University
http://bi.snu.ac.kr/
Contents





Part I: Introduction to Evolutionary Computation
Part II: Genetic Programming
Part III: Advanced Topics
Part IV: Applications
Part V: Summary and Further Info
(C) 2000-2009 SNU CSE Biointelligence Lab
2
Part I: Introduction to Evolutionary
Computation
Overview

The Basic Concept
 General Framework of Evolutionary Computation
 Components of Evolutionary Computation
 Paradigms in Evolutionary Computation
(C) 2000-2009 SNU CSE Biointelligence Lab
4
Basic Concept

Use of Darwinian-like evolutionary processes to solve
difficult computational problems.
 Hence the name, “Evolutionary Computation”

Biological basis
 Biological systems adapt themselves to a new environment by
evolution.
 Generations of descendants are produced that perform better than do
their ancestors.

Biological evolution
 Production of descendants changed from their parents
 Selective survival of some of these descendants to produce more
descendants
(C) 2000-2009 SNU CSE Biointelligence Lab
5
Basic Concept

What is the Evolutionary Computation?
 Stochastic search (or problem solving) techniques that
mimic the metaphor of natural biological evolution.

Metaphor
EVOLUTION
PROBLEM SOLVING
Individual
Fitness
Environment
Candidate Solution
Quality
Problem
(C) 2000-2009 SNU CSE Biointelligence Lab
6
General Framework of EC
Generate Initial Population
Fitness Function
Evaluate Fitness
Termination Condition?
Yes
Best Individual
No
Select Parents
Crossover, Mutation
Generate New Offspring
(C) 2000-2009 SNU CSE Biointelligence Lab
7
Components of EC (1/9)





Representations
Population
Fitness function
Selection mechanism
Variation operators
 Crossover/Mutation

Initialization / Termination
(C) 2000-2009 SNU CSE Biointelligence Lab
8
Components of EC (2/9)

An example: the
8 queens
problem
 Place 8 queens
on an 8x8
chessboard in
such a way that
they cannot
check each
other.
(C) 2000-2009 SNU CSE Biointelligence Lab
9
Components of EC (3/9)

Representations
 How to represent the space to be searched?
 Genotype
 Internal
representation of solutions in EC.
 Minimum domain knowledge.
 Phenotype
 External
representation of solutions for the problem.
 Require domain knowledge.

Be careful so that every feasible solution can be
represented in genotype space.
(C) 2000-2009 SNU CSE Biointelligence Lab
10
Representation Example:
8 Queens Problem
Phenotype:
a board configuration
Genotype:
a permutation of
the numbers 1 - 8
Obvious mapping
1 3 5 2 6 4 7 8
(C) 2000-2009 SNU CSE Biointelligence Lab
11
Components of EC (4/9)

Population
 Usually has a fixed size and is a multiset of genotypes
 Some sophisticated EAs also assert a spatial structure on the
population e.g., a grid.
 Diversity of a population refers to the number of different
fitnesses / phenotypes / genotypes present (note not the same
thing).

Population sizing
 Parent population size (M), offspring population size (K).
 Typically M = K.
 In typical ES (explained later), M << K.
 In steady state algorithms, M > K.
(C) 2000-2009 SNU CSE Biointelligence Lab
12
Components of EC (5/9)

Fitness function
 Represents the requirements that the population should
adapt to
 a.k.a. quality function or objective function
 Assigns a single real-valued fitness to each phenotype
which forms the basis for selection
So the more discrimination (different values) the
better
 Typically we talk about fitness being maximised
Some problems may be best posed as minimisation
problems, but conversion is trivial.
(C) 2000-2009 SNU CSE Biointelligence Lab
13
Fitness Function Example:
8 Queens Problem

Penalty for a queen:
 The number of queens she can
check

Penalty for a configuration:
 The sum of penalties of all
queens

Note: penalty is to be
minimized
 Fitness of a configuration:
 inverse
1 3 5 2 6 4 7 8
2
1
1
1
0
1
2
2
1
 0.1
penalty to be maximized 2  1  1  0  1  1  2  2
or
 (2Lab
 1  1  0  1  1  2  2) 1410
(C) 2000-2009 SNU CSE Biointelligence
Components of EC (6/9)

Parent selection mechanism
 Assigns probabilities for an individual to be selected as parents.
 Selection probabilities are relative to current population.
 Different probabilities can be assigned to the same individuals.
 Usually depends on the individual’s fitness and probabilistic.
 High quality solutions more likely to become parents than low
quality ones
 Selection pressure – the degree of correlation between the
individual’s fitness and its selection probability.
 High selection pressure results in reducing search scope.
 Even worst in current population usually has non-zero
probability of becoming a parent
 This stochastic nature can aid escape from local optima.
(C) 2000-2009 SNU CSE Biointelligence Lab
15
Selection Mechanism Example:
8 Queens Problem
(1) 1 3 5 2 6 4 8 7
1/9 = 0.11
(2) 6 3 7 8 5 1 2 4
1/10 = 0.1
(3) 6 1 5 3 7 2 8 4
1/11 = 0.091
(4) 8 6 4 2 1 5 3 7
1/6 = 0.17
Different selection mechanisms
assign different selection
probabilities for the same individual.
Individual
Proportional
Ranking
(1)
0.23
0.3
(2)
0.21
0.2
(3)
0.19
0.1
(4)
0.36
0.4
(C) 2000-2009 SNU CSE Biointelligence Lab
16
Components of EC (7/9)

Crossover (Recombination)
 Mix information from parents into offspring in stochastic
way.
 Most offspring may be worse, or the same as the parents.
 Hope is that some are better by combining elements of
genotypes that lead to good traits.
 Principle has been used for millennia by breeders of
plants and livestock

Example
1 3 5 2 6 4 7 8
8 7 6 5 4 3 2 1
(C) 2000-2009 SNU CSE Biointelligence Lab
1 3 5 4 2 8 7 6
8 7 6 2 4 1 3 5
17
Components of EC (8/9)

Mutation
 It is applied to one genotype and delivers a (slightly)
modified mutant, the child or offspring of it.
 Element of randomness is essential.
 The role of mutation in EC is different in various EC
subtypes.

Example
 swapping values of two randomly chosen positions
1 3 5 2 6 4 7 8
1 3 7 2 6 4 5 8
(C) 2000-2009 SNU CSE Biointelligence Lab
18
Components of EC (9/9)

Initialization usually done at random
 Need to ensure even spread and mixture of possible
allele values
 Can include existing solutions, or use problem-specific
heuristics, to “seed” the population

Termination condition checked every generation
 Reaching some (known/hoped for) fitness
 Reaching some maximum allowed number of
generations
 Reaching some minimum level of diversity
 Reaching some specified number of generations
without fitness improvement
(C) 2000-2009 SNU CSE Biointelligence Lab
19
Paradigms in EC

Evolutionary Programming (EP)
 [L. Fogel et al., 1966]
 FSMs, mutation only, tournament selection

Evolution Strategy (ES)
 [I. Rechenberg, 1973]
 Real values, mainly mutation, ranking selection

Genetic Algorithm (GA)
 [J. Holland, 1975]
 Bitstrings, mainly crossover, proportionate selection

Genetic Programming (GP)
 [J. Koza, 1992]
 Trees, mainly crossover, proportionate selection
(C) 2000-2009 SNU CSE Biointelligence Lab
20
Appendix: Evolution Strategy
Evolution Strategy (ES)

Problem of real-valued optimization
Find extremum (minimum) of function F(X): Rn ->R

Operate directly on real-valued vector X
 Generate new solutions through Gaussian
mutation of all components
 Selection mechanism for determining new parents
(C) 2000-2009 SNU CSE Biointelligence Lab
22
ES: Representation
One individual:



a  x1 ,, xn ,  1 ,,  n , 1 ,, n  I



x


The three parts of an individual:

x



f (x )
: Object variables
Fitness
: Standard deviations
Variances
: Rotation angles
Covariances
(C) 2000-2009 SNU CSE Biointelligence Lab
23
ES: Operator - Recombination
rr x r r
, where rx, r , r {-, d, D, i, I, g, G}, e.g. rdII
 x S ,i

 xS ,i or xT ,i

 xS ,i or xT ,i
i


xi   xS ,i  ( xT ,i  xS ,i ) / 2

 xS ,i  ( xTi ,i  xS ,i ) / 2

 xS ,i    ( xT ,i  xS ,i )

 xS ,i   i  ( xT ,i  xS ,i )
i

no recombinat ion
r
discrete
rd
panmictic discrete
rD
intermedia te
ri
panmictic intermedia te
rI
generalize d intermedia te
rg
panmictic generalize d intermedia te rG
(C) 2000-2009 SNU CSE Biointelligence Lab
24
ES: Operator - Mutation

m{,’,} : I  I is an asexual operator.
 n = n, n = n(n-1)/2
1


 i   i  exp(   N (0,1)    N i (0,1))    2 n 
1
 j   j    N j (0,1)



2
n
   
 
x   x  N (0, C( , ))
  0.0873
 
 1 < n < n, n = 0
 i   i  exp(   N (0,1)    N i (0,1))
xi  xi   i  N i (0,1)
 n = 1, n = 0
     exp( 0  N (0,1))
xi  xi     N i (0,1)
 0  1/ n
(C) 2000-2009 SNU CSE Biointelligence Lab
25
ES: Illustration of Mutation
Hyperellipsoids
Line of equal probability density to place an offspring
(C) 2000-2009 SNU CSE Biointelligence Lab
26
ES: Evolution Strategy vs. Genetic
Algorithm
Create random initial population
Insert into
population
Evaluate population
Create random initial population
Insert into
population
Evaluate population
Select individuals for variation
Vary
Vary
Selection
(C) 2000-2009 SNU CSE Biointelligence Lab
27
Part II: Genetic Programming
Overview





Genetic Programming
Tree-based Representations
Setting Up a Genetic Programming Run
Example: Wall-Following Robot
Result
(C) 2000-2009 SNU CSE Biointelligence Lab
29
Genetic Programming (GP)



GP is an domainindependent method that
evolves a population of
programs to solve a
problem.
GP uses variable-size treerepresentations rather than
fixed-length strings of
binary values in typical GA.
GP has been successful in
many domains.
(C) 2000-2009 SNU CSE Biointelligence Lab
30
Tree-based Representations (1/6)

Function set: internal nodes
 Functions, predicates, or actions which take one or
more arguments

Terminal set: leaf nodes
 Program constants, actions, or functions which take no
arguments
S-expression: (+ 3 (/ ( 5 4) 7))
Terminals = {3, 4, 5, 7}
Functions = {+, , /}
(C) 2000-2009 SNU CSE Biointelligence Lab
31
Tree-based Representations (2/6)

Trees can represent:
 Arithmetic formula
y 

2     ( x  3) 

5 1

 Logical formula
(x  true)  (( x  y )  (z  (x  y)))
 Program
i =1;
while (i < 20)
{
i = i +1
}
 And many others depending on the definition of
terminals and nonterminals.
(C) 2000-2009 SNU CSE Biointelligence Lab
32
Tree-based Representations (3/6)
y 

2     ( x  3) 

5

1


(C) 2000-2009 SNU CSE Biointelligence Lab
33
Tree-based Representations (4/6)
(x  true)  (( x  y )  (z  (x  y)))
(C) 2000-2009 SNU CSE Biointelligence Lab
34
Tree-based Representations (5/6)
i =1;
while (i < 20)
{
i = i +1
}
(C) 2000-2009 SNU CSE Biointelligence Lab
35
Tree-based Representations (6/6)

In GA, ES, EP chromosomes are linear structures
(bit strings, integer string, real-valued vectors,
permutations)
 Tree shaped chromosomes are non-linear
structures.
 In GA, ES, EP the size of the chromosomes is
fixed.
 Trees in GP may vary in depth and width.
(C) 2000-2009 SNU CSE Biointelligence Lab
36
Setting up a GP Run

Users need to specify:
1. The terminal / function set
2. The fitness measure
3. Algorithm parameters to control the run




Population size, maximum number of generations
Selection / variation operators and their probabilities
The termination criterion
Maximum depth of a GP tree, etc.
(C) 2000-2009 SNU CSE Biointelligence Lab
37
Example: Wall-Following Robot
(Step 1)

Program Representation in GP
 Functions
 AND
(x, y) = 0 if x = 0; else y
 OR (x, y) = 1 if x = 1; else y
 NOT (x) = 0 if x = 1; else 1
 IF (x, y, z) = y if x = 1; else z
 Terminals
 Actions:
move the robot one cell to each direction
{north, east, south, west}
 Sensory
input: its value is 0 whenever the coressponding cell is
free for the robot to occupy; otherwise, 1.
{n, ne, e, se, s, sw, w, nw}
(C) 2000-2009 SNU CSE Biointelligence Lab
38
Program Example
(C) 2000-2009 SNU CSE Biointelligence Lab
39
Example: Wall-Following Robot
(Step 1)

Be careful when specifying function / terminal set.

To avoid syntactic error
 All programs in the initial population should be valid,
executable programs.
 The genetic operators during the run should produce
valid, executable programs as offspring.

To avoid run-time error
 All functions can take any terminal or the results
produced by any other functions as input.
(C) 2000-2009 SNU CSE Biointelligence Lab
40
Example: Wall-Following Robot
(Step 2)

Fitness measures can be
 Error between program’s output and the desired output.
 Accuracy in recognizing patterns or classifying objects into
classes.
 Payoff a game-playing program produces.

Often each program is executed over a representative
sample of fitness cases.
 In our wall-following robot problem
 the number of cells next to the wall that are visited during
60 steps over 10 independent runs.
 Perfect
score (320) : One Run (32)  10 randomly chosen starting points
(C) 2000-2009 SNU CSE Biointelligence Lab
41
Example: Wall-Following Robot
(Step 3)

Genetic operators – crossover (subtree exchange)
+
+

b
a

+

b
b



a
a
b
+
+




a
b
a

+
b
b

a
(C) 2000-2009 SNU CSE Biointelligence Lab
b
42
Example: Wall-Following Robot
(Step 3)

Genetic operators – mutation
+
+

/
b

a
+
/
b
b
a
(C) 2000-2009 SNU CSE Biointelligence Lab


a
b
b
a
43
Example: Wall-Following Robot
(Step 3)

Population size: 5,000
 Termination condition: found perfect solution
 Creating Next Generation
 500 programs (10%) are copied directly into next
generation (elitism).

Tournament selection
•
•
7 programs are randomly selected from the population 5,000.
The most fit of these 7 programs is chosen.
 4,500 programs (90%) are generated by crossover.

Parents are each chosen by tournament selection.
 In this example, mutation was not used.
(C) 2000-2009 SNU CSE Biointelligence Lab
44
Example: Wall-Following Robot
(Step 3)
(C) 2000-2009 SNU CSE Biointelligence Lab
45
Result (1/5)

Generation 0
 The most fit program (fitness = 92)
 Starting
in any cell, this program moves east until it reaches a
cell next to the wall; then it moves north until it can move east
again or it moves west and gets trapped in the upper-left cell.
(C) 2000-2009 SNU CSE Biointelligence Lab
46
Result (2/5)

Generation 2
 The most fit program (fitness = 117)
 Smaller
than the best one of generation 0, but it does get stuck
in the lower-right corner.
(C) 2000-2009 SNU CSE Biointelligence Lab
47
Result (3/5)

Generation 6
 The most fit program (fitness = 163)
 Following
the wall perfectly but still gets stuck in the bottomright corner.
(C) 2000-2009 SNU CSE Biointelligence Lab
48
Result (4/5)

Generation 10
 The most fit program (fitness = 320)
 Following
the wall around clockwise and moves south to the
wall if it doesn’t start next to it.
(C) 2000-2009 SNU CSE Biointelligence Lab
49
Result (5/5)

Fitness Curve
 Fitness as a function of generation number
 The
progressive (but often small) improvement from
generation to generation
(C) 2000-2009 SNU CSE Biointelligence Lab
50
Part III: Advanced Topics and
Applications
Overview

Theoretical topics
 Mathematical Models of Simple Genetic Algorithms
 Bloat Phenomena in Genetic Programming

Applications
 Summary
(C) 2000-2009 SNU CSE Biointelligence Lab
52
Mathematical Models of Simple GAs (1/7)


Based on (Vose & Liepins, 1991).
The model simple GA
1.
2.
3.
4.
5.
6.
7.
Start with a random population of binary strings of length l.
Calculate the fitness f(x) of each string x in the population.
Choose (with replacement) two parents from the population with
probability proportional to each string’s relative fitness in the
population.
Crossover the two parents (at single random point) with
probability pc to from two offspring and discard one at random.
Mutate each bit in the selected offspring with probability pm and
replace it in the new population.
Go to Step 3 until new population is complete.
Go to Step 1.
(C) 2000-2009 SNU CSE Biointelligence Lab
53
Mathematical Models of Simple GAs (2/7)

Notations
 Each string is represented by binary string between 0
and 2l-1.
Proportion of string i in the population
1 1
1 1

p(t )  (0,0.25,0.25,0.5)

s (t )  (0,0.1667,0.1667,0.6667)
0 1
The selection probability of string i,
assuming that fitness is equal to the number of
1’s in the string.
1 0

s (t ) 

F  p(t )
Fi , j  0 for i  j

2l 1
F

p
 j 0 (t ) Fi,i  f (i)
(C) 2000-2009 SNU CSE Biointelligence Lab
54
Mathematical Models of Simple GAs (3/7)

GA with selection only.
 Expectation of next population is equal to the selection
probabilities.


E ( p(t  1))  s (t )


s (t  1) ~ F  p (t  1)


E ( s (t  1)) ~ F  s (t )
(C) 2000-2009 SNU CSE Biointelligence Lab
55
Mathematical Models of Simple GAs (4/7)

Including crossover and mutation.
 Define recombination matrix M for crossover and
mutation.
 ri,j(k) – the probability that string k will be produced,
given that string i and j are selected to mate.
E ( pk (t  1))   si (t ) s j (t )ri , j (k )
i, j
 Defining ri,j(k) and M is tricky. We will show defining
ri,j(0) only.
(C) 2000-2009 SNU CSE Biointelligence Lab
56
Mathematical Models of Simple GAs (5/7)

Defining ri,j(0)
 Case 1: crossover does not occur and the selected
offspring is mutated to all zeros.
 Case 2: crossover occurs and the selected offspring is
mutated to all zeros.

Case 1
 |i|: the number of 1’s in a string i.
|i|
l |i|
p
(
1

p
)
 The probability that i be mutated to all zeros m
m
1
1  pc  pm|i| (1  pm )l |i|  pm| j| (1  pm )l | j|
2


(C) 2000-2009 SNU CSE Biointelligence Lab
57
Mathematical Models of Simple GAs (6/7)
i1

Case 2
 Temporary definition
i2
i: 0 0 0 1 0 1 0 1
h: 0 0 0 0 1 0 1 0
j: 1 1 1 0 1 0 1 0
j1
j2
k: 1 1 1 1 0 1 0 1

1
1 l 1 |h|
pc
pm (1  pm ) l |h|  pm|k | (1  pm ) l |k |

2 l  1 c 1

 |h|=|i|-|i2|+|j2| & |k|=|j|-|j2|+|i2|.
 But, i2  (2c  1)^ i gives the number of 1’s in rightmost
i: 0 0 0 0 1 0 1 0
c bits of i.
25-1: 0 0 0 1 1 1 1 1
c
c
 Thus, i, j ,c  i2  j2  (2  1)^ i  (2  1)^ j
Then, h  i   i , j ,c and k  j   i , j ,c
(1  pm )l
ri , j (0) 
2
  pm /(1  pm )
 i
pc l 1 i , j ,c 
pc l 1 i , j ,c 
j


   1  pc 



 1  pc 
l  1 c 1
l  1 c 1




(C) 2000-2009
SNU CSE Biointelligence Lab
58
Mathematical Models of Simple GAs (7/7)

For the rest of derivation of ri,j(0) and M, refer to
(Vose & Liepins, 1991).
(C) 2000-2009 SNU CSE Biointelligence Lab
59
Bloat Phenomena in GP (1/3)

Bloat
 Program growth without (significant) return in terms of
fitness.
Fitness
Program size
(C) 2000-2009 SNU CSE Biointelligence Lab
60
Bloat Phenomena in GP (2/3)

Why does it happen?
 No certain explanation.
 Replication accuracy theory
 GP
evolves towards (bloated) representations that increase
replication accuracy.
 Crossover bias theory
programs are less fit than long ones  long programs
have a selective advantage  bloat
 Short
(C) 2000-2009 SNU CSE Biointelligence Lab
61
Bloat Phenomena in GP (3/3)

Techniques limiting bloat
 Fixed size or depth limit: programs exceeding the limit
are discarded and a parent is kept.
 Dangerous:
acts as advantage for programs that violate the
limit.
 Parsimony pressure: a penalty term for larger programs
is added to the fitness value.
 (Fitness_parsimony)
= (Fitness_raw) – c * (program_size)
(C) 2000-2009 SNU CSE Biointelligence Lab
62
Part IV: Applications
Applications of EC







Numerical, Combinatorial Optimization
System Modeling and Identification
Planning and Control
Engineering Design
Data Mining
Machine Learning
Artificial Life
(C) 2000-2009 SNU CSE Biointelligence Lab
64
Application Example 1
Co-evolving Soccer Softbots (1/5)
Co-evolving
Soccer Softbots
With Genetic
Programming

At RoboCup there are two "leagues": the "real" robot
league and the "virtual" softbot league
 How do you do this with GP?
 GP breeding strategies: homogeneous and heterogeneous
 Decision of the basic set of function with which to evolve players
 Creation of an evaluation environment for our GP individuals
(C) 2000-2009 SNU CSE Biointelligence Lab
65
Application Example 1
Co-evolving Soccer Softbots (2/5)

Initial Random Population
(C) 2000-2009 SNU CSE Biointelligence Lab
66
Application Example 1
Co-evolving Soccer Softbots (3/5)

Kiddie Soccer
(C) 2000-2009 SNU CSE Biointelligence Lab
67
Application Example 1
Co-evolving Soccer Softbots (4/5)

Learning to Block the Goal
(C) 2000-2009 SNU CSE Biointelligence Lab
68
Application Example 1
Co-evolving Soccer Softbots (5/5)

Becoming Territorial
(C) 2000-2009 SNU CSE Biointelligence Lab
69
Application Example 2
Evolutionary Arts



Exploits the process of evolution to
create an artwork according to an
evolutionary algorithm.
Selection may be done by the viewer
explicitly by selecting individuals
which are aesthetically pleasing, or
implicitly according to the length of
time a viewer spends near a piece of
evolving art.
EvoMUSART workshops 2009
 http://evostar.na.icar.cnr.it/EvoWorkshops/
EvoMUSART/EvoMUSART.html
(C) 2000-2009 SNU CSE Biointelligence Lab
70
Part V: Summary & Further
Information
Recapitulation of EA





EAs fall into the category of “generate and test”
algorithms.
They are stochastic, population-based algorithms.
Variation operators (recombination and mutation)
create the necessary diversity and thereby
facilitate novelty.
Selection reduces diversity and acts as a force
pushing quality.
Fundamental trade-off between exploration and
exploitation
(C) 2000-2009 SNU CSE Biointelligence Lab
72
Exploration vs. Exploitation

There are many possibilities to set the parameters to
increase the explorative capability of an EA
 Increase variation probability



Increase mutation rate
Increase crossover rate
Increase population size
 Decrease selection pressure





Add noise to fitness function
Add noise in selection
Increase rank ratio in ranking selection
Decrease tournament size in tournament selection
Important is the combined effect of various parameter
settings.
(C) 2000-2009 SNU CSE Biointelligence Lab
73
Typical Behavior of an EA

Phases in optimizing on a 1-dimensional fitness landscape
Early phase:
quasi-random population distribution
Mid-phase:
population arranged around/on hills
Late phase:
population concentrated on high hills
(C) 2000-2009 SNU CSE Biointelligence Lab
74
Best fitness in population
Are Long Runs Beneficial?
Progress in 2nd half
Progress in 1st half
Time (number of generations)
Answer:
- It depends how much you want the last bit of progress
- It may be better to do more shorter runs
(C) 2000-2009 SNU CSE Biointelligence Lab
75
Performance of methods on problems
EAs as Problem Solvers
Special, problem tailored method
Evolutionary algorithm
Random search
Scale of “all” problems
(C) 2000-2009 SNU CSE Biointelligence Lab
76
Advantages of EC







No presumptions w.r.t. problem space
Widely applicable
Low development & application costs
Easy to incorporate other methods
Solutions are interpretable (unlike NN)
Can be run interactively, accommodate user
proposed solutions
Provide many alternative solutions
(C) 2000-2009 SNU CSE Biointelligence Lab
77
Disadvantages of EC

No guarantee for optimal solution within finite
time
 Weak theoretical basis
 May need parameter tuning
 Often computationally expensive, i.e. slow
(C) 2000-2009 SNU CSE Biointelligence Lab
78
Further Information on EC

Conferences







IEEE Congress on Evolutionary Computation (CEC)
Genetic and Evolutionary Computation Conference (GECCO)
Parallel Problem Solving from Nature (PPSN)
Foundation of Genetic Algorithms (FOGA)
EuroGP, EvoCOP, and EvoWorkshops
Int. Conf. on Simulated Evolution and Learning (SEAL)
Journals
 IEEE Transactions on Evolutionary Computation
 Evolutionary Computation
 Genetic Programming and Evolvable Machines
(C) 2000-2009 SNU CSE Biointelligence Lab
79
References



Evolutionary Computation by Kenneth A. De Jong, 2006.
Evolutionary Computation: Toward a New Philosophy of Machine
Intelligence, Third Edition (IEEE Press Series on Computational
Intelligence) by David B. Fogel, 2005,
Introduction to Evolutionary Computing by A. E. Eiben and J. E Smith,
Springer, 2003.


Genetic Programming: On the Programming of Computers by Means of
Natural Selection (Complex Adaptive Systems) by John R. Koza, 1992.
Genetic Programming: An Introduction by W. Banzhaf, P. Nordin, R.
Keller, and F. Francone, Morgan Kaufmann, 1997.

A Field Guide to Genetic Programming by R. Poli and W. B. Langdon,
2008. Online free book – http://www.gp-field-guide.org.uk/
(C) 2000-2009 SNU CSE Biointelligence Lab
80