A Theoretical Framework of Approximation Error Analysis of Evolutionary Algorithms
This work addresses a foundational gap in theoretical analysis for evolutionary algorithms, which is incremental as it builds on existing concepts but provides new mathematical tools.
The paper tackles the lack of rigorous analysis for evaluating solution quality in evolutionary algorithms by establishing a theoretical framework for approximation error analysis in discrete optimization, presenting methods for exact expressions and upper bounds, and demonstrating applicability through examples.
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.