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