An initial error analysis for evolutionary algorithms
Jun He, Yuren Zhou, Guangming Li · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2017
The approximation error of an evolutionary algorithm is the fitness difference between the optimal solution and a solution found by the algorithm. In this paper, an initial error analysis has been made to evolutionary algorithms for discrete optimization. First, the order of convergence and asymptotic error constant are defined. Then it is proven that for any EA, under particular initialization, its order of convergence is 1 and its asymptotic error constant equals to the spectral radius of the transition probability sub-matrix; if its transition probability sub-matrix is primitive or upper triangular with unique diagonal entries, then under random initialization, its order of convergence is 1 and its asymptotic error constant equals to the spectral radius of the transition probability sub-matrix. Our study reveals that evolutionary algorithms converge linearly to the optimal solution and the spectral radius of the transition probability sub-matrix is the main factor in affecting the approximation error.