Performance analysis of randomised search heuristics operating with a fixed budget

DOI10.1016/J.TCS.2013.06.007MaRDI QIDQ2250996zbMATH OpenOpenAlexFDO

Authors Christine Zarges, Thomas Jansen

Publication date 10 July 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2013.06.007

zbMATH Keywords

ridgejumpruntime analysisrandom local search\((1+1)\) EAfixed budget computationleading onesOneMax

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Upper and lower bounds for randomized search heuristics in black-box optimization
• Fixed Budget Performance of the (1+1) EA on Linear Functions
• Fixed-target runtime analysis
• Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cites work

• scientific article; zbMATH DE number 2013534 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering
• Analyzing randomized search heuristics: tools from probability theory
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the approximation ability of evolutionary optimization with application to minimum set cover
• Optimizing linear functions with randomized search heuristics -- the robustness of mutation
• Probability and Computing
• Runtime analysis of a binary particle swarm optimizer
• Runtime analysis of the 1-ANT ant colony optimizer
• The analysis of evolutionary algorithms -- A proof that crossover really can help

Cited in

(13)

• On the impact of the performance metric on efficient algorithm configuration
• Fixed-target runtime analysis
• Lower bounds from fitness levels made easy
• Average convergence rate of evolutionary algorithms in continuous optimization
• On the effectiveness of immune inspired mutation operators in some discrete optimization problems
• Fixed Budget Performance of the (1+1) EA on Linear Functions
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Optimal parameter choices via precise black-box analysis
• Multiobjective optimization: when objectives exhibit non-uniform latencies
• A framework for co-optimization algorithm performance and its application to worst-case optimization
• Working principles of binary differential evolution
• On easiest functions for mutation operators in bio-inspired optimisation
• Fourier analysis meets runtime analysis: precise runtimes on plateaus

This page was built for publication: Performance analysis of randomised search heuristics operating with a fixed budget

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