7 ms·

Evolutionary Algorithm: Evolving "Hello, World"

117 points by Garbage 15y ago

kailashbuki 15y ago
For absolute beginners, here's a simple example i worked on about a year ago ... http://www.kailashbudhathoki.com.np/2010/07/genetic-algorithm-example-displaying.html http://www.kailashbudhathoki.com.np/2010/07/genetic-algorith...
mason55 15y ago
Effectively, we square each difference so that they can't cancel each other out. He seems to sort of confuse himself here, at first he says the squaring is so that it emphasizes bigger differences, then he says it's to make positive & negative cancel each other out. I think that the second part is just a nice bonus to the first part, but I don't get why he doesn't just use the absolute value of the distance anyway. "Hellp" is no more or less fit than "Helln". The crossover and mutate are sort of mashed together and could be made much more robust. For example, giving each gene a random chance to mutate would do a much better job at keeping the populations from evolving into one big similar mass. This is a good start but leaves a lot to be done for any sort of real implementation of a genetic algorithm.
- tel 15y ago
  If we're going to talk loss functions, then 1-0 loss is most appropriate here. As you say, "Hellp" is really no more or less fit than "Helln" whereas even absolute distance wouldn't reflect that. Squaring admits a function into the class of loss functions which must be strictly non-negative to be meaningful, but really it's just always been done to make derivatives easy. If you don't need derivatives (or expectations), you can probably get away without using squared loss if you don't want it.
piaskal 15y ago
This is a nice example of simple evolutionary algorithm. Next steps could be separating crossover and mutate operations, selecting more parent pairs for crossover and applying mutation in a more random fashion (not with every crossover).
juretriglav 15y ago
Evolutionary algorithms are fun. I solved a laser ablation modeling problem with them. The idea was to improve the quality of the produced data, by applying what knowledge of the process we had. Laser ablation measurements work something like this: Sample -> Ablation -> Measurement -> Data Since there are several distortions that happen in the middle two steps, you of course get a distorted measurement. You'd like to get the Sample from the Data. Since we know pretty well what happens in the middle two steps, I evolved my theoretical Sample by starting with random data, running it through the model of the middle two steps (ablation and measurement) and then comparing the modeled random data to the experimental data. The fitness function was exactly this difference between experimental and modeled data. I took the best ones of each generation and crossed them over. I then added some mutations and watched the magic happen. It ended up taking most of the night for a very simple set (our experimental sets are mostly orders of magnitude bigger). I took screenshots of every new generation, and made a movie of the whole process. When I played the movie in the morning I had one of those rare and special Eureka! moments, when all that work pays off and then some. I presented that movie at a conference and stole the show :) Long story short, evolutionary algorithms are fun, but I failed to apply them at the required scale.
perone 15y ago
Using Python Pyevolve framework: http://pyevolve.sourceforge.net/0_6rc1/examples.html#example-22-the-infinite-monkey-theorem http://pyevolve.sourceforge.net/0_6rc1/examples.html#example...
jessedhillon 15y ago
If you look closely, you'll notice that for each character, I square the difference. This is to to put extra emphasis on larger differences. If we don't do this, the string "Hannp" would have a fitness of 0. You see, the difference between 'e' and 'a' is -5, between 'l' and 'n' is +2 (which we have twice) and between 'o' and 'p' is +1. Adding these up yields a fitness of 0, but it's not the string we want at all. Squaring is a dumb way to avoid that problem. You can still have false positives: for example if a string differs from the target by two letters, who distances are +1 and -1, then squaring will not mitigate the issue. EDIT: I realize now that -1^2 is a positive number... I'm very surprised that the author doesn't know about the Levenshtein distance metric http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance That seems like it would be the perfect utility function for this case.
- sparky 15y ago
  Err.. I would argue that (+1)^2+(-1)^2 would not yield a false positive. You are right that the explanation is incomplete, though. The squaring provides an 'absolute value' effect as well as disproportionately weighting larger alphabetical distances.
- mahcuz 15y ago
  Regarding the squaring - would it be enough to take the absolute value of the distance? (abs -5) + (abs 5) = 10.
  - jessedhillon 15y ago
    It's still a problematic way to quantify distance between strings. It says that "Rello World" is as close to the target as "Ifmkn Vpqkc" Levenshtein would quantify those differently, and I'd argue, more correctly. It would say the first is much closer than the second.
