An Analytic Expression of Relative Approximation Error for a Class of Evolutionary Algorithms
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
syren-halofit: A fast, interpretable, high-precision formula for the $Λ$CDM nonlinear matter power spectrum
Rapid and accurate evaluation of the nonlinear matter power spectrum, $P(k)$, as a function of cosmological parameters and redshift is of fundamental importance in cosmology. Analytic approximations provide an interpreta…
regressionSymbolic RegressionImproved Coefficients for the Karagiannidis-Lioumpas Approximations and Bounds to the Gaussian Q-Function
We revisit the Karagiannidis-Lioumpas (KL) approximation of the Q-function by optimizing its coefficients in terms of absolute error, relative error and total error. For minimizing the maximum absolute/relative error, we…
Error Analysis of Sampling Algorithms for Approximating Stochastic Optimal Control
This paper is concerned with the error analysis of two types of sampling algorithms, namely model predictive path integral (MPPI) and an interacting particle system (\IPS) algorithm, that have been proposed in the litera…
The Resistance to Label Noise in K-NN and DNN Depends on its Concentration
We investigate the classification performance of K-nearest neighbors (K-NN) and deep neural networks (DNNs) in the presence of label noise. We first show empirically that a DNN's prediction for a given test example depen…
General ClassificationMulti-class ClassificationMoments and Root-Mean-Square Error of the Bayesian MMSE Estimator of Classification Error in the Gaussian Model
The most important aspect of any classifier is its error rate, because this quantifies its predictive capacity. Thus, the accuracy of error estimation is critical. Error estimation is problematic in small-sample classifi…
General Classification