Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Genetic Algorithms in CoffeeScript

janmonschke.com

Post reply on HN
Print view View original

31–40 of 48 posts

Re: Genetic Algorithms in CoffeeScript

#31

Post by azakai »

jules wrote: post #12
PeteBrighton wrote: post #10

Earlier quoted context omitted.

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?

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 NO…

> 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.

Yes, that's my opinion too. GAs model natural selection, which is extremely slow. The only reason it works in nature is the huge timescales and the lack of anything better (since it has to start from essentially nothing - there is no designer).

Re: Genetic Algorithms in CoffeeScript

#32

Post by jules »

moconnor wrote: post #15
jules wrote: post #12

Earlier quoted context omitted.

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 NO…

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 ca…

See my reply here for an explanation of how little that conclusion of the paper means: http://news.ycombinator.com/item?id=4561418

In particular they tuned the GA but not he hill climber, so it's not clear that GAs win even on this artificially designed problem.

Re: Genetic Algorithms in CoffeeScript

#33

Post by jashkenas »

phpnode wrote: post #30
Destroyer661 wrote: post #9

Earlier quoted context omitted.

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.

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 ja…

Hurrah. That's a big part of the entire premise.

Re: Genetic Algorithms in CoffeeScript

#36

Post by Turing_Machine »

jules wrote: post #29
Turing_Machine wrote: post #23

Earlier quoted context omitted.

"We then analyze an "idealized" genetic algorithm (IGA) that is signi cantly faster than RMHC and that gives a lower bound for GA speed. We identify the features of the IGA that give rise to this speedup, and discuss how these features can be incorporated into a real GA." "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, t…

Note that the "IGA" is not a real algorithm. Knowledge of the solution is encoded into the algorithm. It's no surprise that it outperforms an algorithm that does not have the privilege of knowing the solution before it starts. Second, to get a result where a GA outperformed hill climbing they did the following: 1. They started with a problem that was DESIGNED to be very well suited to GAs and not so well suited to hi…

"Even if it did, this is a problem explicitly designed to give GAs an advantage."

Well, yeah, you'd want to use GAs on problems for which they were well-suited. That's not at all the same as "clearly shows that GAs are NOT a good way to solve any problem".

Re: Genetic Algorithms in CoffeeScript

#37

Post by Turing_Machine »

jules wrote: post #32
moconnor wrote: post #15

Earlier quoted context omitted.

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 ca…

See my reply here for an explanation of how little that conclusion of the paper means: http://news.ycombinator.com/item?id=4561418 In particular they tuned the GA but not he hill climber, so it's not clear that GAs win even on this artificially designed problem.

Wait a minute. First you were citing the paper's conclusion as supporting your position and now you're attacking the paper's conclusion?

Re: Genetic Algorithms in CoffeeScript

#38

Post by Turing_Machine »

mck- wrote: post #26

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 Deadline is July 4th, 2013 -- Price $500 & Honourable mention for finding the shortest path to the world's largest TSP problem.

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

Re: Genetic Algorithms in CoffeeScript

#39

Post by Turing_Machine »

the_cat_kittles wrote: post #19

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

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).

Re: Genetic Algorithms in CoffeeScript

#40

Post by jules »

Turing_Machine wrote: post #36
jules wrote: post #29

Earlier quoted context omitted.

Note that the "IGA" is not a real algorithm. Knowledge of the solution is encoded into the algorithm. It's no surprise that it outperforms an algorithm that does not have the privilege of knowing the solution before it starts. Second, to get a result where a GA outperformed hill climbing they did the following: 1. They started with a problem that was DESIGNED to be very well suited to GAs and not so well suited to hi…

"Even if it did, this is a problem explicitly designed to give GAs an advantage." Well, yeah, you'd want to use GAs on problems for which they were well-suited. That's not at all the same as "clearly shows that GAs are NOT a good way to solve any problem".

Sure. The point is the effort they had to find such a problem. That indicates that it is very unlikely that any given practical problem is suitable for GAs. Again, if you are aware of any real problem where GAs work better than hill climbing, please do share. Note that this is not a very high bar. For example the same applied to quicksort vs insertion sort is "find any real example where quicksort outperforms insertion sort". If you couldn't find such an example and had to go to great lengths to artificially construct such an example then I'd call quicksort a failure, given that it's more complicated than insertion sort. Why GAs were/are as hyped as they are is a mystery to me.
Post reply on HN