Local Optima Networks of the Permutation flow-shop Problem

Citation

Daolio F, Verel S, Ochoa G & Tomassini M (2013) Local Optima Networks of the Permutation flow-shop Problem. In: Legrand P, Corsini M, Hao J, Monmarche N, Collet P, Lutton E & Schoenauer M (eds.) Articial Evolution 2013 (Evolution Articielle 2013): 11th Biennal International Conference on Articial Evolution Proceedings. Articial Evolution 2013 (Evolution Articielle 2013): 11th Biennal International Conference on Articial Evolution, Bordeaux, France, 21.10.2013-23.10.2013, pp. 200-212. http://ea2013.inria.fr//proceedings.pdf

Abstract
This article extracts and analyzes local optima networks for the permutation flow-shop problem. Two widely used move operators for permutation representations, namely, swap and insertion, are incorporated into the network landscape model. The performance of a heuristic search algorithm on this problem is also analyzed. In particular, we study the correlation between local optima network features and the performance of an iterated local search heuristic. Our analysis reveals that network features can explain and predict problem difficulty. The evidence confirms the superiority of the insertion operator for this problem.