# 13. Learning: Genetic Algorithms

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=kHyNqSnzP8Y
**Transcript page:** https://www.withtranscript.ai/video/kHyNqSnzP8Y

## Chapters

- 0:16 — Chapter 1 (0:16)
- 1:16 — Chapter 2 (1:16)
- 4:16 — Chapter 3 (4:16)
- 8:29 — Chapter 4 (8:29)
- 11:51 — Chapter 5 (11:51)
- 16:22 — Chapter 6 (16:22)
- 17:28 — Chapter 7 (17:28)
- 19:02 — Chapter 8 (19:02)
- 21:28 — Chapter 9 (21:28)
- 24:28 — Chapter 10 (24:28)
- 26:32 — Chapter 11 (26:32)
- 27:20 — Chapter 12 (27:20)
- 30:11 — Chapter 13 (30:11)
- 31:24 — Chapter 14 (31:24)
- 35:39 — Chapter 15 (35:39)
- 39:43 — Chapter 16 (39:43)
- 41:09 — Chapter 17 (41:09)
- 42:27 — Chapter 18 (42:27)
- 43:36 — Chapter 19 (43:36)
- 44:30 — Chapter 20 (44:30)

## Transcript

**[0:16]:** I have extremely bad news. Halloween falls this year on a Sunday. But we in 6034 refuse to suffer the slings and arrows of outrageous fortune. So we've decided that Halloween is today as far as 6034 is concerned. Kenny, could you give me a hand, please?

**[0:43]:** You can take that put it over there.

**[0:49]:** Mhm, just give it to them.

**[0:54]:** You can take as much of this as you like. The rest will be given to that herd of stampeding freshmen that comes in after.

**[1:16]:** It's a cornucopia of legal drugs. Chocolate um does uh produce a kind of mild high and I recommend it uh before quizzes and giving lectures. It um I have a a friend of mine, one of the Nobel laureates in biology, always eats chocolate before he lectures to give him a little edge. Otherwise, it would be flat. So,

**[1:46]:** I recommend it.

**[1:54]:** It will take I suppose a little while to digest that neural net stuff. Oh, richer than usual in mathematics. So, but today we're going to talk about another effort at mimicking biology. This is a um This is easy stuff. It's just conceptual. And you won't see this on the next quiz, but you will see it on the final. It's one of those quiz five type problems where you ask you questions to see if you were here and awake. So, typical question might be Professor Professor Winston is a creationist. Or something like that. Not too hard to answer. In any event, um

**[2:38]:** if it's been hard to develop a real understanding of intelligence, occasionally the hope is that by mimicking biology or mimicking evolution, you can circumnavigate all the problems. And one of those kinds of efforts is a effort to um imitate evolution. So, we're going to talk today about so-called genetic algorithms, which are naive um attempts to mimic naive evolution. Now, I realize that um most MIT students have a basic grasp of sexual reproduction, but I found in talking with students that many times the details are a little fuzzy on some of the details. So, let's start off by uh reflecting a little bit on how that works. So, uh let's say we need um pink and blue. And here's our cell. And here's its nucleus. And here are mommy and daddy's chromosomes. We'll just pretend there's one pair. Now, ordinarily uh in ordinary uh cell division, you get two cells.

**[3:53]:** Both have a nucleus. And the process of producing them involves the duplication of those chromosomes. And then one pair ends up in each of the child cells. And that's all there is to that. That's mitosis.

**[4:16]:** But then uh when uh we talk about reproduction, it's a more complicated because the those uh chromosomes get all twisted up and they break and they recombine. So, when we talk about the cells that split off from one of these germ cells,

**[4:36]:** it's no longer appropriate to talk about the pink one and the blue one because the pink one and the blue one are all mixed up. So, you get two chromosomes here and two here. But through some miracle of nature, which has always amazed me, these two cells split in turn into four cells altogether.

**[5:05]:** And each of those four cells at the bottom gets one of the chromosomes that was produced by that twisting up of the rope and recombination. Then along comes um along comes a a special occasion. And uh now um you can think of this as being a blue one and this is being a pink one. And they come together. And you get a new person. Like so. Note that your mother and father's uh chromosomes are never never recombined. It's your grandparents' chromosomes that recombine. So, that's uh what it's like. And the main thing to note about this is, well, a couple things. If you happen to be a female, uh this part of the process, this part over here, took place before you were born. If you happen to be male, it's going on right now as we speak, which probably explains something. But anyway, it's going on right now.

