Transcript Learning and Evolution: Lessons from the Baldwin

Learning and Evolution:
Lessons from the Baldwin-Effect
Georg Theiner
P747 Complex Adaptive Systems
March 11th, 2003
Outline
•
•
•
•
•
A brief history of modern evolutionary biology
What is the Baldwin Effect?
Hinton & Nowlan's (1987) simulation
JAVA-applet of BE
The trade-offs between phenotypic plasticity and
rigidity
• Subsequent studies
• Discussion
Lamarckian Evolution
• Published Philosophie Zoologique (1809)
• Assumption: Change in the environment
causes changes in the needs of organisms
living in that environment, which in turn
causes changes in their behavior.
• Mechanisms of evolution
– First Law: Use or disuse causes structures
(organs) to enlarge or shrink
– Second Law: All such acquired changes are
heritable
• Example: long legs and webbed feet of
wading birds, long neck of giraffe
Jean-Baptiste Lamarck
(1744-1829)
Darwinian Evolution
• Published The Origin of Species
(1859)
• direct manipulation of one's genetic
make-up impossible
• acquired characteristics are not
directly passed on to offspring
• Mechanism of evolution:
– Genetic variation in species through
random mutations
– Natural selection operates on
phenotypes
Charles Darwin (1809-82)
Baldwinian Evolution
• Published "A New Factor in
Evolution" (1896)
• Independently identified by Baldwin,
Morgan, and Osborn in 1896
• New factor = phenotypic plasticity: the
ability of an organism to adapt to its
environment during its lifetime
– Examples: ability to learn, to increase muscle
strength with exercise, to tan with exposure to
sun
James Mark Baldwin
(1861-1934)
The Baldwin Effect
• A cluster of effects emerging from an interaction
between 2 adaptive processes:
– genotypic evolution of population (global search)
– individual organism's phenotypic flexibility (local
search)
• Concerned with benefits and costs of lifetime
learning
• lifetime learning can alter the genetic
composition of an evolving population
• Hypothesized
examples:
– bird song (Simpson
1953)
– human language
capacity (Pinker and
Bloom 1990, Deacon
1997)
– consciousness,
intelligence (Dennett
1991, 1995)
• learning capacity
eventually becomes
genetically encoded
 resembles
