So let's do a concrete example of crossover. And so, it turns out that
the crossover operation is always going to
depend critically on how you represent the
input space. So, let's say concretely that our input space is, is eight bit
strings. So here's two parents, 01101100 and
11010111. And we're going to introduce them to
each other. All right, now they know each other.
>> Mm-hm.
>> And now we're going to use them
to create a new individual, a new offspring.
>> So they're really going to know each other.
>> All right. Now we've put these two bit sequences together and
we've lined up so that the bits correspond in each of the
different positions and now we can ask. How can we use this?
To generate a new individual that uses elements of the two individuals that
we have. So if you can think of any ways to do that.
>> I have some ideas. [LAUGH]
>> Yeah okay, what you got?
>> I have lots of ways but I don't think any
of them can be reproduced for the purposes of this learning lesson.
>> All right well so let's, let's do ones
that really kind of stick to the bit patterns.
>> [LAUGH] I swear there's no way you can
say this without getting in trouble Michael. All right.
>> But that's okay. So how about, here's an obvious one. Right,
if we really push the genetic notion as far as we can then
each of those things represent, I don't
know, alleles or some other biological term. And
so what happens in genetics, right, is
you mix and match your chromosones and alleles
together. So why don't I say one child is The first four bits of this
handsome Charles fellow and the last four
bits of this beautiful and wonderful Sheila person.
>> Alright, I see what you're
doing there. So what you're saying is we're going to pick, well
maybe this isn't quite what you said but I'm going to imagine
what you said we're going to pick a random number along the
sequence at the half-way point. And what we're going to do is
now mix and match and create two offspring. One uses the first
half of Charles and the second half of Sheila and then the
other one is the other way around. And as you can see
it's this last bit that determines the sex. Anyway, so these are the
two offspring that these individuals have generated. And this
particular way of, of combining where you randomly choose a
position and then flip flop, is called one point crossover.
Alright, so now I want you to think about this
for a second Charles. So I don't know if it's
an inductive bias, but what kind of bias do we
put in? When we say well we're going to choose one
of these points and we're going to flip flop based
on where that point is chosen.
>> What is that, what is that going to,
what kind of offspring is that going to generate?
>> Huh. Also, you know what, I see 2, I
see 2 kind of assumptions built there. So, maybe that
an inductive bias, so. Or a bias of some sort.
So, one assumption is that locality of the bits matter. Good.
>> Right. So the first by picking halfway through, you are saying,
the first four bits are somehow related and the lsat four bits
are somehow related because otherwise they wouldn't make any
sense. Now to talk about them being together and that
brings it to my second point which I guess really
is just a first point. Which is that it assumes
that there are subparts of the space that can be
kind of independently optimized that you can then put together.
Right, and in particular when I say sub spaces to
optimize, I mean that they're independent part of the subspace,
so that's actually the example that you gave before
you said Well there's these two dimensions and each
dimension kind of matters independently and the total reward
or the total, the total fitness is some kind
of linear combination of them. And so I can
put them, cause if those two things aren't true
than really doing crossover like this won't help you
at all. You're just kind of randomly. Mixing things together.
>> It's kind of an assumption about the way space works, in that,
kind of like the example we did when we were doing bit guessing.
That that you can be heading in a good direction, that they're pieces
that are right and if we reuse those pieces we can get even righter.
>> Sure.
>> Alright so, and if it is the case that
the sequence of the ordering of bits matters, we have this
locality property. This is actually a fairly sensible thing to
do. But can you imagine any other way of combing these
bits together to get to get offspring?
>> Well, I can think of lots.
>> Well, so let's, let's focus, you
know, you have many different possible ideas, but
let's focus on ideas where we still
have this subspace to optimize property. But we
don't really have a locality of bits
property. We don't really, the ordering doesn't matter
anymore. So keeping them clumped together like that.
We don't think that that's a useful thing.
>> Okay. Well, what would that mean? Tell me what that means.
>> Well, so,
The one point crossover, when we talked about that. It really
matters that you know, the two bits that are next to each
other are very likely to stay connected, right? That is, it's, it's
unlikely that the split will happen to happen exactly between them and
so we'll tend to travel as a group. But, if we
don't think it's important that the bits that are next to each
other need to travel together. If we say that It should be
equally likely for any of the bits to kind of remain together.
We need to cross over a lot more than just that one time.
In a sense we might need to cross over every time. Well so,
what I'm trying to get at here is this notion that what we
could do is we could generate individuals
by just scrambling at each bit position.
>> Okay.
>> So. The first bit position, maybe
which stays the same, the second one flips,
the third one stays the same, the fourth
one stays the same, the fifth one flips,
the sixth one stays the same, the seventh one
flips, and the eighth one stays the same. So now,
we've got two individuals, and every bit from these individuals
comes from one of the parents and so that means
that if there is sub pieces that are current that
maybe preserved in the offspring but no longer does it
matter what the ordering is. We get exactly the same
distribution over offspring, no matter how we order the bits.
>> Okay.
>> So
this idea is sometimes called uniform crossover. And
essentially, we are just randomizing at each bit position.
This kind of crossover happens biologically at the level
of genes right so we, we imagine that we
get our genes from our parents but the, for
each different gene like the gene for eyes and
the gene for hair color are not particularly linked
to each other they're uniformly chosen at each position.