How Much Do Swarm Intelligence and Evolutionary Algorithms Improve Over a Classical Heuristic From 1960?

Abstract

Hundreds of variants of Swarm Intelligence or Evolutionary Algorithms are proposed each year and numerous competitions and comparisons between algorithms may suggest rapid improvement in the field. However, such comparisons are often done between a limited number of methods and are based on averaged ranks of algorithms. This way they measure whether one method is on average ranked better than the others, without giving any information on how much improvement is in fact obtained. In this study we show a general comparison between 69 algorithms, starting from methods proposed in the 1960’s up to variants developed in the early 2020’s, on single-objective static numerical problems. Algorithms are compared on searching for a minimum of 30 different 50-dimensional mathematical functions, and on 22 real-world problems. We focus on the relative improvement achieved by various algorithms over a single-solution based method proposed in 1960 by Howard Rosenbrock. We find that the general improvement of Evolutionary Algorithms over Rosenbrock’s algorithm is relatively limited. It is high for the artificial benchmarks, for which many Evolutionary Algorithms find solutions 10 times closer to the global optimum in terms of fitness than Rosenbrock’s algorithm, but much lower for real-world problems. Improvement is also higher when performance averaged over many runs is compared, but lower when the best results from multiple runs are analyzed. In the last case, only the best Evolutionary Algorithms are able to find solutions of a “typical” real-world problem that are 2–3 times better in terms of fitness than those found by Rosenbrock’s algorithm. The relative improvement of recently proposed algorithms is not much better than the improvement achieved by algorithms proposed over a decade ago.

Keywords

• Evolutionary algorithms
• swarm intelligence
• metaheuristics
• performance
• Rosenbrock–s algorithm