An analytic expression of relative approximation error for a class of evolutionary algorithms
An analytic expression of relative approximation error for a class of evolutionary algorithms
复制标题
DOI：
10.1109/cec.2016.7744345
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Jun He
中科院分区：
文献类型：
--
作者：
Jun He
进化计算中的一个重要问题是进化算法如何产生好的解。本文的目的是提供一个解析分析的解决方案的质量方面的相对逼近误差，这是由1之间的误差和进化算法找到的解决方案的逼近比定义。由于进化算法是迭代方法，相对逼近误差是代的函数。借助于矩阵分析，可以得到这种函数的精确表达式。本文对一类进化算法，即（1+1）严格精英进化算法，给出了计算相对逼近误差的解析表达式。此外，还导出了这类进化算法每代适应值和平均收敛速度的解析表达式。该方法是有前途的，它可以扩展到非精英或基于人口的算法。
An important question in evolutionary computation is how good solutions evolutionary algorithms can produce. This paper aims to provide an analytic analysis of solution quality in terms of the relative approximation error, which is defined by the error between 1 and the approximation ratio of the solution found by an evolutionary algorithm. Since evolutionary algorithms are iterative methods, the relative approximation error is a function of generations. With the help of matrix analysis, it is possible to obtain an exact expression of such a function. In this paper, an analytic expression for calculating the relative approximation error is presented for a class of evolutionary algorithms, that is, (1+1) strictly elitist evolution algorithms. Furthermore, analytic expressions of the fitness value and the average convergence rate in each generation are also derived for this class of evolutionary algorithms. The approach is promising, and it can be extended to non-elitist or population-based algorithms too.