**[6:10]:** But whenever it goes on, uh there are lots of opportunities for uh for throwing dice. So, God threw all the dice before you were born if you happen to be a female in this part of the process over here. Then of course more dice got thrown here where the decision was made about which particular cells got to um fuse to form a new individual. So, I want to beat on this idea of lots of choice. When we talk about genetic genetic algorithm, we talk about nature, there there are lots of choices in there and that means there are lots of choices to intervene. Uh to screw around. To make things work out the way you want. But anyway, there we are. That's the basic idea. And it all starts with chromosomes. So, we could think of implementing something that imitates that with the um A C T G stuff that you learned about all about 701.

**[7:07]:** But we're computer scientists, we don't like base four, we like base two. So, I'm going to just suggest that our chromosomes are binary in this system that we're going to build.

**[7:21]:** So, that might be a chromosome. It doesn't have to be binary, it can be it can be symbolic for all I care, but it's just some string of things that determine how the ultimate system behaves. So, it all starts out then with some of these chromosomes. Uh some of these uh simulated chromosomes, simulated, simplified,

**[7:51]:** and there's a population of of of chromosomes. A population of chromosomes that might be subject to a little bit of mutation. That is to say, a zero becomes a one or a one becomes a zero. That happens a lot. That mutation stuff happens over here when things get twisted up and recombine. There are copying errors and stuff. Cosmic rays hit it all the time. All sorts of reasons why there might be a single single point of change. That That produces the mutation effect. So, here we have a a population

**[8:29]:** that starts off over here. And it some of those things are subject to mutation.

**[8:38]:** And you'll note, here here's a whole bunch of choice already. How many of these mutations do you allow per chromosome? For example, uh how many of the chromosomes just slip through without any mutation. Those are choices you can make. Once you've made those choices, then we have the crossover phenomenon.

**[9:01]:** Let's identify one of these guys as the pink one and one of these guys as the blue one. And so now we have the pink one cruising along as well as the blue one. But the pink one and the blue one cross and produce a new chromosome. Just like in nature. So, we take the front part of one, back part of the other, and we fuse them together. And some may slip by without any of that. Like so. Well, these these things are meant to be combined in pairs like so, but they may not they may not have any crossover in them. So, another yet another set of choices. How many crossovers do you allow per recombination? Yet another set of choices. So, now we've got a population of um of modified chromosomes through mutation and crossover. So, the next thing to do is we have the genotype to phenotype transition.

**[10:00]:** That is to say the the chromosome determines the individual. It may be a person, it may be a cow, it may be a computer program. I don't care what. But that that code down there has to be interpreted to be a something. So, it is the genotype and it has to be interpreted to be something which is the phenotype. The thing that the that the that the stuff down there is encoding for. So, out here we have a bunch of individuals. Now, each of those individuals, because they have varying chromosomal composition, will have a different fitness.

**[10:42]:** So, these fitnesses might be uh who knows they might how they might be scored, but we're computer scientists, we might as well use numbers. So, maybe this guy's fitness is 88, this guy's fitness is 77, and so on. So, now that we've got fitness, uh by the way, notice all the choices involved there? Choice of how you interpret the the the genotype, choice about how the phenotype produces a fitness. And now we have a choice about how the fitness produces the probability, like .8 and .1 or something like that, probability of survival into the next generation. So, now once we've got those probabilities, we actually have selection.

**[11:32]:** And those phenotypes out there produce genotypes, a new set of chromosomes, and that completes our loop. It goes back in there, and so that's the new generation.

**[11:51]:** Sounds simple. So, if you're going to make this work, of course, you have a million choices as I'm going to emphasize over and over again, and one of your choices For example, how do you compute the fitness? How do you compute the probability of survival to the next generation given the fitness? So, we have to go somehow from numbers like these to probabilities like those. So, I'm going to talk about several ways of doing it. None of them are are magic. None of them was specified and stipulated by God as the right way. Uh but they have increasingly good properties with respect to this kind of um processing. So, the simplest thing you can do, idea number one for computing the prob See, what you do is you get this whole bag of of of individuals, and you have to decide who's going to survive to the next

