Methods for the Analysis of Evolutionary Algorithms
Analyzing evolutionary algorithms is often surprisingly difficult. It can be challenging even for very simple evolutionary algorithms on very simple functions. This is due to the fact that evolutionary algorithms are a class of randomized search heuristic
- PDF / 797,292 Bytes
- 71 Pages / 439.36 x 666.15 pts Page_size
- 89 Downloads / 240 Views
Methods for the Analysis of Evolutionary Algorithms
Analyzing evolutionary algorithms is often surprisingly difficult. It can be challenging even for very simple evolutionary algorithms on very simple functions. This is due to the fact that evolutionary algorithms are a class of randomized search heuristics mimicking natural evolution that have been designed to search effectively for good solutions in a vast search space without any thought about analysis. The directed random sampling of the search space they perform gives rise to complex and hard to analyze random processes that can be described as complex Markov chains as we have discussed in Sect. 3.1. This motivates us to start our analysis with evolutionary algorithms that are as simple as possible and consider fitness functions that are as simple as possible. We do not claim that such evolutionary algorithms are actually applied in practice or that example problems bear much resemblance to real optimization problems. One must be careful not to hastily assume that such results are neither interesting nor important. It is not the specific results that are of lasting interest but the methods developed and applied to obtain them. While all methods are developed for analytical situations that are very much simplified, they prove to be applicable and useful way beyond such simple circumstances. We concentrate on the methods here, and describe their basis and their application using simple examples devoting one section to one method. We use instructive examples and consider the same example using different methods where possible, demonstrating the specific strengths and weaknesses of the different methods this way. Readers are urged to apply these methods to examples of similar simplicity themselves. It is only in the practical application of these analytical tools that competence in the analysis of evolutionary algorithms can be gained. Clearly, we analyze the optimization time TA;f here for different simple evolutionary algorithms A and different simple example functions f . Since TA;f is a random variable there are many different aspects we can concentrate on. Except for trivial cases, it is not feasible to describe its precise distribution completely. Moreover, such results confront us with a degree of precision that is not necessary to gain an understanding of the functioning of evolutionary algorithm A on example function f . In most cases we will be satisfied to derive results on the expected
T. Jansen, Analyzing Evolutionary Algorithms, Natural Computing Series, DOI 10.1007/978-3-642-17339-4 5, © Springer-Verlag Berlin Heidelberg 2013
85
86
5 Methods for the Analysis of Evolutionary Algorithms 1n OneMax
n
0n
n/2
n n/2 number of 1-bits
Fig. 5.1 Graphical representation of ONEM AX using hypercube representation (left) and function values over the number of 1-bits (right)
optimization time E TA;f . Even there we do not strive for an exact calculation but are content with upper and lower bounds. We make use of the well-known Landau notation (see
Data Loading...
