Randomness in Local Optima Network Sampling

Abstract

We consider statistical randomness in the construction of local optima networks (LONs) and conduct a preliminary and exploratory study into this. LONs capture a fitness landscape into network format: the nodes are local optima, and edges are heuristic search transitions between them. Problem instances from the benchmark quadratic assignment problem library are used in the analysis. LONs are constructed using an iterated local search (ILS) and several different random seeds. Metrics are computed from the networks and visualised to assess the effect of randomness. Algorithm performance models for ILS runtime are built using metrics of LONs constructed using different seeds and the results compared. The results show that some LON metrics seem consistent across seeds, while others vary substantially. Additionally, the quality of algorithm performance models using LON metrics as predictors can differ depending on randomness. Finally, LON metrics associated with separate seeds can lead to different algorithm configuration recommendations for the same instance.