Walking through the Quadratic Assignment-Instance Space: Algorithm Performance and Landscape Measures

This paper presents an analysis of the trends and behavior of Fitness Landscape Analysis (FLA) and corresponding algorithm performance features for instances of the Quadratic Assignment Problem (QAP) and the instance space between them. Given two QAPLIB instances, a transformation generates 30 intermediary instances, i.e. problem versions for further experimentation. For each problem version, we track algorithm performance of robust tabu search (RTS) and variable neighborhood search (VNS), as well as FLA measures obtained by various types of walks. Thus, we are able to analyze how these performances and measures change during the transformation. We observe that RTS dominates VNS in earlier problem versions, while VNS outperforms RTS in later problem versions. Overall, the transformation leads to a smooth traversal of the instance space, and both algorithm performance and FLA measures correlate with problem versions.