← Research

A Theoretical Framework of Approximation Error Analysis of Evolutionary Algorithms

Jun He, Yu Chen, Yuren Zhou

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.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace