Run Time Bounds for Integer-Valued OneMax Functions
Authors: 
Jonathan Gadea Harder, Timo Kötzing, Xiaoyue Li, Aishwarya Radhakrishnan, Janosch RuffAuthors Info & Claims
Pages 1569 - 1577
Abstract
While most theoretical run time analyses of discrete randomized search heuristics focus on finite search spaces, we consider the search space Zn. Understanding this search space is especially relevant for developing better algorithms for mixed-integer black box optimization (MI-BBO) problems.
We consider as a fitness functions the distance to the (unique) non-zero optimum a (based on the ℓ1-metric) and study the (1+1) EA which mutates by applying a step-operator on each component that is determined to be varied. For changing by ±1, we show that the expected optimization time is Θ(n · (|a|∞ + log(|a|H))). In particular, the time is linear in |a|∞, a measure of distance between starting point and target a. Employing a different step operator which chooses a step size from a distribution so heavy-tailed that the expectation is infinite, we get an optimization time of O(n · log2(|a|1) · (log(log(|a|1)))1+∈).
Furthermore, we show that RLS with step size adaptation achieves an optimization time of Θ(n · log(|a|1)) and that ℓ1-symmetric operators (as suggested by Rudolph'94) require a time at least linear in |a|1.
We complement our findings with experimental results which show that asymptotically sub-optimal algorithms can be faster for smaller values of |a|∞.
Supplemental Material
PDF File
Supplementary Material
- Download
- 1.62 MB
References
[1]
Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2022. Fast Mutation in Crossover-Based Algorithms. Algorithmica (2022), 1724--1761.
[2]
Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2023. Lazy Parameter Tuning and Control: Choosing All Parameters Randomly from a Power-Law Distribution. Algorithmica (2023), 442--484.
[3]
Anh Viet Do, Mingyu Guo, Aneta Neumann, and Frank Neumann. 2021. Analysis of Evolutionary Diversity Optimisation for Permutation Problems (GECCO '21). 574--582.
[4]
Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2015. Solving Problems with Unknown Solution Length at (Almost) No Extra Cost (GECCO '15). 831--838.
[5]
Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2017. Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables. Algorithmica 80 (2017).
[6]
Benjamin Doerr, Yassine Ghannane, and Marouane Ibn Brahim. 2022. Towards a Stronger Theory for Permutation-Based Evolutionary Algorithms (GECCO '22). 1390--1398.
[7]
Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2012. Multiplicative Drift Analysis. Algorithmica 64, 4 (2012), 673--697.
[8]
Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast Genetic Algorithms (GECCO '17). 777--784.
[9]
K. W. Fang. 1990. Symmetric Multivariate and Related Distributions (1st ed.). Chapman and Hall/CRC.
[10]
Jun He and Xin Yao. 2004. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing 3 (2004), 21--35.
[11]
Timo Kötzing and Martin S. Krejca. 2019. First-hitting times under drift. Theoretical Computer Science 796 (2019), 51--69.
[12]
Per Kristian Lehre and Carsten Witt. 2012. Black-Box Search by Unbiased Variation. Algorithmica 64, 4 (2012), 623--642.
[13]
Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.
[14]
Günter Rudolph. 1994. An evolutionary algorithm for integer programming. In Parallel Problem Solving from Nature --- PPSN III, Yuval Davidor, Hans-Paul Schwefel, and Reinhard Männer (Eds.). 139--148.
[15]
André Thomaser, Jacob De Nobel, Diederick Vermetten, Furong Ye, Thomas Bäck, and Anna Kononova. 2023. When to be Discrete: Analyzing Algorithm Performance on Discretized Continuous Problems. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '23). 856--863.
Index Terms
- Run Time Bounds for Integer-Valued OneMax Functions
Recommendations
Unknown solution length problems with no asymptotically optimal run time
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceWe revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length N, but only n ≪ N of them have an influence on the fitness. Neither the position of these relevant bits ...
Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax
FOGA '17: Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic AlgorithmsThe Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, ...
A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationUnderstanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1657 pages
This work is licensed under a Creative Commons Attribution-NoDerivs International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '24
Sponsor:
GECCO '24: Genetic and Evolutionary Computation Conference
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 74Total Downloads
- Downloads (Last 12 months)74
- Downloads (Last 6 weeks)13
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in