59
$\begingroup$

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

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

10 Answers 10

Reset to default
29
$\begingroup$

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)

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

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Adding a link would improve this answer. $\endgroup$
    – Dave Clarke
    Commented Sep 4, 2010 at 13:54
10
$\begingroup$

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.

Improve this answer
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Commented Sep 3, 2010 at 14:19
  • 2
    $\begingroup$ 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. $\endgroup$
    – Per Kristian Lehre
    Commented Sep 3, 2010 at 14:31
10
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ hey, he's back :) $\endgroup$
    – Suresh Venkat
    Commented Jan 19, 2011 at 3:44
6
$\begingroup$

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)

Improve this answer
$\endgroup$
6
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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.... $\endgroup$
    – vzn
    Commented Oct 20, 2012 at 3:22
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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