Provable statements about genetic algorithms

Question

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

Answer 1

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)

Answer 2

Have a look at the work of Benjamin Doerr from École Polytechnique and formerly 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

Answer 3

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.

Answer 4

Do you know this paper:

Jens Jägersküpper. Combining Markov-Chain Analysis and Drift Analysis: The (1+1) Evolutionary Algorithm on Linear Functions Reloaded.

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

Answer 5

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

Answer 6

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.

Answer 7

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)

Answer 8

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)

Answer 9

Check these references:

Lothar Schmitt, Theory of genetic algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling

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

C. Dombry, A weighted random walk model. Application to a genetic algorithm

Answer 10

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.