**[12:44]:** generation. So, at each step, everything in the bag has a probability of being the one you pick out and put into the next generation. So, at any step, the sum of the probabilities for each of those guys goes to is the is one. Because that's how probability works. Probability of complete set is uh add all up is probability one. So, one thing you can do is you can say that the probability of that you're going to draw individual I uh is uh equal to or maybe proportional to the fitness uh of of that individual. I haven't completed the expression, so that's why. I haven't completed the expression, so it's not a probability yet because sum over piece of I won't won't add up to one. How could I ensure that it will add up to one? Oh, that's easy, right? All I have to do is divide by the sum of the fitnesses over I.

**[13:43]:** So, there's a probability measure that's produced from the fitnesses. You have to make sure that the fitnesses are negative, right? Have to make sure the fitnesses are what? Are negative. Uh he says I have to make sure the fitnesses aren't negative. Yeah, it'd be embarrassing if they were. So, we'll just truncate anything like that as zero. You have You got a lot of choice how you can calculate the fitness. And maybe you will produce negative numbers, in which case you have to think a little bit more about it. So, now what about an example? Well, I'm going to show you an example. Why don't I show you the example? What we're going to do is we're going to have a genetic algorithm that looks for an optimal value in a space.

**[14:27]:** And there's the space. And you'll notice it's a bunch of contour lines, bunch of hills in that space. Let me show you how that that space was produced. The uh fitness uh is a function of X and Y, and it's equal to the sine of some constant times X quantity squared times the sine of some constant Y quantity squared E to the plus X plus Y divided by some constant. So, sigma and omega there are just in there so that it kind of makes a nice a nice picture for demonstration. So, there's the space, and clearly where you want to be in this space is in the upper right-hand corner. That's the optimal value. But we have a genetic algorithm that doesn't know anything. All it knows how to do is mutate and crossover. So, it's going to start off with a population of one.

**[15:30]:** It's a little red dot down there in the lower left. So, here's how it's going to evolve. Uh there's going to be a chromosome consisting of two numbers, an X number and a Y number, like say .3 and .7. Here's another one, which might be .6 and .2. So, the mutation operator is going to take one of those values and change it a little bit. So, it might say, "Well, we'll take three and we'll make it .2." And the crossover operation is going to exchange the X and Y values of pairs. So, if we have a crossover here, then what we're going to get out from this one, well, we're going to get out a combination of these two.

**[16:22]:** And it's going to look like

**[16:28]:** this. Cuz what we're going to do is we're going to take the X value of one and combine it with the Y value of the other one. So, this is going to be .2, my mutated value, and .2, and this is going to be .6 and .7. So, that's how my little genetic algorithm hack is going to work. So, having coded this up, um we can now see how how it uh how it flows.

**[17:00]:** Oh, let's run it 10 generations. So, the population is rapidly expanded to some fixed limit. I forgot what it is, 30 or so. And we can run it 100 generations.

**[17:15]:** And so, this seems to be getting stuck, kind of, right? So, what's the problem? The problem is local maxima. This is

**[17:28]:** fundamentally a hill-climbing mechanism. You note that I have not included any crossover so far. So, if I do have crossover, then if I've got a good X value and a good Y value, and I I I can cross them over and get them both into the same in the same in the same situation. But nevertheless, this thing doesn't seem to be working very well. Just a general question. Yeah. That picture is the contour lines of that Just contour lines of that function. So, the the reason you see a lot of contour lines in the upper right is because it gets much higher because there's that exponential term that increases as you go up to the right. So, I don't know. Let's uh Let's put some crossover in and repeat the experience.

**[18:15]:** Run it 100 generations.

**[18:23]:** I don't know. It just doesn't seem to be going anywhere. Sometimes it'll go right to the right to the global maximum. Sometimes it takes a long time. It's It's got a random number generator in there, so I have no control over it. So, it's going to get there. Um I I couldn't tell whether the crossover was doing any good or not. Oh, well, here's one. Let's put in a little make this a little bit more complicated. Suppose that's the space.

**[19:02]:** Now, it's going to be in real trouble because it'll never get across that moat.

