TY  - JOUR
A1  - Doerr, Benjamin
A1  - Krejca, Martin Stefan
T1  - A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes
JF  - Theoretical computer science
N2  - With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LEADINGONES benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum in a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. Under similar assumptions, we prove a lower bound that matches our upper bound up to constant factors.
KW  - Theory
KW  - Estimation-of-distribution algorithm
KW  - Run time analysis
Y1  - 2021
U6  - https://doi.org/10.1016/j.tcs.2020.11.028
SN  - 0304-3975
SN  - 1879-2294
VL  - 851
SP  - 121
EP  - 128
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
T1  - First-hitting times under drift
JF  - Theoretical computer science
N2  - 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 lower-bounded, that is, we remove unnecessary restrictions like a finite, discrete, or bounded state space. As corollaries, the same is true for our upper bounds in the case of variable and multiplicative drift. By bounding the step size of the process, we derive new lower-bounding multiplicative and variable drift theorems. Last, we also state theorems that are applicable when the process has a drift of 0, by using a drift on the variance of the process.
KW  - First-hitting time
KW  - Random process
KW  - Drift
Y1  - 2019
U6  - https://doi.org/10.1016/j.tcs.2019.08.021
SN  - 0304-3975
SN  - 1879-2294
VL  - 796
SP  - 51
EP  - 69
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Friedrich, Tobias
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
T1  - Unbiasedness of estimation-of-distribution algorithms
JF  - Theoretical computer science
N2  - In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics - especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-lambda-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, lambda-MMAS(IB), and cGA. We show that an n-Bernoulli-lambda-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [0, 1](n). By restricting how an n-Bernoulli-lambda-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased. (C) 2018 Elsevier B.V. All rights reserved.
KW  - Estimation-of-distribution algorithm
KW  - Unbiasedness
KW  - Theory
Y1  - 2019
U6  - https://doi.org/10.1016/j.tcs.2018.11.001
SN  - 0304-3975
SN  - 1879-2294
VL  - 785
SP  - 46
EP  - 59
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Friedrich, Tobias
A1  - Krejca, Martin Stefan
A1  - Rothenberger, Ralf
A1  - Arndt, Tobias
A1  - Hafner, Danijar
A1  - Kellermeier, Thomas
A1  - Krogmann, Simon
A1  - Razmjou, Armin
T1  - Routing for on-street parking search using probabilistic data
JF  - AI communications : AICOM ; the European journal on artificial intelligence
N2  - A significant percentage of urban traffic is caused by the search for parking spots. One possible approach to improve this situation is to guide drivers along routes which are likely to have free parking spots. The task of finding such a route can be modeled as a probabilistic graph problem which is NP-complete. Thus, we propose heuristic approaches for solving this problem and evaluate them experimentally. For this, we use probabilities of finding a parking spot, which are based on publicly available empirical data from TomTom International B.V. Additionally, we propose a heuristic that relies exclusively on conventional road attributes. Our experiments show that this algorithm comes close to the baseline by a factor of 1.3 in our cost measure. Last, we complement our experiments with results from a field study, comparing the success rates of our algorithms against real human drivers.
KW  - Parking search
KW  - probabilistic routing
KW  - constrained optimization
KW  - field study
Y1  - 2019
U6  - https://doi.org/10.3233/AIC-180574
SN  - 0921-7126
SN  - 1875-8452
VL  - 32
IS  - 2
SP  - 113
EP  - 124
PB  - IOS Press
CY  - Amsterdam
ER  - 
TY  - GEN
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
T1  - First-Hitting times under additive drift
T2  - Parallel Problem Solving from Nature – PPSN XV, PT II
N2  - 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.
Y1  - 2018
SN  - 978-3-319-99259-4
SN  - 978-3-319-99258-7
U6  - https://doi.org/10.1007/978-3-319-99259-4_8
SN  - 0302-9743
SN  - 1611-3349
VL  - 11102
SP  - 92
EP  - 104
PB  - Springer
CY  - Cham
ER  - 
TY  - GEN
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
T1  - First-Hitting times for finite state spaces
T2  - Parallel Problem Solving from Nature – PPSN XV, PT II
N2  - One of the most important aspects of a randomized algorithm is bounding its expected run time on various problems. Formally speaking, this means bounding the expected first-hitting time of a random process. The two arguably most popular tools to do so are the fitness level method and drift theory. The fitness level method considers arbitrary transition probabilities but only allows the process to move toward the goal. On the other hand, drift theory allows the process to move into any direction as long as it move closer to the goal in expectation; however, this tendency has to be monotone and, thus, the transition probabilities cannot be arbitrary. We provide a result that combines the benefit of these two approaches: our result gives a lower and an upper bound for the expected first-hitting time of a random process over {0,..., n} that is allowed to move forward and backward by 1 and can use arbitrary transition probabilities. In case that the transition probabilities are known, our bounds coincide and yield the exact value of the expected first-hitting time. Further, we also state the stationary distribution as well as the mixing time of a special case of our scenario.
Y1  - 2018
SN  - 978-3-319-99259-4
SN  - 978-3-319-99258-7
U6  - https://doi.org/10.1007/978-3-319-99259-4_7
SN  - 0302-9743
SN  - 1611-3349
VL  - 11102
SP  - 79
EP  - 91
PB  - Springer
CY  - Cham
ER  - 
TY  - GEN
A1  - Blaesius, Thomas
A1  - Eube, Jan
A1  - Feldtkeller, Thomas
A1  - Friedrich, Tobias
A1  - Krejca, Martin Stefan
A1  - Lagodzinski, Gregor J. A.
A1  - Rothenberger, Ralf
A1  - Severin, Julius
A1  - Sommer, Fabian
A1  - Trautmann, Justin
T1  - Memory-restricted Routing With Tiled Map Data
T2  - 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)
N2  - Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
Y1  - 2018
SN  - 978-1-5386-6650-0
U6  - https://doi.org/10.1109/SMC.2018.00567
SN  - 1062-922X
SP  - 3347
EP  - 3354
PB  - IEEE
CY  - New York
ER  - 
TY  - JOUR
A1  - Friedrich, Tobias
A1  - Kötzing, Timo
A1  - Krejca, Martin Stefan
A1  - Sutton, Andrew M.
T1  - Robustness of Ant Colony Optimization to Noise
JF  - Evolutionary computation
N2  - Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo- Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical (mu + 1) EA outperforms any ACO algorithm, with smaller mu being better; however, in the case of large noise, the (mu + 1) EA fails, even for high values of mu (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner; that is, as long as the evaporation factor. is small enough, dependent on the variance s2 of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.
KW  - Ant colony optimization
KW  - Noisy Fitness
KW  - Theory
KW  - Run time analysis
Y1  - 2016
U6  - https://doi.org/10.1162/EVCO_a_00178
SN  - 1063-6560
SN  - 1530-9304
VL  - 24
SP  - 237
EP  - 254
PB  - MIT Press
CY  - Cambridge
ER  -