4 ms·

Totally obsurd. Gradient descent will 'almost' always get stuck in a local optima. The point of evolutionary algorithms, or any naturally inspired algorithm for

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.

SeanLuke 12y ago
> 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.
- GordyMD 12y ago
  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.
Houshalter 12y ago
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.

SeanLuke 12y ago

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

GordyMD 12y ago
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.

Houshalter 12y ago

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.