Select Topics in the Analysis of Evolutionary Algorithms
Now that we have a collection of analytical tools tailored for the analysis of evolutionary algorithms, we are ready to consider concrete evolutionary algorithms and derive results, gain insights, prove facts about their behavior and performance. Of cours
- PDF / 823,084 Bytes
- 80 Pages / 439.36 x 666.15 pts Page_size
- 57 Downloads / 154 Views
Select Topics in the Analysis of Evolutionary Algorithms
Now that we have a collection of analytical tools tailored for the analysis of evolutionary algorithms, we are ready to consider concrete evolutionary algorithms and derive results, gain insights, prove facts about their behavior and performance. Of course, what one finds interesting and worth investigating in evolutionary computation is a personal question that is a matter of taste and other circumstances. It is almost inevitable that some questions that a reader finds most interesting will not be considered here. Therefore, the most important purpose this chapter serves is to be an example of how evolutionary algorithms can be analyzed using the methods described in the previous chapter. We do this considering four different topics that cover four different aspects of evolutionary computation. This includes considering effects of specific variation crossovers, dipping into the topic of design of evolutionary algorithms, considering a specific variant of evolutionary computation that we have not covered before, and, finally, considering an example for an application of evolutionary algorithms in combinatorial optimization.
6.1 Crossover So far, we have not analyzed a single evolutionary algorithm that makes proper use of crossover. Almost every single one of our analyses was restricted to evolutionary algorithms using mutation as the only variation operator. The only exception is the (1C1) GA (Algorithm 3) that uses 1-point crossover. It is not a realistic evolutionary algorithm and it sidesteps the analytical difficulties introduced by crossover. We have already discussed (see Sect. 5.8) that increasing the population size complicates the analysis more than increasing the offspring population size . The reason is that increasing the population size increases the number of different populations, the natural state space of a Markov chain that is associated with an evolutionary algorithm. Increasing the offspring population size only changes the transition probabilities of this Markov chain, not its state space. Introducing crossover introduces another fundamental change. When using mutation it is completely T. Jansen, Analyzing Evolutionary Algorithms, Natural Computing Series, DOI 10.1007/978-3-642-17339-4 6, © Springer-Verlag Berlin Heidelberg 2013
157
158
6 Select Topics in the Analysis of Evolutionary Algorithms
sufficient to know about the distribution of single individuals in the population. When using crossover, however, at least two members of the current population are involved and the process becomes dependent on correlations between members of the population. One can argue that an evolutionary algorithm using a crossover operator that creates offspring based on two parents has a quadratical dynamical system as its most natural formal description (as opposed to a linear system like a Markov chain). It is well known that the analysis of quadratical dynamical systems is much harder. This exposes how the (1C1) GA sidesteps the difficulty usua
Data Loading...
