00:00:00
00:00:15
PATRICK WINSTON: I have
extremely bad news.
00:00:18
Halloween falls this
year on a Sunday.
00:00:21
But we in 6.034 refuse to
suffer the slings and arrows
00:00:25
of outrageous fortune.
00:00:27
So we've decided that
Halloween is today,
00:00:30
as far 6.034 is concerned.
00:00:33
Kenny, could you give
me a hand, please?
00:00:34
00:00:43
If you could take that
and put it over there.
00:00:47
STUDENT: [INAUDIBLE]?
00:00:49
PATRICK WINSTON: Mm hm.
00:00:49
Just give it to them.
00:00:51
00:00:54
You can take as much
of this as you like.
00:00:56
The rest will be given to that
herd of stampeding freshman
00:00:59
that comes in after.
00:01:00
00:01:16
It's a cornucopia
of legal drugs.
00:01:21
Chocolate does produce
a kind of mild high,
00:01:24
and I recommend it before
quizzes and giving lectures.
00:01:30
I have a friend of mine, one of
the Nobel laureates in biology,
00:01:33
always eats chocolate
before he lectures.
00:01:36
Gives him a little edge.
00:01:38
Otherwise, he'll be flat.
00:01:41
So I recommend it.
00:01:47
00:01:54
It will take, I
suppose, a little while
00:01:55
to digest that neural net stuff.
00:01:59
A little richer than
usual in mathematics.
00:02:02
So today, we're going to
talk about another effort
00:02:04
at mimicking biology.
00:02:06
00:02:09
This is easy stuff.
00:02:11
It's just conceptual.
00:02:14
And you won't see
this on the next quiz.
00:02:15
But you will see
it on the final.
00:02:17
It's one of those quiz
five type problems,
00:02:19
where I ask you questions to
see if you were here and awake.
00:02:23
So a typical question
might be, Professor Winston
00:02:27
is a creationist, or
something like that.
00:02:31
Not too hard to answer.
00:02:34
In any event, if it's been hard
to develop a real understanding
00:02:41
of intelligence,
occasionally the hope
00:02:42
is that by mimicking biology
or mimicking evolution,
00:02:47
you can circumnavigate
all the problems.
00:02:53
And one of those
kinds of efforts
00:02:55
is ever to imitate evolution.
00:02:59
So we're going to talk
today about so called
00:03:02
genetic algorithms,
which are naive attempts
00:03:06
to mimic naive evolution.
00:03:09
Now, I realize that most MIT
students have a basic grasp
00:03:15
of sexual reproduction.
00:03:17
But I've found in
talking with students
00:03:20
that many times, they're
a little fuzzy on some
00:03:23
of the details.
00:03:24
So let's start off by reflecting
a little bit about how
00:03:27
that works.
00:03:29
So let's see, we
need pink and blue.
00:03:34
And here's our cell,
and here is its nucleus,
00:03:39
and here are mommy and
daddy's chromosomes.
00:03:42
We'll just pretend
there's one pair.
00:03:45
Now ordinarily, in ordinary cell
division, you get two cells.
00:03:53
Both have a nucleus, and the
process of producing them
00:03:57
involves the duplication
of those chromosomes.
00:04:01
And then one pair ends up
in each of the child cells,
00:04:06
and that's all there is to that.
00:04:08
That's mitosis.
00:04:10
00:04:16
But then, when we talk
about reproduction,
00:04:19
it's more complicated
because those chromosomes
00:04:23
get all twisted up, and they
break, and they recombine.
00:04:28
So when we talk about
the cells that split off
00:04:31
from one of these
germ cells, it's
00:04:35
no longer appropriate to
talk about the pink one
00:04:40
and the blue one, because
the pink one and the blue one
00:04:44
are all mixed up.
00:04:45
So you get two chromosomes
here and two here.
00:04:49
But through some miracle
of nature, which has always
00:04:52
amazed me, these two
cells split, in turn,
00:04:57
into four cells altogether.
00:05:00
00:05:05
And each of those four
cells at the bottom
00:05:08
gets one of the
chromosomes that was
00:05:11
produced by the twisting up
of the rope and recombination.
00:05:16
Then, along comes
a special occasion.
00:05:23
And now we can think of this
as being a blue one and this
00:05:29
as being a pink one.
00:05:31
And they come together, and
you get a new person, like so.
00:05:38
Note that your mother
and father's chromosomes
00:05:41
are never, never recombined.
00:05:43
It's your grandparents
chromosomes that recombine.
00:05:47
So that's what it's like.
00:05:48
And the main thing
to note about this
00:05:50
is-- well, a couple things.
00:05:51
If you happen to be female,
this part of the process--
00:05:57
this part over here-- took
place before you were born.
00:06:01
If you happen to be male, it's
going on right now as we speak,
00:06:05
which probably
explains something.
00:06:07
But in any event, it's
going on right now.
00:06:10
But whenever it
goes on, there are
00:06:14
lots of opportunities
for throwing dice.
00:06:18
So God threw all
the dice before you
00:06:20
were born, if you
happen to be a female,
00:06:23
in this part of the
process over here.
00:06:26
Then, of course, more
dice got thrown here
00:06:28
when the decision
was made about which
00:06:30
particular cells got to fuse
to form a new individual.
00:06:35
So I want to beat on this
idea of lots of choice.
00:06:38
When we talk about
genetic algorithms,
00:06:40
and we talk about nature, there
are lots of choices in there.
00:06:44
And that means there
are lots of choices
00:06:46
to intervene, to screw around,
to make things work out
00:06:50
the way you want.
00:06:52
But in any event, there we are.
00:06:54
That's the basic idea, and it
all starts with chromosomes.
00:06:58
So we could think of
implementing something
00:07:00
that imitates that
with the ACTG stuff
00:07:03
that you learned all
about in Seminar 1.
00:07:07
But we're computer scientists.
00:07:08
We don't like Base 4.
00:07:10
We like Base 2.
00:07:11
So I'm going to just suggest
that our chromosomes are binary
00:07:14
in this system that
we're going to build.
00:07:17
00:07:21
So that might be a chromosome.
00:07:23
And it doesn't
have to be binary.
00:07:26
It can be symbolic
for fall I care.
00:07:27
But it's just some
string of things
00:07:30
that determine how the
ultimate system behaves.
00:07:35
So it all starts out, then,
with some of these chromosomes,
00:07:39
some of these
simulated chromosomes,
00:07:46
simulated,
simplified, and naive.
00:07:51
And there's a population
of chromosomes.
00:07:55
The population of
chromosomes-- it
00:07:57
might be subject to a
little bit of mutation.
00:08:00
That is to say, a zero becomes
a one, or a one becomes a zero.
00:08:05
That happens a lot.
00:08:06
That mutation stuff
happens over here
00:08:07
when things get twisted
up and recombined.
00:08:09
There are copying
errors and stuff.
00:08:12
Cosmic rays hit it all the time.
00:08:13
All sorts of reasons
why there might
00:08:15
be a single point of change.
00:08:18
That produces the
mutation effect.
00:08:21
So here, we have a population
that starts off over here.
00:08:32
And some of those things
are subject to mutation.
00:08:34
00:08:37
And you'll note, here's a
whole bunch of choice already.
00:08:41
How many of these mutations
do you allow per chromosome,
00:08:45
for example?
00:08:48
How many of the chromosomes
just slip through
00:08:50
without any mutation?
00:08:51
Those are choices you can make.
00:08:53
Once you've made
those choices, then we
00:08:55
have the crossover phenomenon.
00:08:57
00:09:01
Let's identify one of these
guys as the pink one and one
00:09:05
of these guys as the blue one.
00:09:08
And so now we have the
pink one cruised along
00:09:12
as well as the blue one.
00:09:14
The pink one and the blue
one cross and produce
00:09:17
a new chromosome,
just like in nature.
00:09:20
So we take the front part of
one, back part of the other,
00:09:23
and we fuse them together.
00:09:26
And some may slip by without
any of that, like so.
00:09:32
Well, these things are meant to
be combined in pairs, like so,
00:09:36
but they may not have
any crossover in them.
00:09:38
So you have another
set of choices.
00:09:40
How many crossovers do you
allow per recombination?
00:09:44
You get another set of choices.
00:09:47
So now we've got a population
of modified chromosomes
00:09:53
through mutation and crossover.
00:09:54
So the next thing to do
is we have the genotype
00:09:58
to phenotype transition.
00:10:00
That is to say the chromosome
determines the individual.
00:10:03
It may be a person.
00:10:05
It may be a cow.
00:10:06
It may be a computer program.
00:10:07
I don't care what.
00:10:08
But that code down
there has to be
00:10:12
interpreted to be a something.
00:10:15
So it is the
genotype, and it has
00:10:17
to be interpreted to
be something which
00:10:20
is the phenotype, the thing
that the stuff down there is
00:10:25
encoding for.
00:10:26
So here, we have a
bunch of individuals.
00:10:29
00:10:32
Now, each of those
individuals, because they
00:10:34
have varying
chromosomal composition,
00:10:36
will have a different fitness.
00:10:39
00:10:42
So these fitnesses
might be-- well,
00:10:45
who knows how they
might be scored.
00:10:46
But we're computer scientists.
00:10:48
We might as well use numbers.
00:10:49
So maybe this guy's
fitness is 88,
00:10:51
and this guy's fitness
is 77, and so on.
00:10:57
So now that we've got fitness--
00:10:58
00:11:01
by the way, notice
all the choices
00:11:02
involved there-- choice
of how you interpret
00:11:04
the genotype, choice about
how the phenotype produces
00:11:08
the fitness.
00:11:09
And now we have a choice
about how the fitness produces
00:11:13
a probability, like 0.8
and 0.1, or something
00:11:19
like that--
probability of survival
00:11:23
into the next generation.
00:11:25
So now, once we've got
those probabilities,
00:11:27
we actually have selection.
00:11:28
00:11:32
And those phenotypes out
there produce genotypes,
00:11:35
a new set of
chromosomes, and that
00:11:39
completes our loop that
goes back in there.
00:11:43
And so that's the
new generation.
00:11:45
00:11:51
Sounds simple.
00:11:54
So if you're going to
make this work, of course,
00:11:56
you have a million
choices, as I'm
00:11:58
going to emphasize
over and over again.
00:11:59
And one of your choices
is, for example, how
00:12:04
do you compute the
probability of survival
00:12:06
to the next generation
given the fitness?
00:12:10
So we have to go, somehow,
from numbers like these
00:12:13
to probabilities like those.
00:12:16
So I'm going to talk about
several ways of doing it.
00:12:20
None of them are magic.
00:12:21
None of them was specified
and stipulated by God
00:12:24
as the right way.
00:12:26
But they have increasingly
good properties with respect
00:12:28
to this kind of processing.
00:12:31
So the simplest thing
you can do-- idea number
00:12:35
one for computing
the-- see, what you do
00:12:39
is you get this whole
bag of individuals,
00:12:41
and you have to decide
who's going to survive
00:12:43
to the next generation.
00:12:45
So at each step,
everything in the bank
00:12:48
has a probability of being
the one you pick out and put
00:12:51
in the next generation.
00:12:52
So at any step, the sum
of the probabilities
00:12:54
for each of those guys
is 1, because that's
00:12:57
how high probability works.
00:12:59
The probability of a
complete set, added all up,
00:13:02
is probability of 1.
00:13:05
So one thing you
can do is you can
00:13:08
say that the
probability that you're
00:13:10
going to draw individual
i is equal to,
00:13:14
or maybe is proportional to,
the fitness of that individual.
00:13:18
00:13:24
I haven't completed
the expression,
00:13:25
so it's not a probability
yet, because some piece of it
00:13:29
won't add up to 1.
00:13:31
How can I ensure that
it will add up to 1?
00:13:34
That's easy.
00:13:34
Right.
00:13:36
All I have to do is
divide by the sum
00:13:39
of the fitnesses over i.
00:13:43
So there's a probability
measure that's
00:13:45
produced from the fitnesses.
00:13:46
Yeah.
00:13:47
STUDENT: You need to make
sure that the fitnesses aren't
00:13:49
negative.
00:13:50
PATRICK WINSTON: Have to make
sure the fitnesses are what?
00:13:51
STUDENT: Aren't negative.
00:13:52
PATRICK WINSTON: He
says I have to make
00:13:54
sure the fitnesses
aren't negative.
00:13:55
Yeah, it would be
embarrassing if they were.
00:13:59
So we'll just truncate
anything like that as 0.
00:14:01
You've got a lot of choice how
you can calculate the fitness.
00:14:04
And maybe you will produce
negative numbers, in which case
00:14:06
you have to think a
little bit more about it.
00:14:08
00:14:11
So now, what about an example?
00:14:13
Well, I'm going to
show you an example.
00:14:16
Why don't I show
you the example.
00:14:19
What we're going to
do is we're going
00:14:21
to have a genetic
algorithm that looks
00:14:22
for an optimal value in a space.
00:14:24
00:14:27
And there's the space.
00:14:29
Now, you'll notice it's
a bunch of contour lines,
00:14:32
a bunch of hills in that space.
00:14:34
Let me show you how
that space was produced.
00:14:38
The fitness is a
function of x and y,
00:14:42
and it's equal to the sine of
some constant times x, quantity
00:14:48
squared, times the sine of some
constant y, quantity squared,
00:14:55
e to the plus x plus y
divided by some constant.
00:15:01
So sigma and omega
there are just in there
00:15:04
so that it kind of makes a
nice picture for demonstration.
00:15:09
So there's a space.
00:15:10
And clearly, where you
want to be in this space
00:15:12
is in the upper
right-hand corner.
00:15:16
That's the optimal value.
00:15:18
But we have a genetic algorithm
that doesn't know anything.
00:15:21
All it knows how to do
is mutate and cross over.
00:15:26
So it's going to start off
with a population of 1.
00:15:30
It's a little red dot
down in the lower left.
00:15:33
So here's how it's
going to evolve.
00:15:36
There's going to be s
chromosome consisting
00:15:38
of two numbers, an x
number and a y number,
00:15:43
like, say, 0.3 and 0.7.
00:15:47
Here's another one, which
might be 0.6 and 0.2.
00:15:53
So the mutation
operator is going
00:15:55
to take one of those values
and change it a little bit.
00:15:58
So it might say, well, we'll
take 3, and we'll make it 0.2.
00:16:03
And the crossover
operation is going
00:16:05
to exchange the x and
y values of pairs.
00:16:08
So if we have a
crossover here, then what
00:16:11
we're going to get out
from this one-- well,
00:16:16
we're going to get out a
combination of these two.
00:16:18
00:16:22
And it's going to
look like this.
00:16:31
Because what we're
going to do is we're
00:16:32
going to take the x value of
1 and combine it with the y
00:16:35
value of the other one.
00:16:37
So this is going to be 0.2--
my mutated value and 0.2--
00:16:42
and this is going
to be 0.6 and 0.7.
00:16:46
So that's how my little
genetic algorithm
00:16:48
heck is going to work.
00:16:51
So having coded this up, we
can now see how it flows.
00:16:56
00:17:01
Let's run it 10 generations.
00:17:04
So the population is rapidly
expanded to some fixed limit.
00:17:07
I forgot what it is--
00:17:08
30 or so.
00:17:10
And we can run that
100 generations.
00:17:15
And so this seems to be
getting stuck, kind of, right?
00:17:18
So what's the problem?
00:17:20
The problem is local maxima.
00:17:21
This is fundamentally a
hill climbing mechanism.
00:17:30
Note that I have not included
any crossover so far.
00:17:33
00:17:36
So if I do have
crossover, then if I've
00:17:38
got a good x value
and a good y value,
00:17:41
I can cross them
over and get them
00:17:44
both in the same situation.
00:17:48
But nevertheless,
this thing doesn't
00:17:49
seem to be working very well.
00:17:51
STUDENT: Professor,
I have a question.
00:17:53
PATRICK WINSTON: Yeah.
00:17:54
STUDENT: That picture is
just the contour lines
00:17:56
of that function.
00:17:56
PATRICK WINSTON: The contour
lines of that function.
00:17:58
So the reason you see
a lot of contour lines
00:18:00
in the upper right
is because it gets
00:18:01
much higher because there's that
exponential term that increases
00:18:04
as you go up to the right.
00:18:06
So I don't know, it looks--
let's put some crossover in
00:18:11
and repeat the experience.
00:18:12
00:18:15
We'll run 100 generations.
00:18:24
I don't know.
00:18:24
It just doesn't seem
to be going anywhere.
00:18:27
Sometimes, it'll go right
to the global maximum.
00:18:31
Sometimes it takes a long time.
00:18:33
It's got a random number
generator in there,
00:18:34
so I have no control over it.
00:18:37
So it's going to get there.
00:18:39
I couldn't tell
whether the crossover
00:18:41
was doing any good or not.
00:18:43
Oh, well, here's one.
00:18:47
Let's make this a little
bit more complicated.
00:18:49
Suppose that's the space.
00:18:51
00:19:02
Now it's going to
be in real trouble,
00:19:04
because it'll never
get across that moat.
00:19:06
00:19:09
You know, you would think
that it would climb up
00:19:13
to the x maximum or
to the y maximum,
00:19:16
but it's not going
to do very well.
00:19:19
Even with crossover,
it's just not
00:19:21
going to do very
well, because it's
00:19:22
climbing up those local hills.
00:19:24
Anybody got an idea
about one simple thing
00:19:26
we could do to make
it work better?
00:19:30
Yeah, you could increase
step size, right?
00:19:34
Let me you see if
that will help.
00:19:36
00:19:49
You know, even that
doesn't seem to help.
00:19:51
So we have to conclude--
do we conclude
00:19:54
that this is a bad idea?
00:19:55
Well, we don't have to
conclude it's a bad idea yet,
00:19:58
because we may just look at
it and ask why five times.
00:20:04
And we might ask,
well, maybe we can
00:20:07
get a better mechanism in
there to translate fitness
00:20:10
into probability of survival.
00:20:11
00:20:14
Using this formula is
kind of strange, anyway,
00:20:17
because suppose temperature
is one of your fitness
00:20:20
characteristics.
00:20:20
The hotter, the better.
00:20:22
Then the ratio of
the probability
00:20:24
that you'll survive
versus the person
00:20:27
next to you, that
ratio will depend on
00:20:30
whether you're measuring
the temperature in Celsius
00:20:32
or Fahrenheit, right?
00:20:35
Because you've
shifted the origin
00:20:37
that shifts the
ratio that shifts
00:20:39
the probability of success.
00:20:41
So it seems kind of strange to
just take these things right
00:20:44
straight into probabilities.
00:20:46
So a better idea--
idea number two--
00:20:49
is to say, well,
shoot, maybe we don't
00:20:51
care about what the
actual fitnesses are.
00:20:55
All we really care
about is the rank order
00:20:58
of all the candidates.
00:21:00
So the candidate
with the most fitness
00:21:02
will have the most
probability of getting
00:21:04
into the next generation.
00:21:05
The candidate with the
second most fitness
00:21:07
will have the second highest
probability, and so on.
00:21:11
But we're not going to use the
actual fitnesses themselves
00:21:14
to make the determination.
00:21:16
Instead, what we're going to
do with this mechanism number
00:21:18
two-- this is the
rank space method--
00:21:20
00:21:28
is this.
00:21:29
We're going to say that the
probability of the highest
00:21:32
ranking individual of getting
into the next generation
00:21:35
is some constant P sub c, which,
of course, you can select.
00:21:39
You have another choice.
00:21:42
Then, if that guy
doesn't get selected,
00:21:45
the probability of the second
highest ranking individual
00:21:48
getting in the
next generation is
00:21:49
going to be the probability that
that guy didn't get in there.
00:21:53
That's 1 minus P sub c times
the same probability constant.
00:21:59
And so you can see
how this is going.
00:22:02
P3 will be equal to 1 minus P
sub c squared terms P sub c.
00:22:10
P sub n minus 1
will be equal to 1
00:22:16
minus that probability constant
to the n minus-- n minus 2
00:22:24
times P sub c.
00:22:27
And then there's only
one individual left.
00:22:30
And then if you got
through all these guys
00:22:32
and haven't got
anybody selected,
00:22:33
then you've got to
select the last guy.
00:22:37
And so the probability you're
going to select the last guy
00:22:40
is going to be 1 minus P
sub c to the n minus 1.
00:22:47
So it's a probability
you've missed all those guys
00:22:50
in the first n minus 1 choices.
00:22:53
Yeah, it is, honest to God.
00:22:55
See, this is the probability
that this last guys
00:22:58
is going to get selected.
00:22:59
It's not the
probability that it's
00:23:01
the last guy getting selected,
given that the others haven't
00:23:05
been select.
00:23:05
Trust me, it's right.
00:23:08
Are you thinking
it ought to be 1?
00:23:09
STUDENT: What?
00:23:10
PATRICK WINSTON: Were you
thinking it ought to be 1?
00:23:13
STUDENT: No, I was thinking that
I was wondering why you were re
00:23:17
rolling the dice, so to speak.
00:23:19
PATRICK WINSTON: You
are re rolling the dice.
00:23:20
You've got a
probability each time,
00:23:22
except for the last time, when,
of course, you have to take it.
00:23:24
There's nothing left.
00:23:25
There's no other choice.
00:23:26
STUDENT: I have a question.
00:23:27
PATRICK WINSTON:
Yeah, [? Lunnare ?]..
00:23:28
STUDENT: So when you jump
from P sub 1 to P sub 2,
00:23:32
that makes sense.
00:23:33
P sub 2 to P sub 3 you're
saying that the probability
00:23:35
PATRICK WINSTON:
It's the probability
00:23:36
depends on the
first two choices.
00:23:38
STUDENT: Yeah, but
the second choice
00:23:39
had probability one minus P
sub c times P sub c, not--
00:23:41
PATRICK WINSTON: Think
about it this way.
00:23:43
It's the probability you
didn't choose the first two.
00:23:46
So the probability you
didn't choose the first one
00:23:48
is one minus P sub c.
00:23:49
The probability you didn't
choose the next one, as well,
00:23:51
because you're choosing that
next one with probability P sub
00:23:53
c, it's the square of it.
00:23:56
00:23:59
So that might work better.
00:24:00
Let's give it a shot.
00:24:03
Let's go back to our
original space choice,
00:24:08
and we set and switch to
the rank fitness method.
00:24:14
And we'll run out
100 generations.
00:24:19
Whoa!
00:24:21
What happened there?
00:24:22
That was pretty fast.
00:24:23
Maybe I used a big step size.
00:24:24
00:24:28
Yeah, that's a little
bit more reasonable.
00:24:30
Oops-- what happened?
00:24:33
It's really getting
stuck on a local maximum.
00:24:34
00:24:39
So evidently, I've choosed
a constant P sub c such
00:24:43
that it just drove it
right up the nearest hill.
00:24:48
On the other hand, if I change
the step size a little bit,
00:24:50
maybe I can get
it to spread out.
00:24:53
I sure did.
00:24:55
And now that it's
managed to evolve over
00:24:57
there to find the
maximum value, now I
00:25:00
can clamp down on
the step size again.
00:25:05
And now it shows
no more diversity.
00:25:06
It's just locked on to
that global maximum.
00:25:10
So this is not unlike what
evolution sometimes does.
00:25:13
00:25:16
Sometimes, species
collapse into a state
00:25:19
where they don't change for 500
million or 600 million years,
00:25:22
like sharks, for example.
00:25:24
00:25:28
Sometimes, they only
survive if they've
00:25:29
got a lot of diversity
built into their way of life
00:25:33
so that they can adjust
to habitat changes.
00:25:37
Now, when you increase
the step size,
00:25:39
because you're stuck
on a local maximum,
00:25:42
it's like heating up a metal.
00:25:44
You make everything
kind of vibrate
00:25:46
more, make bigger steps.
00:25:49
So this kind of process, where
you may start with a big step
00:25:53
size and then gradually
reduce the step size,
00:25:56
is called simulated
annealing, because it's
00:25:59
like letting a metal cool down.
00:26:02
So you start off with a
big temperature-- big step
00:26:04
size-- that covers the space.
00:26:06
And then you slowly
reduce the step size,
00:26:09
so you actually crawl
up to the local maxima
00:26:14
that are available.
00:26:15
So that seemed to
work pretty well.
00:26:16
Let's see if we can get
it to work on the harder
00:26:19
problem of the moat.
00:26:21
00:26:32
So it's not doing very well.
00:26:34
Better increase the step size.
00:26:36
00:26:41
No, it's still kind of stuck.
00:26:42
00:26:45
Even though it's got the
capacity to cross over,
00:26:47
it's so stuck on that
lower right hand corner,
00:26:49
it can't get up that vertical
branch to get to a point
00:26:52
where a crossover will
produce a value up there
00:26:55
in the upper right-hand corner.
00:26:57
So we're still not home yet.
00:26:58
00:27:03
So what's the trouble?
00:27:05
The trouble is that the fitness
mechanism is just driving
00:27:10
things up to the local maximum.
00:27:14
It's just terribly unfortunate.
00:27:16
00:27:20
What to do?
00:27:21
Well, here's something
you could do.
00:27:23
You can say, well,
if the problem is
00:27:25
we've lost the diversity
in our population,
00:27:27
then we can measure
the diversity-- not
00:27:31
only the fitness of
the set of individuals
00:27:33
we're selecting from, but we
can measure how different they
00:27:37
are on the individuals
we've already selected
00:27:38
for the next population.
00:27:41
In other words, we can get a
diverse population as well as
00:27:44
a fit population if, when
we make our selection,
00:27:47
we consider not
only their fitness
00:27:49
but how different they are
from the individuals that
00:27:52
have already been selected.
00:27:54
So that's going to be
mechanism number three.
00:27:56
00:28:07
So now we have a space,
and we can measure fitness
00:28:13
along one axis-- ordinary
fitness-- and this is
00:28:18
rank space fitness, so
that's going to be P sub c.
00:28:21
There will always
be some individual
00:28:24
with the highest fitness.
00:28:25
00:28:31
And over here-- that might
not be P sub c, actually.
00:28:35
But there'll be some individual
with a maximal fitness,
00:28:38
and at any given
step in the selection
00:28:40
of the next population, there'll
be some individual that's
00:28:44
maximally diverse from all
of the individuals that
00:28:49
have been selected for the
next generation so far.
00:28:55
So what kind of
individual would you
00:28:56
like to pick for
the next generation?
00:29:00
Well, the one with
the highest fitness
00:29:02
rank and the one with the
highest diversity rank.
00:29:07
So what you'd really
like is you'd like
00:29:10
to have somebody right there.
00:29:14
And if you can't have
somebody right there,
00:29:16
if there's nobody right
there with a maximum fitness,
00:29:19
a maximum diversity
at the same time, then
00:29:23
maybe you can draw in
iso goodness lines,
00:29:26
like so, which are just how
far you are from that ideal.
00:29:32
So let's summarize.
00:29:34
You've got to pick
some individuals
00:29:35
for the next population.
00:29:37
When we pick the
first individual,
00:29:39
all we've got to
go on is how fit
00:29:42
the individual is,
because there's nobody
00:29:43
else in that next generation.
00:29:45
After the first
individual is selected,
00:29:48
then we can look at
our set of candidates,
00:29:51
and we can say which
candidate would
00:29:53
be more different from the
set of things we've already
00:29:55
selected than all the others.
00:29:56
That would get the highest
diversity rank and so on down
00:30:00
the candidate list.
00:30:02
So let's see how
that might work.
00:30:03
00:30:11
So we're going to use a
combination of fitness
00:30:14
rank and diversity rank.
00:30:18
And we'll just use
the simple one so far.
00:30:21
We'll use a small
step size, and we'll
00:30:24
let this run 100 generations
to see what happens.
00:30:26
00:30:31
Bingo.
00:30:32
It crawls right up there,
because it's trying
00:30:34
to keep itself spread out.
00:30:36
It uses that diversity
measurement to do that.
00:30:39
And at the same time,
it's seeking high fitness,
00:30:43
so that's why it's crawling up
to the upper right hand corner.
00:30:46
But in the end, that
diversity piece of it
00:30:49
is keeping the
things spread out.
00:30:52
So suppose you're a
shark or something.
00:30:53
You don't care about
diversity anymore,
00:30:55
And we could just turn that off.
00:30:57
Is that thing still running?
00:30:58
00:31:03
Go back to fitness rank-- bingo.
00:31:06
So there you are-- you're
stuck for 600 million years.
00:31:11
So let's see if this will
handle the moat problem.
00:31:14
00:31:24
See, our step size
is still small.
00:31:27
We'll just let this run.
00:31:31
So the diversity of P sub
is keeping it spread out,
00:31:34
pretty soon, bingo,
it's right in there.
00:31:36
It's across that big moat,
because it's got the crossover
00:31:39
mechanism that combines the
best of the x's and the best
00:31:41
of the y's.
00:31:43
So that seems to
work pretty well.
00:31:47
OK, so see, these are
some of the things
00:31:50
that you can think about
when you're thinking-- oh,
00:31:52
and of course,
we're a shark, we're
00:31:55
going to forget about diversity.
00:31:56
We'll change the
selection method
00:31:58
from fitness and diversity
rank to just diversity.
00:32:01
It collapses down on
to the highest hill.
00:32:04
00:32:07
Yeah, [? Feedball ?], what?
00:32:09
STUDENT: How does step size
translate into mutations?
00:32:12
PATRICK WINSTON: Oh,
just the-- question
00:32:15
is, how does step size
translate into mutation?
00:32:19
Instead of allowing myself
to take steps as big as 1/10,
00:32:22
I might allow myself to
take steps as big as 3/10,
00:32:27
according to some distribution.
00:32:29
00:32:32
So what to say about all this?
00:32:33
00:32:36
It's very seductive,
because it's nature, right?
00:32:40
The trouble is,
it's naive nature.
00:32:42
And as evolutionary theories
go, this is horrible.
00:32:49
This is naive.
00:32:51
So we'd like to use real
evolutionary theory,
00:32:52
except we don't have
real evolutionary theory.
00:32:55
Evolution is still a mystery.
00:32:57
Some things are pretty obvious.
00:33:00
You can breed fast race horses.
00:33:02
That works just like so.
00:33:04
The trouble is, we don't have
any real good idea about how
00:33:07
speciation takes place
and how a lot of evolution
00:33:11
works, because all these
chromosomes are connected
00:33:14
to their phenotype consequences
in very complicated ways
00:33:18
that nobody fully understands.
00:33:21
So there's a great deal
of magic in that genotype
00:33:23
to phenotype transition
that nobody really
00:33:26
understands very well.
00:33:28
So when people write
these programs that
00:33:32
are in the style of so
called genetic algorithm,
00:33:38
they're taking a photograph
of high school biology,
00:33:43
and they're spending a
long time building programs
00:33:46
based on that naive idea.
00:33:48
But that naive idea has lots
of places for intervention,
00:33:54
because look at all the
things you can screw around
00:33:57
with in that process of
going from one generation
00:34:01
to the next.
00:34:02
00:34:04
By the way, what
does mutation do?
00:34:07
It's basically hill
climbing, right?
00:34:09
It's producing a
little spread out,
00:34:10
and you're using the fitness
thing to climb the hill.
00:34:14
So you get a lot of choices
about how you handle that.
00:34:16
Then you get a lot of
choices about much crossover
00:34:17
you're doing.
00:34:18
What does crossover do?
00:34:20
It kind of combines
strong features
00:34:24
of multiple individuals
into one individual, maybe.
00:34:27
00:34:30
So you've got all
kinds of choices there.
00:34:32
And then your genotype to
phenotype translation--
00:34:34
how do you interpret
something like those zeroes
00:34:36
and ones as an if then rule,
for example, as something that's
00:34:40
in the hands of the designer?
00:34:42
Then you've got all the rest
of those things, all which
00:34:46
are left up to the designer.
00:34:48
So in the end, you
really have to ask--
00:34:50
when you see an impressive
demonstration, you have to say,
00:34:53
where does the credit lie?
00:34:55
And I mean that
pun intentionally,
00:34:57
because usually the people
who are claiming the credit
00:35:00
are lying about where
it's coming from.
00:35:03
But nevertheless,
let me give you
00:35:04
a couple of examples
of where this
00:35:06
has found actual, bona
fide practical application.
00:35:13
So when you look for
practical application,
00:35:15
you might say, well,
in what kind of problem
00:35:18
does a good front piece
combine with a good back piece
00:35:22
to produce a good thing overall?
00:35:25
And the answer is, when
you're making a plan.
00:35:28
So you might have a
problem in planning
00:35:31
that requires you to
take a series of steps.
00:35:35
00:35:39
And you might have two
plans, each of which
00:35:43
is a series of steps.
00:35:45
And you might combine these to
produce something new that's
00:35:51
the front half of one and
the back half of another.
00:35:56
So that's practical
application number one.
00:35:58
00:36:01
And that requires you to
interpret your chromosome
00:36:04
as an indicator of
the steps in the plan.
00:36:09
Another example is drawn
from a UROP project
00:36:16
a student did for
me some years ago.
00:36:18
00:36:20
He was a freshman.
00:36:21
He came to me and said, I
want to do a UROP project.
00:36:24
And I said, have
you taken 6.034?
00:36:26
And he said no.
00:36:27
And I said, go away.
00:36:28
And he said, I don't
want to go away.
00:36:29
I want to do a UROP project.
00:36:31
So I said, have
you read my book?
00:36:34
He said no.
00:36:34
I said, well, go away, then.
00:36:35
And he said, I don't
want to go away.
00:36:37
I want to do a UROP project.
00:36:39
So I said, I don't
have any UROP projects.
00:36:40
He said, that's OK.
00:36:41
I've got my own.
00:36:42
00:36:46
He's a finance
type guy, so he was
00:36:49
interested in whether he
could build a rule based
00:36:52
expert system that could predict
the winners at horse races.
00:36:57
So his rule based expert system
consisted of rules like this.
00:37:04
If x and y, then
some conclusion.
00:37:11
If l and m, then some
kind of conclusion.
00:37:19
And from these, he
would produce rules
00:37:23
like if x prime-- that's
a slightly mutated version
00:37:27
of the x antecedent-- and
m, then some conclusion.
00:37:38
So it's mutation and crossover.
00:37:39
And he was able to
produce a system that
00:37:42
seemed to work about as
well as the handicappers
00:37:45
in the newspaper.
00:37:46
So he started losing
money at a less fast rate.
00:37:51
He is now doing something in
the stock market, they say.
00:37:55
Doesn't talk so much
about it, though.
00:37:59
But an interesting application.
00:38:01
He came up with rules
like, if the sum
00:38:03
of the jockey's weight on
the post position is low,
00:38:08
that's good.
00:38:09
Well, that makes
sense in the end,
00:38:11
because the jockey's
weight is always
00:38:12
between 100 and 110 pounds,
and the post position is always
00:38:16
between 1 and 10 or
something, so they
00:38:17
were commensurate values.
00:38:20
And a low one is good, in fact.
00:38:21
Not bad.
00:38:24
But neither of those--
00:38:26
I mean, this is real stuff.
00:38:28
My company uses this sort of
stuff to do some planning work.
00:38:33
But neither of those is as
impressive as the demonstration
00:38:38
I'm about to show
you that involves
00:38:41
the evolution of creatures.
00:38:44
And these creatures consist of
block like objects, like so.
00:38:50
And they combine
like this, and so on.
00:38:54
And so how can
you make a feature
00:38:56
like that from a 0 1 chromosome?
00:38:59
Well, some of the
bits in the chromosome
00:39:02
are interpreted as
the number of objects.
00:39:05
Others are interpreted as
the sizes of the objects.
00:39:08
Others are interpreted
as the structure of how
00:39:11
the objects are articulated.
00:39:14
And still others are interpreted
as fixing the control algorithm
00:39:19
by which the creature operates.
00:39:23
So you see how
that roughly goes?
00:39:26
Would you like to see a
film of that in action?
00:39:29
Yes.
00:39:29
OK.
00:39:30
[? Solo ?] always
likes to see the films.
00:39:32
00:39:42
STUDENT: How would you measure
diversity in that graph?
00:39:46
PATRICK WINSTON:
The question is,
00:39:47
how do I measure the
diversity of the graph?
00:39:50
I did it the same way
I measured the fitness.
00:39:52
That is to say, I
calculated the distance--
00:39:56
the actual metric distance--
of all the candidates
00:39:59
for the next generation from
all of the candidates that
00:40:02
had already been selected.
00:40:03
I summed that up.
00:40:05
And from that sum,
I could rank them
00:40:07
according to how
different they were
00:40:08
from the individuals that were
already in the next generation.
00:40:11
It's like giving a rank,
and then from the rank,
00:40:13
I use that kind of calculation
to determine a fitness, ie,
00:40:18
a probability of
survival, and then
00:40:19
I just combine the two
kinds of probabilities.
00:40:21
STUDENT: So you always
kept-- every time
00:40:23
that you selected
something, you cached those.
00:40:25
And you kept everything
that you've ever
00:40:27
selected [INAUDIBLE].
00:40:28
PATRICK WINSTON: I'm always
using the individuals that
00:40:30
have already been
selected at every step,
00:40:32
so every step is
a little different
00:40:33
because it's working with
a new set of individuals
00:40:35
that have already been selected
for the next generation.
00:40:37
OK?
00:40:38
So let's see how this works.
00:40:40
00:40:49
So this is showing the evolution
of some swimming creatures.
00:40:53
And they're evolved according
to how well they can swim,
00:40:55
how fast they can go.
00:40:57
Some of them have quite exotic
mechanisms, and some of them
00:41:00
quite natural.
00:41:01
That looked like a sperm
cell floating away there.
00:41:04
00:41:09
Once you have these things
evolving, then of course,
00:41:11
you can get groups of
them to evolve together.
00:41:13
00:41:19
So you saw already some
that were evolving to swim.
00:41:24
These are evolving to
move around on the land.
00:41:28
It's interesting-- this was done
by Karl Sims, who at the time
00:41:32
was at a then thriving
company, Thinking Machines,
00:41:35
a fresh spinoff from MIT.
00:41:37
So he was using a vastly
parallel computer,
00:41:40
super powerful for its day,
thousands of processors,
00:41:43
to do this.
00:41:44
And it was a demonstration
of what you could
00:41:46
do with lots of computing.
00:41:48
In the early stages of
the experimentation,
00:41:51
though, its notion of physics
wasn't quite complete,
00:41:54
so some of the creatures evolved
to move by hitting themselves
00:41:57
in the chest and not knowing
about the conservation
00:42:01
of momentum.
00:42:03
I thought that was just great.
00:42:04
00:42:09
So here they are, out
doing some further--
00:42:10
00:42:27
So you look at these,
and you say, wow,
00:42:29
there must be something to this.
00:42:30
This is interesting.
00:42:32
These are complicated.
00:42:33
00:42:40
I think this is one of the ones
that was trained, initially,
00:42:43
to swim and then to
do land locomotion.
00:42:45
00:42:50
So eventually, Karl
got around to thinking
00:42:54
about how to make these
things evolve so that they
00:42:58
would compete for food.
00:42:59
00:43:02
That's the fastest,
I think, by the way,
00:43:05
of the land locomotors.
00:43:08
So that was training them
to-- evolving them to jump.
00:43:11
This is evolving them to
follow a little red dot.
00:43:17
Some of them have stumbled
upon quite exotic methods,
00:43:21
as you can see.
00:43:23
00:43:26
Seem to be flailing
around, but somehow
00:43:29
manage to-- sort of like
watching people take a quiz.
00:43:32
00:43:36
Making progress on it.
00:43:37
00:43:42
But now we're on to
the food competition.
00:43:44
00:44:05
So some of them go for
the food, and some of them
00:44:07
go to excluding their
opponent from the food,
00:44:10
not actually caring too much
about whether they get it.
00:44:13
That's sort of what children do.
00:44:15
00:44:32
There's a kind of
hockey player-- now,
00:44:35
here's two hockey players.
00:44:36
Watch this.
00:44:37
They're kind of-- one
succeeds-- it reminds me
00:44:46
a little bit of hockey,
rugby, something like that.
00:44:49
Sometimes, they just
get kind of confused,
00:44:53
go right after their opponent,
forgetting about the food.
00:44:55
00:45:11
Gives up.
00:45:15
I think these are the overall
winners in this elimination
00:45:20
contest.
00:45:21
I can't quite get there.
00:45:24
OK, so you look at that, and
you say, wow, that's cool.
00:45:26
Genetic algorithms
must be the way to go.
00:45:30
I remember the first
time I saw this film.
00:45:32
It was over in Kresge.
00:45:33
I was walking out of the
auditorium with Toma Poggio
00:45:37
And we looked at each other,
and we said the same thing
00:45:41
simultaneously.
00:45:44
We didn't say that genetic
algorithms were the way to go.
00:45:47
What we said was, wow, that
space is rich in solutions.
00:45:52
What we were amazed
by was not that simple
00:45:54
minded genetic algorithms
produced solutions
00:45:56
but that the space was
so rich with solutions
00:45:59
that almost any mechanism
that was looking around
00:46:02
in that space would find them.
00:46:03
But there's yet another
way of thinking about it,
00:46:05
and that is you could say, wow,
look at how smart Karl Sims is,
00:46:10
because Karl Sims is the
one who had his hands on all
00:46:12
the levers, all those choices.
00:46:15
And I kept emphasizing,
all those choices
00:46:17
that enabled him to trick
this thing, in some sense,
00:46:21
into stumbling across the
solutions in a space that
00:46:24
was guaranteed to be
rich with solutions.
00:46:27
So you have to ask-- so first
of all, diversity is good.
00:46:31
We noticed when we put diversity
into the genetic algorithm
00:46:34
calculations, we were much
better at finding solutions.
00:46:36
But the next gold star
idea that I'd really
00:46:39
like to have you go
away with is the idea
00:46:41
that you have to ask
where the credit lies.
00:46:43
Does it lie with the
ingenuity of the programmer
00:46:46
or with the value of
the algorithm itself?
00:46:49
In this case,
impressive as it is,
00:46:51
the credit lies in the
richness of the space
00:46:53
and in the intelligence
of the programmer,
00:46:55
not necessarily in the
idea of genetic algorithms.
00:47:00