Hacker News Reader

Comment by SeanLuke | Hacker News Reader

That is absurd. Gradient descent assumes you can compute the gradient of your objective function. For a great many functions you cannot define the gradient: indeed you can't even define the objective function well.

Genetic algorithms belong to a family of metaheuristics, algorithms designed to tackle such ill-defined functions where gradient descent is simply impossible to use.

My concern with this webpage is that it is a far too simplistic treatment of genetic algorithms, to the point of being misleading, and has quite a number of outright errors. I wouldn't use it.

View on HN

Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima. The point of evolutionary algorithms, or any naturally inspired algorithm for that matter, is that it does not tend to converge upon local optima and has the possibility of moving out of this space towards the global optima. The fact that most problems it is applied to are NP-Complete means that it is unlikely it will find the optimal solution in polynomial time.

> Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima

Well... just as evolutionary algorithms are essentially elaborate versions of hill-climbing which enable global search, likewise there are many well-established forms of gradient descent which are global searchers as well.

I think the key distinguishing feature is that gradient descent makes strong assumptions about the nature of the space being searched; and metaheuristics make much more general assumptions.

Good point. This is key, as you say.

Meta-heuristics have the flexibility of providing good performance on all Combinatorial Optimisation Problems.

But meta-heuristics, can also be given domain knowledge. and/or be combined with a a heuristic. E.g. Ant Colony Optimisation techniques for Travelling Salesman Problems that combines ACO with Local Search.

In practice genetic algorithms don't do much better than hill climbing with random restarts.

You can do random restarts, stochasticism, or population based stuff on gradient methods too.

Yes it does require at least an estimate of the gradient, but that's not too hard to get and it converges much faster. Meta-heuristics are only a last resort when you can't get a gradient.

Although they are a bit simpler so there is nothing wrong with using them if the search space isn't too big.

Would you recommend a resource serving as an introduction?

Oh man, what a leading question! Try "Essentials of Metaheuristics" of course. :-)

Reply on news.ycombinator.com