Book Chapter

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

Citation

Ochoa G, Verel S & Tomassini M (2010) First-Improvement vs. Best-Improvement Local Optima Networks of NK Landscapes. In: Schaefer R, Cotta C, Kolodziej J & Rudolph G (eds.) Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I. Lecture Notes in Computer Science, 6238. Berlin Heidelberg: Springer, pp. 104-113. http://link.springer.com/chapter/10.1007%2F978-3-642-15844-5_11?LI=true#; https://doi.org/10.1007/978-3-642-15844-5_11

Abstract
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.

StatusPublished
Title of seriesLecture Notes in Computer Science
Number in series6238
Publication date31/12/2010
URLhttp://hdl.handle.net/1893/11051
PublisherSpringer
Publisher URLhttp://link.springer.com/…44-5_11?LI=true#
Place of publicationBerlin Heidelberg
ISSN of series0302-9743
ISBN978-3-642-15843-8