A study on rotation invariance in differential evolution

Caraffini, Fabio; Neri, Ferrante

Abstract

Epistasis is the correlation between the variables of a function and is a challenge often posed by real-world optimisation problems. Synthetic benchmark problems simulate a highly epistatic problem by performing a so-called problem's rotation.

Mutation in Differential Evolution (DE) is inherently rotational invariant since it simultaneously perturbs all the variables. On the other hand, crossover, albeit fundamental for achieving a good performance, retains some of the variables, thus being inadequate to tackle highly epistatic problems.

This article proposes an extensive study on rotational invariant crossovers in DE. We propose an analysis of the literature, a taxonomy of the proposed method and an experimental setup where each problem is addressed in both its non-rotated and rotated version. Our experimental study includes 280 problems over five different levels of dimensionality and nine algorithms.

Numerical results show that 1) for a fixed quota of transferred design variables, the exponential crossover displays a better performance, on both rotated and non-rotated problems, in high dimensions while the binomial crossover seems to be preferable in low dimensions; 2) the rotational invariant mutation DE/current-to-rand is not competitive with standard DE implementations throughout the entire set of experiments we have presented; 3) DE crossovers that perform a change of coordinates to distribute the moves over the components of the offspring offer high-performance results on some problems. However, on average the standard DE/rand/1/exp appears to achieve the best performance on both rotated and non-rotated testbeds.

Citation

Caraffini, F., & Neri, F. (2019). A study on rotation invariance in differential evolution. Swarm and Evolutionary Computation, 50, Article 100436. https://doi.org/10.1016/j.swevo.2018.08.013

• Journal Article Type: Article
• Acceptance Date: Sep 10, 2018
• Online Publication Date: Sep 14, 2018
• Publication Date: 2019-11
• Deposit Date: Jan 10, 2020
• Journal: Swarm and Evolutionary Computation
• Print ISSN: 2210-6502
• Electronic ISSN: 2210-6510
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 50
• Article Number: 100436
• DOI: https://doi.org/10.1016/j.swevo.2018.08.013
• Keywords: General Computer Science; General Mathematics
• Public URL: https://nottingham-repository.worktribe.com/output/2512204
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S2210650218301482