Analysing the fitness landscape rotation for combinatorial optimisation.

Fitness landscape rotation has been widely used in the field of dynamic combinatorial optimisation to generate test problems with academic purposes. This method changes the mapping between solutions and objective values, but preserves the structure of the fitness landscape. In this work, the rotation of the landscape in the combinatorial domain is theoretically analysed using concepts of discrete mathematics. Certainly, the preservation of the neighbourhood relationship between the solutions and the structure of the landscape are studied in detail. Based on the theoretical insights obtained, landscape rotation has been employed as a strategy to escape from local optima when local search algorithms get stuck. Conducted experiments confirm the good performance of the rotation-based local search algorithms to perturb the search towards unexplored local optima on a set of instances of the linear ordering problem