Genetic algorithms don't get much traction in the world of theory, but they are a reasonably well-used metaheuristic method (by metaheuristic I mean a technique that applies generically across many problems, like annealing, gradient descent, and the like). In fact, a GA-like technique [is quite effective for Euclidean TSP][1] in practice. 

Some metaheuristics are reasonably well studied theoretically: there's [work on local search][2], and annealing. We have a pretty good sense of how alternating optimization ([like k-means][3]) works. But as far as I know, there's nothing really useful known about genetic algorithms. 

Is there any solid algorithmic/complexity theory about the behavior of genetic algorithms, in any way, shape or form ?  While I've heard of things like [schema theory][4], I'd exclude it from discussion based on my current understanding of the area for not being particularly algorithmic (but I might be mistaken here). 


  [1]: http://www2.research.att.com/~dsj/papers/stspchap.pdf
  [2]: http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pls
  [3]: http://en.wikipedia.org/wiki/K-means%2B%2B
  [4]: https://cstheory.stackexchange.com/questions/555/what-is-schema-theory-within-genetic-algorithms