Top

Published in:

2018 | OriginalPaper | Chapter

First-Hitting Times Under Additive Drift

Authors : Timo Kötzing, Martin S. Krejca

Published in: Parallel Problem Solving from Nature – PPSN XV

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

For the last ten years, almost every theoretical result concerning the expected run time of a randomized search heuristic used drift theory, making it the arguably most important tool in this domain. Its success is due to its ease of use and its powerful result: drift theory allows the user to derive bounds on the expected first-hitting time of a random process by bounding expected local changes of the process – the drift. This is usually far easier than bounding the expected first-hitting time directly.

Due to the widespread use of drift theory, it is of utmost importance to have the best drift theorems possible. We improve the fundamental additive, multiplicative, and variable drift theorems by stating them in a form as general as possible and providing examples of why the restrictions we keep are still necessary. Our additive drift theorem for upper bounds only requires the process to be nonnegative, that is, we remove unnecessary restrictions like a finite, discrete, or bounded search space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter First-Hitting Times for Finite State Spaces

next chapter Level-Based Analysis of the Population-Based Incremental Learning Algorithm

Lengler [13] briefly mentions infinite search spaces and also gives a proof for a restricted version of the additive drift theorem in the setting of an unbounded discrete search space.

For the upper bound, we require the search space to be lower-bounded but not upper-bounded. We still refer to such a setting as unbounded.

More information on filtrations can be found, for example, in Randomized Algorithms [15] in the section on martingales.

Intuitively, for the natural filtration, a stopping time

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-99259-4_8/472474_1_En_8_IEq33_HTML.gif

is a random variable over

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-99259-4_8/472474_1_En_8_IEq34_HTML.gif

such that, for all

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-99259-4_8/472474_1_En_8_IEq35_HTML.gif

, the event

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-99259-4_8/472474_1_En_8_IEq36_HTML.gif

is only dependent on

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-99259-4_8/472474_1_En_8_IEq37_HTML.gif

Azuma, K.: Weighted sums of certain dependent random variables. Tohoku Math. J. 19(3), 357–367 (1967)MathSciNetCrossRef

Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65(1), 224–250 (2013)MathSciNetCrossRef

Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673–697 (2012)MathSciNetCrossRef

Doerr, B., Kötzing, T., Lagodzinski, J.A.G., Lengler, J.: Bounding bloat in genetic programming. In: Proceedings of the GECCO 2017, pp. 921–928 (2017)

Grimmett, G.R., Stirzaker, D.R.: Probability and Random Processes. Oxford University Press, Oxford (2001)MATH

Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3), 502–525 (1982)MathSciNetCrossRef

He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127(1), 57–85 (2001)MathSciNetCrossRef

He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3(1), 21–35 (2004)MathSciNetCrossRef

Johannsen, D.: Random combinatorial structures and randomized search heuristics. Ph.D. thesis, Universität des Saarlandes (2010). http://scidok.sulb.uni-saarland.de/volltexte/2011/3529/pdf/Dissertation_3166_Joha_Dani_2010.pdf

10.

Kötzing, T.: Concentration of first hitting times under additive drift. Algorithmica 75(3), 490–506 (2016)MathSciNetCrossRef

11.

Kötzing, T., Krejca, M.S.: First-hitting times under additive drift. CoRR abs/1805.09415 (2018). https://arxiv.org/abs/1805.09415

12.

Lehre, P.K., Witt, C.: Concentrated hitting times of randomized search heuristics with variable drift. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 686–697. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13075-0_54CrossRef

13.

Lengler, J.: Drift analysis. CoRR abs/1712.00964 (2017). http://arxiv.org/abs/1712.00964

14.

Mitavskiy, B., Rowe, J.E., Cannings, C.: Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. Int. J. Intell. Comput. Cybern. 2(2), 243–284 (2009)MathSciNetCrossRef

15.

Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)CrossRef

16.

Oliveto, P.S., Witt, C.: Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3), 369–386 (2011)MathSciNetCrossRef

17.

Oliveto, P.S., Witt, C.: Erratum: simplified drift analysis for proving lower bounds in evolutionary computation. CoRR abs/1211.7184 (2012). http://arxiv.org/abs/1211.7184

18.

Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the (1, \(\lambda \)) evolutionary algorithm. Theor. Comput. Sci. 545, 20–38 (2014)MathSciNetCrossRef

19.

Semenov, M.A., Terkel, D.A.: Analysis of convergence of an evolutionary algorithm with self-adaptation using a Stochastic Lyapunov function. Evol. Comput. 11(4), 363–379 (2003)CrossRef

Title: First-Hitting Times Under Additive Drift
Authors: Timo Kötzing
Martin S. Krejca
Publisher: Springer International Publishing
Book: Parallel Problem Solving from Nature – PPSN XV
Print ISBN: 978-3-319-99258-7

Electronic ISBN: 978-3-319-99259-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-99259-4_8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner