5 ms·

Show HN: Genetic Hello World

76 points by sacert 9y ago

hcarvalhoalves 9y ago
Up-voting because even though genetic algorithms seem inefficient compared to back-propagation with gradient descent, it still is an elegant optimization heuristic for many classes of practical problems, and often easier to implement compared to NNs if you're trying to apply on a novel domain.
- sacert 9y ago
  Very true - I had some time at work and remembered how big genetic algorithms were a couple years ago so I decided to get my feet wet in the subject.
  - hcarvalhoalves 9y ago
    A common use case is solving design constraints: https://www.google.com/?q=genetic+algorithm+placement+format:pdf https://www.google.com/?q=genetic+algorithm+placement+format...
- xoroshiro 9y ago
  >Easier to implement. I heard about it first while reviewing literature for some of my operations research classes. They were supposedly good heuristics for hard problems like scheduling and facility layouts, but of course I didn't really get in to that for those introductory classes. I wonder if it's really less scary (harder) than I originally thought? I can't seem to find good resources on them online though, as all the moocs and resources are still raving on about machine learning and data science.
- nurikolan 9y ago
  GAs are also more relevant to problems that cannot be represented in continuous vector space, i.e. where the problem is symbolic and not real-numbered.
natosaichek 9y ago
The cost function just looks like difference squared, but I'm not sure how that yields results like this: Hglmo,wosmd! (8) Gflln* wosle! (9) Hello, wosld! (9999) Hello, world (9999) The bottom two seem to be much closer to the desired result, but the top two score lower cost? Seems weird to me. :-/
- sacert 9y ago
  Oh, I was splitting the two of the top genes within the pool and giving each other half of their respective genes and inserting it at the bottom which is why the ones that look closer to the goal are at the bottom. I added a sorting feature after the creation of children to fix that!
- vanderZwan 9y ago
  I wonder how using Levenshtein distance as a fitness metric would affect the speed of progress: https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance OP, if you want to experiment, here's a gist with a JS implementation that I found after some googling: https://gist.github.com/andrei-m/982927 https://gist.github.com/andrei-m/982927 How the cost function compares to how you mutate probably also matters here.
  - TomNomNom 9y ago
    I used Levenshtein distance for a similar thing some years ago: https://tomnomnom.com/posts/methinks-it-is-like-an-incestuous-weasel https://tomnomnom.com/posts/methinks-it-is-like-an-incestuou... It worked very well!
    - vanderZwan 9y ago
      Very nice and simple example! > The phrase METHINKS IT IS LIKE A WEASEL is 28 characters long, and has 27 possibities for each character, making for 27^28 (about 10^40) possible combinations. To put that into perspective: it's reckoned that there's about 10^80 atoms in the visible universe. Even if the monkey could try millions of combinations per second, he would almost certainly never get there - and that's assuming he never repeated a combination. > So it would take a very long time for the monkey to hit the right keys at random, but what about if it weren't completely random? Dawkins suggests a computer program to simulate the monkey, only using something akin to evolution to form the phrase instead of complete randomness. That is: randomness would still be involved, but in a slightly more predictable capacity than the virtual equivilent of a monkey bashing its head against a keyboard. Funny you should mention that, because one of the unsolved questions for the theory of Evolution is that even with our current understanding of evolution, life evolves faster than one would expect based purely on DNA mutations alone. A few issues back Nautilus had a excellent article on the problem, and the current work being done to solve this problem: http://nautil.us/issue/20/creativity/the-strange-inevitability-of-evolution http://nautil.us/issue/20/creativity/the-strange-inevitabili...
david90 9y ago
I find it interesting - but it would be nice if there is a better README for visitor to grab the concept quick.
deleted 9y ago
[deleted]
nk1tz 9y ago
I've long been a fan of the GA optimization technique. I created this little tool to explore the genetic algorithm. You can tweak parameters on the fly and watch the effect it has on the current set of top solutions. https://github.com/nk1tz/explore-genetic-algorithm https://github.com/nk1tz/explore-genetic-algorithm
gvx 9y ago
Genetic algorithms are always neat. I made something similar as a greeting card in 2015: https://card.robinwell.net/f47f6d670450fad68df8ce45d0fa846d.html https://card.robinwell.net/f47f6d670450fad68df8ce45d0fa846d.... It uses tournament selection for each next generation.
TeMPOraL 9y ago
Cool! A minor nitpick about the README - genetic algorithm is not the same thing as genetic programming. The former is what you're doing here, the latter refers to building a program using genetic algorithms. See: https://en.wikipedia.org/wiki/Genetic_programming https://en.wikipedia.org/wiki/Genetic_programming.
- eternalban 9y ago
  It is not a minor nit & good to point out.
greenpizza13 9y ago
This is a really fun demonstration.
sjmulder 9y ago
Thanks for sharing. Concise and easy to follow. I ported it to C to try it out for myself. Turning off console output makes it finish almost instantly!

