Provable statements about genetic algorithms 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 in practice. 

Some metaheuristics are reasonably well studied theoretically: there's work on local search, and annealing. We have a pretty good sense of how alternating optimization (like k-means) 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, 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).
Y. Rabinovich, A. Wigderson. Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999. (Also available from Avi Wigderson's home page)