13. Learning: Genetic Algorithms

00:47:16
https://www.youtube.com/watch?v=kHyNqSnzP8Y

Ringkasan

TLDRIn his engaging lecture, Patrick Winston humorously addresses the MIT community by declaring an early Halloween celebration due to an inconvenient scheduling on a Sunday. He then delves into the realm of genetic algorithms, a computational approach that draws inspiration from biological evolution. Winston explains these algorithms by paralleling them with the processes of cell division and sexual reproduction, highlighting the similarities with genetic operations such as mutation and crossover. These algorithms start with a population of chromosomes, undergo mutations (flipping binary values), and crossover events to simulate reproduction. Using various illustrations, including contour maps representing solution spaces, Winston discusses potential pitfalls like local maxima and the necessity for maintaining diversity in populations to prevent stagnation. By comparing genetic algorithms' randomness and the programmer's strategic choices, he explores how different approaches impact the success and evolution of solutions. He also shares demonstrations, such as generating creatures capable of movement, to illustrate genetic algorithms’ power to navigate rich solution spaces. Ultimately, Winston emphasizes the complexity, choice-laden nature of genetic algorithms and the significant role of programmer ingenuity in harnessing these computational techniques effectively. By addressing factors such as diversity, solution space richness, and operator proficiency, he underscores key concepts that contribute to the successful application of genetic algorithms in problem-solving.

Takeaways

  • πŸŽƒ Patrick Winston humorously moves Halloween for 6.034 class convenience.
  • πŸ“Š Genetic algorithms mimic evolutionary processes to optimize solutions.
  • πŸ”„ Chromosomes undergo mutation and crossover to simulate evolution.
  • ✨ Diversity is crucial in preventing algorithm stagnation and finding better solutions.
  • πŸ” Genetic algorithms explore spaces rich with potential solutions.
  • πŸ”§ Programmer choices significantly impact genetic algorithms' effectiveness.
  • πŸ“ˆ Fitness values determine survival probability in genetic algorithms.
  • πŸ† Successful algorithms rely on space richness and clever programming.
  • 🧬 Mutation and crossover roles are pivotal in genetic algorithm processes.
  • 🌐 Demonstrations show genetic algorithms generating effective solutions.

Garis waktu

  • 00:00:00 - 00:05:00

    Patrick Winston begins by humorously noting the inconvenience of Halloween falling on a Sunday, declaring it celebrated as part of 6.034 on a different day. He distributes chocolate, humorously likening it to a 'legal drug' that enhances performance, and transitions into the lecture topic, genetic algorithms. This session won't appear in the next quiz but will feature in the final exam.

  • 00:05:00 - 00:10:00

    Winston explains the process of mitosis and the complexity of reproduction. He uses an analogy to illustrate how chromosomes get mixed up during reproduction. The lecture highlights genetic algorithms as attempts to mimic evolution, emphasizing the randomness and choices present in genetic processes. The randomness offers opportunities for intervention in genetic algorithm design.

  • 00:10:00 - 00:15:00

    Explaining genetic algorithms further, Winston illustrates with chromosome analogies, using binary representations. Mutation in chromosomes is shown as an analogy to natural errors during genetic processes, with crossover creating new combinations, mimicking biological reproduction. The focus now is on building a system using a population of chromosomes subject to mutation and crossover.

  • 00:15:00 - 00:20:00

    The genotype-phenotype transition is discussed, with emphasis on how genotype determines phenotype and fitness. Chromosomes are evaluated for fitness, assigned fitness scores that translate into survival probabilities for future generations. This introduces choices in algorithm design, emphasizing the need for a method to determine probability of survival based on fitness.

  • 00:20:00 - 00:25:00

    Winston illustrates the fitness-based selection by modeling it with contour plots representing fitness landscapes. The challenge of local maxima in fitness landscapes is addressed, highlighting that genetic algorithms are essentially hill-climbing algorithms. Different strategies like mutation and crossover are mentioned, but local maxima remain problematic.

  • 00:25:00 - 00:30:00

    A strategy is introduced to cope with local maxima by using rank-based selection instead of fitness values directly, stabilizing selection based on relative fitness ranks. This method ranks individuals' probability to carry over into the next generation based on their rank in fitness, detaching results from the absolute values and focusing on relative performance.

  • 00:30:00 - 00:35:00

    Winston employs a rank-fitness method in a genetic algorithm simulation to demonstrate overcoming local maxima issues. He discusses using a combination of diversity and fitness to maintain varied and adaptable populations, helping to avoid getting stuck at local optima through mechanisms like increased step size and simulated annealing.

  • 00:35:00 - 00:40:00

    In overcoming local optima, the integration of diversity consideration in selection is emphasized. By measuring diversity as well as fitness, a balanced selection process is maintained, ensuring variability within the population while still striving for optimal solutions. Through examples, it's shown that this approach allows genetic algorithms to solve complex problems more effectively.

  • 00:40:00 - 00:47:16

    Using practical examples, Winston concludes by discussing when genetic algorithms can be useful. In contexts where good features combine effectively, like planning or heuristic development, and leveraging programmer ingenuity in guiding algorithms allows for practical application. Karl Sims' work is referenced to illustrate solutions arising not only from algorithm strength but also from the richness of explored spaces.

Tampilkan lebih banyak

Peta Pikiran

Video Tanya Jawab

  • Why was there an early Halloween celebration in Patrick Winston's class?

    Halloween is on Sunday, but Patrick Winston's class will celebrate it early.

  • What is the main topic of Patrick Winston's lecture?

    Patrick Winston discusses genetic algorithms, which mimic biological evolution to find solutions.

  • How does Patrick Winston explain genetic algorithms?

    He uses chromosomes and their combinations to illustrate the process.

  • What roles do crossover and mutation play in genetic algorithms?

    Crossover combines strong features from different parents, while mutation introduces variations.

  • Why is diversity important in genetic algorithms?

    Diversity helps maintain a varied population, increasing the chances of finding better solutions.

  • How effective are genetic algorithms according to the lecture?

    They produce solutions by exploring spaces that are rich with possibilities, enabled through programmer choices.

  • What choices impact the success of genetic algorithms?

    Numerous choices affect genetic algorithms: mutation rates, crossover frequency, and how fitness translates to survival.

  • What factors contribute to a genetic algorithm's success?

    Rich solution spaces and programmer ingenuity are crucial.

  • Why did Patrick Winston mention choosing fitness probabilities as an 'easy' process?

    It is a humorous example emphasizing abundant choices in algorithm design.

  • What demonstration did Patrick Winston use to illustrate genetic algorithms in action?

    He used an example of evolving creatures in a rich solution space to show genetic algorithms' capabilities.

Lihat lebih banyak ringkasan video

Dapatkan akses instan ke ringkasan video YouTube gratis yang didukung oleh AI!
Teks
en
Gulir Otomatis:
  • 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
Tags
  • genetic algorithms
  • Patrick Winston
  • biological evolution
  • chromosomes
  • genotype
  • phenotype
  • mutation
  • crossover
  • fitness
  • solution spaces