On Invariances in Evolutionary Algorithms
Anne Auger, Sylvain Gelly, Sylvie Ruette, Olivier Teytaud · 2006
We summarize current research on the pros and cons of invariance properties of optimization algorithms: 1. Robustness optimality of comparison-based algorithms for the worst case among increasing transfor-mations of the fitness function. Informally, we show that for the worst case on increasing transforma-tions of the fitness function, comparison-based algorithms are in fact optimal. Precisely, we consider x1(o, f),...,xn(o, f) the points visited by an optimization algorithm o when working on a fitness func-tion f, and we let x∗(f) be the argmin of a fitness function f. We show that (under mild technical assumptions) for all random function f, for all optimization algorithm o, there exists an optimization algorithm o ′ which only depends on comparisons such that Ef sup g∈G ||xn(o, g ◦ f) − x∗(g ◦ f)||2 = Ef sup g∈G ||xn(o′, g ◦ f) − x∗(g ◦ f)||2 where G is the set of increasing mappings from R to R [2]. 2. Lower-bounds on the convergence rates in continuous optimization for comparison-based algorithms.