Transcript Power Point lecture

Strategies and Rubrics for Teaching
Chaos and Complex Systems Theories as
Elaborating, Self-Organizing, and
Fractionating Evolutionary Systems
Fichter, Lynn S., Pyle, E.J., and Whitmeyer, S.J., 2010,
Journal of Geoscience Education (in press)
Elaborating Evolutionary
Mechanisms
The General Evolutionary
Algorithm
1. Differentiate
2. Select
3. Amplify
Repeat
The units of selection and
the information carriers
are different in each kind
of system but the
algorithm is the same . . .
Elaborating Evolution
Word Evolv
Genetic Algorithms
Elaborating Evolution
A genetic algorithm (GA) is a search technique used to find
exact or approximate solutions to a problem.
In biological evolution the “solution” is measured as a fitness
function, how well adapted the organism is to its environment.
Natural selection works on the organisms, eliminating those
that are less fit, while allowing the more fit to live, and
reproduce.
For example . . .
General Evolutionary Algorithm in Biology
Differentiate
Select
Repeat
Amplify
Elaborating Evolution
WordEvolv is a genetic algorithm that demonstrates how
efficient natural selection is. The procedure is . . .
Create a fitness function. For example, the phrase, “What is
this phrase.” This is known as the target string.
Then:
1. Generate at random 20 strings of letters and spaces of the
same length as the target string.
2. Pass the 20 strings through a selection filter, comparing
each of the strings with the target string. Keep the one
string closest to the target, discard (select out) all the other
strings.
3. Reproduce
the one surviving string 20 times, but mutate
each at random (i.e. change one letter in each string from
the initial).
4. Repeat
process.
Elaborating Evolution
John Muir Trail
Can we evolve via
natural selection
(i.e. a genetic
algorithm) an
electronic “ant” that
can learn to run a
maze?
The John Muir Trail
The Trail
The trail itself is a series of
black squares on a 32x32 white
toroidal (ie, wraparound) grid.
Each black square is numbered
sequentially, from 1, directly
next to the starting square, to
89, the ending square. The
ant's task is to follow this trail
and move across each square
in sequence: That is, it does not
get a score of 89 for waltzing
across the board from square 0
directly to square 89. It must
first visit each square in turn.
The John Muir Trail
Random Approach
UCLA experiment: the
power, or lack thereof, of a
random search.
• 1 billion strings of
genetic code were
generated at random.
• The best was only able
to get to square 81 on
the trail.
The John Muir Trail
Evolutionary Approach
Generate a series of electronic
“ants” each with a genetic code
created at random.
The John Muir Trail
The Ant gene consists of 512 bits of
information, a series of 1's and 0's. The
genetic makeup is changed each generation at
some low frequency either by cross over—two
individuals exchange part of their string of
genes—or by mutation—one gene has its bit
flipped from 1 to 0 or vice versa.
The John Muir Trail
The ants are simple state
machines which can move
along the trail and sense their
immediate surroundings.
• The ant stands on a single
square and can face north,
south, east, or west.
• It is capable of sensing the
state of the square directly in
front of it.
• In each time step, the ant
must take one of four actions.
It may turn left, turn right,
move forward one step, or
stand still.
• The ant's score is the value
of the highest square it was
able to reach when a fixed
amount of time has passed.
Learning to Run the John Muir Trail
1. The first generation of ants was
given totally random genotypes—
they were strings of ones and zeros
selected by chance.
2. A population of 64 K, or 65,536,
of these "random" ants was
created.
3. In this first generation, it was
common for ants not to move at all,
or to move haphazardly, or to
continue stubbornly in a single
direction.
4. After each ant was scored, the
top
1%
was
selected
for
reproduction in the next generation
and copied to compose a full
population
Learning to Run the John Muir Trail
5. During reproduction.
• Mutate a small percent of the new
ants at a low rate
• Conduct crossovers at a certain
small rate.
REPEAT
The John Muir Trail
Typical Run of an Ant Experiment as run by Patrick
Brennan; note that an ant capable of running nearly the
entire trail evolved in less than 200 generations.
Examples of the General
Evolutionary Algorithm
In Practice
Ramps, Anti-Ramps
and the Red Queen
Danny Hillis, 1991, 'Coevolving Parasites Improve
Simulated Evolution as an
Optimization Procedure'
Ramps is a genetic algorithm evolving to reach a fitness
peak at solving a mathematical problem - the ability to sort
a random number list. Fitness is measured by the shortest
number of steps evolved to solve the various problems
present in the environment.
Antiramps is a genetic algorithm evolving to reach a
fitness peak at creating test cases the Ramps can not
solve well with the strategies evolved to date. That is, the
most fit Antiramps are those which resist being sorted
easily or well.
The Prisoner’s Dilemma and
Evolution of Cooperation