9.1: Genetic Algorithm: Introduction – The Nature of Code

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 thoughts to “9.1: Genetic Algorithm: Introduction – The Nature of Code”

  1. I like the saying on your shirt 😀 it reminds me about a friend of mine who was using Microsoft Word to create techinical drawings of doors and windows which his company was selling 😛

  2. OMG at first I was skeptical because of the presentor but at 7:20 i was like. "THIS IS EXACTLY WHAT I WAS LOOKING FOR" Thanks so much

  3. Hi Daniel,

    I've ported your Shakespeare algorithm to Elixir ( https://github.com/soriyath/genetics ).
    I thought I'd let you know.
    Thank you for the tutorial. I learned many new concepts and porting it to a functional language made me learn new things too.
    I'd love to see the end of your Neural Network series too, looking forward to it.

    Kind regards,

    Sumi

  4. Time stamp 1:15, simulations in software on evolutionary computing was performed in the 1950's? My ass. Transistor wasnt even invented until 1947, to say nothing of a basic computer.

  5. Could you make an algorithm that actually evolves. Based of "life evolution" since a molecular type of life even to a complex one.?

  6. I have created a git repo where you can find this project written in Java using Eclipse. It doesn't include any UI or other fancy stuff, it simply prints the information in the console (added some helper methods to print population, fitness value.. etc). Let me know if there's any issue. This is some good stuff and it's very interesting. Soon I will start working on TSP with Genetic Algorithm using JavaFX, so it'll be fun. Keep up the good work. I love your videos and have a Happy Thanksgiving everyone! 😀
    https://github.com/dgp52/Genetic-Algorithm-Text

  7. there is only and only one thing that could brings the true happiness to me , is when my teachers become like you .

  8. … put some input … and target as input too …. to make the best matrix fitness function… what we call that ?

  9. A humble recommendation for everybody: if you can watch episode 2 "Some of the Things That Molecules Do" of the "Cosmos: A Spacetime Odyssey" series, have seen it helped me a lot to better understand these concepts.

  10. Are there any books or video series on specifically Java that are at all similar to your videos on Processing? I love your enthusiasm and style of teaching and am looking for something as fluid and comfortable for learning Java syntax.

  11. 6:11 The probability is wrong, because you didn't account for the cases were the phrase "to be or not to be that is the question" is divided between two consecutive typed sections of 39 characters. Which would make the probability a bit higher.

  12. Just a minor nitpick: wouldn't the chance of writing "to be or not […]" Be 1/27 * 1/26^38? As there are no characters that repeat. Other than that I love the work you do!

  13. The monkey typing forever concept isn't actually true. If I start counting from 2 and keep counting forever, there wil be an infinite amount of numbers I'll count but I won't ever meet the number 1.

  14. What algorithm was used to make the library of Babel (google it) which contain every word combination that will ever exist?

  15. Great video!! Thanks for the explanation and I also hope I could meet you one day to say hi! to you in person 🙂

  16. If anyone is interested to see this in Java 8 (JavaFX). Brute force Vs Genetic Algo. 🙂 Amazing tutorials!!! https://github.com/dgp52/Genetic-Algorithm-TSP

  17. Sir, can you please help me to rectify errors In code regarding the project titled as " reduction of peak side lobes in the linear array antenna by using genetic algorithm"

  18. Ive never seen a programmer/ code guy being so nice, heartwarming and authentic until i accidentially clicked on one of Daniels videos… its such a pleasure to see him coding/ teaching for us. It brings joy to my life 🙂

  19. If an infinite amount of monkeys sat in front of typewriters one of them would write the complete works of Shakespeare, the others would all write regular expressions.

  20. I have been desperately wanting a good entry point into something like machine learning or a neural network. And you are it <3. Thank you Prof Shiffman!

  21. The genetic algorith doesnt solve that thought experiment. It is hinted the answer by out fitness scale. But it was a nice explanation I guess.

  22. Sorry, but while many people were engaged by your constant going off on tangents, talking about tangential subjects, and inane attempts at humor, I will drop a dislike and move on to another video that may better explain to me the genetic algorithms.

  23. Completely off topic. I'd like anyone that doesn't know it, and is interested in monkeys typing, to meet the Library of Babel. libraryofbabel.info

Leave a Reply

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