Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

On the Attainability of NK Landscapes Global Optima

Abstract :

In this paper, we aim at evaluating the impact of the starting point of a basic local search based on the first improvement strategy. We define the coverage rate of a configuration as the proportion of the search space from which a particular configuration can be reached by a strict hill-climbling with a non-zero probability. In particular, we compute the coverage rate of fitness landscapes global optima, in order to evaluate their attainability by hill-climbing algorithms. The experimental study is realized on NK landscapes, in which the size and ruggedness can be controlled. Results indicate that the coverage rate of global optima is usually high, which means that a basic strictly improving hill-climbing with first improvement strategy is able to reach global optima, independently to the starting point considered.
This confirms that it is more important to focus on an effective search strategy rather than worrying about the choice of the initial configurations.

 

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03256585
Contributeur : Okina Université d'Angers <>
Soumis le : jeudi 10 juin 2021 - 12:29:06
Dernière modification le : vendredi 11 juin 2021 - 03:29:58

Identifiants

  • HAL Id : hal-03256585, version 1
  • OKINA : ua7655

Collections

Citation

Matthieu Basseur, Adrien Goëffon, Frédéric Lardeux, Frédéric Saubion, Vincent Vigneron. On the Attainability of NK Landscapes Global Optima. Proceedings of the Seventh Annual Symposium on Combinatorial Search, 2014, Non spécifié, United States. pp.28-34. ⟨hal-03256585⟩

Partager

Métriques

Consultations de la notice

10