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

• For some inspiration, see also p. 25–29 of Papadimitriou's FCRC 2007 slides. Sep 1, 2010 at 19:13
• @Suresh: I'd prefer to see it as a question rather than an answer; I'd be delighted if someone else went through the trouble of explaining more specifically what is the result that Papadimitriou is referring to in the slides. :) Sep 1, 2010 at 19:40
• here's a pop-sci rendition of that work: tinyurl.com/2f39jrb Sep 1, 2010 at 19:43
• I recently took a course in GA and my hype about GA has diminished when I learned the No Free Lunch Theorem: en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization Sep 3, 2010 at 15:37
• Alexandru, why is that? It should be pretty obvious that almost any technique will be better than others in some instances and worse in others. Did you really believe GA would be uniformly superior? Jan 19, 2011 at 6:37

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)

• It looks like the first link is defunct. Apr 29, 2014 at 2:13
• @JeremyKun: I just tried it and it worked just fine... (It would make me sad if a doi link went defunct, defeating one of the main purposes of the doi system...) Apr 29, 2014 at 2:54
• I'm still getting a "Page Not Found" error from the Wiley Library. Could it be a formatting/browser issue? Apr 29, 2014 at 13:35
• It's not a problem because the link to his homepage works. I was just trying to help make this answer better :) Apr 29, 2014 at 19:13

Have a look at the work of Benjamin Doerr from the Algorithms group at Max Planck (MPI). It is all about trying to make provable contributions to evolutionary algorithms.

In particular, Doerr has co-edited a relevant recent book, Theory of Randomized Search Heuristics

As well as working on simulated annealing, Ingo Wegener had some theoretical results on evolutionary algorithms. The thesis of his PhD student Dirk Sudholt is also worth a look.

Do you know this paper:

It shows an expected running time of $O(n\log n)$ for linear functions for a class of evolutionary algorithms.

During the last decade, there has been made significant progress in runtime analysis of evolutionary algorithms, ant colony optimisation, and other metaheuristics. For a survey, please refer to Oliveto et al. (2007).

• Per Kristian Lehre, I just viewed you and saw your area of interest, so I'd like to ask: do you think similar tools could be used to analyze runtime of ant colony optimization algorithms, and Chazelle's "Natural Algorithm"-type questions (rate of convergence of bird flocking)? Right now, Chazelle's techniques seem like an island to themselves, and I'm wondering if there's some bigger picture. Sep 3, 2010 at 14:19
• Yes, these techniques can be adapted to analyse the runtime of ACOs. I have recently co-authored a paper about ACOs for the MinCut problem. Also, please see the survey by Witt (2009): springerlink.com/content/3727x3255r1816g4 I am not aware of any current links of this research to Chazelle's work, but it is certainly worth exploring. Sep 3, 2010 at 14:31

Lovasz and Vempala (FOCS 2003 special issue of J. Comp. System Sci.) use a variant of simulated annealing to get a better ($O^*(n^4)$) algorithm for computing the volume of a convex body. Obviously, they can prove something about the variant they use, in order to get the provable upper bound on their overall algorithm.

• hey, he's back :) Jan 19, 2011 at 3:44

Check these references:

Shiu Yin Yuen; B.K.S. Cheung, Bounds for probability of success of classical genetic algorithm based on hamming distance

Chang C. Y. Dorea; Judinor A. Guerra Jr.; Rafael Morgado; Andre G. C. Pereira, Multistage Markov Chain Modeling of the Genetic Algorithm and Convergence Results

There is also a paper from D. BHANDARI, C. A. MURTHY and S. K. PAL (unfortunately unavailable online) that provides a convergence proof under two assumptions:

• Elitist selection: the best solution of the generation $t$ must be in the generation $t+1$
• The mutation operator allows to switch from any solution to another in a finite number of steps

The convergence proof uses a Markov chain model.

Here the reference: Dinabandhu Bhandari, C. A. Murthy: Genetic Algorithm with Elitist Model and Its Convergence. IJPRAI 10(6): 731-747 (1996)

Mathematical models of genetic algorithms with finite but non-unitary populations are unwieldy, and have, so far, proven unamenable to analysis for all but the most trivial of fitness functions. Interestingly, if you are willing to accept a symmetry argument, an argument, in other words, not made within the confines of a formal axiomatic system, then there is an exciting and beautiful result to be had about the computational power of genetic algorithms.

Specifically, a genetic algorithm with uniform crossover is capable of evaluating vast numbers of coarse schema partitions implicitly and in parallel, and can efficiently identify partitions whose constituent schemata have differing average fitness values. This form of implicit parallelism is actually more powerful than the kind described by John Holland and his students, and unlike the implicit parallelism described by Holland, can be verified experimentally. (See this blog post.)

The following paper explains how genetic algorithms with uniform crossover parlay implicit parallelism into a general-purpose, global optimization heuristic called hyperclimbing:

Explaining optimization in genetic algorithms with uniform crossover. To appear in the proceedings of the Foundations of Genetic Algorithms 2013 conference.

(Disclaimer: I am the paper's author)

• this is clever/innovative to use random SAT as a benchmark for the GA and shows an idea that seems few papers have explored. suppose the GA can work on any arbitrary complexity class and is maybe really a way of building algorithms in a "higher" complexity class based on results of algorithms in a "lower" complexity class.... then in some sense it does not really make sense to analyze the "complexity" of GAs because they might transcend complexity class classification....
– vzn
Oct 20, 2012 at 3:22

Raphael Cerf did his PhD thesis on Genetic Algorithms in Montpellier under the supervision of Alain Berlinet, from a mathematical point of view. It is quite old, but would probably belong to any bibliography about genetic algorithms.