Fixed-Target Runtime Analysis - Sorbonne Université
Communication Dans Un Congrès Année : 2020

Fixed-Target Runtime Analysis

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02871956 , version 1

Citer

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⟩
65 Consultations
95 Téléchargements

Partager

More