Faster black-box algorithms through higher arity operators

DOI10.1145/1967654.1967669MaRDI QIDQ5276095zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus Wagner, Carola Winzen

Publication date 14 July 2017

Published in Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms (Search for Journal in Brave)

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

zbMATH Keywords

runtime analysispseudo-Boolean optimizationblack-box complexity

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Abstract: We extend the work of Lehre and Witt (GECCO 2010) on the unbiased black-box model by considering higher arity variation operators. In particular, we show that already for binary operators the black-box complexity of leadingones drops from $Theta(n^2)$ for unary operators to $O(nlogn)$. For onemax, the $Omega(nlogn)$ unary black-box complexity drops to O(n) in the binary case. For $k$-ary operators, $kleqn$, the onemax-complexity further decreases to $O(n/logk)$.

Recommendations

• Reducing the arity in unbiased black-box complexity
• Black-box search by unbiased variation
• From black-box complexity to designing new genetic algorithms
• The (1+1) elitist black-box complexity of LeadingOnes
• Optimal parameter choices via precise black-box analysis

Cited in

(17)

• scientific article; zbMATH DE number 1303124 (Why is no real title available?)
• Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm
• Ranking-based black-box complexity
• The (1+1) elitist black-box complexity of LeadingOnes
• Towards a complexity theory of randomized search heuristics: ranking-based black-box complexity
• \textsc{OneMax} in black-box models with several restrictions
• Toward a unifying framework for evolutionary processes
• Choosing the right algorithm with hints from complexity theory
• The query complexity of a permutation-based variant of mastermind
• An experimental study of operator choices in the \((1+(\lambda,\lambda))\) genetic algorithm
• The unbiased black-box complexity of partition is polynomial
• An extended jump functions benchmark for the analysis of randomized search heuristics
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions
• From black-box complexity to designing new genetic algorithms
• Reducing the arity in unbiased black-box complexity
• Unbiasedness of estimation-of-distribution algorithms

This page was built for publication: Faster black-box algorithms through higher arity operators

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