Direction Matters in High-Dimensional Optimisation

Directional biases are evident in many benchmarking problems for real-valued global optimisation, as well as many of the evolutionary and allied algorithms that have been proposed for solving them. It has been shown that directional biases make some kinds of problems easier to solve for similarly biased algorithms, which can give a misleading view of algorithm performance. In this paper we study the effects of directional bias for high-dimensional optimisation problems. We show that the impact of directional bias is magnified as dimension increases, and can in some cases lead to differences in performance of many orders of magnitude. We present a new version of the classical evolutionary programming algorithm, which we call unbiased evolutionary programming (UEP), and show that it has markedly improved performance for high-dimensional optimisation.