Transcript Biologist 50’ talk - University of Idaho

Evolution in Computation
James A. Foster
Initiative for Bioinformatics
And Evolutionary Studies (IBEST),
MRCI, CSDS, and Computer Science
University of Idaho
1
Outline of Talk

Evolutionary computation (EC)



Applications




Overview
History
Optimization
Automatic programming
Hardware design
Problems and promise




Code bloat: survival of the fattest
Robustness: why do evolved things endure?
Hardness: when is EC not efficient?
Randomness
2
Two Abstractions
Evolution and computation are abstractions,
which can be: studied independently of their
implementations, implemented in new ways
Evolution: population based process in which individuals
reproduce, inherit information via a noisy
transmission process, interact with an environment
which defines a fitness gradient on which selection
operates.
Computation: information transformations induced by
finite algorithms in discrete, well-defined steps.
3
EC Overview
Translate
Individual solutions
Evolve:
- Mate parents
- Recombine
- Mutate
- Replace
Evaluate
fitness
Solutions
Design challenges:
- representation
- fitness function
- mutation operators
- recombination
details
- selecting parents
- replication details
- when to stop
4
EC History





’50 A. Turing
’66 I. Rechenberg, H.P. Schwefel, P. Bienert:
fluid dynammics
’66 L. Fogel, A. Owens, M. Walsh: machine
intelligence
’75 J. Holland: modeling natural evolution
’85 J. Koza (and others): genetic
programming
5
Optimization Problems
Minimize sorting network error
 Maximize “locomotion”*
 Optimizing a stock market portfolio
 Fuel optimal two stroke engine
 Drug design
 Disease diagnosis
*Not done in my lab, but sweet stuff

6
Case Study: Sorting Networks
Robustness: an apparent intrinsic property of evolved
systems - ability to degrade gracefully with the
presence of local failures. (Robustness for free)
 Is this effect real, and how strong is it?
 What representations are best for developing
robustness in circuits?
 How does redundancy influence the robustness of
evolved circuits? How much is enough?
Method: evolve sorting networks, measure performance
degradation with point failures in circuits
7
Sorting Nets: Example
Inputs
Output
0
0
1
1
1
0
0
1
0
1
8
Sorting Nets: Example
Inputs
1
Output
10
01
1
0
0
0
0
0
01
1
10
1
0
1
1
1
1
9
SN: Linear Individuals
CE (1,4) CE (0,3) CE (1,3) CE (1,2) CE (2,4) CE (0,2) CE (3,4) CE (0,4)
001 100 000 011 001 011 001 010 010 100 000 010 011 100 000 100
10
SN: Crossover in Arrays
CE (1,4) CE (0,3) CE (1,3) CE (2,4) CE (0,4) CE (2,3) CE (1,4) CE (1,2)
CE (0,3) CE (3,4) CE (0,2) CE (1,3) CE (2,3) CE (1,2) CE (0,3) CE (0,1)
CE (1,4) CE (0,3) CE (0,2) CE (1,3) CE (2,3) CE (2,3) CE (1,4) CE (1,2)
CE (0,3) CE (3,4) CE (1,3) CE (2,4) CE (0,4) CE (1,2) CE (0,3) CE (0,1)
11
SN: Fitness
Number of bits correctly sorted, biased exponentially
toward low order bits:
f ( x) 
k 1
2 C ( x)


i
x
k
i
 N ( x)i 
i 0
Where C(x)i and N(x)i are outputs of wire i from
correct circuit C and evolved circuit N (resp.) on input x,
and k is all k bit inputs.
12
SN: Robustness



Bitwise stability (bs): percentage of
correctly sorted bits over all single point
circuit failures
BS higher in evolved circuits than handdesigned ones
BS low for minimal circuits, high for
circuits 5-10% larger than minimum,
and decreases for larger circuits
13
SN: Robustness Size Data
Here is some data
14
Case Study: Locomotion
Karl Sims, Thinking Machines Inc., evolved
“organism” descriptions and behaviors.
15
Evolving Software & Hardware




Sorting circuits
Robot control
Machine code
Growing chips


Image convolutions
Feature extraction
16
SN: Tree Representation
CE (1,4)
CE (0,3)
CE (1,3)
CE (0,4)
CE (1,2)
CE (2,4)
CE (0,2)
CE (3,4)
17
SN: Tree Crossover
1. Randomly select one node on each tree
2. Swap Nodes and subtrees
18
SN: Representation Effects
Pass Through Stuck on Zero Stuck on
One
MSN
Tree
Linear
*
***
**
*
***
**
*
**
***
All errors
*
***
**
19
SN: Evolving Physical Circuits
0
0
1
1
Cells ….. 64
0
1
1
0
Cells ….. 64
20
Evolving Circuits: More Results





17 electrical circuits evolved to date
which infringe on patents or rediscover
prior best known designs
Filters, thermometers, amplifiers
Arithmetic circuits
Controllers (Higuchi’s prosthetic arm,
missile guidance)
Image convolutions and classification
21
Case Study: Image
Convolutions
We evolved FPGA circuits to produce
convolutions on laser diffraction patterns,
pre-computed on special hardware.
22
Case Study: Regression
Problem: given target function, evolve
symbolic functional representation to
approximate it.
Fitness: square of errors on several
points.
GP Demo by Hans U. Gerber, Swiss
Federal Inst. Of Tech.
23
EC: Limitations & Advantages




Robustness: inherent advantage of
evolution
Survival of the fattest
Hardness: limitations from complexity
theory, VLSI design, information theory
(Pseudo) randomness
24
Survival of the Fattest

Variable size genomes grow without
correlation to fitness




Given insufficient selective pressure for
parsimony



Protective neutral code
Removal bias
Combinatorics (in trees)
Only parsimony pressure helps
“Liposuction” does not
Trees converge toward a fixed shape
25
Concluding Thoughts

Bring more biology into engineering and
Computer Science—it works
Bring more engineers and computer
scientists into biology—it works
There are soooooo many interesting
questions, and soooooo much data
And so very many interesting people

Gee, this is fun!



26
Acknowledgements







John Dickinson
Jim Frenzel
Deb Frincke
Larry & Millie Johnston
Steve McGrew
Holly Wichman
IBEST










BMDO
DOD/OST
NIH/NIGMS


John Cavalieri
Bill Danielson
Joe Dumoulin
Brad Harvey
Kosuke Imamura
Jason Masner
Mark Meysenburg
Bart Rylander
Jackie Shoaf
27