Average Convergence Rate of Evolutionary Algorithms

Abstract

In evolutionary optimization, it is important to understand how fast evolutionary algorithms converge to the optimum per generation, or their convergence rate. This paper proposes a new measure of the convergence rate, called average convergence rate. It is a normalised geometric mean of the reduction ratio of the fitness difference per generation. The calculation of the average convergence rate is very simple and it is applicable for most evolutionary algorithms on both continuous and discrete optimization. A theoretical study of the average convergence rate is conducted for discrete optimization. Lower bounds on the average convergence rate are derived. The limit of the average convergence rate is analysed and then the asymptotic average convergence rate is proposed.

References in corpus (2)

• On the Easiest and Hardest Fitness Functions
• Pure Strategy or Mixed Strategy?

Cited by in corpus (9)

• Average Convergence Rate of Evolutionary Algorithms II: Continuous Optimization
• Helper and Equivalent Objectives: An Efficient Approach to Constrained Optimisation
• An Analytic Expression of Relative Approximation Error for a Class of Evolutionary Algorithms
• A Theoretical Framework of Approximation Error Analysis of Evolutionary Algorithms
• Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms
• Unlimited Budget Analysis of Randomised Search Heuristics
• Energy and Quality of Surrogate-Assisted Search Algorithms: a First Analysis
• Error Analysis of Elitist Randomized Search Heuristics
• Green Optimization: Energy-aware Design of Metaheuristics by Using Machine Learning Surrogates to Cope with Real Problems