Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
2014 Impact factor:

Evolutionary Computation

Winter 2011, Vol. 19, No. 4, Pages 673-691
(doi: 10.1162/EVCO_a_00047)
© 2011 by the Massachusetts Institute of Technology
Tight Analysis of the (1+1)-EA for the Single Source Shortest Path Problem
Article PDF (263.91 KB)

We conduct a rigorous analysis of the (1+1) evolutionary algorithm for the single source shortest path problem proposed by Scharnow, Tinnefeld, and Wegener (The analyses of evolutionary algorithms on sorting and shortest paths problems, 2004, Journal of Mathematical Modelling and Algorithms, 3(4):349–366). We prove that with high probability, the optimization time is O(n2 max{ℓ, log(n)}), where ℓ is the smallest integer such that any vertex can be reached from the source via a shortest path having at most ℓ edges.

This bound is tight. For all values of n and ℓ we provide a graph with edge weights such that, with high probability, the optimization time is of order Ω(n2 max{ℓ, log(n)}).

To obtain such sharp bounds, we develop a new technique that overcomes the coupon collector behavior of previously used arguments. Also, we exhibit a simple Chernoff type inequality for sums of independent geometrically distributed random variables, and one for sequences of random variables that are not independent, but show a desired behavior independent of the outcomes of the previous random variables. We are optimistic that these tools find further applications in the analysis of evolutionary algorithms.