Variable neighborhood algebraic Differential Evolution: An application to the Linear Ordering Problem with Cumulative Costs

Algebraic variants of the Differential Evolution (DE) algorithm have been recently proposed to tackle permutation-based optimization problems by means of an algebraic framework, which allows to directly encode the solutions as permutations. The algebraic DE in the permutation space can be characterized by considering different neighborhood definitions such as swapping two adjacent items, swapping any two items, shifting an item to a given position. Here we propose the Variable Neighborhood Differential Evolution for Permutations (VNDEP), which adaptively searches the three neighborhoods together based on a method of dynamic reward. We provide an extensive and systematic analysis of the theoretical tools required in VNDEP, by studying the complexity of the proposed algorithmic components and by introducing the possibility to use a scale factor parameter larger than one. Experiments have been held on a widely used benchmark suite for the Linear Ordering Problem with Cumulative Costs, where VNDEP has been compared with four known permutation-based DE schemes and with respect to the state-of-the-art results for the considered instances. The experiments clearly show that VNDEP systematically outperforms the competitor algorithms and, most impressively, 32 new best known solutions, of the 50 most challenging instances, have been obtained.