5 ms·

Genetic Algorithms in CoffeeScript

123 points by janmonschke 14y ago

jashkenas 14y ago
Direct link to the code, which is nice and clear to read (Genome / Population): https://github.com/janmonschke/Genetic-Algorithms/tree/gh-pages/coffeescripts https://github.com/janmonschke/Genetic-Algorithms/tree/gh-pa...
domlebo70 14y ago
Can't help this example could have been illustrated much more clearly in something other then CoffeeScript.
- Destroyer661 14y ago
  Out of all the languages to choose from it just had to be coffescript...
  - janmonschke 14y ago
    It's my main language for almost two years now ;)
    - notiontaxi 14y ago
      First they ignore you, then they ridicule you, then they fight you... ...than u rule da web.
    - Destroyer661 14y ago
      I'm not saying that it being your main language is bad, it's just the syntax is absolutely terrible to read and understand for those of us on C-style languages. If the point was to teach others, the vast majority of your audience is not going to be reading coffeescript and learning much.
      - tinco 14y ago
        In all code examples you can press the down arrow to view the horrible (c-style) Javascript source. The javascript seems to be mainly horrible because of the coffeescript code being object oriented and its lack of a more powerful looping construct.
        ville 14y ago
        It looks like there is something missing in the first example in Javascript. Population = (function() { Population.prototype.genomes = []; })(); This throws a ReferenceError because Population is not defined. Genome = (function() { Genome.prototype.values = []; function Genome(values) { this.values = values != null ? values : this.initial(); } Genome.prototype.inital = function(){ return [RANDOMARRAY FROM [0-14]] } })(); After this part Genome will be undefined.
        janmonschke 14y ago
        Thx, forgot to copy the var statements. It's fixed now.
      - jeswin 14y ago
        IMHO, I don't think it is fair to suggest this. - There are GA tutorials available in several other languages, if this doesn't work for you. Btw, if a tutorial was offered in Lisp/Haskell, would we see the same suggestion? - For Ruby/Python programmers, this isn't hard at all to read. Familiarity with non C-style languages might be something to pick up. - Having moved to Coffee from C-style languages, I prefer coffee. But that is just my opinion. I think HNers should be more tolerant of language choices. That argument can't really be won.
      - phpnode 14y ago
        that's funny because coffeescript is meant to be all about readability in code. I wonder if you really tried to read this or if you just commented based on the title. If you did really read it, I wonder if you found it hard to read because your opinion is tainted by those C style languages? It's not scientific of course but I just got my non coder, non technical girlfriend to read through both the coffeescript and javascript versions of this and I definitely had to explain a lot less to her with the coffeescript version, she says it's easier to read because it's structured more like plain English.
- columbo 14y ago
  The coffeescript rocks/sucks crowd does not belong here. This person wrote a blog post explaining something using a language he is familiar with. If articles are boiled down to a shouting match because the java-haters or the coffeescript-haters or the ruby-haters found the article first we all may as well go back to /.
SeanLuke 14y ago
Suggestion: TSP is a combinatorial optimization problem and isn't well suited to GAs. You would be much better off using a method meant for combinatorial optimization: notably ant colony optimization.
- janmonschke 14y ago
  Thx for the hint :) The task originated from a task I had to do at university in Algorithms class as an introduction to GAs and I liked the simplicity of it.
- PeteBrighton 14y ago
  If you don't mind expanding a little, I'd be interested to know why they're not suited to combinatorial optimization, and what they are in fact more suited to?
  - jules 14y ago
    I have searched for a problem that they're more suited to, and I've come to the conclusion that GAs are in fact not known to work on any problem. They do "work" in the sense that sometimes they find an answer, but there are other algorithms that are much simpler and consistently outperform them (notably randomized hill climbing). Here is a paper that despite trying to prove the opposite, clearly shows that GAs are NOT a good way to solve any problem: http://web.cecs.pdx.edu/~mm/nips93.pdf http://web.cecs.pdx.edu/~mm/nips93.pdf
    - moconnor 14y ago
      That's not quite my understanding of the paper's results: "As can be seen, the time to reach level one is comparable for the two algorithms, but the GA is much faster at reaching levels 2 and 3. Further, the GA discovers level 3 approximately twice as often as RMHC [randomized hill climbing]" I don't dispute that there are generally better optimization algorithms than GAs, but this paper does present an artificial case in a GA outperforms hill climbing.
      - 14y ago
