TY - GEN
T1 - Towards Fixed-Target Black-Box Complexity Analysis
AU - Vinokurov, Dmitry
AU - Buzdalov, Maxim
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022/9/10
Y1 - 2022/9/10
N2 - Recently, fine-grained measures of performance of randomized search heuristics received attention in the theoretical community. In particular, some results were proven specifically for fixed-target runtime analysis. However, this research domain still lacks an important counterpart, namely, the (black-box) complexity analysis, which shall augment runtime analyses of particular algorithms with the bounds on what can be achieved with the best possible algorithms. This paper makes few first steps in this direction. We prove upper and lower bounds on the fixed-target black-box complexity of the standard benchmark function OneMax given the problem size n and the target fitness k that we want to achieve. On the way to these bounds, we prove a general lower bound theorem suitable to derive bounds not only in fixed-target settings, but also in settings where a problem instance may have multiple optima.
AB - Recently, fine-grained measures of performance of randomized search heuristics received attention in the theoretical community. In particular, some results were proven specifically for fixed-target runtime analysis. However, this research domain still lacks an important counterpart, namely, the (black-box) complexity analysis, which shall augment runtime analyses of particular algorithms with the bounds on what can be achieved with the best possible algorithms. This paper makes few first steps in this direction. We prove upper and lower bounds on the fixed-target black-box complexity of the standard benchmark function OneMax given the problem size n and the target fitness k that we want to achieve. On the way to these bounds, we prove a general lower bound theorem suitable to derive bounds not only in fixed-target settings, but also in settings where a problem instance may have multiple optima.
KW - Black-box complexity
KW - Fixed-target analysis
KW - OneMax
UR - http://www.scopus.com/inward/record.url?scp=85137271892&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-14721-0_42
DO - 10.1007/978-3-031-14721-0_42
M3 - Conference Proceeding (Non-Journal item)
AN - SCOPUS:85137271892
SN - 9783031147203
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 600
EP - 611
BT - Parallel Problem Solving from Nature – PPSN XVII - 17th International Conference, PPSN 2022, Proceedings
A2 - Rudolph, Günter
A2 - Kononova, Anna V.
A2 - Aguirre, Hernán
A2 - Kerschke, Pascal
A2 - Ochoa, Gabriela
A2 - Tušar, Tea
PB - Springer Nature
T2 - 17th International Conference on Parallel Problem Solving from Nature, PPSN 2022
Y2 - 10 September 2022 through 14 September 2022
ER -