All Constant Mutation Rates for the $(1+1)$ Evolutionary Algorithm
For every mutation rate $p \in (0, 1)$, and for all $\varepsilon > 0$, there is a fitness function $f : \{0,1\}^n \to \mathbb{R}$ with a unique maximum for which the optimal mutation rate for the $(1+1)$ evolutionary algorithm on $f$ is in $(p-\varepsilon, p+\varepsilon)$. In other words, the set of optimal mutation rates for the $(1+1)$ EA is dense in the interval $[0, 1]$. To show that, this paper introduces DistantSteppingStones, a fitness function which consists of large plateaus separated by large fitness valleys.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Runtime Analysis for Self-adaptive Mutation Rates
We propose and analyze a self-adaptive version of the $(1,\lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on th…
Stationary frequencies and mixing times for neutral drift processes with spatial structure
We study a general setting of neutral evolution in which the population is of finite, constant size and can have spatial structure. Mutation leads to different genetic types ("traits"), which can be discrete or continuou…
Precise Runtime Analysis for Plateau Functions
To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the $n$-dimensional Plateau$_k$ function as natural benchmark and analyze how different v…
Evolutionary AlgorithmsA Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive
We propose a new, flexible approach for dynamically maintaining successful mutation rates in evolutionary algorithms using $k$-bit flip mutations. The algorithm adds successful mutation rates to an archive of promising r…
Evolutionary AlgorithmsRuntime Analysis of Fitness-Proportionate Selection on Linear Functions
This paper extends the runtime analysis of non-elitist evolutionary algorithms (EAs) with fitness-proportionate selection from the simple OneMax function to the linear functions. Not only does our analysis cover a larger…
Evolutionary Algorithms