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.
The standard choice for mutating an individual of an evolutionary algorithm with continuous variables is the normal distribution; however other distributions, especially some versions of the multivariate Cauchy distribution, have recently gained increased popularity in practical applications. Here the extent to which Cauchy mutation distributions may affect the local convergence behavior of evolutionary algorithms is analyzed. The results show that the order of local convergence is identical for Gaussian and spherical Cauchy distributions, whereas nonspherical Cauchy mutations lead to slower local convergence. As a by-product of the analysis, some recommendations for the parametrization of the self-adaptive step size control mechanism can be derived. This paper addresses a Markov chain analysis of genetic algorithms (GAs), in particular for a variety called a modified elitist strategy. The modified elitist strategy generates the current population of M individuals by reserving the individual with the highest fitness value from the previous generation and generating M-1 individuals through a generation change. The author's analysis is based on a Markov chain: by assuming a simple GA in which the genetic operation in the generation changes is restricted to selection, crossover, and mutation, and by evaluating the eigenvalues of the transition matrix of the Markov chain, the convergence rate of the GAs is computed in terms of a mutation probability spl mu . In this way, the authors show the probability that the population includes the individual with the highest fitness value is lower-bounded by 1-O(| spl lambda *| sup n ), | spl lambda *| > The best achievable convergence rates of mutation-based evolutionary algorithms are known for various characteristic test problems. Most results are available for convex quadratic functions with Hessians of full rank. Here, we prove that linear convergence rates are achievable for convex quadratic functions even though the Hessians are rank-deficient. This result has immediate implications for recent convergence results for certain evolutionary algorithms for bi-objective optimization problems. This paper discusses the convergence rates of genetic algorithms by using the minorization condition in the Markov chain theory. We classify genetic algorithms into two kinds: one with time-invariant genetic operators, another with time-variant genetic operators. For the former case, we have obtained the bound on its convergence rate on the general state space; for the later case, we have bounded its convergence rate on the finite state space. This paper shows a theoretical property on the Markov chain of genetic algorithms: the stationary distribution focuses on the uniform population with the optimal solution as mutation and crossover probabilities go to zero and some selective pressure defined in this paper goes to infinity. Moreover, as a result, a sufficient condition for ergodicity is derived when a simulated annealing-like strategy is considered. Additionally, the uniform crossover counterpart of the Vose-Liepins formula is derived using the Markov chain model. 