koryk 15y ago
I came across this example before when I was writing a small genetic algorithm library in js. https://github.com/koryk/evolvejs https://github.com/koryk/evolvejs I wrote a few examples as well. tic-tac-toe: http://www.korykirk.com/evolvejs/examples/tic-tac-toe/tic-tac-toe.html http://www.korykirk.com/evolvejs/examples/tic-tac-toe/tic-ta... circle: http://www.korykirk.com/evolvejs/examples/circle/circlega.html http://www.korykirk.com/evolvejs/examples/circle/circlega.ht...
bekirdag 15y ago
here is the same algorithm in php http://www.bekirdag.com/en/php_mysql/a_hello_world_genetic_algorithm_example_in_php.html http://www.bekirdag.com/en/php_mysql/a_hello_world_genetic_a...
tariqk 15y ago
That's a pretty interesting look into what happens in an evolutionary algorithm. But for a minute there I was hoping that the OP was going to evolve an actual "hello world" program. That might be an interesting exercise to do over a Lisp-like language.
- rmc 15y ago
  A lot of programmes have a regular grammer & parsers for their language. You can then use parsers and the like to turn a tree into a source code (and vice versa) and evolve programmes.
- user24 15y ago
  yeah I think genetic programming is often done with Lisp.
  - dmoney 15y ago
    I don't see a reason to write the genetic algorithm in Lisp, but for the code that's being evolved it seems like the logical choice due to its minimal syntax. I'm working on a PHP program for evolving programs, and the evolved programs are in a lisp-like dialect made for just that purpose.
    - user24 15y ago
      IIRC it's something to do with the fact that lisp can easily be represented as a tree and so crossover is very simple; just swap branches. I don't know lisp so I'm just regurgitating info I picked up at university.
      - kruhft 15y ago
        One problem with using that technique is that it's has been patented, along with derivatives of it, for quite a while.
- tomjen3 15y ago
  Somebody actually did that, in Lisp, to be able to write a hello world program in a completely fucked out language. The problem with just generating a hello world program is that there is no guarantee that you wont end up with a bunch of endless loops.
