well let's see what the behavior it's serve the best individual
at different generations. At generation 1
that is the very first generation where we used random strategies
the population was just a bunch of random strategies the best
average score was -81. Let's see why
that's true here's the behavior that strategy
on this particular environment of cans
it's the individual moves down and
then it crashes into a wall then it crashed into all again
and again, and you can guess the rest of its life
its gonna spend crashing into a wall scoring
-5 points each time crashes
So this slightly different scoring different environments but
on average it does very poorly. Okay by generation 10
the best average score was all the way up 0
okay that's what better than -81. What did that individual do
well here's that strategy on this particular configuration of can.
And here's what it did.
In other the words it did nothing.
he just stayed put. By staying put
it didn't crash into any walls or do any other bad things
and so it got a score of 0. Well that's not very a
satisfying but this was better than the other individuals in its population
therefore it got to spread streets more than
other individuals its generation. By generation 200
the fitness was up to 240 for the best individual.
Here's what that did. It moved down
doesn't pick up the can but moved down further that picks up the can
then it comes back up pickup a can. Now it's gonna move back down
moves all the way down to the bottom the cans and then picks them up
so this one's doing a lot better than the previous one
that long we saw it generation zero this course 240
generations later but this individual
is picking up cans but tournament and inefficient way
she could see and by generation a thousand which was
the a maximum I let it run fitness is 492
on average and here's what this individual did.
It does exactly what you'd expected to do it moves down,
systematically picking up cans. My strategy
remember said if you're have a can your site
pick it up otherwise if there's it can adjacent site move there and so on
this one is systematically going down and up
and down and up. it's more systematic than my strategy
Now there is one improvement on my strategy But there was actually another
improvement which is a very
surprising to me: innovation on the part of the genetic algorithm
to explain why the genetic algorithm
outperformed mine, I looked at
my strategies behavior compared with the genetic algorithm strategies behavior in
many different
environments. Here's one particular type of environment that stood out.
So here's Robbie in a cluster of cans
so my strategy says pick up a can in the site if you can
then move to an adjacent site if there's a can in an adjacent site
we're here this cans into adjacent sites so picks one at random
decides to move west. okay it picks up the can
but now because it cannot see
past one square in either direction
it can't see this can overhear since it has no memory
it's lost all information about this can
and it stuck it doesn't see any cans around it and doesn't remember that
had cans over here. However the genetic algorithm
figured out a way to get around that problem
and here's how it did. This is a genetic algorithm strategy
it says don't pick up the can
it moves over to the West
now it picks up that can but now because it did not pick up
this can here, it has sort of breadcrumb trail
or tray love cans to get back
to wear the cans cluster cans were
so it doesn't have any memory itself probably doesn't have any memory
but botanic algorithm invented this kind of external memory by leaving cans there
and then having the robot come back and pick them up
so it was pretty ingenious I thought
and that's an example other genetic algorithm actually thinking of something
that
I didn't think of thus doing better
then my own strategy did.
Robbie is a robot is a very simple example that
I came up with just to teach people about genetic algorithms
but it does illustrate some interesting and general principles of evolution
that are often seen in genetic algorithms. Let me just say what these
are
First is that natural selection works
we went from a bunch of random strategies that perform very poorly
and just using this kind of natural selection
inspired by Darwinian natural selection
the genetic algorithm evolved what is essentially a perfect strategy
also evolution in our system
seem to proceed be a period serve stay sis
that is stain at about the same fitness level
punctuated by periods of rapid innovation
and that something is also seen in biological evolution
in both molecular evolution for since evolution of viruses
and evolution a bacteria all through to
large-scale evolution thats seen in the fossil record closes a little bit
controversy on
in general were able to show that in genetic algorithms
this kind of behavior is quite common even though there's no
external events happening to cause this
rapid steep innovation.
And I should say that this is in biological evolution
this kind of phenomenon has been called punctuated equilibria.
another principle is that the phenomenon of accept haitian is common
acceptation means the shifts in a function of a trait
during evolution and we saw that happening
in that trait that cost the robot
to not pick up a can but move past it
So you actually saw that happening at generation 240
and that was the inefficient version of the strategy.
there it wasn't a very good treat because it cost the robot to be very
inefficient not pick up all the not have time to pick up all the cans
but it was hold by the genetic algorithm by evolution
to actually be a very efficient trait in that it became only used in
appropriate circumstances like the one I just showed you
where I compared my strategy to the genetic algorithm strategy
and so that trait was shaped by evolution
from being a rather non adaptive
to a very adaptive trait and that's also seen in biological evolution.
And finally the dynamics and results of evolution are somewhat unpredictable and
hard to analyze
even in this extremely simple version of evolution
and it takes a lot of work to try and understand what
though results a pollution are doing why the
are fit had how they evolved these are all
in genetic algorithms unpredictable and
typically either very hard or impossible to analyze.