**[19:09]:** You know, you would think that it will climb up to one one uh to to the to the X maximum or to the Y maximum, but it's uh it's not going to do very well. Even with crossover, it's just not going to do very well because it's climbing up those local hills. Anybody got an idea about one simple thing we could do to to make it work better? Yeah, you do. You could uh increase the step size, right? Let me see if that will help.

**[19:49]:** You know, even that doesn't seem to help. So, uh we have to conclude uh do we conclude that this is a bad idea? Well, we don't have to conclude it's a bad idea yet because uh we may just look at it and and ask why five times. And we might ask, well, maybe we can get a better fitness mm a better mechanism in there to translate fitness into probability of survival. You know, these you using that using this formula is kind of strange anyway because, you know, if you suppose temperature is one of your fitness characteristics, the hotter the better. Then the ratio of the probability that you will survive versus some the person next to you, that ratio will depend on whether you're measuring the temperature in Celsius or Fahrenheit. Right? Because you you've shifted the you've shifted the origin. That shifts the ratio.

**[20:38]:** That shifts the probability of success. So, it seems kind of strange to just take these things right straight into probabilities. So, a better idea, idea number two, is to say, well, hmm shoot. Maybe we don't care about what the actual fitnesses are. All we really care about is the rank order of all of the candidates. So, the candidate with the most fitness will have the most probability of getting in the next generation. The candidate with the second most fitness will have the second highest probability and so on. But we're not going to use the actual fitnesses themselves to make the determination. Instead, what we're going to do with this mechanism number two, this is the rank space method.

**[21:28]:** Is this. We're going to say that the probability of the highest ranking individual getting into the next generation is sub some constant piece of C, which of course you can select yet another choice. And then if uh if that guy doesn't get selected, the probability of the second highest ranking individual getting in the next generation is going to be the probability that that guy didn't get in there. That's one minus piece of C. Times the same probability constant. And so you can see how this is going. P3 will be equal to one minus piece of C squared times piece of C. Piece of n minus one will be equal to one minus that probability constant to the n minus n minus two times piece of C. And then there's only one individual left. I mean, if you've gone through all these guys and haven't got anybody selected, then you've got to select the last guy.

**[22:37]:** And so the probability you're going to select the last guy is going to be one minus piece of C to the n minus one. So, it's it's it's the probability of missed all of those guys in the first n n minus one choices. Yeah, it is. Honest to God. See, it's the prob this is the probability that this last guy is going to get selected. It's not the probability that the last guy getting selected given that the others haven't been selected. Trust me, it's right. I think it ought to be one. What? Were you thinking it ought to be one? No.

**[23:19]:** You are re-rolling the dice. You you've got a probability each time except for the last time when of course you you have to take it. There's nothing left. There's no other choice. Yeah. Leonardo? So, when you jump from P1 to P2, that makes sense. Yeah. But from P2 to P3, you're saying It's the probability you missed the first two choices. Yeah, but the the second choice had probability one minus piece of C times piece of C, not No, it's Well, think about it this way. It's the probability you didn't choose the first two. So, the probability you didn't choose the first one is one minus piece of C. The probability you didn't choose the next one as well is because you you're choosing that next one with probability piece of C. It's It's It's the square of it. Oh, okay. Okay. So, that's that might be might work better.

**[24:00]:** Let's give it a shot. Let's go back to our original space choice and uh reset and switch to a fitness the rank fitness method and we'll run that 100 generations.

**[24:19]:** Whoa. What happened there? That was pretty fast. Maybe I used a big step size.

**[24:28]:** Yeah, that's a little bit more reasonable. Oops, what happened? It's really getting stuck on a local maximum.

**[24:39]:** So, evidently I've chose a constant piece of C uh such that it just drove it right up the the nearest hill. On the other hand, if I change the step size a little bit, maybe I can get it to spread out. I sure did. And now that it's um managed to evolve over there to find the maximum value, now I can clamp down on the step size again. And now it shows no more diversity. It's just locked onto that global maximum. So, this is not unlike what evolution sometimes does. It um sometimes uh species collapse into a state where they don't change for 5 or 600 million years, like sharks, for example. Uh sometimes uh they need um sometimes they only survive if they've got a lot of diversity built into their uh way of life so that they can adjust to habitat changes. Now, when you increase the step size because you're stuck on a local maximum, it's like heating up a metal.

