×

Tail bounds on hitting times of randomized search heuristics using variable drift analysis. (English) Zbl 1512.68443

Summary: Drift analysis is one of the state-of-the-art techniques for the runtime analysis of randomized search heuristics (RSHs) such as evolutionary algorithms (EAs), simulated annealing, etc. The vast majority of existing drift theorems yield bounds on the expected value of the hitting time for a target state, for example the set of optimal solutions, without making additional statements on the distribution of this time. We address this lack by providing a general drift theorem that includes bounds on the upper and lower tail of the hitting time distribution. The new tail bounds are applied to prove very precise sharp-concentration results on the running time of a simple EA on standard benchmark problems, including the class of general linear functions. On all these problems, the probability of deviating by an \(r\)-factor in lower-order terms of the expected time decreases exponentially with \(r\). The usefulness of the theorem outside the theory of RSHs is demonstrated by deriving tail bounds on the number of cycles in random permutations. All these results handle a position-dependent (variable) drift that was not covered by previous drift theorems with tail bounds. Finally, user-friendly specializations of the general drift theorem are given.

MSC:

68W20 Randomized algorithms
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
Full Text: DOI

References:

[1] Arratia, R. and Tavaré, S. (1992) The cycle structure of random permutations. Ann. Probab.201567-1591. · Zbl 0759.60007
[2] Auger, A. and Doerr, B., eds, (2011) Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific. · Zbl 1233.90005
[3] Coffman, E. G., Feldmann, A., Kahale, N. and Poonen, B. (1999) Computing call admission capacities in linear networks. Probab. Engrg Inform. Sci.13387-406. · Zbl 0969.90025
[4] Doerr, B., Doerr, C. and Kötzing, T. (2016) The right mutation strength for multi-valued decision variables. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2016), pp. 1115-1122. ACM Press.
[5] Doerr, B., Doerr, C. and Yang, J. (2020) Optimal parameter choices via precise black-box analysis. Theoret. Comput. Sci.8011-34. · Zbl 1436.68408
[6] Doerr, B., Fouz, M. and Witt, C. (2011) Sharp bounds by probability-generating functions and variable drift. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), pp. 2083-2090. ACM Press.
[7] Doerr, B. and Goldberg, L. A. (2013) Adaptive drift analysis. Algorithmica65224-250. · Zbl 1277.68289
[8] Doerr, B., Jansen, T., Witt, C. and Zarges, C. (2013) A method to derive fixed budget results from expected optimisation times. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2013), pp. 1581-1588. ACM Press.
[9] Doerr, B., Johannsen, D. and Winzen, C. (2012) Multiplicative drift analysis. Algorithmica64673-697. · Zbl 1264.68220
[10] Doerr, B. and Neumann, F., eds, (2020) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer. · Zbl 1429.68004
[11] Droste, S., Jansen, T. and Wegener, I. (2002) On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci.27651-81. · Zbl 1002.68037
[12] Eryilmaz, A. and Srikant, R. (2012) Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst. Theory Appl.72311-359. · Zbl 1273.90054
[13] Feldmann, M. and Kötzing, T. (2013) Optimizing expected path lengths with ant colony optimization using fitness proportional update. In Proceedings of Foundations of Genetic Algorithms (FOGA 2013), pp. 65-74. ACM Press. · Zbl 1369.68307
[14] Gießen, C. and Witt, C. (2018) Optimal mutation rates for the (1 + λ) EA on OneMax through asymptotically tight drift analysis. Algorithmica801710-1731. · Zbl 1390.68596
[15] Hajek, B. (1982) Hitting and occupation time bounds implied by drift analysis with applications. Adv. Appl. Probab.14502-525. · Zbl 0495.60094
[16] He, J. and Yao, X. (2001) Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell.12757-85. Erratum in Artif. Intell. 140 (2002) 245-248. · Zbl 1052.68113
[17] Hwang, H., Panholzer, A., Rolin, N., Tsai, T. and Chen, W. (2018) Probabilistic analysis of the (1+1)-evolutionary algorithm. Evol. Comput.26299-345.
[18] Jägersküpper, J. (2011) Combining Markov-chain analysis and drift analysis: the (1+1) evolutionary algorithm on linear functions reloaded. Algorithmica59409-424. · Zbl 1211.68382
[19] Jansen, T. (2013) Analyzing Evolutionary Algorithms: The Computer Science Perspective, Natural Computing Series. Springer. · Zbl 1282.68008
[20] Jansen, T. (2020) Analysing stochastic search heuristics operating on a fixed budget. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization (Doerr, B. and Neumann, F., eds), pp. 249-270. Springer.
[21] Johannsen, D. (2010) Random combinatorial structures and randomized search heuristics. PhD thesis, Universität des Saarlandes, Germany.
[22] Karp, R. M. (1994) Probabilistic recurrence relations. J. Assoc. Comput. Mach.411136-1150. · Zbl 0830.68046
[23] Kötzing, T. (2016) Concentration of first hitting times under additive drift. Algorithmica75490-506. · Zbl 1348.68229
[24] Kötzing, T. and Krejca, M. S. (2019) First-hitting times under drift. Theoret. Comput. Sci.79651-69. · Zbl 1435.68218
[25] Kötzing, T. and Witt, C. (2020) Improved fixed-budget results via drift analysis. In Proceedings of Parallel Problem Solving from Nature (PPSN 2020), Vol. 12270 of Lecture Notes in Computer Science, pp. 648-660. Springer.
[26] Lehre, P. K. (2011) Negative drift in populations. In Proceedings of Parallel Problem Solving from Nature (PPSN 2010), Vol. 6238 of Lecture Notes in Computer Science, pp. 244-253. Springer.
[27] Lehre, P. K. (2012) Drift analysis (tutorial). In Companion to GECCO 2012, pp. 1239-1258. ACM Press.
[28] Lehre, P. K. and Witt, C. (2014) Concentrated hitting times of randomized search heuristics with variable drift. In Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), Vol. 8889 of Lecture Notes in Computer Science, pp. 686-697. Springer. · Zbl 1342.68309
[29] Lehre, P. K. and Witt, C. (2018) General drift analysis with tail bounds. Preprint of this paper, including supplementary material. arXiv:1211.7184
[30] Lengler, J. (2020) Drift analysis. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization (Doerr, B. and Neumann, F., eds), pp. 89-131. Springer.
[31] Lengler, J. and Steger, A. (2018) Drift analysis and evolutionary algorithms revisited. Combin. Probab. Comput.27643-666. · Zbl 1484.68324
[32] Mitavskiy, B., Rowe, J. E. and Cannings, C. (2009) Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intelligent Computing Cybernetics2243-284. · Zbl 1175.90210
[33] Neumann, F. and Witt, C. (2010) Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity, Natural Computing Series. Springer. · Zbl 1223.68002
[34] Oliveto, P. S. and Witt, C. (2011) Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica59369-386. · Zbl 1211.68521
[35] Oliveto, P. S. and Witt, C. (2012) Erratum: Simplified drift analysis for proving lower bounds in evolutionary computation. arXiv:1211.7184 · Zbl 1211.68521
[36] Rowe, J. E. and Sudholt, D. (2012) The choice of the offspring population size in the (1, λ) EA. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012), pp. 1349-1356. ACM Press.
[37] Sasak, G. H. and Hajek, B. (1988) The time complexity of maximum matching by simulated annealing. J. Assoc. Comput. Mach.35387-403.
[38] Sudholt, D. (2013) A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17 418-435.
[39] Wegener, I. (2001) Theoretical aspects of evolutionary algorithms. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001), Vol. 2076 of Lecture Notes in Computer Science, pp. 64-78. Springer. · Zbl 0986.68137
[40] Witt, C. (2013) Tight bounds on the optimization time of a randomized search heuristic on linear functions. Combin. Probab. Comput.22294-318. Preliminary version in STACS 2012.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.