user24 15y ago
I did the same in Javascript a while ago with a genetic algorithm. http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/ http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hel... (HN discussion: http://news.ycombinator.com/item?id=2002673 http://news.ycombinator.com/item?id=2002673) Again just evolving a string not a full program. Mine hit the target significantly faster than OPs (around 70 generations rather than between 2 and 4 thousand). I'm trying to work out where he went wrong. First of all his 'mutate' function in the second example is actually performing both mutation and crossover. As far as the mutation goes it looks fine; almost identical to the way I mutate genes. I think the problem lies in the way he's doing his crossover (breeding), just trying to work it out. He's using one-point crossover, same as me. The selection method is a kind of hybrid elite method where fitter members are more likely to be selected than unfit members, which is reasonable. It might just be that his crossover and mutation probability is 100% and his population is only 20. But if you plug those figures into the interactive demo on my post (http://www.puremango.co.uk/genetic-hello-world.html http://www.puremango.co.uk/genetic-hello-world.html) then it gets as far as "Hbumr Xqnkd" by the 70th generation. Still looks like it's evolving faster than his code. Must be the way he's selecting parents...
- pgroves 15y ago
  I would agree. With a population size of only 20 the algorithm is closer to being hill-climbing with random restart. Crossover can't do much if there isn't a lot of diversity in the population, and a small population can't be very diverse. But it still worked.
  - smoyer 15y ago
    And ... throwing away the least fit every time can lead you to climb the hill to a local maxima. In this case, the only way to leave a local maxima is to get lucky with a mutation, but if you cull the population randomly with a log probability that more fit parents will be kept, you could reach the goal in fewer generations. You could even eliminate mutations altogether if you have the proper character in each position in at least one member of the starting population.
  - 15y ago
andrewcooke 15y ago
if anyone's interested, i evolved a program in malbolge (an esoteric language - http://www.lscheffer.com/malbolge.shtml http://www.lscheffer.com/malbolge.shtml) that prints "HEllO WORld" - see http://acooke.org/malbolge.html http://acooke.org/malbolge.html this was years ago, the work was done in lisp, and not long afterwards someone sent me a better solution that they had done by hand...
- jcmoscon 15y ago
  I bet you put a lot of effort to program this, eh? I think we can say that this is an argument in favor of intelligent design.
- cpeterso 15y ago
  You are too modest. Wikipedia says you wrote (or generated) the first Malbolge program: Malbolge was so difficult to understand when it arrived (in 1998) that it took two years for the first Malbolge program to appear. The program was not even written by a human being: it was generated by a beam search algorithm designed by Andrew Cooke. https://secure.wikimedia.org/wikipedia/en/wiki/Malbolge https://secure.wikimedia.org/wikipedia/en/wiki/Malbolge
TomNomNom 15y ago
I wrote something similar with a slightly longer string in PHP a while back. Read: http://www.tomnomnom.com/posts/methinks_it_is_like_an_incestuous_weasel http://www.tomnomnom.com/posts/methinks_it_is_like_an_incest... Code: https://github.com/TomNomNom/PHP-Evolution-Sim https://github.com/TomNomNom/PHP-Evolution-Sim
maeon3 15y ago
I want a program that will take a set of unit tests, and create a program that takes a piece of code and evolves it until all those tests pass. And I want to be able to guide its evolution, prompt it to use certain technologies in certain places.
- nydev 15y ago
  Sure..and put the rest of us out of business? : ) Although it is interesting to think about what the make-up of the genetic material would be. Just a string of 0s and 1s? CPU opcodes? Or maybe some higher level sub-units.
  - jacques_chester 15y ago
    > Just a string of 0s and 1s? CPU opcodes? These have been tried. Historically Genetic Algorithms have represented their genotypes as bit strings. Some Genetic Programming systems use CPU instruction strings (pros: fast as heck, cons: can produce indecipherable spaghetti code that breaks when you remove those 400 NOOPs because it's adapted to the cache size of this particular CPU). > Or maybe some higher level sub-units. These too. Sometimes as trees of instructions, dataflow diagrams, FSMs and so on.
    - nydev 15y ago
      Very interesting.."indecipherable spaghetti code that breaks when you remove those 400 NOOPs because it's adapted to the cache size of this particular CPU" - sounds a little like our "junk" DNA (though I suspect the analogy breaks down in the details.)
      - jacques_chester 15y ago
        It can get pretty Rube Goldbergesque, apparently. The main rule of thumb is that if you're doing GP with CPU strings as your representation, beware of including run time in the fitness function. Because you will almost inevitably get over adaptation that breaks on any other platform.

117 points by Garbage 15y ago

For absolute beginners, here's a simple example i worked on about a year ago ... http://www.kailashbudhathoki.com.np/2010/07/genetic-algorithm-example-displaying.html http://www.kailashbudhathoki.com.np/2010/07/genetic-algorith...

mason55 15y ago

Effectively, we square each difference so that they can't cancel each other out. He seems to sort of confuse himself here, at first he says the squaring is so that it emphasizes bigger differences, then he says it's to make positive & negative cancel each other out. I think that the second part is just a nice bonus to the first part, but I don't get why he doesn't just use the absolute value of the distance anyway. "Hellp" is no more or less fit than "Helln". The crossover and mutate are sort of mashed together and could be made much more robust. For example, giving each gene a random chance to mutate would do a much better job at keeping the populations from evolving into one big similar mass. This is a good start but leaves a lot to be done for any sort of real implementation of a genetic algorithm.

tel 15y ago
If we're going to talk loss functions, then 1-0 loss is most appropriate here. As you say, "Hellp" is really no more or less fit than "Helln" whereas even absolute distance wouldn't reflect that. Squaring admits a function into the class of loss functions which must be strictly non-negative to be meaningful, but really it's just always been done to make derivatives easy. If you don't need derivatives (or expectations), you can probably get away without using squared loss if you don't want it.

piaskal 15y ago

This is a nice example of simple evolutionary algorithm. Next steps could be separating crossover and mutate operations, selecting more parent pairs for crossover and applying mutation in a more random fashion (not with every crossover).

juretriglav 15y ago

Evolutionary algorithms are fun. I solved a laser ablation modeling problem with them. The idea was to improve the quality of the produced data, by applying what knowledge of the process we had. Laser ablation measurements work something like this: Sample -> Ablation -> Measurement -> Data Since there are several distortions that happen in the middle two steps, you of course get a distorted measurement. You'd like to get the Sample from the Data. Since we know pretty well what happens in the middle two steps, I evolved my theoretical Sample by starting with random data, running it through the model of the middle two steps (ablation and measurement) and then comparing the modeled random data to the experimental data. The fitness function was exactly this difference between experimental and modeled data. I took the best ones of each generation and crossed them over. I then added some mutations and watched the magic happen. It ended up taking most of the night for a very simple set (our experimental sets are mostly orders of magnitude bigger). I took screenshots of every new generation, and made a movie of the whole process. When I played the movie in the morning I had one of those rare and special Eureka! moments, when all that work pays off and then some. I presented that movie at a conference and stole the show :) Long story short, evolutionary algorithms are fun, but I failed to apply them at the required scale.

perone 15y ago

Using Python Pyevolve framework: http://pyevolve.sourceforge.net/0_6rc1/examples.html#example-22-the-infinite-monkey-theorem http://pyevolve.sourceforge.net/0_6rc1/examples.html#example...

jessedhillon 15y ago

If you look closely, you'll notice that for each character, I square the difference. This is to to put extra emphasis on larger differences. If we don't do this, the string "Hannp" would have a fitness of 0. You see, the difference between 'e' and 'a' is -5, between 'l' and 'n' is +2 (which we have twice) and between 'o' and 'p' is +1. Adding these up yields a fitness of 0, but it's not the string we want at all. Squaring is a dumb way to avoid that problem. You can still have false positives: for example if a string differs from the target by two letters, who distances are +1 and -1, then squaring will not mitigate the issue. EDIT: I realize now that -1^2 is a positive number... I'm very surprised that the author doesn't know about the Levenshtein distance metric http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance That seems like it would be the perfect utility function for this case.

sparky 15y ago
Err.. I would argue that (+1)^2+(-1)^2 would not yield a false positive. You are right that the explanation is incomplete, though. The squaring provides an 'absolute value' effect as well as disproportionately weighting larger alphabetical distances.
mahcuz 15y ago
Regarding the squaring - would it be enough to take the absolute value of the distance? (abs -5) + (abs 5) = 10.
- jessedhillon 15y ago
  It's still a problematic way to quantify distance between strings. It says that "Rello World" is as close to the target as "Ifmkn Vpqkc" Levenshtein would quantify those differently, and I'd argue, more correctly. It would say the first is much closer than the second.

koryk 15y ago

I came across this example before when I was writing a small genetic algorithm library in js. https://github.com/koryk/evolvejs https://github.com/koryk/evolvejs I wrote a few examples as well. tic-tac-toe: http://www.korykirk.com/evolvejs/examples/tic-tac-toe/tic-tac-toe.html http://www.korykirk.com/evolvejs/examples/tic-tac-toe/tic-ta... circle: http://www.korykirk.com/evolvejs/examples/circle/circlega.html http://www.korykirk.com/evolvejs/examples/circle/circlega.ht...

bekirdag 15y ago

here is the same algorithm in php http://www.bekirdag.com/en/php_mysql/a_hello_world_genetic_algorithm_example_in_php.html http://www.bekirdag.com/en/php_mysql/a_hello_world_genetic_a...

tariqk 15y ago

That's a pretty interesting look into what happens in an evolutionary algorithm. But for a minute there I was hoping that the OP was going to evolve an actual "hello world" program. That might be an interesting exercise to do over a Lisp-like language.

rmc 15y ago
A lot of programmes have a regular grammer & parsers for their language. You can then use parsers and the like to turn a tree into a source code (and vice versa) and evolve programmes.
user24 15y ago
yeah I think genetic programming is often done with Lisp.
- dmoney 15y ago
  I don't see a reason to write the genetic algorithm in Lisp, but for the code that's being evolved it seems like the logical choice due to its minimal syntax. I'm working on a PHP program for evolving programs, and the evolved programs are in a lisp-like dialect made for just that purpose.
  - user24 15y ago
    IIRC it's something to do with the fact that lisp can easily be represented as a tree and so crossover is very simple; just swap branches. I don't know lisp so I'm just regurgitating info I picked up at university.
    - kruhft 15y ago
      One problem with using that technique is that it's has been patented, along with derivatives of it, for quite a while.
tomjen3 15y ago
Somebody actually did that, in Lisp, to be able to write a hello world program in a completely fucked out language. The problem with just generating a hello world program is that there is no guarantee that you wont end up with a bunch of endless loops.

user24 15y ago

I did the same in Javascript a while ago with a genetic algorithm. http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hello-world/ http://www.puremango.co.uk/2010/12/genetic-algorithm-for-hel... (HN discussion: http://news.ycombinator.com/item?id=2002673 http://news.ycombinator.com/item?id=2002673) Again just evolving a string not a full program. Mine hit the target significantly faster than OPs (around 70 generations rather than between 2 and 4 thousand). I'm trying to work out where he went wrong. First of all his 'mutate' function in the second example is actually performing both mutation and crossover. As far as the mutation goes it looks fine; almost identical to the way I mutate genes. I think the problem lies in the way he's doing his crossover (breeding), just trying to work it out. He's using one-point crossover, same as me. The selection method is a kind of hybrid elite method where fitter members are more likely to be selected than unfit members, which is reasonable. It might just be that his crossover and mutation probability is 100% and his population is only 20. But if you plug those figures into the interactive demo on my post (http://www.puremango.co.uk/genetic-hello-world.html http://www.puremango.co.uk/genetic-hello-world.html) then it gets as far as "Hbumr Xqnkd" by the 70th generation. Still looks like it's evolving faster than his code. Must be the way he's selecting parents...

pgroves 15y ago
I would agree. With a population size of only 20 the algorithm is closer to being hill-climbing with random restart. Crossover can't do much if there isn't a lot of diversity in the population, and a small population can't be very diverse. But it still worked.
- smoyer 15y ago
  And ... throwing away the least fit every time can lead you to climb the hill to a local maxima. In this case, the only way to leave a local maxima is to get lucky with a mutation, but if you cull the population randomly with a log probability that more fit parents will be kept, you could reach the goal in fewer generations. You could even eliminate mutations altogether if you have the proper character in each position in at least one member of the starting population.
- 15y ago

andrewcooke 15y ago

if anyone's interested, i evolved a program in malbolge (an esoteric language - http://www.lscheffer.com/malbolge.shtml http://www.lscheffer.com/malbolge.shtml) that prints "HEllO WORld" - see http://acooke.org/malbolge.html http://acooke.org/malbolge.html this was years ago, the work was done in lisp, and not long afterwards someone sent me a better solution that they had done by hand...

jcmoscon 15y ago
I bet you put a lot of effort to program this, eh? I think we can say that this is an argument in favor of intelligent design.
cpeterso 15y ago
You are too modest. Wikipedia says you wrote (or generated) the first Malbolge program: Malbolge was so difficult to understand when it arrived (in 1998) that it took two years for the first Malbolge program to appear. The program was not even written by a human being: it was generated by a beam search algorithm designed by Andrew Cooke. https://secure.wikimedia.org/wikipedia/en/wiki/Malbolge https://secure.wikimedia.org/wikipedia/en/wiki/Malbolge

TomNomNom 15y ago

I wrote something similar with a slightly longer string in PHP a while back. Read: http://www.tomnomnom.com/posts/methinks_it_is_like_an_incestuous_weasel http://www.tomnomnom.com/posts/methinks_it_is_like_an_incest... Code: https://github.com/TomNomNom/PHP-Evolution-Sim https://github.com/TomNomNom/PHP-Evolution-Sim

maeon3 15y ago

I want a program that will take a set of unit tests, and create a program that takes a piece of code and evolves it until all those tests pass. And I want to be able to guide its evolution, prompt it to use certain technologies in certain places.

nydev 15y ago
Sure..and put the rest of us out of business? : ) Although it is interesting to think about what the make-up of the genetic material would be. Just a string of 0s and 1s? CPU opcodes? Or maybe some higher level sub-units.
- jacques_chester 15y ago
  > Just a string of 0s and 1s? CPU opcodes? These have been tried. Historically Genetic Algorithms have represented their genotypes as bit strings. Some Genetic Programming systems use CPU instruction strings (pros: fast as heck, cons: can produce indecipherable spaghetti code that breaks when you remove those 400 NOOPs because it's adapted to the cache size of this particular CPU). > Or maybe some higher level sub-units. These too. Sometimes as trees of instructions, dataflow diagrams, FSMs and so on.
  - nydev 15y ago
    Very interesting.."indecipherable spaghetti code that breaks when you remove those 400 NOOPs because it's adapted to the cache size of this particular CPU" - sounds a little like our "junk" DNA (though I suspect the analogy breaks down in the details.)
    - jacques_chester 15y ago
      It can get pretty Rube Goldbergesque, apparently. The main rule of thumb is that if you're doing GP with CPU strings as your representation, beware of including run time in the fitness function. Because you will almost inevitably get over adaptation that breaks on any other platform.