First-improvement vs. Best-improvement ...
Type de document :
Communication dans un congrès avec actes
Titre :
First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes
Auteur(s) :
Ochoa, Gabriela [Auteur]
Verel, Sébastien [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Tomassini, Marco [Auteur]
Verel, Sébastien [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Tomassini, Marco [Auteur]
Titre de la manifestation scientifique :
11th International Conference on Parallel Problem Solving From Nature
Ville :
Krakow
Pays :
Pologne
Date de début de la manifestation scientifique :
2010-09-11
Titre de l’ouvrage :
Proceedings of the 11th International Conference on Parallel Problem Solving From Nature
Date de publication :
2010-09-11
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Résumé en anglais : [en]
This paper extends a recently proposed model for combinatorial landscapes: Local Optima Networks (LON), to incorporate a first-improvement (greedy-ascent) hill-climbing algorithm, instead of a best-improvement (steepest-ascent) ...
Lire la suite >This paper extends a recently proposed model for combinatorial landscapes: Local Optima Networks (LON), to incorporate a first-improvement (greedy-ascent) hill-climbing algorithm, instead of a best-improvement (steepest-ascent) one, for the definition and extraction of the basins of attraction of the landscape optima. A statistical analysis comparing best and first improvement network models for a set of NK landscapes, is presented and discussed. Our results suggest structural differences between the two models with respect to both the network connectivity, and the nature of the basins of attraction. The impact of these differences in the behavior of search heuristics based on first and best improvement local search is thoroughly discussed.Lire moins >
Lire la suite >This paper extends a recently proposed model for combinatorial landscapes: Local Optima Networks (LON), to incorporate a first-improvement (greedy-ascent) hill-climbing algorithm, instead of a best-improvement (steepest-ascent) one, for the definition and extraction of the basins of attraction of the landscape optima. A statistical analysis comparing best and first improvement network models for a set of NK landscapes, is presented and discussed. Our results suggest structural differences between the two models with respect to both the network connectivity, and the nature of the basins of attraction. The impact of these differences in the behavior of search heuristics based on first and best improvement local search is thoroughly discussed.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-00488401/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1207.4455
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-00488401/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- FirstImprLON.pdf
- Accès libre
- Accéder au document
- 1207.4455
- Accès libre
- Accéder au document