Selection between Single-Trajectory and Population-Based Meta-heuristics via Optimal Site Networks: Analysis of the Fitness Landscape in the Symmetric and Asymmetric Traveling Salesman Problem

The selection of meta-heuristics for NP-hard combinatorial optimization problems is traditionally empirical and costly. This work demonstrates that Local Optimum Networks (ROLs), as a model of the fitness landscape, are a promising instrument for the selection between classes of meta-heuristics, taking the Symmetric Traveling Salesman Problem (PCVS) and Asymmetric Salesman Problem (VAP) as a case study. ROLs are constructed by snowball sampling combined with random walk, extracting ten topological features. The Iterated Local Search (ILS) and the EAX Operator Genetic Algorithm (AG-EAX), state-of-the-art representatives in single-trajectory and population metaheuristics, are used for validation. The results in twelve TSPLIB instances reveal that the average weight of reflective loops and the number of hill-climbing paths correctly classify eleven instances: ILS prevails in symmetric (funnel) and AG-EAX in asymmetric (fragmented topology), suggesting the predictive potential of ROLs.