9.1: Genetic Algorithm: Introduction – The Nature of Code


Hello and welcome to the first video in
a new playlist! This playlist is all about a field of study that, loosely, you
could call – one call – I could call – I am calling – “Evolutionary Computing.” And I
want to talk about something that’s called the genetic algorithm. I want to talk about why genetic
algorithms exist, what they are traditionally used for, how you might
apply them in different creative contexts, and go through a whole set of
examples. So by the end of this there will probably be 4 or 5 videos showing you about a
range of examples and ideas of things you can try, as well as code that you can
do in both Java, (using the processing framework) and JavaScript (using the p5.js framework). So, that’s my goal. That’s what’s happening. If you are
interested that keep watching. If not go … to a dance party. Ok nevermind. Sorry. It’s just, I just have a new sound
board! It’s too exciting. Ok. So, all the stuff that you’ll be watching (if you are watching and if you continue to watch) is based on material that is in
a book called “The Nature of Code.” I wrote this book so that’s why
I’m using it (that makes sense) and Chapter 9 is the relevant chapter so if
you prefer to read text rather than listening to me ramble on, you can go to this URL [http://natureofcode.com/book/chapter-9-the-evolution-of-code/] and check out this chapter. I’m going to talk you through. Now, the field of evolutionary computing
really dates back, you know, I would say, to the 1950s. John Holland working on different models of simulations of
evolution in software. And so there’s this problem that comes up in computer
science problems, and problems in life in general a lot. Which is: “I need to find
the answer, a single tiny little “optimized perfect example in a sea of so
many possibilities, “it just would be completely impossible
to check every single possibility until “I find the answer.” Now that might seem a little abstract.
What I want to do is talk about [trails off] And, since I’m here what I want to do is talk about this
traditional genic algorithm that was designed to solve those kinds of
problems- Oh this is like a slideshow that’s automatically playing. But over the course of this video series
I’m going to look at three different
scenarios. First, this traditional genetic algorithm that- I’m calling traditional
but it’s kind of the original- the “classic” genetic algorithm. And then some creative
twist on this algorithm looking at this technique called interactive selection
which allows users and audience to kind of help participate in this evolutionary
process an ecosystem simulation to think of using genetics as applied to agents
that are moving around the screen and experiencing the sort of artificial
world. The video games Spore is quite famous for having stuff like this built into it. But this traditional genetic algorithm- A good way to think about why this problem is
necessary and how and what- Why this algorithm is necessary and how this
algorithm can be applied is the Shakespearean monkey
problem. The Shakespearean monkey problem is this thought experiment that
says: if you had a monkey typing at a typewriter for an infinite
amount of time, typing randomly/X/ eventually this monkey
would randomly- by typing every random possibility- type out the
complete works of William Shakespeare. While I think we could probably agree that this abstractly as a concept is possible- is true, let’s think about what this really means.
So let’s say there’s a monkey. This monkey here, and this monkey- Let’s actually just say there’s not actually a monkey. I don’t/X/ have a monkey to bring
in or anything like that. That would be interesting though. Try that another video. But let’s say/X/ there’s a computer simulation of a monkey. And I’m going to say that-
Let’s just say- Let’s simplify the problem and say that the only thing we
care about is the phrase: “to be or not to “be that is the question.” Now that phrase
has 39 characters in it and let’s say we have a simplified keyboard. I have a
keyboard right here which has a lot of keys and numbers and punctuation marks.
Let’s just say we have a simplified keyboard. And this keyboard has
only 26 letters lowercase a through z. And it has the space bar. That’s 27
letters in total. So, if you know/X/ about
probability- I don’t have a coin but- right- If you have a coin- A coin has a heads and a tails. You have a one out of two chance- One possibility being the heads- There’s two possibilities in total. Typing on a keyboard we can sort of say
the same thing. There’s 27 keys. I have a one out of 27 chance of typing
the ‘T.’ Now, Event Probability- If you want to string two events together- If I
have a one out of two chance of flipping heads, and then a one out of two chance
of flipping heads, I have a chance of flipping heads twice
in a row: ½ × ½ so one out of four times. Right. And you can think about
that because I could/X/ flip and here my possibilities:
heads, heads; heads, tails; tails, heads; tails, tails. There are four ways that I could flip a
coin twice. Only one of those is heads, heads. One out of four, or one out of two times
one out two. So the same problem here: The chance that I have for typing a “T”
and then an “O” is 1/27 x 1/27 Ok so that’s- Even that is kind of like a
very low probability. If I’m just typing at a keyboard randomly it’s quite rare that i’m going to type a “T”
and an “O.” But it would happen, probably in a day of me doing this over
and over/X/ again. The phrase “to be or not to be that
is the question” has 39 characters in it. In order for me to have the
probability of typing [singing] a “T” then an “O” then a space then a “B” then an “E” then a space then an “O” then an “R” then a space then an “N” then an “O” then a “T”- That’s another song for
somebody to compose. [Dan restarts his song] {Yeah I’m not typing this again. Nope.} … This is now the probabilities 1/27 to the 39th power. That’s ( 1 / 27 ) times ( 1 / 27 ) /X/ 39 times. Now I- Previously not -right now or this morning, like a while
ago ; so hopefully this math is right- I did this math, and the actual answer is a
one in 66 [blah blah blah blah blah] It’s a really massively like BIG
unfathomable number. So basically this thought experiment is — we were talking about genetic algorithms right, so why is this relevant? This is like an artificial — this is a
completely trivial problem right ? Because I want to — I’m going to open up
my Processing code, I’m going to make a new sketch and I’m gonna say “println( ‘to be or not to be’);” Wait, I have to say : “that is the question”. So look at that : I have now just
solved this problem of typing “to be or not to be” with one line of code — ta da da daaa —
I don’t have a sound effect for “ta da da daaa” yet so I have to make it, right. “To be or not to be that is the question” ;
one line of code but you can serve as an example problem, right ? We know the answer, I know the answer is “To
be or not to be”, there are 66 bazillion gazillion bazillion gazillion
possible random phrases only one of which is the answer. I happen to know the answer so i could
just spit out the answer, but what if there is a problem that the search space
is so vast that you couldn’t possibly — and you don’t know the answer —
and you
can’t check every possibility this is what a genetic algorithm is for, and i’m going
to demonstrate this to you in a couple different ways in a moment. So let’s go back to go to this
particular slide and just look at a little bit more about these numbers. So one thing that I did let’s say you
have a computer simulation that is typing what… — just to think about like
really have the the sheer vastness of the solution space ; let’s say you have a computer simulation that can type 1 million random phrases per second. I don’t even know if
I could do that, if Processing would run that fast — probably could — but whatever, the
point is if I ran that it would take for me to have a 99%
probability of at least that phrase coming up once I would have to run that
simulation for this many years : 9.719 gazillion bazillion gazillion blah blah
blah blah blah years. Notice by the way the age of the known universe is this
number down here (13.750.000.000 years) this number is a lot bigger than that, so
these numbers are so incredibly [mindblow] sort of mind blowing huge,
this is, again, the reason that I’m here right now to talk about genetic
algorithms and this problem is a good way for us to look at what is an
algorithm that could solve this problem without it taking this much time,
and a genetic algorithm is that problem. Now, let’s think about this more
practically one example that I love that’s on the internet somewhere that
I’m gonna just pull up for you right now, is a call “boxcar2D”. I’m gonna
google “boxcar2D” and i’m going to run this right now, and I’m gonna let this
run for a while. So I think this is a nice demo — Ooh… come on really you’re going to be so
slow, you don’t… — I wonder if this page or this page to close a few things just for
a second and refresh this page up I lost it refresh this page ok so this
is boxcar to di did not make this I don’t know why it’s running so slow
but now it seems to be doing a little bit better on you could think about I here’s the problem i want to design a
car and I could say that oh I know so let’s say I’m I’m a car designer and
I know I ok I’m going to design a car I wanted to be aerodynamic so it should
look like this I wanted to have you know small wheels
in the front and big wheels in the back and because I like rainbows I wanted to
have a sign you know with a rainbow on it and i also like unicorns so I wanted to have like a unicorn thing
at the front but i have no artistic talent but this is the best I could do and I’ve designed this car this is like
me designing a car but here let’s think about the possible ways let’s say I have I could design a car out of here are my
things any polygon I could design a car out of any number
of wheels those wheels could be the attached to the polygon any number of
ways and I could have any mythological creature I don’t think this partisan box2d
mythological creature somebody make a boxcar 2d with physiological features
like unicorns that will be exciting um so you can see like if we started
working this out I probably would also have his billions and billions and billions
of possible car designs so one way of finding an optimized car
design is to evolve that optimize car design and if i come back over here and
press my button you can see that’s what boxcar to do is doing its testing out a
whole lot of different possible car designs using the box to the physics
engine i do have some video tutorials about that so this is ultimately what I’m building
– how can you design a system that uses evolutionary algorithm to evolve a
behavior or design or solve some particular kind of search problem and
there are lots of ways you can apply genetic algorithms and what I’m going to
do in this tutorial series is start with what start with a simple problem with a known
answer and if we can get the genetic algorithm to solve this simple problem
with a known answer then we can take that genetic algorithm and start to
apply it to lots of other interesting scenarios without known answers and the
simple problem with a known answer that I want to solve who that is this one to be or not to be that is the
question without a brute first force search so I could make a brute force search
that just tries every possible get there or I could create an evolutionary search
genetic algorithm search and that’s what I’m going to do and in that and and that will cover the
sort of traditional genetic algorithm one of the pieces of the algorithm how does it work and how do you
implement that in code so this video is my brief sort of overview of kind of
covered where the stuff is coming from what I’m thinking about and in the next video what I’m going to
do is actually start talking you through the algorithm itself and starting to
write pieces of code that implements that algorithm and showed you in the
context of the Shakespeare to be or not to be that is the question example okay thanks for watching and maybe i’ll
see you in the next video I don’t actually see anybody and if you’re
watching this in a video and just recorded so i’m not actually even a
thing but i have a real person and you could say hi to me sometime if you
wanted to know where I don’t know where okay bye

100 Comments

Add a Comment

Your email address will not be published. Required fields are marked *