An initial error analysis for evolutionary algorithms
An initial error analysis for evolutionary algorithms
复制标题
进化算法的初始误差分析
DOI：
10.1145/3067695.3075981
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
He J
中科院分区：
文献类型：
--
作者：
He J
进化算法的逼近误差是最优解与算法找到的解之间的适应度差。本文对求解离散优化问题的进化算法进行了初始误差分析。首先定义了收敛阶和渐近误差常数。证明了对于任意进化算法，在特定的初始条件下，其收敛阶为1，渐近误差常数等于转移概率子矩阵的谱半径;如果其转移概率子矩阵是具有唯一对角元素的本原或上三角矩阵，则在随机初始化下，其收敛阶为1，渐进误差常数等于转移概率子矩阵的谱半径。我们的研究表明，进化算法线性收敛到最优解，转移概率子矩阵的谱半径是影响近似误差的主要因素。
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.
DOI：
10.1109/cec.2016.7744345
发表时间：
2015-11
期刊：
2016 IEEE Congress on Evolutionary Computation (CEC)
影响因子：
--
作者：
Jun He
通讯作者：
Jun He