First-improvement vs. Best-improvement Local Optima Networks of NK Landscapes
This work provides incremental insights for researchers in combinatorial optimization by comparing two hill-climbing variants in landscape analysis.
The paper extended the Local Optima Networks model to use first-improvement hill-climbing instead of best-improvement for analyzing NK landscapes, finding structural differences in network connectivity and basins of attraction, and discussed their impact on search heuristics.
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.