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 research in this paper is also linked to fixed budge analysis. Jansen and Zarges @cite_12 @cite_4 proposed fixed budget analysis. It aims to find lower and upper bounds @math and @math such that @math usually for a fixed budget @math . They investigated two algorithms: random local search and the @math EA and obtained such bounds on several pseudo-Boolean optimization problems.
@cite_4 @cite_12
2111575001 2041706554
When for a difficult real-world optimisation problem no good problem-specific algorithm is available often randomised search heuristics are used. They are hoped to deliver good solutions in acceptable time. The theoretical analysis usually concentrates on the average time needed to find an optimal or approximately optimal solution. This matches neither the application in practice nor the empirical analysis since usually optimal solutions are not known and even if found cannot be recognised. More often the algorithms are stopped after some time. This motivates a theoretical analysis to concentrate on the quality of the best solution obtained after a pre-specified number of function evaluations called budget. Using this perspective two simple randomised search heuristics, random local search and the (1+1) evolutionary algorithm, are analysed on some well-known example problems. Upper and lower bounds on the expected quality of a solution for a fixed budget of function evaluations are proven. The analysis shows novel and challenging problems in the study of randomised search heuristics. It demonstrates the potential of this shift in perspective from expected run time to expected solution quality. Randomised search heuristics are used in practice to solve difficult problems where no good problem-specific algorithm is known. They deliver a solution of acceptable quality in reasonable time in many cases. When theoretically analysing the performance of randomised search heuristics one usually considers the average time needed to find an optimal solution or one of a pre-specified approximation quality. This is very different from practice where usually the algorithm is stopped after some time. For a theoretical analysis this corresponds to investigating the quality of the solution obtained after a pre-specified number of function evaluations called budget. Such a perspective is taken here and two simple randomised search heuristics, random local search and the (1+1) evolutionary algorithm, are analysed on simple and well-known example functions. If the budget is significantly smaller than the expected time needed for optimisation the behaviour of the algorithms can be very different depending on the problem at hand. Precise analytical results are proven. They demonstrate novel and interesting challenges in the analysis of randomised search heuristics. The potential of this different perspective to provide a more practically useful theory is shown.