Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration

ABSTRACT

Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that ED As may improve optimisation performance on epistatic fitness landscapes by learning variable interactions.

However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in 𝒪(nλ log λ) [9]. Later, Krejca and Witt proved the lower bound [EQUATION] via an involved drift analysis [16].

We prove a O (nλ) bound, given some restrictions on the population size. This implies the tight bound Θ (n log n) when λ = O (log n), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.

References

1. Jean-Bernard Baillon, Roberto Cominetti, and Jose Vaisman. 2016. A sharp uniform bound for the distribution of sums of Bernoulli trials. Combinatorics, Probability and Computing 25, 3 (2016), 352--361.
2. Ronald Rivest Charles E. Leiserson, Clifford Stein and Thomas H. Cormen. 2009. Introduction to Algorithms. MIT Press.
3. Tianshi Chen, Per Kristian Lehre, Ke Tang, and Xin Yao. 2009. When is an Estimation of Distribution Algorithm Better than an Evolutionary Algorithm?. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2009. 1470--1477.
4. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao. 2007. On the analysis of average time complexity of estimation of distribution algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2007. 453--460.
5. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao. 2009. Rigorous Time Complexity Analysis of Univariate Marginal Distribution Algorithm with Margins. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2009. 2157--2164.
6. Tianshi Chen, Ke Tang, Guoliang Chen, and Xin Yao. 2010. Analysis of Computational Time of Simple Estimation of Distribution Algorithms. IEEE Transactions on Evolutionary Computation 14, 1 (2010), 1--22.
7. Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. 2014. Level-Based Analysis of Genetic Algorithms and Other Search Processes. In Proceedings of Parallel Problem Solving from Nature - PPSN XIII. 912--921.
8. Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre. 2016. Level-based Analysis of Genetic Algorithms and other Search Processes. CoRR abs/1407.7663 (2016). http://arxiv.org/abs/1407.7663
9. Duc-Cuong Dang and Per Kristian Lehre. 2015. Simplified Runtime Analysis of Estimation of Distribution Algorithms. In Proceedings of Genetic and Evolutionary Computation Conference, GECCO'15.
10. Stefan Droste. 2006. A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing 5, 3 (2006), 257--283.
11. Uriel Feige. 2004. On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. In Proceedings of the 36th STOC. 594--603.
12. Tobias Friedrich, Timo Kötzing, and Martin S. Krejca. 2016. EDAs cannot be balanced and stable. In Proceedings of Genetic and Evolutionary Computation Conference, GECCO'16.
13. Georges R. Harik, Fernando G. Lobo, and David E. Goldberg. 1999. The compact genetic algorithm. IEEE Transactions on Evolutionary Computation 3, 4 (1999), 287--297.
14. Mark Hauschild and Martin Pelikan. 2011. An introduction and survey of estimation of distribution algorithms. Swarm and Evolutionary Computation 1, 3 (2011), 111--128.
15. Kumar Jogdeo and S. M. Samuels. 1968. Monotone Convergence of Binomial Probabilities and a Generalization of Ramanujan's Equation. The Annals of Mathematical Statistics 39, 4 (1968), 1191--1195.
16. Martin S. Krejca and Carsten Witt. 2017. Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax. In Proceedings of Foundation of Genetic Algorithms, FOGA'17.
17. Per Kristian Lehre and Xin Yao. 2014. Runtime analysis of the (1+1) EA on computing unique input output sequences. Information Sciences 259 (2014), 510--531.
18. Heinz Mühlenbein and Gerhard Paaß. 1996. From recombination of genes to the estimation of distributions I. Binary parameters. In Parallel Problem Solving from Nature - PPSN IV, Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel (Eds.). Lecture Notes in Computer Science, Vol. 1141. Springer Berlin Heidelberg, 178--187.
19. Jonathan L. Shapiro. 2005. Drift and Scaling in Estimation of Distribution Algorithms. Evolutionary Computation 13, 1 (2005), 99--123.
20. Carsten Witt. 2017. Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax. In (To appear) Proceedings of Genetic and Evolutionary Computation Conference, GECCO'17.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Theory of randomized search heuristics