Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
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
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : jeudi 10 juin 2021 - 12:29:06
Dernière modification le : lundi 14 novembre 2022 - 02:42:07


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



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⟩



Consultations de la notice