Two-dimensional drift analysis: optimizing two functions simultaneously can be hard

DOI10.1016/j.tcs.2023.114072arXiv2203.14547OpenAlexW4384564523MaRDI QIDQ6175522

Duri Janett, Johannes Lengler

Publication date: 18 August 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

drift analysisruntime analysisdynamic environmentstheory of evolutionary algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Concentration of first hitting times under additive drift
• Improved time complexity analysis of the simple genetic algorithm
• Linear multi-objective drift analysis
• On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization
• Multiplicative drift analysis
• Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
• Runtime analysis of the \((\mu + 1)\)-EA on the dynamic BinVal function
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• The complex parameter landscape of the compact genetic algorithm
• Drift Analysis and Evolutionary Algorithms Revisited
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
• On the Brittleness of Evolutionary Algorithms

This page was built for publication: Two-dimensional drift analysis: optimizing two functions simultaneously can be hard