Theory of (1+1) ES on SPHERE Revisited

The theory of evolutionary algorithms on continuous space gravitates around the evolution strategy with one individual, adaptive mutation, and elitist selection, optimizing the symmetric, quadratic SPHERE function. The classic, normal mutation theory consists of three main building-blocks: 1) a two-...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2023-08, Vol.27 (4), p.938-948
Main Authors: Agapie, Alexandru, Solomon, Ovidiu, Beadin, Luiza
Format: Article
Language:English
Subjects:
Adaptive algorithms
Algorithms
Behavioral sciences
Continuous space optimization
Convergence
drift analysis
Elitism
Evolutionary algorithms
Gaussian distribution
Kernel
Markov processes
Mutation
Optimization
Prediction algorithms
spherical distribution
Wald equation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The theory of evolutionary algorithms on continuous space gravitates around the evolution strategy with one individual, adaptive mutation, and elitist selection, optimizing the symmetric, quadratic SPHERE function. The classic, normal mutation theory consists of three main building-blocks: 1) a two-term formula for the local (constant mutation) expected progress; 2) an exponential formula for the global behavior of the (adaptive mutation) algorithm; and 3) linear convergence time with respect to both space dimension n and (logarithm of) initial distance to optimum. We show that the three main results still hold if we replace the normal mutation with uniform inside the sphere and also with the sum of two uniforms. That makes the case for an important conclusion: the linear convergence time of the algorithm is not a consequence of the normal mutation, but of the elitist selection and 1/5 success rule. A simplified version of the 1/5-rule allows also for an intuitive representation of the algorithm, as a sequence of constant-mutation, independent, and identical (expected) length cycles.
ISSN:1089-778X
1941-0026
DOI:10.1109/TEVC.2022.3217524