Become a Creator today!Start creating today - Share your story with the world!
Start for free
00:00:00
00:00:01
8: Evolution and Engineering (Genetic Algorithms)
812 Plays7 years ago
Computation is a nascent science, and as such, looks towards the other sciences for inspiration. Whether it be physics, as in simulated annealing, or, as now is popular, biology, as in neural networks, computer science has shown repeatedly that it can learn great things from other sciences. Genetic algorithms are one such method that is inspired, of course, by biological evolution. So what are genetic algorithms used for? What have they taught us about the natural process of evolution? And how can we use them to improve our world?
---
Support this podcast: https://anchor.fm/breakingmathpodcast/support
Recommended
Transcript
Inspiration from Biology: Genetic Algorithms
00:00:00
Speaker
Computation is a nascent science, and as such looks towards the other sciences for inspiration. Whether it be physics as in simulated annealing, or is now as popular, biology as in neural networks, computer science has repeatedly shown that it could learn great things from other sciences. Genetic algorithms are one such method that is inspired, of course, by biological evolution. So what are genetic algorithms used for? What have they taught us about the natural process of evolution? And how can we use them to improve our world?
00:00:28
Speaker
All this and more on this episode of Breaking Math. Episode eight, evolution and engineering. I'm Jonathan. And I'm Gabriel. And you're listening to Breaking Math. Breaking Math, of course, is brought to you by KUNM Generation Listen. And Gabriel, you wanted to talk about the Patreon?
00:00:49
Speaker
Yes, we do have a set, we do have a Patreon set up with Breaking Math. We do intend to purchase more mics as well as some portable mics so we can do some in-person interviews. And of course our expenses are $17 a month. If you donate $5 a month you're paying for a huge percentage of that.
00:01:08
Speaker
And that'll be at patreon.com slash breaking math podcast. And if you haven't checked it out yet, check out the Facebook at facebook.com slash breaking math podcast. And of course we're being recorded double today. That's right. Today we have a special guest. We are featuring, um, a guest from the university of new Mexico communications and marketing department. Her name is Rachel wit and she will be recording us on video as we are being recorded on audio.
00:01:34
Speaker
And you'll be able to check out that article and we'll let you know when on the Facebook page and it'll be at news.unm.edu.
Engineering Applications: Circuits and Aerofoils
00:01:43
Speaker
Why are we talking about evolutionary algorithms on a math podcast?
00:01:49
Speaker
Well, I am happy to answer that. Just recently, yesterday in fact, I finally defended my master's degree project here at the University of New Mexico. I'm getting a master's degree in electrical engineering, and I just did my project on genetic algorithms.
00:02:05
Speaker
And of course, genetic algorithms do have a lot of mathematical components which will delineate in due time. And actually, that's the reason why you might have noticed the dearth of Facebook content lately. That's correct. We've been very, very quiet on our Facebook because I've been working so hard on putting together my master's degree presentation, not to mention analyzing the data and spending a lot of time debugging. So we've been plenty busy recently.
00:02:32
Speaker
Given the fact that this is your project, you could probably answer the question, what are genetic and evolutionary algorithms used for? Yes, yes. This question I feel very, very well versed in discussing. So evolutionary and genetic algorithms are actually used to design components. I'll say right now in engineering, but of course they have other applications as well, including art or data mining or things like that.
00:02:57
Speaker
My specific use for it was to design a genetic algorithm, which is slightly different than an evolutionary algorithm. My project was to design a genetic algorithm that would automate the design of a circuit, which could match an arbitrary waveform. For those of you who are not engineers,
00:03:18
Speaker
Essentially, every circuit has a waveform when a voltage is applied through it, and I wanted to be able to automate the process of a circuit design to match any given waveform that exists that you can choose.
00:03:35
Speaker
And of course, these are called nonlinear problems. And these have been used traditionally for aerofoil design, wing design, neural networks, and a problem, which we're going to introduce to you. It's called the eight queens problem.
00:03:49
Speaker
a lot of our listeners may be wondering how long have they been used for. These algorithms actually go back to the 1960s. They are nothing new, in fact. And of course, the principles of Darwinian evolution go back to the days of Charles Darwin. Yeah, which is like 1860s or something.
00:04:08
Speaker
And I wanted to mention specifically, you were talking about what kind of problems are these used for, and you said nonlinear problems. So I think another way of wording it is, if you can approximate a solution to a problem and have it be acceptable, then this sort of algorithm would work just fine. These algorithms would not work if you need a very, very precise, a very exact solution.
00:04:34
Speaker
And by exact, we mean exact because evolutionary algorithms can come up with extremely close solutions. Indeed, indeed. Absolutely. So it's a very exciting field and it's a very exciting way of thinking about design. And Gabriel, I think you had a message to people who might be getting their masters.
00:04:49
Speaker
Absolutely. This is where I've been thinking about this for the last weeks. For our listeners, for anybody who is wanting to get a master's degree or specifically anybody who needs a research project, I thought about how I'd phrase this and I almost said, just steal my idea. And the reason why I say this is there are so many, there are countless ways of doing what I did and I only chose one of them.
00:05:14
Speaker
this field is so exciting. So might I encourage you, if you have any interest in computer science and you're in an engineering field at all, might I encourage you to consider solving a problem with a genetic algorithm? You can even do the same problem that I chose because you'll do it your own way. Pick a waveform and design a program to emulate that waveform.
Core Components of Genetic Algorithms
00:05:39
Speaker
Yes, and to give you a quick example of a nonlinear problem, we're going to talk about the eight queens problem. Imagine you have a chessboard. You have eight queens on the chessboard and you need to put them in position such that no two queens can attack one another. How do you do that? It's difficult to do, except a genetic algorithm can actually do it very well. And we'll keep coming back to this example.
00:06:04
Speaker
for every component of the genetic algorithm. We will split this episode into four main components that we have identified as the crux of working on any genetic algorithm project. These are as follow. DNA representation. Fitness evaluation.
00:06:21
Speaker
parent selection, and offspring creation. DNA is a method of representation found in natural creatures, and it is extremely complex and nonlinear. It is also hierarchical. DNA can be divided into subcategories of chromosomes and even further into genes and base pairs.
00:06:41
Speaker
There are four base pairs, A, C, G, and T. Three base pairs represent one of 21 different amino acids. These acids go on to create proteins and enzymes which catalyze reactions that govern everything that goes on inside a cell. So, what can we learn from such a complex process?
00:07:03
Speaker
Now DNA obviously is really complicated, but its purpose is very simple. It represents who you are, what created you. The difference between a genotype and a phenotype is important. Gabriel, do you want to talk about that?
00:07:18
Speaker
Oh yes, absolutely. So, as Jonathan said, DNA represents who you are. If we use that term in talking about an algorithm, DNA is just information that you would have in a parent that goes on to a child. Now, the term is phenotype and genotype for a few non-biologists. Genotype is all of the information in your genes. Phenotype is how that information is expressed in your physical body.
00:07:43
Speaker
So, not all the information that is in your genes gets expressed in your physical body. The example I like to use is the difference between a blueprint and a house. On a blueprint, you have, for example, like a ruler. There's no ruler in the house. But you have all the components of the house that go into it. Very good, very good, yes. I like that analogy a lot. Now, I wanted to talk about the DNA and the eight queens problem.
00:08:08
Speaker
Let's say that your DNA is just
DNA Representation Examples
00:08:10
Speaker
a list of numbers from one through eight. Let's say, for example, 47523861. What that would mean, in this case, is that in the first column, it's the fourth one down. Second column, seventh one down, and so on. Now, Gabriel, isn't it true that those can be pretty arbitrary? Oh, absolutely. Yes, yes. In terms of genetic algorithms, how you define DNA is a completely arbitrary distinction, as long as it's consistent throughout your program.
00:08:37
Speaker
So what was one gene in your thing that you made? So the way I designed my evolutionary algorithm, and again, it breeds circuits. One gene is simply one electrical component that has two nodes on either side. Actually, two or three nodes, because I also included things like MOSFETs. They weren't used very much. For the sake of this conversation, let's just say a single electric component with two nodes is one gene in my program.
00:09:07
Speaker
And if you haven't seen an electrical component that isn't in a circuit board, what they look like is imagine a wire with a lump in the middle. That's most of them. Pretty much. And that's resistors, capacitors. Mine included resistor, capacitor, inductor, also voltage source and current source. So those are very, very common electrical components and circuits.
00:09:29
Speaker
I didn't have to go that route. I could have also defined one gene as one simple closed loop circuit that has a very simple waveform. It's completely up to me how I do it. Yeah. Remember that your code went through like five iterations. That's right. And almost all of them had different DNA representations. Yes. Maybe we can share, maybe I can share some of my wisdom with all my iterations with the listeners as we talk about how to make a successful evolutionary algorithm.
00:09:56
Speaker
Yeah. So, so I mentioned we were talking about what DNA is in my program, but, but again, it's so, it's completely arbitrary. Let's say that you just, let's say that you're trying to breed, uh, just two matrix, uh, two matrices, uh, you know, three by threes and they each have numbers. I'm not sure what you'd be trying to breed, but let's say that's what you're doing. Your DNA could simply be a single number in one of the boxes. That's it. Yeah. That would be a gene in the DNA.
00:10:23
Speaker
Let's say that you're designing a wing. The DNA could be the list of shapes, eat the shapes defined by pairs of numbers that go down the wing. Let's say you're designing an algorithm that's trying to go to the houses in the shortest period of time. This is the most house, it's called the traveling salesman problem. Your DNA then would be the sequence of houses and so on.
00:10:44
Speaker
Yeah, so it's fascinating. And again, I keep saying this, it's so arbitrary. What I really like to do is think of it as many engineering problems as I can and think, okay, so if I were to break this down, what would be useful for me to consider one bit of DNA? Would it also work in the traveling salesman problem to just say a one step of distance could be DNA depending on how you set it up?
00:11:09
Speaker
It really depends on how you set it up, if it's Cartesian or graph-based, but yeah. Nice. And in the problem that you had, how many thousands of different combinations were there of different circuits? Oh, my goodness. Okay, okay. Before...
00:11:24
Speaker
I want to explain this number very quick. In my program, I made one creature and I made it so it had a minimum of between four nodes and six nodes. Again, that's going to make a lot of sense for electrical engineers. Basically, that's a fairly complex circuit. Mine was not a simple program.
00:11:45
Speaker
If you don't include the value ranges of the components, then there are 147,600 different possible creatures that mine could create just starting out, just in the first generation.
00:12:04
Speaker
Yeah, and it blew up if you wanted to include the range of different values. By the way, if you're thinking of designing a genetic algorithm, you don't have to make it as diverse as mine. That required a lot of computer power and that made it more difficult. You can start small. In fact, I would even suggest get a grasp on how to do a genetic algorithm and make it simple first and then expand.
00:12:28
Speaker
Just remember that for every free bit of data, you could go back to our episode TMI, episode three, to learn what a bit really does represent. You have twice as many possible things to search. Depending on your fitness function, which we'll talk about next, that could be a problem.
00:12:47
Speaker
Part two, fitness evaluation. Fitness in nature is a simple definition with a complex implementation. A creature is fitter if it passes on its genes more times. This works for everything from bacteria dividing to dogs chosen artificially to trees competing for sunlight in the forest. And before we go into fitness, I'd like to introduce for the second half of the episode Jalila Arthur. Hello, I am the breaking math studio engineer.
00:13:15
Speaker
You may recognize her from episode, I think it was episode two, where she did the game. 20 questions. Episode three, right? Episode three, TMI? Yeah. TMI. That's right. That's right. She's back. She's back by popular demand. We're glad to have her. And so anyway, fitness in a genetic algorithm is something that's calculated rather than something that just happens.
Understanding Fitness in Genetic Algorithms
00:13:38
Speaker
I guess you could say that the fitness function for nature is just existing.
00:13:43
Speaker
Yeah, actually, I was thinking about this because in nature, with evolution in nature, it's clearly whatever lives long enough to have children. Yeah, I guess that's the difference. But it's different for a genetic algorithm, of course. In a genetic algorithm, it's a lot like how you might actually design a dog. Because a dog, that's an example where we have our own fitness function.
00:14:09
Speaker
We breed dogs for their ability to smell or their ability to take back game without dissecting it. Would an example of fitness in nature besides just existing be proliferation? Yes, proliferation is definitely a huge component of fitness. So that would be like greater fitness for natural species.
00:14:35
Speaker
Yeah, so for example, if somebody has more children, then they're going to pant us on more of their DNA. So they were more fit, but fitness is decided almost retrospectively in nature. Whereas when you're designing a dog or doing a genetic algorithm, you rank these things and you basically make them breed.
00:14:57
Speaker
Yeah, one more thing. So I think that we had made very, very clear earlier on when we're describing all these components that every single one of these are completely arbitrary. So everything that you want to design with a genetic algorithm will have its own arbitrarily defined fitness. You could have something, a tallness itself could be a fitness.
00:15:18
Speaker
Oh, I see. You pick it. So in my case, I don't think I've addressed this yet. So from my master's degree, I created a genetic algorithm that designs circuit boards of all things. And in mine, I chose a reachable goal. I wanted to design a circuit board that would match a very specific
00:15:41
Speaker
waveform. Now, for those of you who are non-engineers, basically with every circuit, anything that has something like a capacitor or an inductor, if you run a voltage through it, you flip it on, you flip it off, it'll have a waveform. It'll have a pulse. Think about one of those dimmer switches. If you make it go up and then down, then the waveform goes up and down over time. That's basically what we're doing when I was helping him with the algorithm.
00:16:07
Speaker
like this. That changed and it's clear in my editing software the waveform that was produced as a result.
00:16:21
Speaker
Oh, and in the eight queens problem, like we've been talking about, the fitness score is different than what you do with the fitness. The fitness score in this case would be how many queens can attack each other. You want to minimize that. So in this case, you would minimize the fitness instead of maximize it.
00:16:40
Speaker
Yeah, yeah, absolutely. And in mine, so with my problem, the fitness score, of course, was an equation that we came up with. And again, there's so many ways to do this. It's so arbitrary. We came up with an equation that compared the waveform of the evolved circuit. You just pick one, you know, one of the evolved circuits. How closely is its waveform to the goal waveform? And there's ways of comparing two waveforms. It gets into a little more complex math, you know. And for those who are interested, it's the cosine distance.
00:17:08
Speaker
But again, so a fitness function is just how fit, however you define it, your breed species are. Are there other examples of fitness in other algorithms?
00:17:21
Speaker
Sure. For example, when you're doing neural networks, you have a certain data that you want to train. Okay. You have training data. This isn't a certain example of a neural network. You have your inputs and your outputs and you want it to be able to choose the category as well. So you rank the fitness based on how well it chooses categories. If you're evolving something for a wing design, you would rate it on efficiency.
00:17:45
Speaker
Nice, nice. And then without going too far into this, you can even have multiple criteria for a fitness. I'm trying to imagine. I know that there was the evolved antenna design from NASA. I haven't read the specific fitness for that one. But for example, if you needed an antenna to be both within a certain volume, a certain size, and have a certain radiation pattern as well, you can design your algorithm so that that's your fitness as well.
00:18:14
Speaker
And all of this is stuff that you have to design. Parent selection. Life is divided into two main categories, that which reproduces sexually and that which reproduces asexually. This is not to mention parthenogenesis, wherein a creature has the option of reproducing without a mate. In the natural world, these mates are chosen by a turbulent relationship with their environment. How do we emulate this task computationally?
Role of Randomness and Parent Selection
00:18:43
Speaker
And joining us now is Rachel Witt. And yes, we're going to have a new person on for every segment. At the end of the episode, how many people are we going to have on? It was a combinatoric problem. So, you know, each time, you know, just kidding. But Rachel, would you like to introduce yourself?
00:18:58
Speaker
Absolutely. Hi. Yeah, my name is Rachel Witts. Great to be on the podcast with you guys today. I'm a big fan of your work. I've checked it out via Facebook and also on the website. I work for the University Communication and Marketing Department here at UNM. And part of what we do is work on getting the stories of our students and staff and faculty members out to members of the community, connecting them with the research that's being done at the university and also with the students and their initiatives that they're bringing forward into the community, trying to
00:19:27
Speaker
make a good kind of bridge between the university and the community. And Rachel also was the videographer who we mentioned at the top of the show. So now let's get into parent selection. We touched on this a little bit in the last segment, thickness evaluation, because the two are very closely intertwined.
00:19:45
Speaker
Yeah, absolutely. And again, the same theme, the same thing that I said in the last section, parent selection is quite arbitrary. It's largely dependent on the designer, on the program designer, how he or she wishes to do it. And now before we go into that too much, off-air, Rachel brought up an important question. Would you like to ask that question again?
00:20:08
Speaker
Absolutely. For a little bit of background for the listeners, I am not mathematically minded, although I can do math. I am a journalist by trade and a writer. Looking at mathematical concepts like you guys bring about is always really interesting. When Gabe emailed me about this particular topic, he mentioned that randomness can be used to create particular images, which you guys are talking about now.
00:20:38
Speaker
But when I think of randomness, I think of it as a biological function, randomness within genetics. And I'd never considered it as being a computational element as well. I didn't know that that could be a thing. The way that this is done is through a process called pseudo-random number generation.
00:20:57
Speaker
Half the time they do that and half the time you actually get a natural process and measure it electrically somehow. But what that is is you have an algorithm that does a bunch of weird stuff to a number. One of them is called the Mersenne Twister, not related to the Game Twister.
00:21:14
Speaker
Now, it's interesting. In computer science classes, they mention random numbers because it's extremely hard to write a program that creates a genuine random number. And if I'm not mistaken, what's typically done is a huge list is made, a ginormous list is made. It's just a list like a receipt at a grocery store. And one after the other, random numbers are included. And then those numbers are made, you know,
00:21:40
Speaker
Well that's one method. A lot of them have to do with primality, some of them have to do with, it's all number theory stuff and you get a very difficult to predict thing. It has a lot to do actually with cryptography which we'll be covering in a future episode.
00:21:59
Speaker
So essentially, yes, it is difficult to have true randomness. It's not impossible with a deterministic machine like a computer. That's how I think. I don't get how you can have something genuinely. I'm on the same page with you, Rachel. How can you have something that's genuinely random when you yourselves have said it's difficult to design the program that can generate that?
00:22:20
Speaker
Especially considering that you are the computer programmer, thus you are telling the computer what to think. So how does the computer then take that on by itself and generate a random number?
00:22:31
Speaker
When I use this computer, I access the disk. That, after a while, turns out to be a very, very random thing because of the way in which I interact with it. Imagine the sum of all of your actions. It's influenced by randomness all the time. So that's called basically entropy, which we covered a little bit in episode three. The entropy for a true random number generator, like you need to generate something for cryptography,
00:22:56
Speaker
Sometimes you have to let your computer run for a couple of hours. So the more random you need something, the more time it takes. But essentially it's how twisted you could get something. And I think if I'm not mistaken, one way to approximate that, if I were to say all that in one sentence, the longer you run the program, the more closely to true randomness it does approach or it does approach. You know, that's some way of saying it.
00:23:22
Speaker
A little bit, yeah. And you could use things like magnets, specially designed circuits to get almost true randomness, because after a while, quantum fluctuations make themselves greater and greater. Yep. So it's nice to have a longer running program. But you are absolutely right. That's a very valid question. And the explanation is not always easy to distill in a quick answer.
00:23:45
Speaker
But are you saying that quantum computers can help? Quantum computers might be able to help with easier sources of true randomness. Yes. Very interesting. Actually, they do that automatically. All you would have to do is initialize something using an H gate as many times as you have qubits.
00:24:03
Speaker
Right. Which I'm like, goes right over my head. Oh, Cubits. Jonathan, I'm glad you brought up Cubits. Just kidding. I have no idea what those are. No, no. Yeah. I'm also less familiar with the computer hardware myself. So anyways, I'll take your word for it. Still interesting.
00:24:20
Speaker
Indeed. So yeah, parent selection. What method of parent selection did you use in your algorithm? Hey, very, very glad you asked. So in my algorithm, I specifically included a bias, a pretty strong bias toward very fit circuits.
00:24:37
Speaker
So, I started off, I had my entire generation of just parents. That's my Adam and Eve generation. I created all of them. Again, there was some randomness involved in them. But basically, I already identified the most fit parent out of all of them.
00:24:55
Speaker
Now, to help influence the offspring in the next generations, I specifically wrote my program so that one third of the time, the fittest parent out of the entire population was always chosen. I did that because I needed to finish my project in two months and I needed results. So I was like, let's just help you along a little here. Speeding up the evolutionary process. Yeah, exactly, exactly. Now, here's what sacrificed.
00:25:23
Speaker
When I do that, I have much less diversity, but I have results that show up sooner, you know? And to talk about why your diversity is important, imagine trying to find the tallest peak on a mountain. The simplest and most naive way to do that would just be to walk upwards. What's the problem with that approach?
00:25:43
Speaker
Just walking upwards, oh yes, on a mountain's gonna take you a long, long time. Well, not only that, but you might- What if you're wrong? Yeah, exactly. You might climb up a hill in the foothills and be at the top of a foothill and you're not gonna be at the top of a mountain. That's right. So the information to you is only available when you're at the top of that structure. So that's the tallest building that you're aware of. Yeah, and so- And then you see the next tallest building if you go to that one. Building, sorry, mountain, right, you know.
00:26:07
Speaker
Yeah, so you can think of a computer or an evolutionary algorithm as a blind person climbing a mountain where they can't see the peaks. You don't know the peaks and the problem. That's one of the things that they're useful for because you might imagine all these mountain climbers and they're evolving to try to find the tallest mountain peak.
00:26:27
Speaker
Yeah, and that's fascinating. I'd love to redo my program, and I'd love to have six solid months to run it, and I don't want to include a bias. In that case, I want to be truly random and see what kind of different results I get after six months, but considering that I have deadlines.
00:26:43
Speaker
It would also be interesting with more diversity in the parent class, 10,000 or something. I think you're right. By the way, that's something else as well we wanted to mention. I think we're going to get to this later in this process, but I made sure that my first generation was pretty large. I didn't want it so large that my computer slowed down.
00:27:01
Speaker
But I don't want it so small that I have a really limited gene pool. So I had a thousand, kind of arbitrarily chosen, but, you know, a little trial and error. I ended up with a thousand different possible parents. And then I would choose at random any three, but I'd make sure that, you know, as I said earlier, a third of the time, it was always the champion circuit. And another way to do this would be to just do one generation at a time.
00:27:25
Speaker
breed the parents randomly but have the fitter parents fit as they are that much more likely to breed and then have a new generation totally of children and just keep doing that over and over again. Oh wow. Fun, fun question, fun question. As we design these programs we realize how truly how many different ways you can do it.
00:27:43
Speaker
You know, even among our listeners and even us later in the day, I'm sure we're going to think of so many other ways of picking parents, you know, for, you know, like, do you have a short deadline? Do you have a long deadline? How, like, how many different ways aside from just randomly picking parents, can you do it? Size, shape and color, maybe.
00:28:00
Speaker
Oh, depending on, like I don't have color or, well I do have size, I do have size. But you're right, I mean really, you can sort them by any arbitrary characteristic and choose by any arbitrary characteristic. Which is definitely related to how parents are selected, which has to do with fitness evaluation, which you weren't here for. Yes. Yeah.
00:28:19
Speaker
I was just trying to understand. So your end product, it approximates a waveform. Correct. And so I'm just curious if you were to take away the bias and in a perfect world have the six months without the deadline to run those generations, do you think that the approximation would become closer to noon?
00:28:43
Speaker
Oh, brilliant question. Here's how I'm going to answer this. When you said noon, again, previously, if anyone just turned on our podcast now, I mean, who turns on a podcast halfway
Diversity Strategies in Genetic Algorithms
00:28:53
Speaker
through? I don't know. I do. That's what I do. For those of you just joining us, I actually have this really cool clock.
00:29:01
Speaker
And again, this is kind of arbitrary because I used a cosine function. I needed a 90 degree angle to stand for the worst fitness and then needed a zero degree angle to be the fit. But in short, if somebody who doesn't know trigonometry, that's the same as 3 o'clock for the worst and noon, 12 o'clock for the best fitness. I literally had a clock print out on each of my circuits. And you can see right away how fit that circuit was just by looking at the clock.
00:29:31
Speaker
And you were trying to get as close to noon as you could. Yes, exactly, exactly. Isn't this like a back tip? Aren't we all? Lunchtime. Awesome, awesome. But no, that's exactly right. To answer your question earlier, so let's say that I had the full six months, I think that I would have had a huge diversity, much bigger diversity in routes that got us there.
00:29:51
Speaker
You know what I mean? And I think that we would have had some circuits that got us there but were really complicated. Some circuits that just had a nice arrangement and were simple and got us there. So the long and short is I would have had more diversity. So that's the really cool part.
00:30:04
Speaker
And when you're dealing with creatures, there's so much you can do. Just take inspiration from nature if you decide to do this as a project. You could do things like create new Adam and Eve things just halfway through that just shake up the population a little bit. You can do things like have what's called a heat function that gets colder over time and the colder it is, the less randomness there is. You could throw in meteors or a grim reaper.
00:30:29
Speaker
Yeah, oh gosh, again, this is so much fun. And this is why I actually am, so I'm done with the project. This is the first time in my life that I'm continuing to tweak my code long after I've turned it in. Because it's so awesome, you know? I'd love to publish. I haven't published yet because it's not that I'm too shy, but I'd rather publish after six months, you know? And I want more results. But I wanted to say this, a lot of our listeners might be wondering right now, we choose two parents. Is there any reason why in a program you can't choose three parents, four parents, five parents? And actually, I want to toss this off to you, Jonathan.
00:30:58
Speaker
There is. When you select just one parent, you get very quick evolution, but you don't get traits that might help each other combining. Think about it like a tree, and each leaf is a different solution. Those leaves don't really run into each other very often. When you have two parents, you get basically the best of both worlds. But think about dating.
00:31:24
Speaker
Think about how difficult it would be if three people had to mate. That would take so much more energy and the exact same thing happens with evolutionary algorithms. You do not get an increase in diversity, you just get an increase in difficulty. Oh wow, there's no increase in diversity when you have more than two parents. Nope.
00:31:41
Speaker
Wow. That was what I was going to ask, actually, was like, does this mean that you could, in the terms of your product, move towards designer waveforms? Oh. With multiple different pools in there. I see. Yeah, and it's funny. I guess, yeah. But I guess not. Mathematically speaking, it doesn't improve. Yeah. That's crazy. So that will save our listeners who want to try their own program. We'd say, again, I don't have the math in front of me right now, but it'd be cool to actually show them we can prove it. We can say, it's not going to help you if you have much more than two parents.
00:32:12
Speaker
So now we're going to talk about offspring creation. This is basically how you take two strands of artificial DNA and make one strand of artificial DNA.
00:32:25
Speaker
Yeah, yeah. This is very, very interesting because what's the common theme that I've been saying all along about each section? It's completely arbitrary. Random. Oh, it's okay. There is randomness. There is randomness. Oh, boo. I was going to say, I was going to use the term arbitrary specifically. It's how the designer designed it. That's what I've gotten if the theme is design. That's what you have a design choice after random. Exactly. That was my second choice.
00:32:51
Speaker
Oh, yeah. Nice, nice. So when we talk about DNA, so DNA is information. DNA is one unit of information. And I guess I think it'd be a good time to even talk about my project, obviously. Oh, yeah. Well, how did you combine your DNA? OK. So well, before I combined it, I decided what one gene was. And again, my arbitrary assignment, I decided that one gene is a single electric component as well as two nodes on either end.
00:33:21
Speaker
And for those who would like to know what a note is, just imagine you have all these different wires, the place where they connect together, the wires. Yep, a connection for wires. That's actually really, really good, in fact. So one gene would be a resistor of any value at all, and little two wires on either end. That's one gene.
00:33:42
Speaker
And each circuit is designed by how many genes they have, the value of the genes, you know, like my values, well, gosh, I included a wide range. I had anything from one ohm for a resistor to, want to guess how big? Seven. Seven ohms. No, I had between one ohm and 50. That's a great guess, I thought. Oh, it's all good. It's okay. 50. Okay, one ohm and 50 million ohms. Whoa. Nice.
00:34:09
Speaker
No, it's fine. Basically, I have a huge amount of diversity. Now, I need to say one more thing. One version of my software included randomly chosen resistors from that whole range. I had absurd circuits very, very soon. It wasn't very viable.
00:34:24
Speaker
They're like low power circuit, like weird low power circuits combined with like trash can sized capacitors. Yes, exactly. So I fixed it. I wanted to keep the now I fixed it now. I'm not a real math person. So I consulted with a math guru. Oh, fair enough.
00:34:40
Speaker
Well, no. So I talked about my problem with a wise guy with a very smart dude who helped me design a specific formula so it really throttled it. So I'll go and say it was Jonathan, the awesome dude right here. Jonathan, will you tell him how we specified it so it narrowed the range a bit?
00:35:00
Speaker
Sure. Um, what it did was it clamped down the, um, the range. So for example, um, let's, let me just give you an example of what this would look like locally. Let's say you have a die. It's a, it's a die with six sides, but four of them have ones on them.
00:35:18
Speaker
One of them has a 2 on them, and the other has a 6 on it. That's kind of what it's like. Now, just to add to what you said, it is still possible to get any resistor value at all in the whole range, but there is a huge probability clamp to where the most common value that I chose was 470. I figured that's a nice low power, simple circuit value, and that was fine.
00:35:40
Speaker
I would say it's not a true probabilistic, it's not a Gaussian random distribution at all, but I would say very, very common values were between 470 ohms and give or take 1,000. Well, we didn't have negative ohms really.
00:35:56
Speaker
No, I don't think you could have negative. Oh, yeah. Yeah, so so give or take so, you know There was there's a small distribution around 470 but but rarely did you get a million but it's possible It's possible. So I'm just again trying to trying to understand. Yes You talked about how so Jonathan you came up with this equation and it kind of puts a Law or a rule or some sort of limit. That's right around this
00:36:26
Speaker
The DNA the way that new components are chosen in mutations. Oh, yes, so not the DNA itself There's like a bunch of diversity there But it's a rule on the on the value of it on the value of the DNA and so I think that's interesting I of course understand why we would want to avoid getting
00:36:45
Speaker
a low-power, huge capacitor computer, or to generate that as a result. I get why that's not a good idea. But what I'm trying to understand is where that law, that limit comes into play with diversity and where, if you're going to put a law, I mean, we're talking about evolution. There's no laws there. That's correct. That's correct. Think about it this way. There are laws in evolution.
00:37:14
Speaker
For example, if I sprouted wings right now, I couldn't fly. Things like that. This is a way of simulating that kind of thing. And yeah, you can make it random, but you can even make it more random. For example, the DNA that Gabriel chose, it had a component and the nodes that it's connected to. And as I recall, the nodes were numbered in such a way so that the topology of the graph
00:37:39
Speaker
that represents a circuit would be similar between two similar DNA strands.
00:37:46
Speaker
Yeah, I want to go and break it down into layman's term. I was really proud of this little part here because this was a breakthrough. This is cool. As I said earlier, I decided to arbitrarily decide that one gene is just an electrical component and the two ends on each side. What I'm really happy with is I added what's called a history marker, per se, where the first time a resistor shows up on the two sides, you've got a number one and a number two.
00:38:14
Speaker
So there's this really cool list that's just stored in my program where it's history marker number one. This is still a rough approximation of it. I'm not going to go into every detail. But let's just say it's called history marker one. The first time that you see the node number one and a resistor of any value and number two, that's considered one gene. So that can evolve very, very often.
00:38:40
Speaker
And if I get two parents, and if I want to say, so I want these parents to be somewhat related, then you look at their history markers. How many of their, like, how many of their genes are shared in the same spot, in the same component? Does that make sense? And this is related to real evolution too, because you can't mate a human with a horse. There's pre and post psychotic barriers to this.
00:39:02
Speaker
Yeah, exactly. So literally. Seems kind of obvious now. Oh, yeah, yeah. But yeah, that makes perfect sense. Now, what's unique about my algorithm is I didn't look at any tutorial online. It was through a lot of trial and error. I'm like, how can I better pick parents so I don't have so many failures that just don't breed anything? If I grab two random parents, I wanted some means of seeing if they're going to successfully breed. It turns out that you do have to have some degree of relatability.
00:39:29
Speaker
Now, I didn't discover this aspect. It was actually Jonathan who discovered the degree of relatability and how all that works out. Yeah, I tried a bunch of values. If they're more than 40% related, basically you get inbreeding, which is as bad in digital circuits as it is in real life. And if you do less than 30% by a significant amount, you get humans trying to mate with horses.
00:39:53
Speaker
Yeah, it just doesn't work. Basically, yeah, in short, your offspring will not be viable if they're not related. Yeah, there's got to be some degree of similarity. They've got to be in the same ... We'll use the word species. How did centaurs come about? I was going to bring that up next. For example, a centaur, you could think of it like, okay, yeah, but what would be a half human, half banana?
00:40:15
Speaker
Oh. A Humana. Honestly, don't be so close-minded. This episode not brought to you by a Humana. Love is love, Jonathan. Love is love. Of course in real DNA, the amount of DNA that two things can share is a lot more than in Gabriel's program. For example, humans share like 99% of their DNA.
00:40:39
Speaker
And so let's talk about your program just once more. So when you're talking about trying to get them to create something that's viable and that sometimes it doesn't work and it's like getting animals and humans to mating, what does that look like as a product for your program?
00:40:58
Speaker
Oh, good question, good question. So obviously you're going to have something. You will have something that exists. But again, what might happen is you're going to have a circuit that just has obscenely unrealistic things. Like you're going to have, I'll give you a value of 12 voltage and then you're going to have a 50 mega ohm huge resistor and you're not going to have any voltage go through at all. It just doesn't work. So we were talking about that before with like the low power and the trash can size.
00:41:25
Speaker
So it's like it can't happen, but it's inefficient, inefficient way. Not just inefficient, sometimes it won't even be like a real circuit or it's like, and sometimes you just get an abomination. One last component that we want to talk about, and this is related to offspring creation, so you kept it in the same section, is DNA mutation.
Offspring Creation Process
00:41:43
Speaker
We can say, so as we're talking about how I did, how I assigned DNA, I said that one gene would just be a component and then the two nodes. But again, a gene is just one unit of information as far as our algorithm is concerned. So there are many other things that we talked about. I even talked with Jonathan about other ideas. Jonathan, what were some of your other ideas for how we would define one gene?
00:42:07
Speaker
Oh, you could define it as loops. You could define them as trees. Trees, just when you have the DNA itself, imagine if DNA, instead of being a long chain of stuff, were shaped like a tree. You could do that. Interesting. There's so many ways to do any kind of problem. And with the eight queens problem that we keep mentioning, the way that you combine DNA is actually pretty interesting.
00:42:31
Speaker
So, let's say they have two pieces of DNA, and one is just one, four, three, two, five, seven, six, eight. And the second one is two, four, three, five, six, eight, one, seven. You don't have to write those down. So, when you combine the DNA, what you do is you would line them up, cut both of them at the same spot, and just glue them together. Of course, you might have some numbers that are the same on both sides, and what you do with those is you just skip them, and you just get the next number up. That way you have a new range of values from one through eight.
00:43:02
Speaker
When you say that it doesn't necessarily have to be a strand, it can be like a tree, can you explain that?
00:43:07
Speaker
Sure, so let's say you have a problem where you're designing artificial creatures. You could define an artificial creature where the DNA is a tree, where you have the trunk of the tree being the main body, the limbs of the tree, and the fingers being the limbs of those limbs, something like that. There's a more abstract way called genetic programming that you could do with actual functions. So you write down a math equation at a tree where the junctions are
00:43:37
Speaker
the pluses and minuses and the leaves are all the numbers. And so to combine DNA in that case, what you would do is you would graft on a limb with all its branches to the other one.
00:43:51
Speaker
OK. Yeah. And just real quick. So one other thing as well. We said like one gene could be a single a single circuit itself like a single closed loop circuit that has a basic waveform. I mean that it could be even one gene. And then of course you can have a variety of different complex genes depending on on your skills with computer science and depending on on how complicated you want to make it. You can have a whole variety of genes and a whole strategy for gene exchange. Oh and that's the next part. We talk about how genes from the two parents
00:44:21
Speaker
How do you design your program to get information and genes from the two parents to go to your child? Oh yeah, and how did it work in your program?
00:44:29
Speaker
So in this program, I had a couple. My initial design was I had two parents, and I had a row of information from either one, and I just kind of randomly selected from either one. And that's one way to do it. That's fine. As I wanted it to be a little more like human genes to a degree, there are genes that belong to one parent or the other, and there are genes that are shared, especially when we have that 30% rule.
00:44:58
Speaker
So, I put a strong bias toward the fitter parent. I said, so I've got these two parents here. Parent A and parent B. Parent A is the fit parent. Parent B is the less fit parent. I intentionally selected it so that all of the genes that only belong to the fittest parent get passed on right on all the time.
00:45:20
Speaker
Then there's genes that belong to both parents. All of the genes that are active, and I'm sorry, we didn't talk about active genes and deactive genes. All that is, is you could have a gene that's turned off. So I think in humans, you could have like, okay, in humans, we get scurvy if we don't eat vitamin C, even though we have the gene for making vitamin C, it's turned off so that we can see red.
00:45:45
Speaker
Yeah, yeah, exactly. So basically, what it is, all of the genes that are shared among both parents, if they're active, they get passed right on. And if they're not active, they also get passed on. And there's a 50-50 chance whether the gene will be... I'm sorry, it gets complicated. If it's active in one parent and not active in the other, then it's just a coin toss. It may or may not be active in the child.
00:46:06
Speaker
Here's where it gets interesting. If genes are deactivated in both parents, I do a coin toss. And depending on the probability, half the time the gene is just deleted. The other half the time it is passed on, but it's passed on inactive. And that's to start weeding things out. I wanted to weed out genes that got deactivated. It just adds an element of change. But then, lastly, there are genes that only belonged to the less fit parent.
00:46:34
Speaker
I really wanted to throttle those genes. So 75% of the time, they don't get passed on at all in any active form. Only 25% of the time, as you would have surmised, they do. And I have a few other nuances, but the idea is I put a strong bias toward the fitter parent. One other thing I want to say, the values. So you've gotten not only the genes, but you've got a resistor. Well, what's the value going to be? Is the value going to be
00:47:03
Speaker
the value of parent A or parent B, what I did is two things. I averaged the values, so if you had 1 and 3, the average would be 2. But then on top of that, I added a probabilistic distribution.
00:47:19
Speaker
So that most of the time it's a perfect average, but there's a standard deviation, and very often the value will shift anywhere. So the lowest that the value can be is the value of the resistor in the weaker parent, or in the parent with the weaker resistor. The strongest it can be is the value of the stronger parent, and it's just a probabilistic distribution that's weighted about the average. So that's, again, that was an arbitrary choice on my end. You can do it however you want.
00:47:48
Speaker
And what all this drives home is you obviously didn't have enough time in three months to go through every single possible probability. I mean, just the amount of probabilities, even if you had only four numbers between zero and 100%, you would have like probably thousands of choices. So programming can, especially genetic programming,
00:48:08
Speaker
can help you get a solution when you're lost. I mean, designing a circuit to make a waveform is difficult. That's why they hire engineers to do it. That's why this program is so unique and this problem is so difficult.
00:48:25
Speaker
It's fascinating. I think we even said previously in this recording, I would love to see a whole bunch of students take on the same problem because no two students are going to do it the same way. There's so much knowledge to be gained here. I know that for me personally, the main takeaway for me is before I throttled the value of each component thanks to the equation that Jonathan helped me put together.
00:48:55
Speaker
Before I did that, I had so many possible circuits that it wasn't realistic. I guess that's the advice I'd pass on. Identify where you have... What's the term I'll use? Runaway probabilities? Identify where you've got so many possibilities that it's not a practical algorithm for your fitness function.
00:49:18
Speaker
I'd say design when you can. You get to play God sometimes. Design when you can, right. So given your time constraints, obviously there are certain things to consider. I'm just beginning to understand, and I think that this is really great. So you're talking about how you can make that value of the genes change depending on what you want to do. You can design. There's all these ways that you can use your agency in this.
00:49:45
Speaker
you have a normal distribution, you're averaging between the two parents to get the value of the offspring. And what you're saying is that other researchers can apply the same thing, and then instead of averaging them together, they could add them together. Yes, totally. And then just like change the whole game. Yo, you know what? See, isn't that why it's exciting?
00:50:07
Speaker
I mean, the fact that I can understand what the result would be from that kind of change, I'm like, oh, genetic algorithms, couldn't even remember that the other day. You're totally onto it. You could just decide to add, and obviously that would result in a resistor that's twice as strong. But again, hey, it's your chance to play God in this form
Mutations and Innovation
00:50:27
Speaker
of life.
00:50:27
Speaker
So, what you say is a great transition to our next topic on mutations, because mutations are part of every single genetic algorithm. Yeah, I'm excited about this. Yeah, exactly. So, obviously in biological evolution, a mutation is something, it's kind of like something occurs that's not supposed to happen. What's a good example of a mutation?
00:50:52
Speaker
A mutation, for example, happened I think somewhere around 50 to 20,000 years ago, I don't remember the exact amount of time, where humans were a T changed to, don't quote me on this, but it changed to a G.
00:51:08
Speaker
because of that sickle cell exists. Interesting, interesting. It's funny because sickle cell has huge advantages for malaria, but it's not advantageous for anything else. Anything else. Yeah, yeah, yeah, so that's crazy. Also, I know the blue eyes are a mutation, and that's a deleterious mutation where people with blue eyes don't have information that people with brown eyes had, you know. Yeah, for example, and not only that, but there might be a reason for the blue eyes mutation
00:51:37
Speaker
And also just like there is in a single cell, for example, if you put, if you ever, if you're ever a blue eyed person and somebody brown eyed is driving a car during, in the rain, they're going to drive you nuts because they don't put on the windshield wipers frequently enough because the focal distance for how much you could focus on a sheet of rain versus the road is different for people with brown eyes and people with blue eyes.
00:51:59
Speaker
Wow, that's fascinating. So it's always a trade-off. So mutations, now real quickly. So on my algorithm specifically, I throttled the mutations big time. I wanted to guarantee them. So okay, I'll just tell you straight up. Every single circuit that is bred in mind, every single one of them will have one of five mutations guaranteed.
00:52:18
Speaker
And to show you how rarely mutations are really beneficial, and why obviously your program used a lot of guaranteed fitter parents surviving over time, there used to be a thing called atomic gardens in the 50s and 60s where they had a big gamma ray source in the middle
00:52:40
Speaker
and the plants nearest the gamma ray source would die. The ones really far away would survive, but the ones in the middle, sometimes they would do things like create the most popular grapefruit in Texas.
00:52:50
Speaker
That's amazing. All three of us went, Oh my gosh. Wow, dude. Atomic garden. And so what became of the atomic gardens? Um, we refined it and created, um, uh, genetically modified. Yes. We, we improved the process and created genetically modified crops. So, so are we, why did we stop doing atomic gardens? Was it Helen healthy?
00:53:14
Speaker
Well it's kind of like, it's not unhealthy actually. It was done for a while. They used to send out seed packets full of genetically modified seeds and then people would do experiments and send back the results. But it stopped because people got better at genetic engineering basically.
00:53:30
Speaker
They didn't need the gamma ray to create those changes. Yeah, instead of throwing a hammer at something like a monkey, you could hammer it with a much smarter monkey. Sorry. That was really cute. You could gently prod the monkey and get the same result, right? Yes. Okay, awesome. I was not aware of Atomic Gardens. They need to incorporate that in the Fallout franchise. I play Fallout. It's a video game with atomic mutations and all kinds of stuff. That's awesome. Wow.
00:53:59
Speaker
So the mutations that I included, the most basic mutation is a value change. It's the most minor nudge at all. It's a very, very probabilistic thing. The most likely scenario is that the value will change by 10% of one unit. So if it's a, there's something called a picofarad, and that is 10 to the negative 12th.
00:54:17
Speaker
So if you've got a capacitor and if it's identified as being measured in picofarads, then the most likely probable mutation will be one-tenth of a picofarad, greater or less than. So that's a very minor nudge, and that's fine. You can have minor mutations. There's nothing wrong with that. Another thing that I do that's actually very similar to nature is a given component, one bit of DNA, can suddenly duplicate, and the other gene can suddenly transform. It's kind of a two-part mutation, really.
00:54:45
Speaker
You know, it'll clone an element and the other element will be passed through a random generator and it'll have any other of the possible genes pop up. So you can have just a resistor and suddenly at the end of this you have the resistor and a capacitor next to it. You know what I mean? And it only happens in series. And the mutation that you would see in the eight queens problem is you just take two of the queens on the board and swap their horizontal positions. That's one mutation.
00:55:14
Speaker
Yeah, yeah. Again, so a mutation, this is completely up to the designer. What do you want to do that will guarantee an unpredictable change in your children? And how frequently do you want to do it? You want to guess how many children out of 100 made it on average?
00:55:31
Speaker
Three. Close. Wow, really? That small? It was actually 11, 11. Wow. Dude. Yeah, yeah. So like 11%? Yeah. Which is actually very common in nature to have numbers that
Future Potential of Genetic Algorithms
00:55:43
Speaker
low. Yeah. For example, sea turtles, it's something like one out of 5,000 make it.
00:55:47
Speaker
And so to summarize, for the four key components of the genetic algorithm are DNA representation, that's how you represent your problem, fitness evaluation, where you see how fit creatures are, parent selection, where you breed your creatures, and offspring creation, where the creature is birthed.
00:56:06
Speaker
We've explored the world of artificial genetics, the problems it can be applied to, and the omnipresence of areas in which it can be used for. Anyone, at any time, can improve the state of the art of artificial genetics and genetic algorithms by simply doing a project. It's an intellectual gold rush. So if you decide to write your own, be safe in the knowledge that you're adding to what it means to know how things evolve.
00:56:30
Speaker
I'm Jonathan Baca. And I'm Gabrielle Hesh. And this has been Breaking Math. Breaking Math is brought to you in collaboration by KUNM Generation Listen. Leela, want to say anything about Generation Listen? Yes. Hello. My name is Jaleela Arthur. I'm the president of KUNM Generation Listen. And we are here for UNM students to use KUNM as the resource that it is to you. And we invite you to get involved. And today we had Rachel from the newsroom. Rachel, do you want to plug anything?
00:56:57
Speaker
Once again, my name is Rachel Witt. I'm a Communication Representative with the University of New Mexico Communication and Marketing Department. We cover all kinds of news stories across campus, including interesting student, faculty, and staff research, awards, achievements. So check out our website news.unm.edu to see all the most relevant news going on at UNM today. Also follow my adorable pugdoxen on etdabi underscore pup, D-O-B-B-Y underscore pup.
00:57:26
Speaker
Your dog has an Instagram? And he is insta-fabulous. Oh my gosh, I'm going to him now. Is it okay if we share him? Is it okay if we call him math dog? We've been looking for him. Oh, math, that's perfect. Math dog. I was hoping no one would notice that I plugged my dog's Instagram account there.