**[25:44]:** You make everything kind of vibrate more, make bigger steps. So, this this kind of process where you may start with a big step size and then gradually reduce the step size is called simulated annealing because it's like letting a metal cool down. So, you start off with a big temperature big step size that kind of covers the space and then you slowly reduce the step size so that you so you actually crawl up to the local maximum of the local maxima that are available. So, that seemed to work pretty well. Let's see if we can get it to work on the harder problem with the moat.

**[26:32]:** So, it's not doing very well. Better increase the step size.

**[26:41]:** No, it's still kind of stuck. It even though it even though it's got the capacity to cross over, it's so stuck on that lower right hand corner, it can't get up the that vertical branch to get to a point where crossover will will produce a a value up there in the upper right hand corner. So, we're still not home yet.

**[27:03]:** So, what's the trouble? The trouble is that the that the fitness measure the fitness mechanism is just driving things up the local maximum. It's just terribly unfortunate.

**[27:20]:** What to do? Well, here's something you can do. You can say, well, if if the problem is we we've lost the diversity in our population, then we can measure the diversity not only the fitness of the of the set of individuals we're selecting from, but we can measure how different they are from the individuals we've already selected for the next population. In other words, we can factor in we can get a diverse population as well as a fit population if when we make our selection we consider not only their fitness, but how different they are from the individuals that have already been selected. So, that's going to be mechanism number three.

**[28:07]:** So, now we have a a space and we can measure fitness along one axis, ordinary fitness. And this is rank space fitness, so that's going to be piece of C. There'll always be some individual with prob with with the highest fitness. Um and and and and over here, it might not be piece of C, actually. But there'll be some individual with a maximal fitness and at at any given step in the selection of the next population, there'll be some individual that's maximally diverse from all of the individuals that have been selected for the next generation so far. So, what would what kind of individual would you like to pick for the next generation? Well, the one with the highest fitness rank and the one with the highest diversity rank. So, what you really like is you'd like to have somebody right there. And if you can't have somebody right there, if there's nobody right there with maximum with the maximum fitness and maximum diversity at the same time, then maybe you can draw in iso goodness lines like so, which is just

**[29:28]:** how far you are from that ideal. So, let's summarize. We got to pick some individuals for the next population. When we pick the first individual, all we've got to go on is is is how fit the individual is cuz there's nobody else in that next generation. After the first first individual is selected, then we can look at our set of candidates and we can say which candidate would be more different from the set of things we've already selected than all the others. That would get the highest diversity rank. And so on down the candidate list. So let's see how that might work.

**[30:11]:** So we're going to use a combination of fitness rank and diversity rank. And we'll just use the simple one so far. We use a small step size. And we'll let this run 100 generations to see what happens.

**[30:31]:** Bingo. It crawls right up there because it's trying to keep itself spread out. Uses the diversity measurement to do that. And at the same time it's seeking um high fitness. So that's why it's crawling up to the upper right hand corner. But in the end, that diversity piece of it is keeping the things spread out. So suppose you're a shark or something, you don't care about diversity anymore. And we can just turn that off. The thing's still running.

**[31:03]:** And go back to fitness rank. Bingo. So there you are. You're stuck for 600 million years.

**[31:12]:** So let's see if this will handle the moat problem.

**[31:24]:** See our step size is still small. We'll just let this run. So the diversity piece of it's keeping it spread out. And pretty soon bingo, it's all right. It's right in there even it's crossed that big moat because it's got the crossover mechanism that combines the best of the X's and the best of the Y's. So that seems to work like work pretty well. Okay. So see these are some of the These are some of the things that you can think about when you're thinking of Oh, and of course we're shark, we're going to forget about diversity. Change the selection method from fitness and diversity rank to just diversity and collapses down under to the highest hill.

**[32:07]:** Yeah, fitball what? How does the step size translate into mutations? Oh, it's just the you're The question is how does step size translate into mutation? Oh, uh instead of uh allowing myself to take steps as big as a tenth, I may allow myself to take steps as big as 3/10. According to some distribution.

