Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

Abstract

We use an elementary argument building on group actions to prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO 2019) takes an expected number of (2^n / n) iterations to find any particular target search point. This bound is valid for all population sizes . Our result improves over the previous lower bound of ((n^/2)) valid for population sizes = O(n^1/2 - ), 0 < < 1/2.

Tasks

Reproductions