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.

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.

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

Would you recommend a resource serving as an introduction?

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