First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes

Ochoa, Gabriela; Verel, Sébastien; Tomassini, Marco

Document type :

Communication dans un congrès avec actes

Title :

First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes

Author(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]

Conference title :

11th International Conference on Parallel Problem Solving From Nature

City :

Krakow

Country :

Pologne

Start date of the conference :

2010-09-11

Book title :

Proceedings of the 11th International Conference on Parallel Problem Solving From Nature

Publication date :

2010-09-11

HAL domain(s) :

Informatique [cs]/Intelligence artificielle [cs.AI]

English abstract : [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) ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://hal.archives-ouvertes.fr/hal-00488401/document
Open access
Access the document

http://arxiv.org/pdf/1207.4455
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-00488401/document
Open access
Access the document

document
Open access
Access the document

FirstImprLON.pdf
Open access
Access the document

1207.4455
Open access
Access the document

document
Open access
Access the document

FirstImprLON.pdf
Open access
Access the document

First-improvement vs. Best-improvement ... BibTeX CSV Excel RIS

Files

First-improvement vs. Best-improvement ...

BibTeX

CSV

Excel

RIS