Fixed-Target Runtime Analysis - Sorbonne Université
Conference Papers Year : 2020

Fixed-Target Runtime Analysis

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 a theoretical viewpoint , more fine-grained performance measures are needed. Two complementary approaches have been suggested: fixed-budget analysis and fixed-target analysis. In this work, we conduct an in-depth study on the advantages and 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 the existing runtime result to a fixed-target result is highly non-trivial.
Fichier principal
Vignette du fichier
2020-GECCO-fixed-Target.pdf (426.59 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-02871956 , version 1 (17-06-2020)

Identifiers

  • HAL Id : hal-02871956 , version 1

Cite

Maxim Buzdalov, Benjamin Doerr, Carola Doerr, Dmitry Vinokurov. Fixed-Target Runtime Analysis. GECCO 2020 - The Genetic and Evolutionary Computation Conference, Jul 2020, Cancun, Mexico. ⟨hal-02871956⟩
51 View
94 Download

Share

More