Transcript BiomoW04Week2

Biomorphic Computing
Professor: Bill Tomlinson
Tuesday 2:00-4:50pm
Winter 2004
CS 189
Week 2: Genetic Algorithms
•
•
•
•
•
•
News
Last Week’s assignment
Natural Evolution
Synthetic Evolution (& Sims reading)
Assignment 2
Lab Time
Go over Game of Life
assignment
• Problems?
Go over Sims reading
• fixed-length bit strings vs. lisp expressions
• parameter spaces
• mutating and mating symbolic expressions
Natural Evolution
• Descent with modification
• The central process by which the abundance
of life forms have come to exist.
Linnaean Classification
• Carolus Linnaeus, 1707-1787
• Initially based on visible, behavioral and
other obvious characteristics.
• Kingdom, Phylum, Class, Order, Family,
Genus, Species (pick your favorite
mnemonic device)
Defining the species
• How do you tell whether two things are
from the same species?
Defining the species
• Reproductive isolation (produce viable
offspring)
• Morphological similarity
• Genetic similarity
• Ecological similarity
Questioning the species
concept…
• DNA studies are calling some of these
classifications into question.
• Organisms that reproduce asexually - self-cloning
bacteria
• Ring species
• Species over time
• Based on human decisions about classification
• A conceptually useful mechanism to work with the
uneven genotypic/phenotypic distribution
Charles Darwin
•
•
•
•
•
1809-1882
Voyage of the Beagle to the Galapagos
Finches
Origin of Species - 1859
Expression of Emotion in Man and Animals
- 1872
Darwin vs. Lamarck
• How does a giraffe get its long neck?
• Lamarck (1744-1829)
Mendelian Genetics
• Gregor Mendel
1822-1884
• Dominant vs. recessive
• Genotype vs. phenotype
(expression)
Punctuated Equilibria
• Niles Eldredge
• Stephen Jay Gould (1941-2002)
• long periods of stability with abrupt periods of
change and appearances of new species
• splitting off of daughter species (cladogenesis),
rather than transformation of species as a whole
(anagenesis)
• Founder effects
Mitosis vs. Meiosis
• Mitosis: one cell
becomes two cells
with the same DNA
• Meiosis: one cell
becomes four cells
with one strand each
Crossing Over
• Meiosis -> production of germ cells
• Parts of two
chromosomes
get swapped.
• Also called recombination
Mutation
• Occasional misfirings of the replication
process.
• Almost always harmful.
• On occasion,
very successful.
Differential Survival
• Once there is variability (through sexual
reproduction, crossover and mutation) in a
population, the environment culls some
while others survive.
• Natural selection.
Biological Diversity
• Simple mechanism
of natural selection
enables the propagation
of vastly different
organisms.
Convergent Evolution
• Same selection pressures cause similar
morphology/behavior/etc. in different
species.
• Other examples?
From Biology to Computation
• From natural selection to evolutionary
computation
Simulating evolution
• Descent with modification
• Fitness landscape determines differential
survival
Different Branches of
Evolutionary Computation
•
•
•
•
•
Genetic Algorithms
Genetic Programming
Evolutionary Strategies
Evolutionary Programming
etc.
Evolved Virtual Creatures
• Karl Sims
What problems are evolutionary
techniques good for?
• Discuss…
What problems are evolutionary
techniques good for?
• Problems in which the solution can be
characterized in terms of variables (or
human feedback)
• Overcoming fitness landscapes with many
local optima (i.e., where gradient descent
won’t work).
Shortcomings
• Computationally expensive
Applications: Artificial Life
• Tierra
– Synthetic
organisms
compete
for time
and
computer
memory.
Applications: Biocomputing
• Protein Folding
• RNA Folding
• Sequence alignment
Applications: Evolvable
Hardware
• Golem Project @ Brandeis (movie)
Applications: Coordinating
Groups of Robots
• Evolving teams for reconnaissance, terrain
mapping, etc. - UCF/GMU
Applications: Game Theory
• Prisoner’s Dilemma - Axelrod
Applications: Art
• Karl Sims
Genetic Algorithms
• Project ideas?
Break
Assignment 2
• Implement a genetic algorithm to evolve a
creature that can go as fast as possible to a
point where you click.
Representation of a Creature
• Ability to sense and take action
– Conditional bits - perception
– Action bits - motor
Conditional Bits
• How are conditional bits hooked up to the
sensory world?
• Dot product and cross product offer one
way to slice perceptual world into chunks.
Sensor radius
How far around them can they see?
How do they detect the target?
Action Bits
• How do action bits allow the creature to
move around or otherwise affect its world?
How a rule works.
• Rule: 010010
• First four bits are perception
– e.g., front-left, back-left, back-right, front-right
• Last two bits are action
– go-straight-or-turn, if-turn-which-direction
• So this bitstring might mean “If I sense
something in back left quadrant, turn left.”
Number of rules
• How many do you need?
• How many is too many?
The Bitstring Genome
• all the bits of all the rules
• equivalent of DNA
• Total length = #bits/rule * #rules.
Populations
• Genetically Diverse
• Provide the raw materials for “survival of
the fittest.”
Initialize population
• Random
• Seeded
Evolving the creatures
•
•
•
•
Initialize population
Evaluate population
Generate new population
Loop between evaluating population and
generating new one.
Population size
• Large enough for genetic diversity
• Small enough for computational speed
Evaluate Population
• Load population into simulated world
(reset)
• Fitness criteria?
number of creatures loaded in
• can just be one, or can be several (take
average of fitness)
Generate new population
• Find best (mom) and second best (dad) (or
some other combination of top performers)
• Crossing over
• Mutation
Crossover rate
• How much recombination?
Mutation rate
• How often to change a random bit?
Number of time steps
• Too short and it’s hard to learn
• Too long and success is trivial
Number of generations
• Genetic change occurs in small stages over
many generations.
Assignment 2
• Distribute Assignment sheet
• Distribute source code
The Files
•
•
•
•
•
•
GAMain
Creature
Evolver
TestWorld
GridWorld
Vec2
What needs to be written?
Evolver. generateNewPopulation()
Creature.sense()
Creature.chooseAction()
Creature.takeAction()
TestWorld. testFitness()
Lab Time
• All please log into a computer
• If you don’t have an account, please get one