Theoretical Perspectives on Evolutionary Algorithms
There have been a number of different attempts at building a theory for evolutionary algorithms that delivers interesting and meaningful results. All these theories have in common that they tend to start with rather simple evolutionary algorithms since ev
- PDF / 166,600 Bytes
- 14 Pages / 439.36 x 666.15 pts Page_size
- 67 Downloads / 203 Views
Theoretical Perspectives on Evolutionary Algorithms
There have been a number of different attempts at building a theory for evolutionary algorithms that delivers interesting and meaningful results. All these theories have in common that they tend to start with rather simple evolutionary algorithms since even those turn out to be particularly difficult to analyze. This chapter is devoted to the presentation of some of these approaches. The choice of which branches of evolutionary computation theory to cover is mostly governed by the influence on current research in this area. The first two approaches that we discuss in some detail have in common that they use a precise and specific description of evolutionary algorithm runs as their basis. Let us assume that we start a theoretical approach by fixing some specific evolutionary algorithm as our object of study, e.g., the simple genetic algorithm. We set all its parameters to some fixed values so that we have some concrete population size , some concrete crossover probability pc , and some concrete mutation probability pm . Remember that using the simple GA implies that we employ fitness-proportional selection for reproduction, 1-point crossover, and standard bit mutations. In addition to these choices, we fix some concrete fitness function f W f0; 1gn ! IRC . Considering all these details as fixed during the course of our analysis, what else needs to be considered to have a precise and complete description of a run of this simple GA on this fitness function f ? Clearly, only the sequence of populations P0 ; P1 ; P2 ; : : : needs to be taken into account. This motivates that we concentrate on the way the current population Pt of our simple GA can be described. The third approach is quite different. It is based in spirit on design and analysis of efficient algorithms. While appreciating the differences between problem-specific algorithms and general search heuristics the same basic notions for measuring their efficiency is used. Since this third approach is the one that we concentrate on in the remainder of this book we only give a very brief introduction in this chapter, which is restricted to brief overviews.
T. Jansen, Analyzing Evolutionary Algorithms, Natural Computing Series, DOI 10.1007/978-3-642-17339-4 3, © Springer-Verlag Berlin Heidelberg 2013
31
32
3 Theoretical Perspectives on Evolutionary Algorithms
3.1 Approaches Based on Markov Chains Markov chains are a classical tool for the formal, mathematical description of random processes. The description of a Markov chain consists of two main elements. One is a set Z containing all states that the Markov chain can be in. In the context of evolutionary algorithms we can restrict our attention to finite state sets Z and Markov chains that work in discrete time steps. In each step the Markov chain moves from its current to another state. The second main ingredient are the probabilities that govern this movement. The defining property of Markov chains is that the probability for moving from the current state
Data Loading...
