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

On the efficiency of worst improvement for climbing NK-landscapes

Abstract :

Climbers are often used in metaheuristics in order to intensify the search and identify local optima with respect to a neighborhood structure. Even if they constitute a central component of modern heuristics, their design principally consists in choosing the pivoting rule, which is often reduced to two alternative strategies: first improvement or best improvement. The conception effort of most metaheuristics belongs in proposing techniques to escape from local optima, and not necessarily on how to climb toward better local optima. In this paper, we are interested in attaining good local optima with basic hill-climbing techniques. The NK model will be used to evaluate a set of climbers proposed in this paper. By focusing on the pivoting rule definition, we show that choosing the worst improving neighbor often leads to attain better local optima. Moreover, by slightly modifying the worst improvement strategy, one can design efficient climbers which outperform first and best improvement in terms of tradeoff between quality and computational effort.

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

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

Lien texte intégral

Identifiants

Collections

Citation

Matthieu Basseur, Adrien Goëffon. On the efficiency of worst improvement for climbing NK-landscapes. the 2014 conferenceProceedings of the 2014 conference on Genetic and evolutionary computation - GECCO '14, 2014, Vancouver, BC, CanadaNew York, New York, USA, Canada. pp.413-420, ⟨10.1145/2576768.2598268⟩. ⟨hal-03256595⟩

Partager

Métriques

Consultations de la notice

19