Search moves in the local optima networks of permutation spaces: the QAP case

In this work we analyze, from a qualitative point-of-view, the structure of the connections among the local optima in the fitness landscapes of the Quadratic Assignment Problem (QAP). In particular, we are interested in determining which search moves, intended as pairwise exchanges of permutation items, are beneficial for moving from one optimum to another. Novel algebraic methods are introduced for determining, and measuring the effectiveness, of the exchange moves connecting two given optima. The analysis considers real-like QAP instances whose local optima networks are clustered in communities. The results of the conducted experimentation shows the presence of few preferred search moves that look more effective for moving across intra-community optima, while the same is not so apparent when the optima are taken from different communities.