**[32:32]:** So what to say about all this? It's um It's uh very seductive because it's nature, right? The trouble is it's naive nature. And this is a as evolutionary theories go, this is horrible. This is naive. And so we'd like to use real evolutionary theory except we don't have real evolutionary theory. Evolution is still a mystery. Some things are pretty obvious. You can you can you can breed fast racehorses. That works just like so. The trouble is we don't have any real good idea about how speciation takes place and how a lot of evolution works because all these chromosomes are connected to their phenotype consequences in very complicated ways that nobody fully understands. So there's a great deal of magic in that genotype to phenotype transition that nobody really understands very well. So when people write these programs that do um that that are in the in the style of so-called genetic algorithm, they're they're they're taking they're they're uh taking a photograph of high school biology and and and they're spending

**[33:44]:** a long time building programs based on that naive idea. But that naive that naive idea have has lots of places for intervention. Because you can look at all the things you can screw around with in the in the in that uh process of going from one generation to the next. You got um By the way, what does mutation do? It's basically hill climbing, right? It's producing a little spread out and you're using the fitness thing to climb the hill. So you got a lot of choices about how you handle that. Then you got a lot of choices about how much crossover you do. And what does crossover do? Kind of combines features of strong features of multiple individuals into one individual maybe. Um So you got all kinds of choices there. And then your genotype to phenotype translation, how do you interpret something like those zeros and ones as an if-then rule, for example, is is something that's in the hands of the designer.

**[34:42]:** And then you got all the rest of those things, all which are left up to the designer. So in the end, you really have to ask when you see an impressive demonstration, you have to say where does the credit lie? And I mean that pun intentionally. Because usually the people who are claiming the credit are lying about where it's coming from. But nevertheless, let me give you a couple of examples of where this has found actual bona fide um practical application. So when when you look for practical application, you might say, "Well, where in what kind of problem does a good front piece combined with a good back piece to produce a good thing overall?" And the answer is when you're making a plan. So you might have a problem in planning that requires you to take a series of steps.

**[35:39]:** And you might have two plans, each of which is a series of steps. And you might combine these to produce something new that's the front half of one and the back half of another. So that's practical application number one.

**[36:01]:** And that requires you to interpret your chromosome as an indicator of the steps in a plan. But another example uh comes up is um drawn from a UROP project a student did for me some years ago. Came to me and said he's a freshman. He came to me and said, "I want to do a UROP project." And I said, "Have you taken 6034?" And he said, "No." And I said, "Go away." And he said, "I don't want to go away. I don't want to do a UROP project." So I said, "Have you read my book?" He said, "No." I said, "Well, go away then." And he said, "I don't want to go away. I want to do a UROP project." So I said, "I don't have any UROP projects." He said, "That's okay. I've got my own." And he And he was interested in He's a finance type guy.

**[36:48]:** So he was interested in uh whether he could build a rule-based expert system that could predict the winners at horse races. So his rule-based expert system consisted of rules like this. If uh X and Y, then some conclusion. If L and M, uh then some kind of conclusion. And from these, he would produce rules like if X prime, that's a slightly mutated version of the of the X antecedent, and M, then some conclusion. So it's mutation and crossover. And he was able to produce a system that seemed to work as about as well as the handicappers in the uh newspapers. So he started losing money at a less fast rate. He uh is now doing something in the stock market, they say. Doesn't talk so much about it, though. But an interesting interesting application. He came up with rules like if the sum of the jockey's weight and the post position is low, that's good.

**[38:09]:** Well, that makes sense in the end because the jockey's weight is always between 100 and 110 lb and the post position's always between a one and 10 or something. So they're kind of commensurate values and a low one is good in fact. Not bad. Uh but neither of those I mean this is this is real stuff. Uh my company uses this sort of stuff to do um to do some planning work. Uh but uh neither of those is as impressive as a demonstration I'm about to show you that involves the evolution of creatures. And each creature consists of um block-like objects like so. And they they combine like this and so on. And and so how how can you make a creature like that from a 01 chromosome? Well, some of the bits in the chromosome are are interpreted as the number of objects. Others are interpreted as the sizes of the objects.

**[39:08]:** Others are interpreted as the structure of how the objects are articulated. And still others are interpreted as uh fixing the control algorithm by which the creature operates. So you see how that roughly goes? Would you like to see a film of that in action? Yes. Okay. So always likes to see the films.

