(10) | |||
The and individuals divide the domain of each gene into three subintervals: , where ; ; ; being and the bounds of the domain (see Figure 2).
The crossover operator creates one offspring , from an individual of the population , randomly selected, and one of the individuals , or , depending on the localization of , as follows:
where is a random number in the interval .
With this definition, the offspring always takes values in the direction of the best of the two parents but never between them. If the virtual individual is one of the bounds of the confidence interval and is better than the other parent, the offspring is generated in the direction of the confidence interval where it is more likely to generate better individuals. If the virtual individual is worse than the other parent, the offspring is generated near the other parent in the opposite direction of the confidence interval. On the other hand, if a parent selected from the population is within the confidence interval, the offspring can be outside the interval - but always in its neighborhood - if the fitness of the center of the confidence interval is worse. This formulation tries to avoid a shifting of the population towards the confidence interval, unless this shifting means a real improvement of the fitness in the population.
If is distant from the other parent, the offspring will probably undergo a marked change, and if both parents are close, the change will be small. The first circumstance will be likely to occur in the first stages of the evolutionary process, and the second one in the final stages.
The width of the interval depends on the confidence coefficient, , the number of best individuals, , and the dispersion of the best individuals. In the first stages of the evolution, the dispersion will be large, specially for multimodal functions, and will decrease together with the convergence of the genetic algorithm. These features allow the balance between exploitation and exploration to adjust itself dynamically. The crossover will be more exploratory at the beginning of the evolution, avoiding a premature convergence, and more exploitative at the end, allowing a fine tuning. The parameters and regulate the dynamics of the balance favoring a higher or lower degree of exploitation. That suggests the CIXL2 establishes a self-adaptive equilibrium between exploration and exploitation based on the features that share, with a certain confidence degree , the best individuals of the population. A preliminary theoretical study of this aspect is carried out by Hervás-Martínez and Ortiz-Boyer [HMOB05].
|
Domingo 2005-07-11