The impact of random initialization on the runtime of randomized search heuristics

DOI10.1007/S00453-015-0019-5MaRDI QIDQ306492zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Carola Doerr

Publication date 31 August 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-015-0019-5

zbMATH Keywords

evolutionary algorithmscoupon collectorruntime analysistheory of randomized search heuristics

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

• Fitness levels with tail bounds for the analysis of randomized search heuristics
• STACS 2005
• On the size of weights in randomized search heuristics
• Tight bounds on the optimization time of a randomized search heuristic on linear functions
• Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint

Cites work

• scientific article; zbMATH DE number 6019547 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 837692 (Why is no real title available?)
• scientific article; zbMATH DE number 1416816 (Why is no real title available?)
• Analyzing randomized search heuristics: tools from probability theory
• Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding
• Black-box search by unbiased variation
• Combinatorial sums and finite differences
• Comparing evolutionary algorithms to the (\(1+1\))-EA
• Drift analysis and average time complexity of evolutionary algorithms
• Fitness levels with tail bounds for the analysis of randomized search heuristics
• Multiplicative drift analysis
• Probability and Computing
• The analysis of Quicksort programs
• The impact of random initialization on the runtime of randomized search heuristics
• Tight bounds on the optimization time of a randomized search heuristic on linear functions

Cited in

(9)

• Optimal parameter choices via precise black-box analysis
• Runtime analysis of evolutionary algorithms via symmetry arguments
• Static and self-adjusting mutation strengths for multi-valued decision variables
• The impact of random initialization on the runtime of randomized search heuristics
• Fixed-target runtime analysis
• Stagnation detection with randomized local search
• Lower bounds from fitness levels made easy
• Stagnation detection in highly multimodal fitness landscapes
• On the size of weights in randomized search heuristics

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: The impact of random initialization on the runtime of randomized search heuristics

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