Evolutionary Computation Melanie Mitchell Portland State University and Santa Fe Institute Complex Systems Summer School Thursday June 19, 2008 Copyright 2008 by Melanie Mitchell Outline of Lectures
Brief history of evolutionary computation A simple example: Evolving Robby the Robot EC in the real world: Case studies Co-evolutionary learning Adaptive Computation Using ideas from natural adaptive systems to build adaptive or life-like computing systems. Neural networks Genetic algorithms
Cellular automata Ant-colony optimization Swarm computing Artificial immune systems Market-inspired artificial intelligence Evolution made simple Essentials of Darwinian evolution: Organisms reproduce in proportion to their
fitness in the environment Offspring inherit traits from parents Traits are inherited with some variation, via mutation and sexual recombination Charles Darwin 18091882
Evolution made simple Essentials of evolutionary algorithms: Computer organisms (e.g., programs) reproduce in proportion to their fitness in the environment (e.g., how well they perform a desired task) Offspring inherit traits
from their parents Traits are inherited, with some variation, via mutation and sexual recombination Essentials of Darwinian evolution: Organisms reproduce in proportion to their fitness in the
environment Offspring inherit traits from parents Traits are inherited with some variation, via mutation and sexual recombination Appeal of ideas from evolution: Successful method of searching large spaces for good solutions (chromosomes / organisms)
Massive parallelism Adaptation to changing environments Emergent complexity from simple rules Evolutionary Computation: A Brief History 1940s 1950s: Automata theory considered to be both an engineering discipline and an approach to theoretical biology (e.g., von Neumann, Wiener, Turing) 1960s - 1970s:
Evolutionary programming (Fogel, Owens, and Walsh) Evolution strategies (Rechenberg and Schwefel) Genetic algorithms (Holland) Evolutionary Computation: A Brief History 1980s 1990s: Genetic Programming (Koza) Evolutionary Computation EC in the real world: A few
examples Automating parts of aircraft design (Boeing) Analyzing satellite images (Los Alamos) Automating assembly line scheduling (John Deere) Improving telecommunications networks (British Telecom) Generating realistic computer animation (The Lord of the Rings, Troy) Drug discovery (Daylight Chemical Information Systems) Detecting fraudulent stock trades (London Stock
Exchange) Analysis of credit card data (Capital One) Forecasting financial markets and portfolio optimization (First Quadrant). Interactive evolution for graphics design (Karl Sims) A Simple Example: Using Genetic Algorithms to Evolve Robby the Robot What Robby can see
North: empty South: empty East: empty West: can Center: empty North: wall South: empty East: wall West: empty Center: empty
What Robby can do: Actions 0: Move north 1: Move south 2: Move east 3: Move west 4: Stay put 5: Pick up can
6: Random move Example Strategy (243 possible situations or states) 0 1 2 3
242 Genetic Algorithm Components of a GA: Population of candidate solutions to a given problem (chromosomes) Fitness function that assigns fitness to each chromosome in the population Selection operator that selects individuals to reproduce Genetic operators that take existing chromosomes and produce offspring with variation (e.g., mutation,
crossover) Evolving Robby: Details Repeat for 1000 generations: 1. Generate initial population of 200 random strategies. 2. Calculate the fitness of each strategy in the population. 3. Apply evolution to the current population of strategies to create a new population of 200 strategies. 4. Return to step 2 with this new generation.
Example random initial population Individual 1: 23300323421630343530546006102562515114162260435654334066511514 15650220640642051006643216161521652022364433363346013326503000 40622050243165006111305146664232401245633345524126143441361020 150630642551654043264463156164510543665346310551646005164 Individual 2: 16411343121025360340361241431201104235462525304202044516433665 61035322153105131440622120614631432154610256523644422025340345
30502005620634026331002453416430151631210012214400664012665246 351650154123113132453304433212634555005314213064423311000 Individual 3: 20423344402411226132136452632464212206122122252660626144436125 32512664061335340153411110206164226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 Individual 200: 34632525136001012225612106043301135205155320130656005322235043 32425064124255265534635345523053326612010632124554423440613654
30246240160663016464641103026540006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Calculate the fitness of each strategy Points: Successfully picks up can: 10 Tries to pick up can in empty site: -1 Crashes in to wall: -5 (bounces back t original site)
Calculate the fitness of each strategy 23300323421630343530546006102562515114162260435654334066511514 15650220640642051006643216161521652022364433363346013326503000 40622050243165006111305146664232401245633345524126143441361020 150630642551654043264463156164510543665346310551646005164 ... Run for 200 actions per session, 100 different random sessio
Fitness = average number of points per session Apply evolution to the current population of strategies to create a new population of 200 strategies. Individual 1: 23300323421630343530546006102562515114162260435654334066511514 Fitness: -80 15650220640642051006643216161521652022364433363346013326503000 40622050243165006111305146664232401245633345524126143441361020 150630642551654043264463156164510543665346310551646005164
Individual 2: 16411343121025360340361241431201104235462525304202044516433665 Fitness: -120 61035322153105131440622120614631432154610256523644422025340345 30502005620634026331002453416430151631210012214400664012665246 351650154123113132453304433212634555005314213064423311000 Individual 3: 20423344402411226132136452632464212206122122252660626144436125 Fitness: 0 32512664061335340153411110206164226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006
134440626160505641421553133236021503355131253632642630551 Individual 200: 34632525136001012225612106043301135205155320130656005322235043 Fitness: -11 Select pair of parents, crossover, and mutate Parent 1: 20423344402411226132136452632464212206122122252660626144436125 32512664061335340153411110206164226653145522540234051155031302
22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 Cross over parents Parent 2: 34632525136001012225612106043301135205155320130656005322235043 32425064124255265534635345523053326612010632124554423440613654 30246240160663016464641103026540006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251
Select pair of parents, crossover, and mutate Parent 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 Cross over parents
Parent 2: 34632525136001012225612106043301135205155320130656005322235043 32425064124255265534635345523053326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Select pair of parents, crossover, and mutate Parent 1:
20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 Cross over parents Parent 2: 34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305
3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Select pair of parents, crossover, and mutate Parent 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006
134440626160505641421553133236021503355131253632642630551 Cross over parents Parent 2: 34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251
Child 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Child 2: 34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551
Select pair of parents, crossover, and mutate Parent 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 . Parent 2:
34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Child 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251
Mutate: At each locus, with low probability, replace Child 2: 34632525136001012225612106043301135205155320130656005322235043 digit by random digit in [0,6 3242506412425526553463534552305 4226653145522540234051155031302 . 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551
Select pair of parents, crossover, and mutate Parent 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 Parent 2:
34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Child 1: 20423344402411226132136452632465212206122122252660626144436125 3251266406133534015341111022616 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102033212142402251
Mutate: At each locus, with low probability, replace Child 2: 34632525136001012225612106043301135205155320130656005322235043 digit by random digit in [0,6 3242502412425526553463534542305 4226653145522540234051155031302 22020065445125062206631466135532010000400031640130154160162006 134440626160505641421553133236021603355131253632642630551 Select pair of parents, crossover, and mutate
Parent 1: 20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 . Parent 2: 34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305
3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Child 1: 20423344402411226132136452632465212206122122252660626144436125 3251266406133534015341111022616 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102033212142402251 Add children to new
generation Child 2: 34632525136001012225612106043301135205155320130656005322235043 3242502412425526553463534542305 4226653145522540234051155031302 22020065445125062206631466135532010000400031640130154160162006 134440626160505641421553133236021603355131253632642630551 Select pair of parents, crossover, and mutate Parent 1:
20423344402411226132136452632464212206122122252660626144436125 3251266406133534015341111020616 4226653145522540234051155031302 22020065445125062206631426135532010000400031640130154160162006 134440626160505641421553133236021503355131253632642630551 . Continue this process until new generation is full (200 strings) Replace current population with new generation.
Parent 2: 34632525136001012225612106043301135205155320130656005322235043 3242506412425526553463534552305 3326612010632124554423440613654 3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102533212142402251 Child 1: 20423344402411226132136452632465212206122122252660626144436125 3251266406133534015341111022616 3326612010632124554423440613654
3024624016066301646464110302654 0006334126150352262106063624260 550616616344255124354464110023463330440102033212142402251 Repeat algorithm for a total of 1000 generations Child 2: 34632525136001012225612106043301135205155320130656005322235043 3242502412425526553463534542305 4226653145522540234051155031302 22020065445125062206631466135532010000400031640130154160162006 134440626160505641421553133236021603355131253632642630551
Strategy M (Designed by me): If there is a can in the current site, pick it up. Otherwise, if there is a can in one of the adjacent sites, move to that site. Otherwise, choose a random direction to move in. 6563536562523532526563536561513531512523532521513
531516535365 Strategy 6252353252656353656050353050252353252050353050151 G (evolved by GA): 353151223532 5215135315105035305025235325205035305065635365625 25435515325623525105635546115133615415103415611055015005203025 235325256353 62561322523503251120523330540552312550513361541506652641502665 6561513531512523532521513531516563536562523532526
06012264453605631520256431054354632404350334153250253251352352 56353454 04515013015621343625235322313505126051335620152451434343212 Fitness: 346 (out of maximum 500) Fitness: 483 (out of maximum 500) Strategy M in a cluster of cans
Strategy G in a cluster of cans Dynamics from one run Best fitnes s Generation
Evolutionary Computation in the Real World: Case Studies Genetic Programming (Koza, 1990) Any computer program can be expressed as a parse tree:
(* PI (* R R)) Kozas genetic programming algorithm: 1. Choose a set of functions and terminals for the program, e.g., {+, -, *, /, sqrt, sin, cos, abs, pow, R, PI, D, C, rand()} 2. Generate an initial
population of random programs (trees), each up to some maximum depth. 3. Run the GA: Fitness: Run each program on training data. Fitness is how many training cases the program gets right (or
how close it gets to correct answer). Selection: Select parents probabilistically, based on fitness. Crossover: Exchange subtrees of parents. Mutation: Replace subtree with a random tree.
Genetic Art and Computer Graphics (Karl Sims, 1993) GA individuals: equations that generate a color for each pixel coordinate Function set: +, -, /, mod, round, min, max, abs, expt, log, and, or, xor, sin, cos, atan, if, dissolve, hsv-torgb, vector, transform-vector, bw-noise, colornoise, warped-bw-noise, warped-color-noise, blur, band-pass, grade-mag, grad-dir, bump, ifs, warped-ifs, warp-abs, warp-rel, warp-by-grad Terminal set: X, Y, rand_scalar(), rand_vector(n)
Each function returns an image (an array of pixel colors) Left to right, top to bottom: a. b. c. d. e.
f. g. h. Y X (abs X) (mod X (abs Y)) (and X Y) (bw-noise .2 2) (color-noise .1 2)
(grad-direction (bw-noise .15 2) 0 0) i. (warped-color-noise (* X .2) Y .1 2) Demo http://www.jhlabs.com/java/art.html Some Results
(round (log (+ y (color-grad (round (+ (abs (round (log (+ y (color-grad (round (+ y (log (invert y) 15.5)) x) 3.1 1.86 #(0.95 0.7 0.59) 1.35)) 0.19) x)) (log (invert y) 15.5)) x) 3.1 1.9 #(0.95 0.7 0.35) 1.35)) 0.19) x) Evolution of Collective Computation in Cellular Automata Jim Crutchfield
Rajarshi Das Wim Hordijk Melanie Mitchell Erik van Nimwegen Cosma Shalizi One-dimensional cellular automata One-dimensional cellular automata Rule:
One-dimensional cellular automata Rule: One-dimensional cellular automata Rule: One-dimensional cellular automata Rule: One-dimensional cellular automata Rule:
Space-time diagram ECA 110 Time Space Cellular automata as computers: Current renewal of interest due to: Distributed spatial computing in sensor networks Reconfigurable computing (FPGAs)
Molecular and quantum-scale computation (e.g., quantum dot cellular automata; molecular self-assembly of nanoscale electronics) Renewed interest in how biological systems compute (and how that can inspire new computer architectures) A new kind of science? A computational task for cellular automata A computational task for cellular automata
Design a cellular automata to decide whether or not the initial pattern has a majority of oncells. A computational task for cellular automata Design a cellular automata to decide whether or not the initial pattern has a majority of oncells. If a majority of cells are initially on, then after some number of iterations, all cells
should turn on A computational task for cellular automata Design a cellular automata to decide whether or not the initial pattern has a majority of oncells. If a majority of cells are initially on, then after some number of iterations, all cells should turn on Otherwise, after some number of iterations,
all cells should turn off. majority on initial majority on initial final majority on
initial final majority off majority on initial final
majority off majority on initial How to design a CA to do this? final majority off
We used cellular automata with 6 neighbors for each cell: ... Rule: .. . ...
A candidate solution that does not work: local majority voting Evolving cellular automata with genetic algorithms Evolving cellular automata with genetic algorithms Create a random population of candidate cellular automata rules
Evolving cellular automata with genetic algorithms Create a random population of candidate cellular automata rules The fitness of each cellular automaton is how well it performs the task. (Analogous to surviving in an environment.) Evolving cellular automata with genetic algorithms
Create a random population of candidate cellular automata rules The fitness of each cellular automaton is how well it performs the task. (Analogous to surviving in an environment.) The fittest cellular automata get to reproduce themselves, with mutations and crossovers. Evolving cellular automata with genetic algorithms Create a random population of candidate cellular
automata rules The fitness of each cellular automaton is how well it performs the task. (Analogous to surviving in an environment.) The fittest cellular automata get to reproduce themselves, with mutations and crossovers. This process continues for many generations. The chromosome of a cellular automaton is an encoding of its rule table:
The chromosome of a cellular automaton is an encoding of its rule table: Rule table: .. . The chromosome of a cellular automaton is an encoding of its rule table:
Rule table: Chromosome: 0 0 1 .. . 0
. . . 1 Create a random population of candidate cellular automata rules: Create a random population of candidate cellular automata rules: rule 1:
0010001100010010111100010100110111000... rule 2: 0001100110101011111111000011101001010... rule 3: 1111100010010101000000011100010010101... . . . rule 100: 0010111010000001111100000101001011111...
Calculating the Fitness of a Rule Calculating the Fitness of a Rule For each rule, create the corresponding cellular automaton. Run that cellular automaton on many initial configurations. Calculating the Fitness of a Rule For each rule, create the corresponding cellular automaton. Run that cellular automaton on many initial configurations.
Fitness of rule = fraction of correct classifications For each cellular automaton rule in the population: For each cellular automaton rule in the population: rule 1: 0010001100010010111100010100110111000...1 For each cellular automaton rule in the population: rule 1:
0010001100010010111100010100110111000...1 Create rule table For each cellular automaton rule in the population: rule 1: 0010001100010010111100010100110111000...1 Create rule table .. .
rule 1 rule table: .. . rule 1 rule table: .. . Run corresponding cellular automaton on many random
initial lattice configurations rule 1 rule table: .. . Run corresponding cellular automaton on many random initial lattice configurations ...
... . .. . incorrect ...
... rule 1 rule table: .. . Run corresponding cellular automaton on many random initial lattice configurations ...
... . .. . incorrect ...
... ... ... .. . correct ...
... rule 1 rule table: .. . Run corresponding cellular automaton on many random initial lattice configurations ...
... . .. . incorrect ...
... ... ... .. . correct ... etc.
... rule 1 rule table: .. . Run corresponding cellular automaton on many random initial lattice configurations ...
... . .. . incorrect ...
... ... ... .. . ... etc. ...
correct Fitness of rule = fraction of correct classifications GA Population: GA Population: rule 1: 0010001100010010111100010100110111000... Fitness = 0.5 rule 2: 0001100110101011111111000011101001010... Fitness = 0.2 rule 3: 1111100010010101000000011100010010101... Fitness = 0.4 .
. . rule 100:0010111010000001111100000101001011111... Fitness = 0.0 majority on majority off A cellular automaton evolved by the genetic algorithm (Performance 80%))
Another Task: Synchronization Evolving image-processing algorithms GENIE project (GENetic Image Exploitation), Los Alamos National Laboratory Brumby, Harvey, Perkins, Porter, Bloch, Szymanski, et al. Consider a large library of multi-spectral
photographic images from satellites and high-flying airplanes. How to automatically find images containing desired features? E.g., water, clouds, craters on Mars, forest fire damage, vegetation, urban areas, roads, airports, bridges, beaches,... Special-purpose algorithms can (possibly) be
developed for any particular feature, but goal of GENIE project is to have a general-purpose system: Special-purpose algorithms can (possibly) be developed for any particular feature, but goal of GENIE project is to have a general-purpose system: A user can specify any feature (via training examples), and system will quickly find images containing that feature. Training Examples for GENIE
Input images consist of ~10-100 spectral planes. User brings up training image(s) in GUI User paints examples of true and false pixels. rom Brumby et al., 2000 rom Brumby et al., 2000
Human created training images Roads Green = feature Red = non-feature Black = not classified Vegetation
Water Data and Feature Planes Truth plane Data planes (spectral channels) Feature planes
What GENIE Evolves GENIE evolves an image processing algorithm that operates on data planes to produce a new set of feature planes. New feature planes are used as training data for conventional classifiers (e.g., linear discriminants, neural networks, support vector machines)
GENIEs Genes Genes are elementary image-processing operations that read from data planes (spectral channels) or feature planes and write to feature planes e.g., addp(d1, d2, s2) linear_comb(s2, s1, s1, 0.9) erode(s1, s1, 3, 1) Elementary operators include spectral, morphological, logical, and thresholding operators
GENIEs Chromosomes Chromosomes are algorithms made up of genes lawd (d3, s2) ; Laws textural operator variance (s2, s2, 3, 1) ; local variance in circular neighb. min(d1, d2, s1) ; min at each pixel location linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) ; textural operator r5r5
open (s2,s2, 3,1) ; erode, then dilate subp (d1, s1, s1) ; subtract planes min (d0, s2, s2) adds (d1, s0, 0.25); add scalar opcl (s1,s1, 1, 1) ; erode, dilate, dilate, erode h_basin (s0, s0, 18) ; regional minima linear_comb (s0, d9, s0, 0.2) linear_comb (d4, s2, s2, 0.9) addp (d6, s0, s0) ; add planes
GENIEs Population Initial population is a set of 20-50 randomly generated chromosomes: awd (d3, s2) variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) open (s2,s2, 3,1) subp (d1, s1, s1) min (d0, s2, s2)
adds (d1, s0, 0.25) opcl (s1,s1, 1, 1) erode(d3, s2,3,1) linear_comb (d2, d1, s2, 0.5) min (s1, s2, s2) open (s2,s2, 3,1) open (s1,s2, 1,1) variance (s2, s2, 3, 1) addp (s1, s0, s2)
smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3) lawd(d2, s0) subp (s1, s1, s1) GENIEs Fitness Fitness: Run chromosome on image data to produce feature planes. Find linear combination of planes that maximizes spectral separation between labeled true and
false pixels. Threshold resulting plane to get binary image (each pixel is 1 or 0): 1 = feature, 0= non-feature Use threshold that will maximize fitness GENIEs Fitness Fitness: F 500( Rd (1 R f )) where
Rd is detection rate: fraction of feature pixels (green) classified correctly Rf is false alarm rate: fraction of non-feature pixels (red) classified incorrectly F=1000 is perfect fitness. The GA Selection: Selection some number of best in population Crossover: Recombine different genes from two different parents
Mutation: Randomly change a chosen gene Parent 1awd (d3, s2) variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) open (s2,s2, 3,1) subp (d1, s1, s1) min (d0, s2, s2) adds (d1, s0, 0.25)
opcl (s1,s1, 1, 1) Parent 2 open (s1,s2, 1,1) variance (s2, s2, 3, 1) addp (s1, s0, s2) smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3) lawd(d2, s0) subp (s1, s1, s1)
Parent 1awd (d3, s2) Parent 2 variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) open (s2,s2, 3,1) subp (d1, s1, s1)
min (d0, s2, s2) adds (d1, s0, 0.25) opcl (s1,s1, 1, 1) open (s1,s2, 1,1) variance (s2, s2, 3, 1) addp (s1, s0, s2) smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3) lawd(d2, s0) subp (s1, s1, s1)
Child awd (d3, s2) variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) open (s2,s2, 3,1) smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3) lawd(d2, s0)
subp (s1, s1, s1) Parent 1awd (d3, s2) Parent 2 variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) open (s2,s2, 3,1)
subp (d1, s1, s1) min (d0, s2, s2) adds (d1, s0, 0.25) opcl (s1,s1, 1, 1) open (s1,s2, 1,1) variance (s2, s2, 3, 1) addp (s1, s0, s2) smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3) lawd(d2, s0)
subp (s1, s1, s1) Child awd (d3, s2) variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3)
lawd(d2, s0) subp (s1, s1, s1) Parent 1awd (d3, s2) Parent 2 variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2)
open (s2,s2, 3,1) subp (d1, s1, s1) min (d0, s2, s2) adds (d1, s0, 0.25) opcl (s1,s1, 1, 1) open (s1,s2, 1,1) variance (s2, s2, 3, 1) addp (s1, s0, s2) smooth_r5r5 (d1, s3) opcl (s1,s1, 1, 3)
lawd(d2, s0) subp (s1, s1, s1) Child awd (d3, s2) variance (s2, s2, 3, 1) min(d1, d2, s1) linear_comb (s1, d0, s1, 0.9) smooth_r5r5 (s2, s2) lawd(s1,s3) smooth_r5r5 (d1, s3)
opcl (s1,s1, 1, 3) lawd(d2, s0) subp (s1, s1, s1) The GA is run until acceptable performance on the training examples is found. Generalization performance is evaluated, and user then creates new training example, based on generalization performance. Some Results
From Brumby et al., 2000 Training Data Evolved classifier Roads and buildings Vegetation
Water From Brumby et al., 2000 From Brumby et al., 2000 Recent work by Ghosh & Mitchell Combine GENIEs texture-learning ability with genetic shape-learning algorithm.
Application: Find prostate in CAT scans of pelvic region rom Ghosh & Mitchell, 2006 Training image, contour drawn by radiologist Test image, with hand-segmentation by a radiologist
Results from GENIE alone Results from our hybrid algorithm Examples of Advanced EC topics Multi-objective optimization Self-adapting evolutionary algorithms Stochastic process theory of EC More realistic analogies with evolution: Diploid chromosomes
Development of phenotype Ecological interactions (e.g., co-evolution, spatial proximity) Examples of Advanced EC topics Multi-objective optimization Self-adapting evolutionary algorithms Stochastic process theory of EC More realistic analogies with evolution: Diploid chromosomes Development of phenotype
Ecological interactions (e.g., co-evolution, spatial proximity) Co-evolutionary Learning Melanie Mitchell (Portland State U.) Ludo Pagie (U. Utrecht) Mick Thomure (Portland State U.) Jennifer Meneghin (Portland State U.) Martin Cenek (Portland State U.)
Problem for GAs (and other machine learning methods): How to select training examples appropriate to different stages of learning? One solution: Co-evolve training examples, using inspiration from hostparasite co-evolution in nature. Host-parasite co-evolution in nature Hosts evolve defenses against parasites Parasites find ways to overcome defenses Hosts evolve new defenses Continual biological arms race
Heliconius-egg mimicry in Passiflora http://www.ucl.ac.uk/~ucbhdjm/courses/b242/ Coevol/Coevol.html Darwin recognized the importance of coevolution in driving evolution Darwin recognized the importance of coevolution in driving evolution Co-evolution was later hypothesized to be major factor in evolution of sexual reproduction
Co-evolutionary Learning Co-evolutionary Learning Candidate solutions and training examples coevolve. Co-evolutionary Learning Candidate solutions and training examples coevolve. Fitness of candidate solution (host): how well it performs on training examples.
Co-evolutionary Learning Candidate solutions and training examples coevolve. Fitness of candidate solution (host): how well it performs on training examples. Fitness of training example (parasite): how well it defeats candidate solutions. Co-evolutionary Learning Candidate solutions and training examples coevolve. Fitness of candidate solution (host): how well it performs on training examples.
Fitness of training example (parasite): how well it defeats candidate solutions. Co evolutionary learning originally proposed by Hillis (1990). Why should we expect co-evolution to work? Why should we expect co-evolution to work? Hypotheses:
Why should we expect co-evolution to work? Hypotheses: 1. Allows arms races to emerge, with the evolution of training examples targeted to weaknesses in learners, and subsequent adaptation of learners to those training examples, and so on. Why should we expect co-evolution to
work? Hypotheses: 1. Allows arms races to emerge, with the evolution of training examples targeted to weaknesses in learners, and subsequent adaptation of learners to those training examples, and so on. 2. Helps maintain diversity in the population Why should we expect co-evolution to work?
Hypotheses: 1. Allows arms races to emerge, with the evolution of training examples targeted to weaknesses in learners, and subsequent adaptation of learners to those training examples, and so on. 2. Helps maintain diversity in the population Effect: Increases success of learning while reducing the amount of training data needed Why should we expect co-evolution to work?
Hypotheses: 1. Allows arms races to emerge, with the evolution of training examples targeted to weaknesses in learners, and subsequent adaptation of learners to those training examples, and so on. 2. Helps maintain diversity in the population Effect: Increases success of learning while reducing the amount of training data needed These hypotheses are plausible but have been largely untested in work on co-evolution.
Results Cellular Automata Function Induction Spatial Coev. 64% (32/50) 78% (39/50)
Non-Spatial Coev. 0% (0/50) 0% (0/50) Spatial Evol. 0% (0/50)
14% (7/50) Non-Spatial Evol. 0% (0/50) 6% (3/50) Non-Spatial Boosting
0% (0/10) Percentage of successful runs (mutation only) Spatial Co-evolution Spatial Co-evolution 2D toroidal lattice with one host (h) and one
parasite (p) per site Spatial Co-evolution 2D toroidal lattice with one host (h) and one parasite (p) per site h p h p h p
h p h p . . . .
. . Spatial Co-evolution 2D toroidal lattice with one host (h) and one parasite (p) per site h p h p h
p h p h p . . .
. . . fitness(h) fraction of 9 neighboring p answered correctly Spatial Co-evolution 2D toroidal lattice with one host (h) and one parasite (p) per site h
p h p h p h p h p
. . . . . . fitness(h) fraction of 9 neighboring p answered correctly
0 if h(p) is correct fitness ( p ) 0 if h( p ) is not correct Spatial Co-evolution 2D toroidal lattice with one host (h) and one parasite (p) per site Each h is replaced by mutated h p h
p h p h p h p .
. . copy of winner of tournament among itself and 8 neighboring hosts. . . . fitness(h) fraction of 9 neighboring
p answered correctly 0 if h(p) is correct fitness ( p ) 0 if h( p ) is not correct Spatial Co-evolution 2D toroidal lattice with one host (h) and one parasite (p) per site Each h is replaced by mutated h
p h p h p h p h p
. . . copy of winner of tournament among itself and 8 neighboring hosts. . . .
fitness(h) fraction of 9 neighboring p answered correctly Each p is replaced by mutated copy of winner tournament among itself and 8 neighboring parasites. 0 if h(p) is correct fitness ( p )
0 if h( p ) is not correct Non-Spatial Co-evolution Non-Spatial Co-evolution No spatial distribution of host and parasite populations Non-Spatial Co-evolution No spatial distribution of host and parasite populations
hosts parasites Non-Spatial Co-evolution No spatial distribution of host and parasite populations hosts parasites
fitness(h) fraction of 9 p (randomly chosen from parasite population) answered correctly Non-Spatial Co-evolution No spatial distribution of host and parasite populations hosts parasites
fitness(h) fraction of 9 p (randomly chosen from parasite population) answered correctly 0 if h(p) is correct fitness( p ) 0 if h( p ) is not correct for host h randomly chosen from host population Non-Spatial Co-evolution
No spatial distribution of host and parasite populations Each h is replaced by mutated hosts copy of winner of tournament among itself and 8 randomly chosen hosts. parasites
fitness(h) fraction of 9 p (randomly chosen from parasite population) answered correctly 0 if h(p) is correct fitness( p ) 0 if h( p ) is not correct for host h randomly chosen from host population Non-Spatial Co-evolution
No spatial distribution of host and parasite populations Each h is replaced by mutated hosts copy of winner of tournament among itself and 8 randomly chosen hosts. Each p is replaced by mutated copy of winner tournament among itself and
8 randomly chosen parasites. parasites fitness(h) fraction of 9 p (randomly chosen from parasite population) answered correctly 0 if h(p) is correct fitness( p ) 0 if h( p ) is not correct
for host h randomly chosen from host population Spatial Evolution: Same as spatial co-evolution, except parasites dont evolve. A new population of random parasites is generated at each generation. Spatial Evolution: Same as spatial co-evolution, except parasites dont evolve.
A new population of random parasites is generated at each generation. Non-Spatial Evolution: Same as non-spatial co-evolution, except parasites dont evolve. A new sample of 100 random parasites is generated at each generation. Fitness of a host is classification accuracy on these 100 randomly generated parasites Results Cellular Automata
Function Induction Spatial Coev. 64% (32/50) 78% (39/50) Non-Spatial Coev.
0% (0/50) 0% (0/50) Spatial Evol. 0% (0/50) 14% (7/50)
Non-Spatial Evol. 0% (0/50) 6% (3/50) Non-Spatial Boosting 0% (0/10)
Percentage of successful runs (mutation only) In short: Spatial co-evolution significantly outperforms other methods on both problems Analysis Why was spatial co-evolution successful? Hypotheses: 1. Maintains diversity over long period of time
2. Creates extended arms race between hosts and parasite populations Here we examine these hypotheses for the CA task. The GA evolves four types of strategies: Random Default Block Expanding Particle Default strategy
(performance 0.5) Block-expanding strategy (0.55 performance < 0.72) Particle strategy (performance 0.72) Measuring diversity in host population Plot distribution of host strategies in typical
CA runs Random Very low performance Default Low performance Block expanding Particle
Medium performance High performance Spatial Co-evolution (typical run) Non-Spatial Co-evolution (typical run) Spatial Evolution
(typical run) 173 Non-Spatial Evolution (typical run) 174 Summary of diversity results
Summary of diversity results Spatial co-evolution seems to preserve more diversity in the host population than the other methods. Summary of diversity results Spatial co-evolution seems to preserve more diversity in the host population than the other methods. In the other methods: Spatial methods: One strategy quickly
comes to dominate the population Nonspatial methods: Population oscillates between two different strategies Arms races between the host and parasite populations Arms races between the host and parasite populations Hypothesis: Initial configurations are evolving deceptive blocks:
Arms races between the host and parasite populations Hypothesis: Initial configurations are evolving deceptive blocks: Occurrence of a block of seven or more adjacent 0s or 1s in the 149-bit IC Probability of such an occurrence in a randomly generated string of the same density is less than 0.01.
Arms races between the host and parasite populations Hypothesis: Initial configurations are evolving deceptive blocks: Occurrence of a block of seven or more adjacent 0s or 1s in the 149-bit IC Probability of such an occurrence in a randomly generated string of the same density is less than 0.01. For a typical run of spatial co-evolution, we plotted the fraction of parasites with deceptive blocks
generations Summary: Why does spatial co-evolution improve performance? Summary: Why does spatial co-evolution improve performance? Maintains diversity in population
Summary: Why does spatial co-evolution improve performance? Maintains diversity in population Produces arms race with ICs targeting weaknesses in CAs (e.g., block expanding) and CAs adapting to overcome weaknesses (e.g., particle strategies) Summary:
Why does spatial co-evolution improve performance? Maintains diversity in population Produces arms race with ICs targeting weaknesses in CAs (e.g., block expanding) and CAs adapting to overcome weaknesses (e.g., particle strategies) Note that spatial co-evolution requires significantly fewer training examples for successful learning
But why, precisely, does putting population on a spatial lattice improve performance? But why, precisely, does putting population on a spatial lattice improve performance? Still an open question. Possible applications to real-world problems Possible applications to real-world problems
Drug design to foil evolving viruses/bacteria Possible applications to real-world problems Drug design to foil evolving viruses/bacteria Coevolving software/hardware with test cases Possible applications to real-world problems Drug design to foil evolving
viruses/bacteria Coevolving software/hardware with test cases Evolving game-playing programs Possible applications to real-world problems Drug design to foil evolving viruses/bacteria Coevolving software/hardware with test cases Evolving game-playing programs Coevolving computer security systems with possible threats
ESL Certification Summer Institute Assessing English Language ...
TELPAS - Texas English Language Proficiency Assessment System Developed to meet the federal testing requirements of the No Child Left Behind Act of 2001 (NCLB) Requires that ELLs be assessed annually in Listening, Speaking, Reading, and Writing beginning in Kindergarten...