**[39:43]:** How did you measure that I question how I measure diversity in the graph. I did I did it the same way I measured the fitness. That is to say I calculated the the distance the actual metric distance of of all of the candidates for the next generation from all of the candidates that already been selected. I summed that up. And from that sum I could rank them according to how different they were from the individuals that are already in the next generation. So that gives me a rank. And then from the rank I use that kind of calculations to determine a fitness a probability of survival and then I just combine the two kinds of probabilities. So you always kept like every time that you selected something you kept those and you kept everything that you had already selected and then those ones were somewhere I'm always using the people the individuals that already been selected

**[40:31]:** at every step. So at every step is a little different because it's working with a new set of individuals that have already been selected for the next generation. Okay. All right. So let's see how this works.

**[40:49]:** So this is showing the evolution of some swimming creatures. And they're evolved according to how well they can swim, how fast they can go. Some of them have quite exotic mechanisms and some of them quite natural that look like a sperm cell floating away there.

**[41:09]:** Once you have these things evolving then of course you can get groups of them to evolve evolve together.

**[41:19]:** So you saw already some that were that were evolving to swim. Uh these are evolving uh to uh move around on the land. It's interesting this was done by Karl Sims um at who at the time was at uh a then thriving company Thinking Machines first spin off from MIT. So he was using a a vastly parallel computer super powerful for its day of thousands of processors uh to do this and it was a demonstration of what you could do with lots of computing. In the early stages of the uh of the experimentation though it its notion of physics wasn't quite complete. So some of the creatures evolved to move by hitting themselves in the chest and not knowing about the conservation of momentum. Thought that was just great.

**[42:09]:** So here they are doing some further uh

**[42:27]:** So you look at these and you say, "Wow, there must be something to this. This is interesting. These are complicated."

**[42:39]:** This one I think this is one of the ones that was trained a bit initially to swim and then to do a land locomotion.

**[42:50]:** So eventually uh Karl got around to thinking about how to make these things evolve so they would compete for food. That's the fastest I think by the way of the land locomotors. Some that was that was training them to evolving them to jump. This is evolving them to follow a little red dot. Some of them have quite exotic method have have stumbled across quite exotic methods as you can see.

**[43:26]:** Seem to be flailing around but somehow managed to sort of like uh watching people take a quiz.

**[43:36]:** Making progress on it.

**[43:42]:** But now we're on to the food competition.

**[44:05]:** So some of them go for the food and some of them go to excluding their their opponent uh from the food uh not actually caring too much about whether they get it. It's sort of uh what children do.

**[44:30]:** There's a kind of there's a kind of hockey hockey player. Now here's two hockey players. Watch this.

**[44:43]:** The one succeeds reminds me a little bit of I don't know hockey, rugby, something like that. Sometimes they just kind of get kind of confused and go right after their opponent forgetting about the food.

**[45:11]:** Gives up. These are I think these are overall winners in this elimination contest. That can't quite get there. Okay. So you look at that and you say, "Wow, that's cool. Genetic algorithms must be the way to go." I remember the first time I saw this film. It was over in Kresge. I was walking out of the auditorium with Tomaso Poggio and uh we looked at each other and we said the same thing simultaneously. We didn't say that genetic algorithms are the way to go. What we said was, "Wow, that space is rich in solutions." What we were amazed by was not that genetic that simple-minded genetic algorithms produce solutions but that the space was so rich with solutions that almost any mechanism that was looking around in that space would find them. But there's yet another way of thinking about it and that is you could say, "Wow, look at how smart Karl Sims is."

**[46:10]:** Because Karl Sims is the one who had his hands on the levers, all those choices that I keep that I kept emphasizing. All those choices that enabled him to trick this thing in some sense into stumbling across the these the solutions in a space that was guaranteed to be rich with solutions. So you have to ask So So first of all, diversity is good. We noticed that when we put diversity into the genetic algorithm calculations we were much better at finding solutions. But the next gold star idea that I really like to have you go away with is the idea that you have to ask where the credit lies. Does it lie with the ingenuity of the programmer or with the value of the algorithm itself? In this case impressive as it is the credit lies in the richness of the space and in the intelligence of the programmer, not necessarily in the idea of genetic algorithms.
