Parallel Evolutionary Algorithms Performing Pairwise Comparisons
Marie-Liesse Cauwet, Olivier Teytaud, Shih-Yuan Chiu, Kuo-Min Lin, Shi-Jim Yen, David L. Saint-Pierre, Fabien Teytaud · 2015
We study mathematically and experimentally the convergence rate of differential evolution and particle swarm optimization for simple unimodal functions. Due to parallelization concerns, the focus is on lower bounds on the runtime, i.e. upper bounds on the speed-up, as a function of the population size. Two cases are particularly relevant: A population size of the same order of magnitude as the dimension and larger population sizes. We use the branching factor as a tool for proving bounds and get, as upper bounds, a linear speed-up for a population size similar to the dimension, and a logarithmic speed-up for larger population sizes. We then propose parametrizations for differential evolution and particle swarm optimization that reach these bounds.