Error Analysis of Elitist Randomized Search Heuristics
When globally optimal solutions of complicated optimization problems cannot be located by evolutionary algorithms (EAs) in polynomial expected running time, the hitting time/running time analysis is not flexible enough to accommodate the requirement of theoretical study, because sometimes we have no idea on what approximation ratio is available in polynomial expected running time. Thus, it is necessary to propose an alternative routine for the theoretical analysis of EAs. To bridge the gap between theoretical analysis and algorithm implementation, in this paper we perform an error analysis where expected approximation error is estimated to evaluate performances of randomized search heuristics (RSHs). Based on the Markov chain model of RSHs, the multi-step transition matrix can be computed by diagonalizing the one-step transition matrix, and a general framework for estimation of expected approximation errors is proposed. Case studies indicate that the error analysis works well for both uni- and multi-modal benchmark problems. It leads to precise estimations of approximation error instead of asymptotic results on fitness values, which demonstrates its competitiveness to fixed budget analysis.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
The (1+1) Elitist Black-Box Complexity of LeadingOnes
One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime anal…
Evolutionary AlgorithmsHyper-Heuristics Can Profit From Global Variation Operators
In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local optimum of the multimodal CLIFF benchmark with remarkable efficien…
Evolutionary AlgorithmsProbabilistic Tools for the Analysis of Randomized Optimization Heuristics
This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser…
Parameterized Complexity Analysis of Randomized Search Heuristics
This chapter compiles a number of results that apply the theory of parameterized algorithmics to the running-time analysis of randomized search heuristics such as evolutionary algorithms. The parameterized approach artic…
Combinatorial OptimizationEvolutionary AlgorithmsMulti-Level Evolution Strategies for High-Resolution Black-Box Control
This paper introduces a multi-level (m-lev) mechanism into Evolution Strategies (ESs) in order to address a class of global optimization problems that could benefit from fine discretization of their decision variables. S…
global-optimizationVocal Bursts Intensity Prediction