Analysis of Evolutionary Algorithms: From Computational Complexity Analysis to Algorithm Engineering

摘要

Analyzing the computational complexity of evolutionary algorithms has become an accepted and important branch in evolutionary computation theory. This is usually done by analyzing the (expected) optimization time measured by means of the number of function evaluations and describing its growth as a function of a measure for the size of the search space. Most often asymptotic results describing only the order of growth are derived. This corresponds to classical analysis of (randomized) algorithms in algorith-mics. Recently, the emerging field of algorithm engineering has demonstrated that for practical purposes this analysis can be too coarse and more details of the algorithm and its implementation have to be taken into account in order to obtain results that are valid in practice. Using a very recent analysis of a simple evolutionary algorithm as starting point it is shown that the same holds for evolutionary algorithms. Considering this example it is demonstrated that counting function evaluations more precisely can lead to results contradicting actual run times. Motivated by these limitations of computational complexity analysis an algorithm engineering-like approach is presented.