abuiles 14y ago
Nice talk Jan!
the_cat_kittles 14y ago
This got me thinking- is there a use case for client-side ML?
- dmix 14y ago
  The better question is would you even want to do ML in javascript?
  - the_cat_kittles 14y ago
    for client side ML! hence my question...
    - dmix 14y ago
      Well, ML is almost always very CPU and memory intensive, I'm not sure how running any data-heavy algorithms would make sense in a browser.
- Turing_Machine 14y ago
  Just for clarification, you mean machine learning rather than ML the language, right? (I ask because this discussion is talking about both the genetic algorithms and Coffeescript). Hmm... maybe some sort of GPS application that took into account current road conditions -- length of time stopped at traffic lights, performance characteristics of the current vehicle (velocity and acceleration away from lights, etc). At one time there was talk of making the air traffic control system distributed rather than centralized. The win there is that 1) each aircraft only has to worry about the other aircraft that near enough to interfere and 2) if the control system goes out in one aircraft, the systems in the other aircraft can compensate. By contrast the centralized system has to watch all the aircraft in a large chunk of airspace, and if it goes out, well... This is sort of what Google is doing with their self-driving cars, I think (that's just my impression -- I haven't looked into it in detail).
unix-dude 14y ago
Just ran through this quickly, I don't know too much about algorithms, so I can't judge GA's usefulness when compared to other methods, but it certainly seems like a cool/fun thing to implement.
mck- 14y ago
Everyone seems to claim a better way to do it (myself included). Here's a TSP challenge for you to prove yourselves: http://www.tsp.gatech.edu/data/usa/index.html http://www.tsp.gatech.edu/data/usa/index.html Deadline is July 4th, 2013 -- Price $500 & Honourable mention for finding the shortest path to the world's largest TSP problem.
- Turing_Machine 14y ago
  Anyone who came up with a radically superior solution to that problem could use it to make significantly more than 500 bucks. :-)
cbrandolino_ 14y ago
That's supernice! You may want to fix the links in the readme though.
- janmonschke 14y ago
  Thanks Claudio, I fixed them!
deleted 14y ago
[deleted]
grendelt 14y ago
What did you/he use to make the presentation?
- janmonschke 14y ago
  I used reveal.js: http://lab.hakim.se/reveal-js/ http://lab.hakim.se/reveal-js/

123 points by janmonschke 14y ago

Direct link to the code, which is nice and clear to read (Genome / Population): https://github.com/janmonschke/Genetic-Algorithms/tree/gh-pages/coffeescripts https://github.com/janmonschke/Genetic-Algorithms/tree/gh-pa...

domlebo70 14y ago

Can't help this example could have been illustrated much more clearly in something other then CoffeeScript.

Destroyer661 14y ago
Out of all the languages to choose from it just had to be coffescript...
- janmonschke 14y ago
  It's my main language for almost two years now ;)
  - notiontaxi 14y ago
    First they ignore you, then they ridicule you, then they fight you... ...than u rule da web.
  - Destroyer661 14y ago
    I'm not saying that it being your main language is bad, it's just the syntax is absolutely terrible to read and understand for those of us on C-style languages. If the point was to teach others, the vast majority of your audience is not going to be reading coffeescript and learning much.
    - tinco 14y ago
      In all code examples you can press the down arrow to view the horrible (c-style) Javascript source. The javascript seems to be mainly horrible because of the coffeescript code being object oriented and its lack of a more powerful looping construct.
      - ville 14y ago
        It looks like there is something missing in the first example in Javascript. Population = (function() { Population.prototype.genomes = []; })(); This throws a ReferenceError because Population is not defined. Genome = (function() { Genome.prototype.values = []; function Genome(values) { this.values = values != null ? values : this.initial(); } Genome.prototype.inital = function(){ return [RANDOMARRAY FROM [0-14]] } })(); After this part Genome will be undefined.
        janmonschke 14y ago
        Thx, forgot to copy the var statements. It's fixed now.
    - jeswin 14y ago
      IMHO, I don't think it is fair to suggest this. - There are GA tutorials available in several other languages, if this doesn't work for you. Btw, if a tutorial was offered in Lisp/Haskell, would we see the same suggestion? - For Ruby/Python programmers, this isn't hard at all to read. Familiarity with non C-style languages might be something to pick up. - Having moved to Coffee from C-style languages, I prefer coffee. But that is just my opinion. I think HNers should be more tolerant of language choices. That argument can't really be won.
    - phpnode 14y ago
      that's funny because coffeescript is meant to be all about readability in code. I wonder if you really tried to read this or if you just commented based on the title. If you did really read it, I wonder if you found it hard to read because your opinion is tainted by those C style languages? It's not scientific of course but I just got my non coder, non technical girlfriend to read through both the coffeescript and javascript versions of this and I definitely had to explain a lot less to her with the coffeescript version, she says it's easier to read because it's structured more like plain English.
