Transcript Evolutionary Computation and Co

Evolutionary Computation
and
Co-evolution
• Alan Blair
• October 2005
Overview
Evolutionary Computation
• population of individuals
• fitness function
• repeat cycle of:
– evaluation,
– selection,
– crossover/mutation
Bit-String Operators:
Schema “Theorem”
• Implicit Parallelism
• Fitter schemas increase their representation
over time
• Schemas combine like “building blocks”
Evolutionary Issues:
•
•
•
•
Representations
Mutation operators
Crossover operators
Fitness functions
Representations
•
•
•
•
•
•
continuous parameters (Schwefel)
Bit-strings (Holland)
genetic programs (Koza)
machine language (Schmidhuber)
NN building operators (Gruau)
genotype = phenotype itself
Crossover Operators
•
•
•
•
•
one-point
two-point
uniform
special-purpose operators
mutation only (parthenogenesis)
Fitness Functions
• “deceptive” landscapes
– e.g. HIFF (Watson)
– local optima
– premature convergence
• Baldwin effect
• variation over time (robustness)
“Gaps” in the Fossil Record?
“Gaps” in the Fossil Record?
Partial Geographic Isolation
Punctuated Equilibria
“Gaps” in the Fossil Record?
• Eldridge & Gould
– partial geographic isolation
– punctuated equilibria
• ideas for Evolutionary Computation?
– “island” models
– co-evolution / artificial ecology ?
Co-Evolution
• competitive (leapard vs. gazelle)
• co-operative (insects/flowers)
• mixed co-operative/competitive (MaynardSmith)
• different genes within same genome?
• “diffuse” co-evolution
Sorting Networks
Sorting Networks #1 (Hillis)
• Evolving population of networks
• converged to local optimum
• final network not quite as good as handcrafted human solution
Sorting Networks #2 (Hillis)
• two co-evolving populations (networks
and strings)
• can escape from local optima
• punctuated equilibria observed
• better than hand-crafted solution (Tufts,
Juillé & Pollack)
Co-evolutionary Paradigms
•
•
•
•
•
•
machine vs. machine (Sims)
human vs. machine (Tron)
mixed co-operative/competitive (IPD)
language games (Tonkes, Ficici)
single individual ? (Backgammon)
brain / body (Sims, Hornby, Lipson)
Virtual Creatures (Sims)
• Evolution
– running / skipping / jumping
• Co-evolution
– fighting for control of a cube
Tournament Structures
•
•
•
•
•
single species
multi-species
all vs. all
round robin
all vs. best
Tron
Tron
• population of GP players co-evolve with
population of humans over the Internet
(Funes, Sklar, Juillé, Pollack)
Tron Results
Tron Results
Iterated Prisoner’s Dilemma
C
D
• TFT
ALL-C
C D
3, 3 0, 5
5, 0 1, 1
ALL-D
TFT
Collusion
Meta-Game of Learning
• Co-evolution tends to provide an opponent
of appropriate ability
• generally helps to escape local optima
• however, can create new “mediocre stable
states” (collusion)
Language Games
Simulated Hockey
Shock Results (single player)
Shock Results (one-on-one)
Evolutionary Robotics
• too many generations - robot may get worn
out
• start in simulation, refine on real robot
Brain/Body Co-evolution
Biped Walking
•
•
•
•
dynamically stable gait
evolved parameters
start on fast approximate simulator
refine on slow accurate simulator
Future Directions
•
•
•
•
massive parallelism
modularity and evolution
credit-assignment problem
society / economic models