This is absolutely brilliantly explained. The mouse on screen and motion and the way you broke down your discussion and argument is incredible. After having watched many evolutionary and neural network videos, I can say that most are less than half this long and less than half as informed and clear.
Here's an idea: You could give the turtle an "energy" value. Each gene/cell on the grid has an energy cost that is subtracted from the turtle's energy when the turtle moves to (or from, maybe) that cell. When the turtle's energy is gone, it stops. The energy value for each cell could then evolve independently.
@@kamoroso94 you could probably just throw it in and randomly lengthen/shorten by one/randomly select which for sexual reproduction. At first sight, it doesn't seem this would be hugely problematic?
Finally, this solution fights local minimum problems, and directly focuses the evolutionary efforts of each organism towards their greatest challenges. This increases evolutionary efficiency.
I have some criticism that I hope you take as constructive since it is meant that way. You have a number of paradigm issues. (I have degrees in math and genetics btw). 1) You are starting with the ideal solution, and trying to evolve towards that. Genetic algorithms find novel solutions that are robust through diversity. You need to relinquish control and allow the algorithm to find its own solution, otherwise you have just found the most complicated method for solving optimization problems. 2) You are stuck in the common mathematical "generalize" and "reduce" mindset. Too often mathematicians produce some beautiful piece of reduced math and forget that each element is a complicated function in its own right, and resolving the simple function requires a boatload of work that can be computationally expensive behind the scenes. 3) You are trying to mimic natural selection, but your understanding of genetics is too weak. As and example, the height of a plant is base on the number of "height" genes it contains. The more "height" genes, the taller the plant within a min/max bound. There are very few single point mutations in any organism that can have a large impact on phenotype. You should either learn more genetics and do a better job of adding complexity in certain areas (nothing novel here), or fully deconstruct evolution and start from the ground up (novel, and PhD worthy if you succeed). 4) Your 3d chromosome is a symptom of all of the above. You are attempting to contrive the ideal solution that you have already solved, discovered that your reduced function requires tons of background work and then finding a horribly complicated and expensive method. Rather than try to map directly from genome to bitmap, try to use a simpler stimulus/response algorithm. "here I am, what now?" >>What does the environment look like? "The environment looks like this." >>Read genome "I will do this because my genome says to do this in this environment." An algorithm like this will jump the loop easily and get you around the local max problems that genetic algorithms are plagued with
joshua43214 very nice criticism i would agree with. There are certainly many better ways to solve this problem. It's almost the *Travelling Salesman Problem* at this point. especially so with the *environment checking*, that would make it able to *avoid overfitting*, and be used on *multiple images* without much evolution.
How is he starting with the ideal solution? What underlying complexity did he reduce away? The 3d chromosome is the most interesting part of the video and if you can't understand that then I don't know if you understand research.
First video I ever found really explaining evolution in computers. I had to pause the video at 18 min. I got so deep in thinking. I made my own program that simulates evolution. It works. It's briliant too. I'll eventually get into more complex AI. but ohhh man! Thank you for helping me on the first step.
This allows the two solutions I propose: 1) Allow the grid to self-modify. The regions on the grid attempt to reach a stable mutation rate by splitting into finer divisions in areas where a solution cannot be found, and reducing complexity in areas where a solution is found too quickly. This has the twin benefits of allowing the 'problem areas' be more closely approximated, while increasing the efficiency of the DNA structure itself. It also helps avoid local minimum problems.
It would be better to use coordinates that tell the turtle where to travel to next, then convert those to turtle commands. That is way simpler and doesn't lead to the problems of a single mutation affecting the rest of the drawing.
Great and very instructive. i loved how you dealt with the rigidity of code with a 2D chromosom from which you derive code, it gave me lots of ideas ! thanks !
I like how well the two different "chromosomes" used for this problem illustrate an evolutionary problem with real genes (in that it's a problem for the organisms, that is). Your first chromosome was designed simply, but it easily got caught on local maxima because small changes could easily devastate the organism's fitness. This is because the chromosome consisted of a series of commands which were followed to get the final result, which roughly parallels how real genes work. (There's another layer between gene and phenotype in organisms-specifically, protein function-but otherwise, it's a solid approximation.) On the other hand, your second chromosome design was tailor-made for the problem at hand, including a 1:1 map between genes and the problem space, loosely analogous to an organism which literally had separate sets of genes for growing each of its body parts (ie, LEGO Genetics). This makes it harder for the algorithm to be caught on local maxima, which not only dampens the effects of mutation but also allows more and larger mutations to enjoy their beneficial effects without incidentally destroying everything that evolutionary history has built for it. A world where genetics worked more like that, with genomes designed from the ground up to be safe and flexible and allowing for maximum evolution, would be a world with biology that _wasn't_ riddled with weird evolutionary flaws that would be too costly to fix. The idea of using an evolutionary algorithm to optimise (parts of) the chromosome design of your main evolutionary algorithm is also interesting. Obviously, there is no way that real animals with their clunky linear genes could evolve some way of optimizing their genetic structure without incidentally dying because all of their proteins are coming out wrong, but a genome which is designed differently potentially could. Funny how the Intelligent Design folks don't pick up on this sort of thing. If we were designed, we were designed pretty lazily.
I definitely hope you will continue making video's. This was a very interesting approach to evolutionary algorithms. (Definitely saw what you did with the Turing like generalisation.)
To deal with the infinite loop problem, have you considered having two instructions per site, so that if a site is visited more than once it reads the second instruction the second time? To me it seems that this would avoid infinite loops. It would require a rather simple procedure to reconstruct the LOGO instructions regardless of this added complexity. Loved the video though, you make me want to change field :)
Is there any particular reason why the turtle couldn't stop one pixel early and pick up a new set of commands? I mean, it seems that given N pixels which are active on the grid, there are at most N-1 commands required to move a turtle to reach each active pixel.
Regarding the problem of performing recombination of 2D and 3D chromosomes, perhaps you could implement indexing with a Hilbert space-filling curve or a similar space-filling curve to map the genes to a linear chromosome. Then you could simply use linear recombination. Many space-filling curves preserve the spatial (sequential) relationships of their indices (in this case, genes).
2) Each of the 3d chromosomes themselves have a far wider spread of possible values, since they have a far larger set of possible destination squares. Both of these tend towards far more generations to achieve a decent fitness, resulting in a far more difficult fitness curve. I think it is important to remember that the organism does not need to duplicate the image directly, simply have a high fitness result. This allows the organism to generate solutions which are 'close enough'.
I really like your concept of "junk DNA", I like how you speak about how to setup your genes and all. I played a bit with genetic algorithm and the really bad mutation is always my main problem. Most mutation or reproduction ends up being really bad compared to the parent, so my population rapidly converge towards my first "good" DNA, which is not that good really since it didn't evolve much. Most videos mostly talk about the algortihm itself without going into details, mostly not talking about what their genes looks like. Good video, thank you.
Very cool. Couldn't you use an nxnx2 chromosome instead of nxnx3? I am just curious why you decided that h=3 was better than h=2 for solving the eltrut problem.
+fritt wastaken It's usually faster to make up your own question and answer it rather than read and answer it, he asked what he used to make create, not where he got them, idiot.
Purple Ice It's usually faster to make up your own message and start to shittalking rather than understand it? Lol I said nothing about "where he got them"
This video presents brilliant ideas and makes them approachable to layman - which is why the comment section is full of people who think they can do it better than you (but really have no idea what they are talking about).
First off, you detect such problem areas by scoring all organisms by their success not for the drawing as a whole, but based upon subregions. This allows each organism to have an overall fitness rating, while also allowing one to find the location and magnitude of such problem areas. It also allows you to find the areas where a solution to the problem is trivial, and has become 'boilerplate dna' for any successful organism.
Instead of encoding more in the genes to battle that 'dramatic' effect of small gene changes, why not rework the fitness function? Those two zigzag paths ARE very similar if you evaluate similarity based on progressively matching parts of the image under rotations and translations. The less parts are required the better the fitness. You could also try breaking the problem down into steps where the first step involves genetic generation of instructions to match at least part of the image and the second step requires stitching together the results of the first problem, genetically or otherwise.
I agree, this sounds remarkably inefficient. It got me to thinking. What if instead of using “junk” DNA to point to the real DNA here. Why not replicate specific traits and recombine them with an average. For example, instead of one gene for turn one (say turn right) that must be replicated exactly to preserve the following sequence, a successful gene is replicated. So a successful replication will duplicate the gene to give you two turn right genes for the first step. If it is selected 4 times in a row, you will have 4 copies of step #1. You then execute the consensuses for step one. If a mutation changes one of the genes, you still execute the consensus found with the three unaltered genes. Thus the more it is selected, the more robust that step becomes. This is not without its issues however. Not only dose it become more robust, it becomes less flexible and less able to adapt to change. The process might also freeze unfit genes into place. After so many generations, there can be little effective change in the gene sequence.
No, it is VERY unlikely. Because you've come from stable loops in 2D, which simply cannot be escaped without breaking the pattern, to non-stable loops in 3D, which can be escaped with just one random mutation.
you can remove a variable, if instead of if (mode) forward(forwardBy); else right(turnBy); you'd've used forward(forwardBy); right(turnBy); forwardBy = 0; turnBy = 0; or if (mode) forward(num); else right(num); instead. although this kind of optimization may be pointless.
Secondly, since we can score the difficulty of the graph on a per region basis, we can form a fitness function that scores the organisms on that same basis. If an organism evolves a novel solution to a difficult subregion, its dna should be passed on, even if its solutions in other areas is sub-par. In fact, instead of evolving 'organisms' by using a single generic fitness score for an organism, it could selectively pass DNA based on the success of each chromosome vs its competition.
11 ปีที่แล้ว
This is brilliant! I am working on evolutionary algorithms too and this will help a lot, thank you!
Maybe you could select every single gene as a number (or array), made by 3 numbers combined (pen status, rotation and line lenght), treated as a single number, example: 1 bit for pen status, 9 bit without sign for rotation, 6 bit without sign for lenght = total of 2 bytes of data these 3 values might be combined as one number. You can then generate a number of random genes to build your chromosoms, and build your base population. This could be considered as a "basic move". I will follow this path, maybe also adding 2 coordinates for the starting point. an array of these 5 numbers should form my single gene, a chromosom made by M of these genes randomly chosen, a population of N chromosoms could then apply for the fitting function. Depending on the size of each of the 5 parameters you could have a usable number of combinations, as an example, choosing 1 byte for each coordinate, supposing to add the 3 dimensions provided above, your single gene should have a maximum of (2^32 -1) 4294967295 different combinations of values. You can even limit more the number of combinations by limiting rotation and lenght values or decide to use 2 complement to generate negative values. The crossover from two chromosomes in a population, should be performed by swapping the values of these 4 bytes together from one chromosome to another and create new chromosomes. Than you could apply some randomic genetic alteration on single bits of the gene numbers. Does it make sense? Sorry for my poor English. Kind regards.
Benjamin, your video is superb.Very well done and helpful. Now I agree with @regitmail. You can make your genes as complex as you want, and use multidemensionality for your understanding, but in the end you can stake everything as a linear series (eg, for a 3 dimensional 2 by 2: 111=a, 112=b, 121=c, 122=d, 211=e, 212=f, 221=g, 222=h) adding dimensions, just add an index to the name. You can also group numbers to create sub-genes and this kind of funny thing ;) Cheers and keep up the good work.
while having mathematical merit, you will never be able to optimize a system by higher abstraction planes, as they always use more performance. the way to go to optmize a computer program is to run a genetic algoritm on machine code.
Isn't this just the travelling salesman problem? Could you explain why it isn't enough to just find the shortest path between all "on" pixels and then just put a penup command when you're travelling between pixels that aren't nearest neighbours?
Two major problems with the 3d genes. 1) Junk DNA - which he considers a strength (and I would generally agree) is not directly selected or, and thus are not well supported without a large number of generations. The more junk DNA, the greater number of cycles required to actually select for helpful junk. 3d genes have far larger noise:signal ratio, resulting in a far larger number of repetitions required to make use of the junk DNA.
just a suggestion, why not try adding to a pixel's red, green or blue component to a maximum determined by the pen down (eg. if less than 127, add 16 to red) and either play the Dawkins bimorphs style artificial aesthetics OR try match the Mona Lisa ? etc. awesome presentation, I love this field. thanks heaps.
What we need is a nice Java app to see how this operates interactively. Love the idea of using evolution to solve problems and wold like to see this done on an competitive level so people across the internet could design the base chromosome and release it to compete against others on the internet to see how it fairs.
In addition, there is another solution, here. If all of the successful organisms have the exact same deficiency, then obviously, something is wrong with the model.. in this case, a perfect solution to the problem is intractable due to the looping nature of the ideal solution set. GA allow 'close enough' results, which, in turn, allow you to find problem areas in such solutions. There are 2 real solutions that I see.
Wow, that is really cool! ...pretty sure 3D chromosomes is overkill, though. I have an idea: how about each gene is only allowed to be used once per drawing? What I'm saying is, for any given attempt, once the turtle reads a gene, it fades out. Then, if the turtle lands on it again, it could...how about just execute the last instruction again? Or... just keeps going one more space? Hmm...sounded a lot better until the very end there...doesn't even help with the "two squares" issue... ...you know, suddenly, 3D chromosomes don't seem like such a bad idea...
what if each gene was a position, along with information of whether the turtle should draw in that move or not? That way, if you mutated a gene, it wouldn't have incremental changes to the result, as long as instead of using the crossover method to pass down the parent's information, you used random genes in random positions from each parent. I'm a noob so i might not know what i'm talking about but it's an idea. If having few moves was part of the fitness function, you could also have the advantage of generating algorithms with a low memory footprint. If a you had an "off chance" of adding a gene with random information to a child, you could have an unlimited number of moves. I'm not sure about anything anyway.
Well, if each gene was a position, it could still be a "brush stoke". You just needed to translate the point information to data about direction and length of the stroke. Moreover, if you wanted to make it evolve to draw the image in the minimum amount of strokes, you could put efficiency on the fitness function. No?
Paulo Andre Azevedo Quirino -- Oh, you mean having a destination rather than a direction and length? That would effectively be the same thing, but it's clearer.
Well that locks like its gonna need a lot of calculation power why not go a simpler path start with linear DNA of length 2 add a mutation that adds DNA length force the turtle to draw each odd move and to not draw each even move. make the fitness function count the tiles the turtle has moved over by 50% and those untouched by 50% now count the correctly coloured tiles. that should be fairly simple ;)
Nice video, people still visiting it, maybe you do a little writeup of it somewhere too? Probably your non-coding genes is not analogous, or only a bit, to how it functions in actual DNA. Maybe instead of more dimension, have a linear gene again, but each with a position, and if the x,y is high/low you get four quadrants of that gene? Maybe something like that for rotation too? Gets rid of that N².. For practically doing this particular task not sure if this is best. But then maybe the general idea was the real question here anyway.
These solutions are non-exclusive, and analogues to both solutions can be found in nature; the DNA chain itself has evolved over time (solution 1), and numerous species have been shown able to selectively pass DNA (solution 2). This solution never reaches a 'perfect' answer (which GA is notoriously bad at, regardless; just like nature), but instead allows for 'close enough' to become ever closer to perfect.
It's funny because I've been a programmer for about 15 years now and I remember doing the logo turtle in elementary school and I HATED it. Probably because it was finite, the magic of programming imo is that it has rules and it keep going forever. Logo turtle is more an hardcoded thing than a program, but I guess you have to start somewhere, but for me it totally failed to make me grasp programming.
I know this is old but I don't get this. Having a genotype with a search space LARGER than the bitmap makes no sense whatsoever. This can be solved using much simpler models. I once tried similar work on a game-of-life based compression, but stopped early because i could demonstrate that the method really wasn't working. The 3d solution is a good extension though, but the basic ideas are wrong. The first model (linear) would have been a lot better, and should have been pursued. All the comments on how to solve crossover and mutations are sort of unecessary. The model is what's most important.
The brush strokes used to create the 2D bitmap are more complex than procedural 2D gene maps can encode. You need more info per location, either more locations, as 3D stacked planes, or dynamic genes that change expression with conditions or feedback.
Niklas Jansson Hello? Have you watched the video? 8:25? 16:34? Why would you limit genotypes if that will cause huge problems in evolutionary process? Or you know a solution to these problems?
Okay, so we should be careful about what we say. If the goal is to make a robot draw actual lines, that's one story. This is obviously not the goal, but the video isn't really clear, and I don't know the actual point of this algorithm (it was a year since I saw it, it might have missed it). If the goal is to create an algorithm that somehow replicates a bitmap using "logo syntax", its better to skip EA and just walk through the array, say in a spiral or zig-zag pattern, and perhaps use some run-length encoding. Note that the fitness in the described solution is on _correctness_, not number of steps. The problem at 8:25 is an obvious marker of a bad representation, but the 2D one is a very weird solution. A perhaps better, would be to let the genotype be an ordered sequence of points, with a boolean marker for pen down/up, and then a transformation on that to get the "logo syntax". That would solve both problems.
I still don't understand why you took the leap to 3d... Any entity that reaches an infinite loop solution would not reach solution, and given that each entity would be allowed xx cycles to run, they would not even suck up resources. Any entity trapped like this would be weeded out of the breeding pool by the fitness function... so there is no reason to expand your chromosonal design to account for it exclusively.
fascinating. Why do you discard 50% in the fitness test? (Im guessing that this process itself must be an evolutionary algorithm in the natural world) When it comes to computing though, why cant you compute the entire matrix. For example, we might discard downs syndrome - but there may be significant advantages that we are both unaware of and don't have the clairvoyance to know. For example the asteroid theory that killed off the dinosaurs, though not specifically an evolutionary event, steered the evolution matrix. That is, derivatives of t-rex for example, are forever lost. Seems to me then, that there is a evolutionary algorithm to best "compute" the most appropriate algorithm. Trouble is, humans have judgement about what "best" or "favorable" is, whereas the most appropriate may be some other metric. I note this video is couple of years old - what are you working on now? Rgds, and thanks v much for sharing.
You can´t compute all algorithms. If you half the number of genes you half the number of calculation but the probability to success in the next generation goes down by less than a half.
I love how in his 2D gene example he's rigged the game by showing an example where all the "junk dna" is pointing in the direction that helps the coding dna. In a real example where you start with completely random inputs I imagine you would have just as much trouble as a 1d gene.
Your linear chromosomes worked perfectly fine. Unfortunately the purpose of natural selection is to create organisms that survive, not produce perfect organisms. This is why you could only achieve command lines that were almost right, but never a perfect one.
I think evolutionary algorithm should be renamed to creation algorithm since there is no such thing as evolution without creationism. the creator had to input data for it to do anything at all.
Alex Terzaghi the only stupid is you. it is creation since the program was created, the data inputs for what the simulations should be doing or looking for is created. even the graphics is created. there is no such thing as evolution. Even the hardware is created and since its a computer it will always have a pre-defined set of outcomes since computers can not create random numbers. There is no such thing as evolution in computers simulation, it is called Creationism.
This is absolutely brilliantly explained. The mouse on screen and motion and the way you broke down your discussion and argument is incredible.
After having watched many evolutionary and neural network videos, I can say that most are less than half this long and less than half as informed and clear.
No more videos? I was hoping to see the results of the experiment. Good work, though.
This was dope af. Good job!
Rather than using a predfined number of moves, why not allow the number of moves to evolve as well.
That's what i thought, too. Though i'm not sure how that information would be passed down from parent to child.
I've thought of this too, and it could be useful if implemented effectively. However, I can't think of a way to do so.
Here's an idea: You could give the turtle an "energy" value. Each gene/cell on the grid has an energy cost that is subtracted from the turtle's energy when the turtle moves to (or from, maybe) that cell. When the turtle's energy is gone, it stops. The energy value for each cell could then evolve independently.
@@kamoroso94 you could probably just throw it in and randomly lengthen/shorten by one/randomly select which for sexual reproduction. At first sight, it doesn't seem this would be hugely problematic?
Where can I find the relating videos you refer to? I would very much like to watch them!
Finally, this solution fights local minimum problems, and directly focuses the evolutionary efforts of each organism towards their greatest challenges. This increases evolutionary efficiency.
I have some criticism that I hope you take as constructive since it is meant that way. You have a number of paradigm issues. (I have degrees in math and genetics btw).
1) You are starting with the ideal solution, and trying to evolve towards that. Genetic algorithms find novel solutions that are robust through diversity. You need to relinquish control and allow the algorithm to find its own solution, otherwise you have just found the most complicated method for solving optimization problems.
2) You are stuck in the common mathematical "generalize" and "reduce" mindset. Too often mathematicians produce some beautiful piece of reduced math and forget that each element is a complicated function in its own right, and resolving the simple function requires a boatload of work that can be computationally expensive behind the scenes.
3) You are trying to mimic natural selection, but your understanding of genetics is too weak. As and example, the height of a plant is base on the number of "height" genes it contains. The more "height" genes, the taller the plant within a min/max bound. There are very few single point mutations in any organism that can have a large impact on phenotype.
You should either learn more genetics and do a better job of adding complexity in certain areas (nothing novel here), or fully deconstruct evolution and start from the ground up (novel, and PhD worthy if you succeed).
4) Your 3d chromosome is a symptom of all of the above. You are attempting to contrive the ideal solution that you have already solved, discovered that your reduced function requires tons of background work and then finding a horribly complicated and expensive method.
Rather than try to map directly from genome to bitmap, try to use a simpler stimulus/response algorithm.
"here I am, what now?"
>>What does the environment look like?
"The environment looks like this."
>>Read genome
"I will do this because my genome says to do this in this environment."
An algorithm like this will jump the loop easily and get you around the local max problems that genetic algorithms are plagued with
joshua43214
very nice criticism i would agree with. There are certainly many better ways to solve this problem. It's almost the *Travelling Salesman Problem* at this point.
especially so with the *environment checking*, that would make it able to *avoid overfitting*, and be used on *multiple images* without much evolution.
How is he starting with the ideal solution? What underlying complexity did he reduce away?
The 3d chromosome is the most interesting part of the video and if you can't understand that then I don't know if you understand research.
First video I ever found really explaining evolution in computers. I had to pause the video at 18 min. I got so deep in thinking. I made my own program that simulates evolution. It works. It's briliant too. I'll eventually get into more complex AI. but ohhh man! Thank you for helping me on the first step.
+deleteaman although my DNA was only 1 dimensional
+deleteaman All that matters is that it's working ^^
The simplest you get it to work well, the better :)
lol I wish I could say it was working. but the program is flawed.
Gave phone number and email on a youtube video. RIP
Rooket6 People might confuse him with the other 'Bush'...
+Bungis Albondigas Nascar driver Reggie Bush?
+Rooket6 i hope you realise that this is apart of his portfolio... thats how you get a job.
This allows the two solutions I propose:
1) Allow the grid to self-modify. The regions on the grid attempt to reach a stable mutation rate by splitting into finer divisions in areas where a solution cannot be found, and reducing complexity in areas where a solution is found too quickly.
This has the twin benefits of allowing the 'problem areas' be more closely approximated, while increasing the efficiency of the DNA structure itself.
It also helps avoid local minimum problems.
The problem presented at 17:12 reminds me of the puzzles in SpaceChem
Was this video narrated by a voice generating software developed through evolutionary algorithms similar to this method?
It would be better to use coordinates that tell the turtle where to travel to next, then convert those to turtle commands. That is way simpler and doesn't lead to the problems of a single mutation affecting the rest of the drawing.
Technically, he is using polar coordinates. The difference between polar and Cartesian coordinates would be subtle at best.
When are you going to post new video? We are all waiting :-)
Great and very instructive. i loved how you dealt with the rigidity of code with a 2D chromosom from which you derive code, it gave me lots of ideas !
thanks !
I like how well the two different "chromosomes" used for this problem illustrate an evolutionary problem with real genes (in that it's a problem for the organisms, that is). Your first chromosome was designed simply, but it easily got caught on local maxima because small changes could easily devastate the organism's fitness. This is because the chromosome consisted of a series of commands which were followed to get the final result, which roughly parallels how real genes work. (There's another layer between gene and phenotype in organisms-specifically, protein function-but otherwise, it's a solid approximation.)
On the other hand, your second chromosome design was tailor-made for the problem at hand, including a 1:1 map between genes and the problem space, loosely analogous to an organism which literally had separate sets of genes for growing each of its body parts (ie, LEGO Genetics). This makes it harder for the algorithm to be caught on local maxima, which not only dampens the effects of mutation but also allows more and larger mutations to enjoy their beneficial effects without incidentally destroying everything that evolutionary history has built for it. A world where genetics worked more like that, with genomes designed from the ground up to be safe and flexible and allowing for maximum evolution, would be a world with biology that _wasn't_ riddled with weird evolutionary flaws that would be too costly to fix.
The idea of using an evolutionary algorithm to optimise (parts of) the chromosome design of your main evolutionary algorithm is also interesting. Obviously, there is no way that real animals with their clunky linear genes could evolve some way of optimizing their genetic structure without incidentally dying because all of their proteins are coming out wrong, but a genome which is designed differently potentially could.
Funny how the Intelligent Design folks don't pick up on this sort of thing. If we were designed, we were designed pretty lazily.
13:23 the turtle moved in the wrong direction.
I definitely hope you will continue making video's.
This was a very interesting approach to evolutionary algorithms. (Definitely saw what you did with the Turing like generalisation.)
To deal with the infinite loop problem, have you considered having two instructions per site, so that if a site is visited more than once it reads the second instruction the second time? To me it seems that this would avoid infinite loops. It would require a rather simple procedure to reconstruct the LOGO instructions regardless of this added complexity.
Loved the video though, you make me want to change field :)
Is there any particular reason why the turtle couldn't stop one pixel early and pick up a new set of commands? I mean, it seems that given N pixels which are active on the grid, there are at most N-1 commands required to move a turtle to reach each active pixel.
this is certainly a more elegant solution, especially if you visit a cell n times you get n different directions
Regarding the problem of performing recombination of 2D and 3D chromosomes, perhaps you could implement indexing with a Hilbert space-filling curve or a similar space-filling curve to map the genes to a linear chromosome. Then you could simply use linear recombination. Many space-filling curves preserve the spatial (sequential) relationships of their indices (in this case, genes).
2) Each of the 3d chromosomes themselves have a far wider spread of possible values, since they have a far larger set of possible destination squares.
Both of these tend towards far more generations to achieve a decent fitness, resulting in a far more difficult fitness curve.
I think it is important to remember that the organism does not need to duplicate the image directly, simply have a high fitness result. This allows the organism to generate solutions which are 'close enough'.
This video has been very inspiring.
I really like your concept of "junk DNA", I like how you speak about how to setup your genes and all. I played a bit with genetic algorithm and the really bad mutation is always my main problem. Most mutation or reproduction ends up being really bad compared to the parent, so my population rapidly converge towards my first "good" DNA, which is not that good really since it didn't evolve much. Most videos mostly talk about the algortihm itself without going into details, mostly not talking about what their genes looks like.
Good video, thank you.
I think, one could also use a changing color in the Master bitmap and the pen, in order to prevent a local maximum.
Very cool. Couldn't you use an nxnx2 chromosome instead of nxnx3? I am just curious why you decided that h=3 was better than h=2 for solving the eltrut problem.
If I start with random and preserve the longest novel strings as "genes" How do i simulate a need for resources?
Benjamin, what did you use to create graphics?
It's usually much easier and faster for the programmer to make graphics by himself rather than searching for a soft to use.
+fritt wastaken It's usually faster to make up your own question and answer it rather than read and answer it, he asked what he used to make create, not where he got them, idiot.
+fritt wastaken
Thats like someone asking "did you draw that in MS paint" and you replying I drew it myself lolwut?
Ghost Emblem Well I could've draw it without any soft right? So there's the same.
Purple Ice It's usually faster to make up your own message and start to shittalking rather than understand it? Lol
I said nothing about "where he got them"
This video presents brilliant ideas and makes them approachable to layman - which is why the comment section is full of people who think they can do it better than you (but really have no idea what they are talking about).
For the linear chromosome model, would some of the problems be fixed if each gene encodes both a move and a turn?
Very nice video.
Okay, Preserving the longest novel random string smulates ability to acquire resources. Resource resource depletion "demand" is implied right?
First off, you detect such problem areas by scoring all organisms by their success not for the drawing as a whole, but based upon subregions.
This allows each organism to have an overall fitness rating, while also allowing one to find the location and magnitude of such problem areas.
It also allows you to find the areas where a solution to the problem is trivial, and has become 'boilerplate dna' for any successful organism.
Amazing work, thanks for sharing. I would love to experiment with your ideas with robotics.
Instead of encoding more in the genes to battle that 'dramatic' effect of small gene changes, why not rework the fitness function? Those two zigzag paths ARE very similar if you evaluate similarity based on progressively matching parts of the image under rotations and translations. The less parts are required the better the fitness. You could also try breaking the problem down into steps where the first step involves genetic generation of instructions to match at least part of the image and the second step requires stitching together the results of the first problem, genetically or otherwise.
This should be taught to everyone. It explains life.
i dont see how adding a dimension fixes the loop vulnerability
its still very likely if you do millions of generations
I agree, this sounds remarkably inefficient. It got me to thinking. What if instead of using “junk” DNA to point to the real DNA here. Why not replicate specific traits and recombine them with an average.
For example, instead of one gene for turn one (say turn right) that must be replicated exactly to preserve the following sequence, a successful gene is replicated. So a successful replication will duplicate the gene to give you two turn right genes for the first step.
If it is selected 4 times in a row, you will have 4 copies of step #1. You then execute the consensuses for step one.
If a mutation changes one of the genes, you still execute the consensus found with the three unaltered genes. Thus the more it is selected, the more robust that step becomes.
This is not without its issues however. Not only dose it become more robust, it becomes less flexible and less able to adapt to change. The process might also freeze unfit genes into place. After so many generations, there can be little effective change in the gene sequence.
No, it is VERY unlikely. Because you've come from stable loops in 2D, which simply cannot be escaped without breaking the pattern, to non-stable loops in 3D, which can be escaped with just one random mutation.
you can remove a variable, if instead of
if (mode)
forward(forwardBy);
else
right(turnBy);
you'd've used
forward(forwardBy);
right(turnBy);
forwardBy = 0;
turnBy = 0;
or
if (mode)
forward(num);
else
right(num);
instead. although this kind of optimization may be pointless.
Secondly, since we can score the difficulty of the graph on a per region basis, we can form a fitness function that scores the organisms on that same basis.
If an organism evolves a novel solution to a difficult subregion, its dna should be passed on, even if its solutions in other areas is sub-par.
In fact, instead of evolving 'organisms' by using a single generic fitness score for an organism, it could selectively pass DNA based on the success of each chromosome vs its competition.
This is brilliant! I am working on evolutionary algorithms too and this will help a lot, thank you!
very interestring and abstract solution to many problems.
Maybe you could select every single gene as a number (or array), made by 3 numbers combined (pen status, rotation and line lenght), treated as a single number, example: 1 bit for pen status, 9 bit without sign for rotation, 6 bit without sign for lenght = total of 2 bytes of data these 3 values might be combined as one number. You can then generate a number of random genes to build your chromosoms, and build your base population. This could be considered as a "basic move".
I will follow this path, maybe also adding 2 coordinates for the starting point. an array of these 5 numbers should form my single gene, a chromosom made by M of these genes randomly chosen, a population of N chromosoms could then apply for the fitting function.
Depending on the size of each of the 5 parameters you could have a usable number of combinations, as an example, choosing 1 byte for each coordinate, supposing to add the 3 dimensions provided above, your single gene should have a maximum of (2^32 -1) 4294967295 different combinations of values.
You can even limit more the number of combinations by limiting rotation and lenght values or decide to use 2 complement to generate negative values.
The crossover from two chromosomes in a population, should be performed by swapping the values of these 4 bytes together from one chromosome to another and create new chromosomes. Than you could apply some randomic genetic alteration on single bits of the gene numbers.
Does it make sense?
Sorry for my poor English.
Kind regards.
Benjamin, your video is superb.Very well done and helpful. Now I agree with @regitmail. You can make your genes as complex as you want, and use multidemensionality for your understanding, but in the end you can stake everything as a linear series (eg, for a 3 dimensional 2 by 2: 111=a, 112=b, 121=c, 122=d, 211=e, 212=f, 221=g, 222=h) adding dimensions, just add an index to the name. You can also group numbers to create sub-genes and this kind of funny thing ;) Cheers and keep up the good work.
Hey man, I liked this video a lot. When is the next video coming out? :)
while having mathematical merit, you will never be able to optimize a system by higher abstraction planes, as they always use more performance. the way to go to optmize a computer program is to run a genetic algoritm on machine code.
Isn't this just the travelling salesman problem? Could you explain why it isn't enough to just find the shortest path between all "on" pixels and then just put a penup command when you're travelling between pixels that aren't nearest neighbours?
I can remember using logo in school computer club back in the 80's. It was bundled with the apple IIe.
+Mick Wright Do you mean Terrapin Logo? On of our Teachers still uses it :) (Germany)
Not sure which one... hey it was decades ago...
This video is so great. I feel sorry for everyone who has not seen it yet.
Two major problems with the 3d genes.
1) Junk DNA - which he considers a strength (and I would generally agree) is not directly selected or, and thus are not well supported without a large number of generations.
The more junk DNA, the greater number of cycles required to actually select for helpful junk.
3d genes have far larger noise:signal ratio, resulting in a far larger number of repetitions required to make use of the junk DNA.
just a suggestion, why not try adding to a pixel's red, green or blue component to a maximum determined by the pen down (eg. if less than 127, add 16 to red) and either play the Dawkins bimorphs style artificial aesthetics OR try match the Mona Lisa ? etc. awesome presentation, I love this field. thanks heaps.
What we need is a nice Java app to see how this operates interactively. Love the idea of using evolution to solve problems and wold like to see this done on an competitive level so people across the internet could design the base chromosome and release it to compete against others on the internet to see how it fairs.
Why not use another movement type where the turtle jumps? That way there is still only a 2D space regarding the genes.
so.... almost 5 years later, where's that "future video"?
In addition, there is another solution, here.
If all of the successful organisms have the exact same deficiency, then obviously, something is wrong with the model.. in this case, a perfect solution to the problem is intractable due to the looping nature of the ideal solution set.
GA allow 'close enough' results, which, in turn, allow you to find problem areas in such solutions.
There are 2 real solutions that I see.
Wow, that is really cool! ...pretty sure 3D chromosomes is overkill, though. I have an idea: how about each gene is only allowed to be used once per drawing? What I'm saying is, for any given attempt, once the turtle reads a gene, it fades out. Then, if the turtle lands on it again, it could...how about just execute the last instruction again? Or... just keeps going one more space? Hmm...sounded a lot better until the very end there...doesn't even help with the "two squares" issue...
...you know, suddenly, 3D chromosomes don't seem like such a bad idea...
what if each gene was a position, along with information of whether the turtle should draw in that move or not? That way, if you mutated a gene, it wouldn't have incremental changes to the result, as long as instead of using the crossover method to pass down the parent's information, you used random genes in random positions from each parent. I'm a noob so i might not know what i'm talking about but it's an idea. If having few moves was part of the fitness function, you could also have the advantage of generating algorithms with a low memory footprint. If a you had an "off chance" of adding a gene with random information to a child, you could have an unlimited number of moves. I'm not sure about anything anyway.
I think the point of this algorithm is to recreate the brush strokes, not copy the image.
Well, if each gene was a position, it could still be a "brush stoke". You just needed to translate the point information to data about direction and length of the stroke. Moreover, if you wanted to make it evolve to draw the image in the minimum amount of strokes, you could put efficiency on the fitness function. No?
Paulo Andre Azevedo Quirino -- Oh, you mean having a destination rather than a direction and length? That would effectively be the same thing, but it's clearer.
Yeah that's what i ment :P thanks.
17:31 wuthering about 4D XD
Well that locks like its gonna need a lot of calculation power
why not go a simpler path start with linear DNA of length 2 add a mutation that adds DNA length
force the turtle to draw each odd move and to not draw each even move.
make the fitness function count the tiles the turtle has moved over by 50% and those untouched by 50%
now count the correctly coloured tiles.
that should be fairly simple ;)
Nice video, people still visiting it, maybe you do a little writeup of it somewhere too?
Probably your non-coding genes is not analogous, or only a bit, to how it functions in actual DNA.
Maybe instead of more dimension, have a linear gene again, but each with a position, and if the x,y is high/low you get four quadrants of that gene? Maybe something like that for rotation too? Gets rid of that N²..
For practically doing this particular task not sure if this is best. But then maybe the general idea was the real question here anyway.
i am now very tempted to build this in second life script, easily showing it in a 3d environment.
such a great video!
These solutions are non-exclusive, and analogues to both solutions can be found in nature; the DNA chain itself has evolved over time (solution 1), and numerous species have been shown able to selectively pass DNA (solution 2).
This solution never reaches a 'perfect' answer (which GA is notoriously bad at, regardless; just like nature), but instead allows for 'close enough' to become ever closer to perfect.
It's funny because I've been a programmer for about 15 years now and I remember doing the logo turtle in elementary school and I HATED it. Probably because it was finite, the magic of programming imo is that it has rules and it keep going forever. Logo turtle is more an hardcoded thing than a program, but I guess you have to start somewhere, but for me it totally failed to make me grasp programming.
You are party to the machine apocalypse! I hope you're happy with yourself!
I know this is old but I don't get this. Having a genotype with a search space LARGER than the bitmap makes no sense whatsoever. This can be solved using much simpler models.
I once tried similar work on a game-of-life based compression, but stopped early because i could demonstrate that the method really wasn't working.
The 3d solution is a good extension though, but the basic ideas are wrong. The first model (linear) would have been a lot better, and should have been pursued.
All the comments on how to solve crossover and mutations are sort of unecessary. The model is what's most important.
But he showed exact benefits of 2D and 3D genotypes. You cannot achieve this with small genotypes.
The brush strokes used to create the 2D bitmap are more complex than procedural 2D gene maps can encode. You need more info per location, either more locations, as 3D stacked planes, or dynamic genes that change expression with conditions or feedback.
That's bullshit. The brush strokes are completely determined by n^2 bits and it's dead simple to create a sequence of brush strokes from them.
Niklas Jansson Hello? Have you watched the video? 8:25? 16:34?
Why would you limit genotypes if that will cause huge problems in evolutionary process? Or you know a solution to these problems?
Okay, so we should be careful about what we say.
If the goal is to make a robot draw actual lines, that's one story.
This is obviously not the goal, but the video isn't really clear, and I don't know the actual point of this algorithm (it was a year since I saw it, it might have missed it).
If the goal is to create an algorithm that somehow replicates a bitmap using "logo syntax", its better to skip EA and just walk through the array, say in a spiral or zig-zag pattern, and perhaps use some run-length encoding. Note that the fitness in the described solution is on _correctness_, not number of steps.
The problem at 8:25 is an obvious marker of a bad representation, but the 2D one is a very weird solution. A perhaps better, would be to let the genotype be an ordered sequence of points, with a boolean marker for pen down/up, and then a transformation on that to get the "logo syntax". That would solve both problems.
Its beautiful.
I still don't understand why you took the leap to 3d...
Any entity that reaches an infinite loop solution would not reach solution, and given that each entity would be allowed xx cycles to run, they would not even suck up resources.
Any entity trapped like this would be weeded out of the breeding pool by the fitness function... so there is no reason to expand your chromosonal design to account for it exclusively.
shall i know u r mail id plz...
it is not clear inthe video. bcoz i have some doubts regarding this
Terrific video -
fascinating. Why do you discard 50% in the fitness test? (Im guessing that this process itself must be an evolutionary algorithm in the natural world) When it comes to computing though, why cant you compute the entire matrix. For example, we might discard downs syndrome - but there may be significant advantages that we are both unaware of and don't have the clairvoyance to know. For example the asteroid theory that killed off the dinosaurs, though not specifically an evolutionary event, steered the evolution matrix. That is, derivatives of t-rex for example, are forever lost. Seems to me then, that there is a evolutionary algorithm to best "compute" the most appropriate algorithm. Trouble is, humans have judgement about what "best" or "favorable" is, whereas the most appropriate may be some other metric. I note this video is couple of years old - what are you working on now? Rgds, and thanks v much for sharing.
You can´t compute all algorithms. If you half the number of genes you half the number of calculation but the probability to success in the next generation goes down by less than a half.
Amazing!
I love how in his 2D gene example he's rigged the game by showing an example where all the "junk dna" is pointing in the direction that helps the coding dna. In a real example where you start with completely random inputs I imagine you would have just as much trouble as a 1d gene.
I'm 12, why the fuck am I here?
learning!
There is no too early.
...
O.K., there is :D but not as much as one might think.
im 11 and im intrested
I remember how gangsta I was when I cursed as a 12 year old.
You just *had* to use the F word in a comment on a college presentation...
myBrain.exe stopped working!
Mind blow
"We'll be discussing in my next video" - Never posts another video, lol...
nice!
amen.
Your linear chromosomes worked perfectly fine. Unfortunately the purpose of natural selection is to create organisms that survive, not produce perfect organisms. This is why you could only achieve command lines that were almost right, but never a perfect one.
And i thought i am smart... i hardly got it! ^_^
wow...
ogm; you have added more dimensions, and there is some very high complexity. u r going to run out of nucleotides to make yur chromosomes.
Man, your faith in humanity is way too high, dont put your cellphone number on a youtube video :P
I think evolutionary algorithm should be renamed to creation algorithm since there is no such thing as evolution without creationism. the creator had to input data for it to do anything at all.
I can't tell if this is ironically stupid or actually stupid, could you please clarify this point.
+Alex Terzaghi yeah, we need the answer to that question...
Alex Terzaghi the only stupid is you. it is creation since the program was created, the data inputs for what the simulations should be doing or looking for is created. even the graphics is created. there is no such thing as evolution.
Even the hardware is created and since its a computer it will always have a pre-defined set of outcomes since computers can not create random numbers.
There is no such thing as evolution in computers simulation, it is called Creationism.
MrPepsicola123 The algorithm is LITERALLY the theory of evolution.
moonorc so its false.