Crossover Dynamics

Figure 3 shows a simulation of the behavior of the crossover for the optimization of Rosenbrock function [EB97b] with two variables. On Figure 3a, we observe how most of the individuals are within the domain $ D^{CIP}$; while the best $ n$ are within the confidence domain $ D^{CI} \equiv I_1^{CI} \times
I_2^{CI}$. $ D^{CI}$ is shifted towards the minimum of the function placed in $ (1, 1)$, the domain $ D^{CIP}$ of the new population, generated after applying CIXL2, will be shifted to the optimum. This displacement will be higher in the first stages of evolution, and will decrease during evolution. It may be modulated by the parameters $ n$ and $ 1-\alpha $.

Figure 3a shows how the population, after applying the crossover operator, is distributed in a region nearer the optimum whose diversity depends on the parameters of the operator.

Figure 3b shows how the whole population and the $ n$ best individuals are distributed. As we can see, the distribution of the best $ n$ individuals keeps the features of the distribution of the population, but it is shifted to the optimum. The shifting towards the optimum will be more marked if the value of $ n$ is small. The tails of the distribution of the best individuals will be larger if the dispersion of the best individuals is also large, and smaller if they are concentrated in a narrow region. The size of these tails also depends on the features of the problem, the stage of the evolution, and the particular gene considered. The effect of the crossover on the distribution of the population is to shift the distribution towards the best $ n$ individuals and to stretch the distribution modulately depending on the amplitude of the confidence interval. The parameters $ n$ and $ 1-\alpha $ are responsible for the displacement and the stretching of the region where the new individuals will be generated.

If $ n$ is small, the population will move to the most promising individuals quickly. This may be convenient for increasing the convergence speed in unimodal functions. Nevertheless, it can produce a premature convergence to suboptimal values in multimodal functions. If $ n$ is large, both the shifting and the speed of convergence will be smaller. However, the evolutionary process will be more robust, this feature being perfectly adequate for the optimization of multimodal, non-separable, highly epistatic functions.

The parameter $ n$ is responsible for the selectiveness of the crossover, as it determines the region where the search will be directed. The selection is regulated by the parameter $ 1-\alpha $. This parameter bounds the error margin of the crossover operator in order to obtain a search direction from the feature that shares the best individuals of the population.

Domingo 2005-07-11