Marcus replied to that http://news.ycombinator.com/item?id=90115.

Exactly. He's describing gradient descent (and possibly simulated annealing), not a genetic algorithm.

Mutation, especially burst mutation with population stagnation, is what stops you getting stuck in local maxima.

It does not matter _how_ it is done, it is still an iteration. You may have several iterations going on but at best you can expect to find several local maxima - at any given time. Further, if there is no "stagnation", how do you know that you've found a solution?

Stagnation is the case where the best individuals in the populations fitness hasn't increased by some value for a certain period of time.

I'm not sure I understand what you mean by 'a solution'? You know you've not arrived at an acceptable solution when your fitness is below your required level.

Granted, you never know there is a configuration with a fitness greater than your required fitness but this is generally considered when constructing the fitness function.

I understand that when a certain level of fitness is reached the procedure stops. But, it may stop too early - missing the global max. And second, it may never stop!

True.

I've seen some interesting work on the latter case that produces upper and lower bounds for time to an acceptable solution but so far it seems to be limited in it's application to real world tasks.

Missing the global max less of an issue, an acceptable level of fitness is generally all that's required for most applications. Though I guess there are several tasks for which a global max would be useful.