When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument

DOI10.1137/1.9781611975505.10zbMath1430.68477arXiv1808.01137OpenAlexW2887847591MaRDI QIDQ5195237

Anders Martinsson, Johannes Lengler, Angelika Steger

Publication date: 18 September 2019

Published in: 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions ⋮ Two-dimensional drift analysis: optimizing two functions simultaneously can be hard ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions

This page was built for publication: When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument