<p>Have a look at <a href="http://www.lix.polytechnique.fr/Labo/Benjamin.Doerr/" rel="nofollow noreferrer">the work of Benjamin Doerr</a> from École Polytechnique and formerly the Algorithms group at Max Planck (MPI). It is all about trying to make provable contributions to evolutionary algorithms.</p>
<p>In particular, Doerr has co-edited a relevant recent book, <a href="https://www.worldscientific.com/worldscibooks/10.1142/7438#t=aboutBook" rel="nofollow noreferrer">Theory of Randomized Search Heuristics</a></p>

CC BY-SA 2.5
2010-09-04T13:54:00.173Z
Adding a link would improve this answer.
Dave Clarke
CC BY-SA 4.0
2010-09-04T13:51:29.927Z
2023-01-31T19:13:38.867Z
2023-01-31T19:13:38.867Z
Alex Lopez-Ortiz
<p>As well as working on simulated annealing, Ingo Wegener had some theoretical results on evolutionary algorithms. The <a href="http://ls2-www.cs.uni-dortmund.de/~sudholt/dissertation-sudholt.pdf">thesis</a> of his PhD student Dirk Sudholt is also worth a look.</p>

CC BY-SA 2.5
2010-09-01T23:20:14.763Z
2010-09-01T23:20:14.763Z
Rahul Savani
<p>Do you know this paper:</p>
<p>Jens Jägersküpper. <a href="https://doi.org/10.1007/s00453-010-9396-y" rel="nofollow noreferrer">Combining Markov-Chain Analysis and Drift Analysis: The (1+1) Evolutionary Algorithm on Linear Functions Reloaded</a>.</p>
<p>It shows an expected running time of <span class="math-container">$O(n\log n)$</span> for linear functions for a class of evolutionary algorithms.</p>

CC BY-SA 4.0
2010-09-02T02:09:09.633Z
2022-10-09T10:14:02.580Z
2022-10-09T10:14:02.580Z
Marcos Villagra
<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.8474&amp;rep=rep1&amp;type=pdf">Oliveto et al. (2007)</a>.</p>

CC BY-SA 2.5
2010-09-03T14:19:58.107Z
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
CC BY-SA 2.5
2010-09-03T14:31:08.540Z
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): http://www.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
CC BY-SA 2.5
2010-09-03T13:40:59.907Z
2010-09-03T13:40:59.907Z
Per Kristian Lehre
<p><a href="http://www.cc.gatech.edu/~vempala/papers/vol4.ps">Lovasz and Vempala</a> (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.</p>

CC BY-SA 2.5
2011-01-19T03:44:17.253Z
hey, he's back :)
Suresh Venkat
CC BY-SA 2.5
2011-01-19T02:19:23.047Z
2011-01-19T02:19:23.047Z
Joshua Grochow
<p>Check these references:</p>

<p>Lothar  Schmitt, <a href="http://portal.acm.org/citation.cfm?id=967712">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</a>
<a href="http://portal.acm.org/citation.cfm?id=967712"></a></p>

<p>Shiu Yin Yuen; B.K.S. Cheung, <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1583623">Bounds for probability of success of classical genetic algorithm based on hamming distance</a>
<a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1583623"></a></p>

<p>Chang C. Y. Dorea; Judinor A. Guerra Jr.; Rafael Morgado; Andre G. C. Pereira, <a href="http://www.informaworld.com/smpp/content~db=all~content=a919893617">Multistage Markov Chain Modeling of the Genetic Algorithm and Convergence Results</a>
<a href="http://www.informaworld.com/smpp/content~db=all~content=a919893617"></a></p>

<p>C. Dombry, <a href="http://www-math.univ-poitiers.fr/~dombry/marcheponderee-JAP.pdf">A weighted random walk model. Application to a
genetic algorithm</a>
<a href="http://www-math.univ-poitiers.fr/~dombry/marcheponderee-JAP.pdf"></a></p>

CC BY-SA 2.5
2010-09-01T20:32:43.463Z
2010-09-01T20:58:10.627Z
2010-09-01T20:58:10.627Z
Mohammad Al-Turkistany
<p>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: </p>

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

<p>The convergence proof uses a Markov chain model.</p>

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

CC BY-SA 2.5
2011-02-21T12:58:52.467Z
2011-02-21T12:58:52.467Z
Lamine
<p>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 <em>symmetry argument</em>, 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.</p>

<p>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 <strong>implicit parallelism</strong> 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 <a href="http://blog.hackingevolution.net/2013/03/24/implicit-concurrency-in-genetic-algorithms/" rel="nofollow">this</a> blog post.)</p>

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

<p><a href="http://s3.amazonaws.com/burjorjee/www/foga010-burjorjee.pdf" rel="nofollow">Explaining optimization in genetic algorithms with uniform crossover</a>. To appear in the proceedings of the Foundations of Genetic Algorithms 2013 conference. </p>

