Lower bounds from fitness levels made easy - Laboratoire d'informatique de l'X (LIX) Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Lower bounds from fitness levels made easy

Résumé

One of the first and easy to use techniques for proving run time bounds for evolutionary algorithms is the so-called method of fitness levels by Wegener. It uses a partition of the search space into a sequence of levels which are traversed by the algorithm in increasing order, possibly skipping levels. An easy, but often strong upper bound for the run time can then be derived by adding the reciprocals of the probabilities to leave the levels (or upper bounds for these). Unfortunately, a similarly effective method for proving lower bounds has not yet been established. The strongest such method, proposed by Sudholt (2013), requires a careful choice of the viscosity parameters γi,j, 0 ≤ i ≤ j ≤ n. In this paper we present two new variants of the method, one for upper and one for lower bounds. Besides the level leaving probabilities, they only rely on the probabilities that levels are visited at all. We show that these can be computed or estimated without greater difficulties and apply our method to reprove the following known results in an easy and natural way. (i) The precise run time of the (1 + 1) EA on LeadingOnes. (ii) A lower bound for the run time of the (1 + 1) EA on OneMax, tight apart from an O(n) term. (iii) A lower bound for the run time of the (1 + 1) EA on long k-paths.
Fichier principal
Vignette du fichier
2104.03372.pdf (327.56 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-04486470 , version 1 (04-04-2024)

Identifiants

Citer

Benjamin Doerr, Timo Kötzing. Lower bounds from fitness levels made easy. GECCO '21: Genetic and Evolutionary Computation Conference, 2021, Lille, France. pp.1142-1150, ⟨10.1145/3449639.3459352⟩. ⟨hal-04486470⟩
8 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More