  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.
