CIXL2 Definition

From this definition of the confidence interval, we define three intervals to create three ``virtual'' parents, formed by the lower limits of the confidence interval of each gene, $ CILL$4, the upper limits, $ CIUL$5, and the means $ CIM$6. These parents have the statistical information of the localization features and dispersion of the best individuals of the population, that is, the genetic information the fittest individuals share. Their definition is:
$\displaystyle CILL$ $\displaystyle =$ $\displaystyle (CILL_1,\ldots, CILL_i,\ldots CILL_p)$ (10)
$\displaystyle CIUL$ $\displaystyle =$ $\displaystyle (CIUL_1,\ldots, CIUL_i,\ldots CIUL_p)$  
$\displaystyle CIM$ $\displaystyle =$ $\displaystyle (CIM_1,\ldots, CIM_i,\ldots CIM_p),$  

where
$\displaystyle CILL_i$ $\displaystyle =$ $\displaystyle \bar{\beta}_i^* - t_{n-1,\alpha/2}{S_{\beta_i^*} \over
\sqrt{n}}$ (11)
$\displaystyle CIUL_i$ $\displaystyle =$ $\displaystyle \bar{\beta}_i^* + t_{n-1,\alpha/2} {S_{\beta_i^*} \over
\sqrt{n}}$  
$\displaystyle CIM_i$ $\displaystyle =$ $\displaystyle \bar{\beta_i}.$  

The $ CILL$ and $ CIUL$ individuals divide the domain of each gene into three subintervals: $ D_i \equiv I_i^L \cup I_i^{CI} \cup I_i^{U}$, where $ I_i^L \equiv [a_i,CILL_i)$; $ I_i^{CI} \equiv [CILL_i, CIUL_i]$; $ I_i^U \equiv (CIUL_i, b_i]$; being $ a_i$ and $ b_i$ the bounds of the domain (see Figure 2).

Figure 2: An example of confidence interval based crossover
Image RepGenIC

The crossover operator creates one offspring $ \beta^s$, from an individual of the population $ \beta^f \in \boldsymbol{\beta}$, randomly selected, and one of the individuals $ CILL$, $ CIUL$ or $ CIM$, depending on the localization of $ \beta^f$, as follows:

where $ r$ is a random number in the interval $ [0, 1]$.

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 $ \beta^f$ 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 $ I^{CI}$ depends on the confidence coefficient, $ 1-\alpha $, the number of best individuals, $ n$, 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 $ n$ and $ 1-\alpha $ 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 $ 1-\alpha $, the best $ n$ individuals of the population. A preliminary theoretical study of this aspect is carried out by Hervás-Martínez and Ortiz-Boyer [HMOB05].

Figure 3: Effect of the CIXL2 crossover over a population used for the minimization of the Rosenbrock function with two variables
Image SupRosCruICIng Image HisRosyCruICIng
(a) (b)

Domingo 2005-07-11