76 points by sacert 9y ago

Up-voting because even though genetic algorithms seem inefficient compared to back-propagation with gradient descent, it still is an elegant optimization heuristic for many classes of practical problems, and often easier to implement compared to NNs if you're trying to apply on a novel domain.

sacert 9y ago
Very true - I had some time at work and remembered how big genetic algorithms were a couple years ago so I decided to get my feet wet in the subject.
- hcarvalhoalves 9y ago
  A common use case is solving design constraints: https://www.google.com/?q=genetic+algorithm+placement+format:pdf https://www.google.com/?q=genetic+algorithm+placement+format...
xoroshiro 9y ago
>Easier to implement. I heard about it first while reviewing literature for some of my operations research classes. They were supposedly good heuristics for hard problems like scheduling and facility layouts, but of course I didn't really get in to that for those introductory classes. I wonder if it's really less scary (harder) than I originally thought? I can't seem to find good resources on them online though, as all the moocs and resources are still raving on about machine learning and data science.
nurikolan 9y ago
GAs are also more relevant to problems that cannot be represented in continuous vector space, i.e. where the problem is symbolic and not real-numbered.

natosaichek 9y ago

The cost function just looks like difference squared, but I'm not sure how that yields results like this: Hglmo,wosmd! (8) Gflln* wosle! (9) Hello, wosld! (9999) Hello, world (9999) The bottom two seem to be much closer to the desired result, but the top two score lower cost? Seems weird to me. :-/

sacert 9y ago
Oh, I was splitting the two of the top genes within the pool and giving each other half of their respective genes and inserting it at the bottom which is why the ones that look closer to the goal are at the bottom. I added a sorting feature after the creation of children to fix that!
vanderZwan 9y ago
I wonder how using Levenshtein distance as a fitness metric would affect the speed of progress: https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance OP, if you want to experiment, here's a gist with a JS implementation that I found after some googling: https://gist.github.com/andrei-m/982927 https://gist.github.com/andrei-m/982927 How the cost function compares to how you mutate probably also matters here.
- TomNomNom 9y ago
  I used Levenshtein distance for a similar thing some years ago: https://tomnomnom.com/posts/methinks-it-is-like-an-incestuous-weasel https://tomnomnom.com/posts/methinks-it-is-like-an-incestuou... It worked very well!
  - vanderZwan 9y ago
    Very nice and simple example! > The phrase METHINKS IT IS LIKE A WEASEL is 28 characters long, and has 27 possibities for each character, making for 27^28 (about 10^40) possible combinations. To put that into perspective: it's reckoned that there's about 10^80 atoms in the visible universe. Even if the monkey could try millions of combinations per second, he would almost certainly never get there - and that's assuming he never repeated a combination. > So it would take a very long time for the monkey to hit the right keys at random, but what about if it weren't completely random? Dawkins suggests a computer program to simulate the monkey, only using something akin to evolution to form the phrase instead of complete randomness. That is: randomness would still be involved, but in a slightly more predictable capacity than the virtual equivilent of a monkey bashing its head against a keyboard. Funny you should mention that, because one of the unsolved questions for the theory of Evolution is that even with our current understanding of evolution, life evolves faster than one would expect based purely on DNA mutations alone. A few issues back Nautilus had a excellent article on the problem, and the current work being done to solve this problem: http://nautil.us/issue/20/creativity/the-strange-inevitability-of-evolution http://nautil.us/issue/20/creativity/the-strange-inevitabili...

david90 9y ago

I find it interesting - but it would be nice if there is a better README for visitor to grab the concept quick.

deleted 9y ago

[deleted]

nk1tz 9y ago

I've long been a fan of the GA optimization technique. I created this little tool to explore the genetic algorithm. You can tweak parameters on the fly and watch the effect it has on the current set of top solutions. https://github.com/nk1tz/explore-genetic-algorithm https://github.com/nk1tz/explore-genetic-algorithm

gvx 9y ago

Genetic algorithms are always neat. I made something similar as a greeting card in 2015: https://card.robinwell.net/f47f6d670450fad68df8ce45d0fa846d.html https://card.robinwell.net/f47f6d670450fad68df8ce45d0fa846d.... It uses tournament selection for each next generation.

TeMPOraL 9y ago

Cool! A minor nitpick about the README - genetic algorithm is not the same thing as genetic programming. The former is what you're doing here, the latter refers to building a program using genetic algorithms. See: https://en.wikipedia.org/wiki/Genetic_programming https://en.wikipedia.org/wiki/Genetic_programming.

eternalban 9y ago
It is not a minor nit & good to point out.

greenpizza13 9y ago

This is a really fun demonstration.

sjmulder 9y ago

Thanks for sharing. Concise and easy to follow. I ported it to C to try it out for myself. Turning off console output makes it finish almost instantly!