A Theoretical Framework of Approximation Error Analysis of Evolutionary Algorithms
In the empirical study of evolutionary algorithms, the solution quality is evaluated by either the fitness value or approximation error. The latter measures the fitness difference between an approximation solution and the optimal solution. Since the approximation error analysis is more convenient than the direct estimation of the fitness value, this paper focuses on approximation error analysis. However, it is straightforward to extend all related results from the approximation error to the fitness value. Although the evaluation of solution quality plays an essential role in practice, few rigorous analyses have been conducted on this topic. This paper aims at establishing a novel theoretical framework of approximation error analysis of evolutionary algorithms for discrete optimization. This framework is divided into two parts. The first part is about exact expressions of the approximation error. Two methods, Jordan form and Schur's triangularization, are presented to obtain an exact expression. The second part is about upper bounds on approximation error. Two methods, convergence rate and auxiliary matrix iteration, are proposed to estimate the upper bound. The applicability of this framework is demonstrated through several examples.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
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 t…
Evolutionary AlgorithmsEvolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems …
Evolutionary AlgorithmsAn Analytic Expression of Relative Approximation Error for a Class of Evolutionary Algorithms
An important question in evolutionary computation is how good solutions evolutionary algorithms can produce. This paper aims to provide an analytic analysis of solution quality in terms of the relative approximation erro…
Evolutionary AlgorithmsInfluence of Binomial Crossover on Approximation Error of Evolutionary Algorithms
Although differential evolution (DE) algorithms perform well on a large variety of complicated optimization problems, only a few theoretical studies are focused on the working principle of DE algorithms. To make the firs…
Evolutionary AlgorithmsAverage Convergence Rate of Evolutionary Algorithms II: Continuous Optimization
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 approximatio…
Evolutionary Algorithms