Max-Planck-Institut für Informatik, Campus E1 4, 66123 Saarbrücken, Germany.
Evol Comput. 2011 Winter;19(4):673-91. doi: 10.1162/EVCO_a_00047. Epub 2011 Sep 16.
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.
我们对 Scharnow、Tinnefeld 和 Wegener（2004 年，《排序和最短路径问题的进化算法分析》，《数学建模与算法杂志》，第 3 卷（4）：349-366）提出的用于单源最短路径问题的（1+1）进化算法进行了严格的分析。我们证明，在很大的概率下，优化时间为 O(n2 max{ℓ, log(n)})，其中 ℓ 是最小的整数，使得任何顶点都可以通过具有最多 ℓ 条边的最短路径从源到达。该界是紧的。对于所有的 n 和 ℓ，我们提供一个带有边权的图，使得在很大的概率下，优化时间的阶为 Ω(n2 max{ℓ, log(n)})。为了得到这样的精确界，我们开发了一种新的技术，克服了以前使用的论点中的彩票收集者行为。此外，我们还展示了一个简单的 Chernoff 型不等式，用于独立的几何分布随机变量的和，以及一个用于不是独立的，但表现出与前面的随机变量的结果无关的期望行为的随机变量序列。我们乐观地认为这些工具在进化算法的分析中会有进一步的应用。
