Fixed-Target Runtime Analysis
arXiv:2004.09613 · doi:10.1007/s00453-021-00881-0
Abstract
Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and from a theoretical viewpoint, more fine-grained performance measures are needed to gain a more detailed understanding of the main working principles and their resulting performance implications. Two complementary approaches have been suggested: fixed-budget analyses and fixed-target analyses. In this work, we conduct an in-depth study on the advantages and the limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of existing runtime results to fixed-target results is highly non-trivial.
arXiv commentThis is an extended version of a paper which appeared at GECCO 2020
References in corpus (9)
- COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting
- Multiplicative Drift Analysis
- Better Runtime Guarantees Via Stochastic Domination
- IOHprofiler: A Benchmarking and Profiling Tool for Iterative Optimization Heuristics
- A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
- Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms
- Towards a Theory-Guided Benchmarking Suite for Discrete Black-Box Optimization Heuristics: Profiling EA Variants on OneMax and LeadingOnes
- Lower Bounds from Fitness Levels Made Easy
- Drift Analysis