Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
5  
For some inspiration, see also p. 25–29 of Papadimitriou's FCRC 2007 slides. –  Jukka Suomela Sep 1 '10 at 19:13
1  
@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. :) –  Jukka Suomela Sep 1 '10 at 19:40
1  
here's a pop-sci rendition of that work: tinyurl.com/2f39jrb –  Suresh Venkat Sep 1 '10 at 19:43
1  
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 –  Alexandru Sep 3 '10 at 15:37
1  
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? –  Raphael Jan 19 '11 at 6:37

10 Answers 10

up vote 28 down vote accepted

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)

share|improve this answer
    
It looks like the first link is defunct. –  JeremyKun Apr 29 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...) –  Joshua Grochow Apr 29 at 2:54
    
I'm still getting a "Page Not Found" error from the Wiley Library. Could it be a formatting/browser issue? –  JeremyKun Apr 29 at 13:35
    
@JeremyKun: Could be. If you have access to MathSciNet, try this link instead: ams.org/mathscinet-getitem?mr=1667317 –  Joshua Grochow Apr 29 at 15:29
    
It's not a problem because the link to his homepage works. I was just trying to help make this answer better :) –  JeremyKun Apr 29 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

share|improve this answer
1  
Adding a link would improve this answer. –  Dave Clarke Sep 4 '10 at 13:54

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.

share|improve this answer

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

share|improve this answer
    
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. –  Aaron Sterling Sep 3 '10 at 14:19
2  
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. –  Per Kristian Lehre Sep 3 '10 at 14:31

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.

share|improve this answer

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.

share|improve this answer
1  
hey, he's back :) –  Suresh Venkat Jan 19 '11 at 3:44

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)

share|improve this answer

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)

share|improve this answer
    
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 '12 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.