Estimating Approximation Errors of Elitist Evolutionary Algorithms.

When EAs are unlikely to locate precise global optimal solutions with satisfactory performances, it is important to substitute the hitting time/running time analysis with another available theoretical routine. In order to bring theories and applications closer, this paper is dedicated to perform an analysis on approximation error of EAs. First, we proposed a general result on upper bound and lower bound of approximation errors. Then, several case studies are performed to present the routine of error analysis, and consequently, validate its applicability on cases generating transition matrices of various shapes. Meanwhile, the theoretical results also show the close connections between approximation errors and eigenvalues of transition matrices. The analysis validates applicability of error analysis, demonstrates significance of estimation results, and then, exhibits its potential to be applied for theoretical analysis.