columbo 14y ago
The coffeescript rocks/sucks crowd does not belong here. This person wrote a blog post explaining something using a language he is familiar with. If articles are boiled down to a shouting match because the java-haters or the coffeescript-haters or the ruby-haters found the article first we all may as well go back to /.

SeanLuke 14y ago

Suggestion: TSP is a combinatorial optimization problem and isn't well suited to GAs. You would be much better off using a method meant for combinatorial optimization: notably ant colony optimization.

janmonschke 14y ago
Thx for the hint :) The task originated from a task I had to do at university in Algorithms class as an introduction to GAs and I liked the simplicity of it.
PeteBrighton 14y ago
If you don't mind expanding a little, I'd be interested to know why they're not suited to combinatorial optimization, and what they are in fact more suited to?
- jules 14y ago
  I have searched for a problem that they're more suited to, and I've come to the conclusion that GAs are in fact not known to work on any problem. They do "work" in the sense that sometimes they find an answer, but there are other algorithms that are much simpler and consistently outperform them (notably randomized hill climbing). Here is a paper that despite trying to prove the opposite, clearly shows that GAs are NOT a good way to solve any problem: http://web.cecs.pdx.edu/~mm/nips93.pdf http://web.cecs.pdx.edu/~mm/nips93.pdf
  - moconnor 14y ago
    That's not quite my understanding of the paper's results: "As can be seen, the time to reach level one is comparable for the two algorithms, but the GA is much faster at reaching levels 2 and 3. Further, the GA discovers level 3 approximately twice as often as RMHC [randomized hill climbing]" I don't dispute that there are generally better optimization algorithms than GAs, but this paper does present an artificial case in a GA outperforms hill climbing.
    - 14y ago

abuiles 14y ago

Nice talk Jan!

the_cat_kittles 14y ago

This got me thinking- is there a use case for client-side ML?

dmix 14y ago
The better question is would you even want to do ML in javascript?
- the_cat_kittles 14y ago
  for client side ML! hence my question...
  - dmix 14y ago
    Well, ML is almost always very CPU and memory intensive, I'm not sure how running any data-heavy algorithms would make sense in a browser.
Turing_Machine 14y ago
Just for clarification, you mean machine learning rather than ML the language, right? (I ask because this discussion is talking about both the genetic algorithms and Coffeescript). Hmm... maybe some sort of GPS application that took into account current road conditions -- length of time stopped at traffic lights, performance characteristics of the current vehicle (velocity and acceleration away from lights, etc). At one time there was talk of making the air traffic control system distributed rather than centralized. The win there is that 1) each aircraft only has to worry about the other aircraft that near enough to interfere and 2) if the control system goes out in one aircraft, the systems in the other aircraft can compensate. By contrast the centralized system has to watch all the aircraft in a large chunk of airspace, and if it goes out, well... This is sort of what Google is doing with their self-driving cars, I think (that's just my impression -- I haven't looked into it in detail).

unix-dude 14y ago

Just ran through this quickly, I don't know too much about algorithms, so I can't judge GA's usefulness when compared to other methods, but it certainly seems like a cool/fun thing to implement.

mck- 14y ago

Everyone seems to claim a better way to do it (myself included). Here's a TSP challenge for you to prove yourselves: http://www.tsp.gatech.edu/data/usa/index.html http://www.tsp.gatech.edu/data/usa/index.html Deadline is July 4th, 2013 -- Price $500 & Honourable mention for finding the shortest path to the world's largest TSP problem.

Turing_Machine 14y ago
Anyone who came up with a radically superior solution to that problem could use it to make significantly more than 500 bucks. :-)

cbrandolino_ 14y ago

That's supernice! You may want to fix the links in the readme though.

janmonschke 14y ago
Thanks Claudio, I fixed them!

deleted 14y ago

[deleted]

grendelt 14y ago

What did you/he use to make the presentation?

janmonschke 14y ago
I used reveal.js: http://lab.hakim.se/reveal-js/ http://lab.hakim.se/reveal-js/