Average convergence rate of evolutionary algorithms in continuous optimization

DOI10.1016/J.INS.2020.12.076MaRDI QIDQ6081271zbMATH OpenFDO

Authors Yu Chen, Jun He

Publication date 25 October 2023

Published in Information Sciences (Search for Journal in Brave)

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

zbMATH Keywords

approximation errorcontinuous optimizationconvergence rateevolutionary algorithmMarkov chain

Mathematics Subject Classification ID

Nonlinear programming (90C30) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: The average convergence rate (ACR) measures how fast the approximation error of an evolutionary algorithm converges to zero per generation. It is defined as the geometric average of the reduction rate of the approximation error over consecutive generations. This paper makes a theoretical analysis of the ACR in continuous optimization. The obtained results are summarized as follows. According to the limit property, the ACR is classified into two categories: (1) linear ACR whose limit inferior value is larger than a positive and (2) sublinear ACR whose value converges to zero. Then, it is proven that the ACR is linear for evolutionary programming using positive landscape-adaptive mutation, but sublinear for that using landscape-invariant or zero landscape-adaptive mutation. The relationship between the ACR and the decision space dimension is also classified into two categories: (1) polynomial ACR whose value is larger than the reciprocal of a polynomial function of the dimension for any generation, and (2) exponential ACR whose value is less than the reciprocal of an exponential function of the dimension for an exponential long period. It is proven that for easy problems such as linear functions, the ACR of the (1+1) adaptive random univariate search is polynomial. But for hard functions such as the deceptive function, the ACR of both the (1+1) adaptive random univariate search and evolutionary programming is exponential.

Recommendations

• On asymptotic convergence rate of random search
• scientific article; zbMATH DE number 1100794
• Convergence properties of evolutionary algorithms under elitist strategy
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
• Convergence rates for a class of evolutionary algorithms with elitist strategy

Cites work

• Convergence rates for a class of evolutionary algorithms with elitist strategy
• Convergence results for the (1,)-SA-ES using the theory of -irreducible Markov chains
• Drift analysis and average time complexity of evolutionary algorithms
• Drift conditions for estimating the first hitting times of evolutionary algorithms
• Evolutionary programming using a mixed mutation strategy
• scientific article; zbMATH DE number 1100794 (Why is no real title available?)
• scientific article; zbMATH DE number 2039367 (Why is no real title available?)
• Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
• Log-linear convergence and divergence of the scale-invariant \((1+1)\)-ES in noisy environments
• Markov chains and stochastic stability
• Matrix iterative analysis
• On geometric convergence rate of Markov search towards the fat target
• On the convergence rate issues of general Markov search for global minimum
• On the convergence rates of genetic algorithms
• Performance analysis of randomised search heuristics operating with a fixed budget
• Theory of evolution strategies: a new perspective

Cited in

(4)

• Convergence Rates of Evolutionary Algorithms and Parallel Evolutionary Algorithms
• Convergence of Factored Evolutionary Algorithms
• On asymptotic convergence rate of random search
• An adaptive helper and equivalent objective evolution strategy for constrained optimization

This page was built for publication: Average convergence rate of evolutionary algorithms in continuous optimization

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