Lamarckian sequence
• consistent with
Darwinian mechanism
for inheritance of
traits
The Baldwin Effect, Step 1
• Evolutionary value of learning: accelerates
evolution of an adaptive trait
– As a result of mutation, an organism becomes capable of
learning how to do X
– Learning how to do X increases an organism's fitness
– Creates new selective pressures: because selection is now
also working on the ability to perform X.
– Since the successful X-er has greater reproductive success,
eventually the population may consist entirely of individuals
able to learn how to do X.
The Baldwin Effect, Step 2
• Since learning can be costly, evolution favors rigid
solutions in which acquiring X is part of an organism's
genetic make-up (phenotypic rigidity)
– Chance of reproductive success be proportional to how
quickly (reliably) X can be learnt
– New selective pressures cause competition between slow and
fast learners
– Some individuals are innately better equipped for performing
X, have reproductive advantage
– Eventually, capacity to X comes under direct genetic control
= genetic assimilation, canalization of a trait (Waddington
1942)
Hinton & Nowlan Simulation (1987)
• Organism with neural net, 20 connections
(phenes)
• 20 genes, one-to-one mapping on phenes
• Each gene can have 3 alleles
– 0 = no connection
– 1 = connection
– ? = undetermined, learning
• one Good Phenotype: net works just in case all
nodes are connected
• one Good Genotype: all 1's
"Needle in a haystack"-fitness landscape
• Evolutionary search
modeled by GA
• Population of 1000
organisms
• Each allele is randomly
initialized
– p = 0.5 for ?
– p = 0.25 for 0 and 1
• performs no better than
random
fitness
combination of alleles
Problem of passing on the good genome
• Even if good solution discovered, not
easily passed on
• unless fit organism finds very-close-to-fit
mate, good genome will be destroyed
• expected number of good (immediate)
offspring < 1
– can be bypassed in artificial simulations using
elitism operator, asexual reproduction
The importance of lifetime learning
• Augment evolutionary search with phenotypic
plasticity
• Each organism performs 1000 learning trials
during lifetime
• learning mechanism: random guess
– if correct net is found, stop; else keep searching
• all phenes equally hard to learn
• requires that organism recognizes the correct
solution
Determine next generation
• Use a version of
Holland's GA (1975)
• Perform 1000 matings
• Selection algorithm:
Roulette Wheel
• Select parents with
probability
proportional to fitness
• Fitness function F of an
individual A in a population i is
F(A[i]) = 1 + [(G – g) / G] * (N – 1)
– G = number of allowed
guesses
– g = number of guesses
until solution found
– N = length of genotype
• in our case: 1 + (19n/1000)
• Wheel is spun twice (2 parents) for each
mating, single offspring is generated
• cross-over point for combining parental
alleles is chosen randomly
• offspring inherit only genome, never learnt
connection settings
• Model parameters are fine-tuned
– typical genotype has about 10 connections
genetically determined (0's or 1's)
– about 2^10 learning trials
Results 1
• Phenotypic plasticity smoothes "needle in a
haystack" fitness landscape
• by allowing an organism to explore neighboring
regions of phenotypic space
• no unlikely saltations necessary to climb fitness
peak
Results 2
• if no phenotypic plasticity,
about 2^20 (~ 1 million)
organisms have to be
produced to succeed in
search
• with learning, finding the
correct net requires only
16 x 1000 organisms
• little selection pressure to
fix all phenes genetically
JAVA-Simulation (Watson and Wiles 2001)
• Run with "Show all data" check-box to see frequency
of 0's and ?'s
• Alter random number seed
• Additional evolutionary operators
– mutation
• chance (as specified in Advanced Options) that a given allele will be
flipped to either 0, 1, or ? (with equal p)
• maintain diversity, avoid local fitness maxima
– elitism
• forces best individual of each population to be included unchanged in
next generation
• Alternative Selection Algorithms
– Ranked Roulette Wheel
• slice of wheel is proportional to ranked fitness
• minimizes real differences in fitness
• less selection bias for top-fit individuals
– Tournament
• randomly picks 2 individuals from population, chooses
fitter one with p = k (as set in Advanced Options)
• runs much faster
• preserves genetic diversity much longer
• Standard combinations for optimization
algorithms
– Standard roulette without elitism
– tournament with elitism
Fundamental insight of BE
• Trade-offs between
learning (plasticity)
and instinct (rigidity)
French and Messinger (1994)
• amount of plasticity and amount of benefit of
learnt behavior is crucial to size of BE
– having blue eyes vs. humming Middle C vs. winking
– x-axis: agent's normalized distance from Good Gene
(number of bits differing by total number of bits)
– y-axis: probability of learning the Good Phene
• BE is significant only for a narrow window of
plasticity
• if too low or too high, virtually no convergence
towards Good Gene
Mayley (1996a, 1996b, 1997)
• Possible selective disadvantage of learning:
Hiding Effect
• phenotypic fitness differentials are compensated
by learning capacity
• genetic differences are hidden from selection by
learning
• trade-offs between Baldwin and Hiding effect
Discussion
• Unrealistic assumptions about fitness landscape
– extremely rugged fitness landscape makes pure
evolutionary search very hard
– How smooth are real search spaces?
• Unrealistic assumption about learning
mechanism
– instead e.g. use hillclimbing procedure for local
optimization
– enhances BE only if learning procedure is not too
sophisticated, otherwise insufficient selective
pressure for hard-wiring
• Learning trials are "cheap" genetic
experiments
– but biological reality of those two search
strategies differs in many respects
• Unrealistic assumption about genomephenome mapping
– mapping could be one-to-many
– genetic specification and successful guessing
of a trait are treated interchangeably
– transformation of phenotype to genotype
(development) is trivialized
• Do we need an explicit fitness function?
– French & Messinger (1994): introduce spatial
dimension
– consider 3 areas of plasticity: Good Phene =
more efficient metabolism, movement,
reproduction
– world determines fitness of a given genotype
• Using simple models to understand
complex phenomena
– Controlled experiments are practically
unfeasible
– How simple is too simple?
Selective Bibliography on BE
A bibliography on BE (last update: 2001)
http://www.cs.bath.ac.uk/~jjb/web/baldwin.html
An online JAVA-simulation of BE
http://www.itee.uq.edu.au/~jwatson/bdemo/index.html
requires JAVA version 1.3.1 or greater
Ancel, L. (2000)
Undermining the Baldwin Expediting Effect: Does Phenotypic
Plasticity Accelerate Evolution? Theoretical Population Biology, 58,
307-19.
http://www.santafe.edu/~ancel/PAPERS/TPB.pdf
Baldwin, J.M. (1896)
A New Factor in Evolution, American Naturalist, 30, 441-51.
http://www.santafe.edu/sfi/publications/Bookinforev/baldwin.html
Belew, R.K. (1990)
Evolution, Learning, and Culture: Computational Metaphors for Adaptive
Search, Complex Systems, 4, 11-49.
Downes, S. (2003)
Baldwin Effects and Expansion of the Explanatory Repertoire in
Evolutionary Biology, in: Weber, B., and Depew, D.J., (eds.), loc.cit.
French, R., and Messinger, A. (1994)
Genes, phenes and the Baldwin effect, in: Brooks, R., and Maes, P. (eds.),
Artificial Life IV, MIT Press, 277-82.
http://www.santafe.edu/~amessing/baldwin.ps
Hinton, G.E., and Nowlan, S.J. (1987)
How Learning Can Guide Evolution, Complex Systems, 1, 495-502.
[reprinted in Mitchell, M., and Belew, R. (eds.), Adaptive Individuals in
Evolving Populations: Models and Algorithms (1996)]
http://www-advancedgec.ge.uiuc.edu/papers/Chap 25 Adaptive
Individuals.pdf
Jones, M., and Konstam, A. (1999) The Use of Genetic Algorithms
and Neural Networks to Investigate the Baldwin Effect, in: Carroll,
J., and Hiddad, H. et al. (eds.), Proceedings of the 1999 ACM
Symposium on Applied Computing, 275-79.
Ku, K., and Mak, M. (1998) Empirical Analysis of the Factors that
Affect the Baldwin Effect, in: Eiben, A.E., and Baeck, T. et al.
(eds.), Parallel Problem Solving From Nature, Springer, 481-90.
Mayley, G. (1996a) The evolutionary cost of learning. In Maes, P.,
Mataric, M., Meyer, J-A., Pollack, J., and Wilson, S. (Eds), From
Animals to Animats: Proceedings of the Fourth International
Conference on Simulation of Adaptive Behaviour, 458-467, MIT
Press.
http://www.cogs.susx.ac.uk/users/gilesm/sab96.ps
Mayley, G., (1996) Landscapes, Learning Costs and Genetic
Assimilation, Evolution, Learning, and Instinct: 100 Years of the
Baldwin Effect, a Special Issue of Evolutionary Computation, 4(3),
1996. http://www.cogs.susx.ac.uk/users/gilesm/ec.ps
P.Turney, D. Whitley and R. Anderson (eds), Evolution, Learning,
and Instinct: 100 Years of the Baldwin Effect, Special Issue of
Evolutionary Computation, 4(3), 1996
Check out Table of contents:
http://alife.ccp14.ac.uk/baldwin/baldwin/toc.html
Editorial with a short history of BE:
http://alife.ccp14.ac.uk/baldwin/baldwin/editorial.html
Turney, P. (1996) Myths and legends of the Baldwin effect, in:
Fogarty, T., and Venturini, G. (eds.), Proceedings of the ICML-96,
135-42.
ftp://ai.iit.nrc.ca/pub/iit-papers/NRC-39220.pdf
Waddington, C.H. (1942) Canalization of Development and the
Inheritance of Acquired Characteristics, Nature, 150, 563-65.
Weber, B., and Depew, D.J. (eds.), Evolution and Learning : the
Baldwin Effect Reconsidered, MIT Press, 2003.
on-order by B-Main Lib