Average convergence rate of evolutionary algorithms in continuous optimization

Chen, Y and He, J ORCID: https://orcid.org/0000-0002-5616-4691, 2021. Average convergence rate of evolutionary algorithms in continuous optimization. Information Sciences. ISSN 0020-0255

Preview

Text 1408047_He.pdf - Post-print Download (623kB) | Preview

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.

Item Type:	Journal article
Publication Title:	Information Sciences
Creators:	Chen, Y. and He, J.
Publisher:	Elsevier
Date:	9 February 2021
ISSN:	0020-0255
Identifiers:	Number Type 10.1016/j.ins.2020.12.076 DOI 1408047 Other
Divisions:	Schools > School of Science and Technology
Record created by:	Jonathan Gallacher
Date Added:	24 Feb 2021 09:42
Last Modified:	09 Feb 2022 03:00
URI:	https://irep.ntu.ac.uk/id/eprint/42368

Actions (login required)

Edit View

Statistics

Views

Downloads