Local Optima Network Sampling for Permutation Flowshop

This work presents an analysis of sampled Local Optima Networks (LONs) on flowshop instances. LON metrics are addressed here to scrutinize the performance of four sampling strategies, each one resulting from the combination of a local search (iterative or best improvement) and a perturbation operator (deconstruction with or without local search on partial solutions). The results highlight the superiority of iterative improvement and the advantages of exploiting partial solutions, especially when they are combined to discover new local optima regions on large problems. LON metrics are also useful for predicting performance of optimization algorithms - in particular, this work considers two Iterated Greedy variants when solving flowshop instances. The predictive capacity of metrics calculated from sampled LONs is evaluated here based on the R2 and RMSE indicators. Results show that the best sampling strategies provide LON metrics capable of predicting 80% and 73% of variance for small and large flowshop instances, respectively.