OneMax is not the easiest function for fitness improvements

DOI10.1007/978-3-031-30035-6_11MaRDI QIDQ6149099zbMATH OpenOpenAlexFDO

Authors Marc Kaufmann, Maxime Larcher, Johannes Lengler, Xun Zou

Publication date 12 January 2024

Published in Evolutionary Computation in Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.07017

zbMATH Keywords

\((1,\lambda )\)-EAdynamic environmentsevolutionary algorithmone-fifth ruleOneMaxparameter controlself-adaptation

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We study the $(1:s+1)$ success rule for controlling the population size of the $(1,lambda)$-EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run into problems for large $s$ if the fitness landscape is too easy. They conjectured that this problem is worst for the OneMax benchmark, since in some well-established sense OneMax is known to be the easiest fitness landscape. In this paper we disprove this conjecture and show that OneMax is not the easiest fitness landscape with respect to finding improving steps. As a consequence, we show that there exists $s$ and $varepsilon$ such that the self-adjusting $(1,lambda)$-EA with $(1:s+1)$-rule optimizes OneMax efficiently when started with $varepsilonn$ zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Hence, we show that there are landscapes where the problem of the $(1:s+1)$-rule for controlling the population size of the $(1,lambda)$-EA is more severe than for OneMax.

Cites work

• A rigorous analysis of the compact genetic algorithm for linear functions
• Concentration of first hitting times under additive drift
• From black-box complexity to designing new genetic algorithms
• scientific article; zbMATH DE number 3599865 (Why is no real title available?)
• Learning probability distributions in continuous evolutionary algorithms -- a comparative review
• Multiplicative drift analysis
• On easiest functions for mutation operators in bio-inspired optimisation
• On the Brittleness of Evolutionary Algorithms
• On the runtime analysis of the simple genetic algorithm
• Optimal parameter choices via precise black-box analysis
• Runtime analysis for self-adaptive mutation rates
• Runtime analysis of the ( + 1)-EA on the dynamic BinVal function
• Self-adjusting mutation rates with provably optimal success rules
• Self-adjusting offspring population sizes outperform fixed parameters on the cliff function
• Self-adjusting population sizes for the (1, )-EA on monotone functions
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Theory of evolutionary computation. Recent developments in discrete optimization
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cited in

(3)

• Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter
• Hardest monotone functions for evolutionary algorithms
• Comma selection outperforms plus selection on OneMax with randomly planted optima

This page was built for publication: OneMax is not the easiest function for fitness improvements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149099)