This got me thinking- is there a use case for client-side ML?
The better question is would you even want to do ML in javascript?
Genetic Algorithms in CoffeeScript
21–30 of 48 posts
Re: Genetic Algorithms in CoffeeScript
#22Earlier 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…
A domain in which GAs are slowly finding resurgence is algorithmic portfolio management - I work in this area a bit (ie portfolio management - but not directly involved with the GA guys - plus their research is proprietary) - but their premise is that evolution has done pretty well surviving against nature and products of evolution itself.
The financial markets are a bit like that - stochastic exogenous factors (headline risk like the Euro crisis, the FOMC meeting decisions etc.) and evolved responses based on the principle of no-arbitrage (ie other traders) determine portfolio performance and trading decisions along with transaction costs.
But GAs as they exist are unsuitable for this, from what I've gathered from conversations with those quants. The modifications required appear to be in the direction of structured intra-generation genome modification (or adaptation) rather than pure randomness and crossover to produce agents with a specific trading behaviour (much in the same way as evolution allows a sensible change in the DNA to produce a particular protein suited for a task).
Re: Genetic Algorithms in CoffeeScript
#23Earlier 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…
"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, the GA discovers level 3 approximately twice as often as RMHC."
"We have presented analyses of two algorithms, RMHC and the IGA, and have used the analyses to identify some general principles of when and how a genetic algorithm will out- perform hill climbing."
I'm not sure this paper says what you're claiming that it says.
Re: Genetic Algorithms in CoffeeScript
#24Just 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.
Re: Genetic Algorithms in CoffeeScript
#25Suggestion: 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.
I agree on this -- I wrote my thesis on the VRP (Vehicle Routing Problem) which is an even more difficult problem. I've studied GAs extensively (they are pretty awesome, hence my interest), but other methods are much better. I've heard great things about ACOs, but eventually I settled for Tabu Search, because:
- It is deterministic, hence not a black box - It is a local search, easy to explain - Does not require as many parameters to tweak (GAs' performance demands on how you set these: mutation rate, population size, cross-over mechanism (dozens of possibilities), stopping procedure, selection procedure, etc...) - Considered by literature to be one of the strongest class of algorithms for the class of TSP problems, in both solution quality and computational effort
Here's an open-source implementation in Common Lisp: https://github.com/mck-/Open-VRP
Re: Genetic Algorithms in CoffeeScript
#26Everyone 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.
Re: Genetic Algorithms in CoffeeScript
#27Re: Genetic Algorithms in CoffeeScript
#28Re: Genetic Algorithms in CoffeeScript
#29Earlier 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…
"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 hill climbing. It turned out that when you do hill climbing in a non ridiculous way that GAs lose big time (by a factor of 10).
2. Through several steps they further modified the artificial problem to give a disadvantage to hill climbing and an advantage to GAs.
3. They tuned the GA's parameters and did not tune the hill climber's parameters.
4. They compared the performance by number of fitness function evaluations. This is unfair to hill climbing because GAs have bigger overheads elsewhere.
After these steps the GA outperformed hill climbing by about a factor of 2. So it is not clear that the GA would still win if you tuned the hill climber. Even if it did, this is a problem explicitly designed to give GAs an advantage. The fact that they had to go through so much effort to design such a problem doesn't instill much confidence that there exists a real world problem where GAs work.
I have tried to replicate their results and do the tuning of the hill climber, but unfortunately the paper is so vague on what the problem is that the algorithms are actually supposed to solve, so that I was not able to do this. If anybody knows a study of a problem (preferably real world) where GAs are shown to outperform reasonable forms of hill climbing I'd be very happy to hear it.
Re: Genetic Algorithms in CoffeeScript
#30Earlier quoted context omitted.
It's my main language for almost two years now ;)
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 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.