<p>(Disclaimer: I am the paper's author) </p>

CC BY-SA 3.0
2012-10-20T03:22:43.050Z
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
CC BY-SA 3.0
2012-10-19T09:38:07.587Z
2013-04-11T07:42:06.673Z
2013-04-11T07:42:06.673Z
Keki Burjorjee
<p><A HREF="http://www.math.u-psud.fr/~cerf/">Raphael Cerf</A> did his PhD <A HREF="http://www.math.u-psud.fr/~cerf/atga.ps.gz">thesis</A> 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.</p>

CC BY-SA 2.5
2011-02-21T13:09:39.797Z
2011-02-21T13:09:39.797Z
J.y B.y
<p>Y. Rabinovich, A. Wigderson. <a href="http://dx.doi.org/10.1002/(SICI)1098-2418(199903)14:2%3c111::AID-RSA1%3e3.0.CO;2-6">Techniques for bounding the convergence rate of genetic algorithms.</a> Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999. (Also available <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/YURI/GENALG/paper.pdf">from Avi Wigderson's home page</a>)</p>

CC BY-SA 3.0
2014-04-29T02:13:22.277Z
It looks like the first link is defunct.
Jeremy Kun
CC BY-SA 3.0
2014-04-29T02:54:58.243Z
@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
CC BY-SA 3.0
2014-04-29T13:35:55.357Z
I'm still getting a "Page Not Found" error from the Wiley Library. Could it be a formatting/browser issue?
Jeremy Kun
CC BY-SA 3.0
2014-04-29T15:29:32.043Z
@JeremyKun: Could be. If you have access to MathSciNet, try this link instead: http://www.ams.org/mathscinet-getitem?mr=1667317
Joshua Grochow
CC BY-SA 3.0
2014-04-29T19:13:32.353Z
It's not a problem because the link to his homepage works. I was just trying to help make this answer better :)
Jeremy Kun
CC BY-SA 2.5
2010-09-01T19:55:09.550Z
2010-09-01T19:55:09.550Z
Joshua Grochow
<p>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 <a href="http://www2.research.att.com/~dsj/papers/stspchap.pdf" rel="noreferrer">is quite effective for Euclidean TSP</a> in practice. </p>

<p>Some metaheuristics are reasonably well studied theoretically: there's <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pls" rel="noreferrer">work on local search</a>, and annealing. We have a pretty good sense of how alternating optimization (<a href="http://en.wikipedia.org/wiki/K-means%2B%2B" rel="noreferrer">like k-means</a>) works. But as far as I know, there's nothing really useful known about genetic algorithms. </p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/555/what-is-schema-theory-within-genetic-algorithms">schema theory</a>, 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). </p>

CC BY-SA 2.5
2010-09-01T19:13:58.267Z
For some inspiration, see also p. 25–29 of [Papadimitriou's FCRC 2007 slides](http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf).
Jukka Suomela
CC BY-SA 2.5
2010-09-01T19:34:37.820Z
that's a nice result and is in the realm of what I was looking for. maybe you should repost as an answer
Suresh Venkat
CC BY-SA 2.5
2010-09-01T19:40:58.757Z
@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
CC BY-SA 2.5
2010-09-01T19:43:10.907Z
here's a pop-sci rendition of that work: http://tinyurl.com/2f39jrb
Suresh Venkat
CC BY-SA 2.5
2010-09-02T08:34:49.827Z
Do Markov processes count?
Chris S
CC BY-SA 2.5
2010-09-02T08:39:38.080Z
I don't know. Do Markov processes have some equivalence with GAs ? do they capture GAs ?
Suresh Venkat
CC BY-SA 2.5
2010-09-03T15:21:01.897Z
(Markov aren't algorithmic, I missed that part)
Chris S
CC BY-SA 2.5
2010-09-03T15:37:18.193Z
I recently took a course in GA and my hype about GA has diminished when I learned the No Free Lunch Theorem: http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
Alexandru
CC BY-SA 2.5
2011-01-19T06:34:41.857Z
Oftentimes, the notion of GA/EA is not clear. What do you mean by that? For instance, I consider simulated annealing a means to increase their performance, not an alternative. Furthermore, simple versions seem to be quite similar in behaviour as techniques like MCMC.
Raphael
CC BY-SA 2.5
2011-01-19T06:37:46.173Z
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
<ds.algorithms><ne.neural-evol>
Provable statements about genetic algorithms
Suresh Venkat
# Provable statements about genetic algorithms

(Asked by: username_0 on 2010-09-01)

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](http://www2.research.att.com/~dsj/papers/stspchap.pdf) in practice.

Some metaheuristics are reasonably well studied theoretically: there's [work on local search](http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pls), and annealing. We have a pretty good sense of how alternating optimization ([like k-means](http://en.wikipedia.org/wiki/K-means%2B%2B)) 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](https://cstheory.stackexchange.com/questions/555/what-is-schema-theory-within-genetic-algorithms), 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).

**Tags:** ds.algorithms, ne.neural-evol

> **Comments:**
> **username_1**: For some inspiration, see also p. 25–29 of [Papadimitriou's FCRC 2007 slides](http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf).  
> **username_0**: that's a nice result and is in the realm of what I was looking for. maybe you should repost as an answer  
> **username_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. :)  
> **username_0**: here's a pop-sci rendition of that work: http://tinyurl.com/2f39jrb  
> **username_2**: Do Markov processes count?  
> **username_0**: I don't know. Do Markov processes have some equivalence with GAs ? do they capture GAs ?  
> **username_2**: (Markov aren't algorithmic, I missed that part)  
> **username_3**: I recently took a course in GA and my hype about GA has diminished when I learned the No Free Lunch Theorem: http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization  
> **username_4**: Oftentimes, the notion of GA/EA is not clear. What do you mean by that? For instance, I consider simulated annealing a means to increase their performance, not an alternative. Furthermore, simple versions seem to be quite similar in behaviour as techniques like MCMC.  
> **username_4**: username_3, 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?  

---

## 10 answers

### Answer by username_11 on 2010-09-01. Score: 29 | Accepted answer

Y. Rabinovich, A. Wigderson. [Techniques for bounding the convergence rate of genetic algorithms.](http://dx.doi.org/10.1002/(SICI)1098-2418(199903)14:2%3c111::AID-RSA1%3e3.0.CO;2-6) Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999. (Also available [from Avi Wigderson's home page](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/YURI/GENALG/paper.pdf))

> **Comments:**
> **username_17**: It looks like the first link is defunct.  
> **username_11**: @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...)  
> **username_17**: I'm still getting a "Page Not Found" error from the Wiley Library. Could it be a formatting/browser issue?  
> **username_11**: @JeremyKun: Could be. If you have access to MathSciNet, try this link instead: http://www.ams.org/mathscinet-getitem?mr=1667317  
> **username_17**: It's not a problem because the link to his homepage works. I was just trying to help make this answer better :)  

---

### Answer by username_5 on 2010-09-04. Score: 13

Have a look at [the work of Benjamin Doerr](http://www.lix.polytechnique.fr/Labo/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](https://www.worldscientific.com/worldscibooks/10.1142/7438#t=aboutBook)

> **Comments:**
> **username_6**: Adding a link would improve this answer.  

---

### Answer by username_7 on 2010-09-01. Score: 10

As well as working on simulated annealing, Ingo Wegener had some theoretical results on evolutionary algorithms. The [thesis](http://ls2-www.cs.uni-dortmund.de/~sudholt/dissertation-sudholt.pdf) of his PhD student Dirk Sudholt is also worth a look.


---

### Answer by username_8 on 2010-09-02. Score: 10

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](https://doi.org/10.1007/s00453-010-9396-y).

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


---

### Answer by username_9 on 2010-09-03. Score: 10

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)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.8474&rep=rep1&type=pdf).

> **Comments:**
> **username_10**: username_9, 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.  
> **username_9**: 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): http://www.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.  

---

### Answer by username_11 on 2011-01-19. Score: 7

[Lovasz and Vempala](http://www.cc.gatech.edu/~vempala/papers/vol4.ps) (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.

> **Comments:**
> **username_0**: hey, he's back :)  

---

### Answer by username_12 on 2010-09-01. Score: 6

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](http://portal.acm.org/citation.cfm?id=967712)

Shiu Yin Yuen; B.K.S. Cheung, [Bounds for probability of success of classical genetic algorithm based on hamming distance](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1583623)

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](http://www.informaworld.com/smpp/content~db=all~content=a919893617)

C. Dombry, [A weighted random walk model. Application to a
genetic algorithm](http://www-math.univ-poitiers.fr/~dombry/marcheponderee-JAP.pdf)


---

### Answer by username_13 on 2011-02-21. Score: 6

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 by username_14 on 2012-10-19. Score: 6

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](http://blog.hackingevolution.net/2013/03/24/implicit-concurrency-in-genetic-algorithms/) 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](http://s3.amazonaws.com/burjorjee/www/foga010-burjorjee.pdf). To appear in the proceedings of the Foundations of Genetic Algorithms 2013 conference.

(Disclaimer: I am the paper's author)

> **Comments:**
> **username_15**: 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....  

---

### Answer by username_16 on 2011-02-21. Score: 5

[username_4 Cerf](http://www.math.u-psud.fr/~cerf/) did his PhD [thesis](http://www.math.u-psud.fr/~cerf/atga.ps.gz) 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.


---

