Multi-layer local optima networks for the analysis of advanced local search-based algorithms

A Local Optima Network (LON) is a graph model that compresses the fitness\nlandscape of a particular combinatorial optimization problem based on a\nspecific neighborhood operator and a local search algorithm. Determining which\nand how landscape features affect the effectiveness of search algorithms is\nrelevant for both predicting their performance and improving the design\nprocess. This paper proposes the concept of multi-layer LONs as well as a\nmethodology to explore these models aiming at extracting metrics for fitness\nlandscape analysis. Constructing such models, extracting and analyzing their\nmetrics are the preliminary steps into the direction of extending the study on\nsingle neighborhood operator heuristics to more sophisticated ones that use\nmultiple operators. Therefore, in the present paper we investigate a twolayer\nLON obtained from instances of a combinatorial problem using bitflip and swap\noperators. First, we enumerate instances of NK-landscape model and use the hill\nclimbing heuristic to build the corresponding LONs. Then, using LON metrics, we\nanalyze how efficiently the search might be when combining both strategies. The\nexperiments show promising results and demonstrate the ability of multi-layer\nLONs to provide useful information that could be used for in metaheuristics\nbased on multiple operators such as Variable Neighborhood Search.\n