Comparative Study of the Crossovers

Due to the large amount of different crossovers available, it is unfeasible to make a comprehensive comparison between all those crossovers and CIXL2. We have chosen those crossovers that obtain interesting results and those whose features are similar to our crossover, that is, which are self-adaptive and establish a balance between the exploration and the exploitation of the search space. The way in which these two features are balanced is regulated by one or more parameters of each crossover. These parameters have been chosen following the authors' recommendations and the papers devoted to the comparison of the different operators.

The crossovers used in the comparison are: BLX$\alpha$ [ES93] with different degrees of exploration determined by the values $\alpha=\{0.2,0.5\}$ [HLS03]; fuzzy recombination [VMC95]; based on fuzzy connectives of the logical family (logical crossover) [HLV98] using S2 strategies and $\lambda=0.5$ [HL00], SBX [DA95] using the values $\nu=\{2,5\}$ [DB01]; UNDX [OK97] with $\sigma_{\xi}={1 \over 2}$ and $\sigma_{\eta}={0.35 \over \sqrt{p}}$ [KOK98,Kit01]. For CIXL2, as we have determined in the previous study, we will use $n=5$ and $1-\alpha=0.70$.

Following the setup of the previous study, we performed an ANOVA II analysis and a multiple comparison test. As might have been expected, keeping in mind the ``no-free lunch'' theorem and the diversity of the functions of the test set, the tests show that there is no crossover whose results are significatively better than the results of all other crossovers. This does not mean that these differences could not exist for certain kinds of functions. So, in order to determine for each kind of function whether a crossover is better than the others, we have performed an ANOVA I analysis -- where the only factor is the crossover operator -- and a multiple comparison test. Additionally, we graphically study the speed of convergence of the RCGA with regard to the crossover operator. In order to enforce the clearness of the graphics for each crossover, we show only the curve of the best performing set of parameters for BLX and SBX crossovers.

Table 3: Average values and standard deviation for the 30 runs of every crossover operator.

Crossover	$\mathbf{Mean}$	$\mathbf{St. Dev.}$			$\mathbf{Mean}$	$\mathbf{St. Dev.}$			$\mathbf{Mean}$	$\mathbf{St. Dev.}$
	$\mathbf{f_{Sph}}$				$\mathbf{f_{SchDS}}$				$\mathbf{f_{Ros}}$
CIXL2	6.365e-16	2.456e-16			1.995e-03	2.280e-03			2.494e+01	1.283e+00
BLX(0.3)	3.257e-16	1.396e-16			1.783e-02	1.514e-02			2.923e+01	1.723e+01
BLX(0.5)	4.737e-16	4.737e-16			9.332e-03	1.086e-02			3.161e+01	2.094e+01
SBX(2)	1.645e-12	8.874e-13			2.033e-01	1.966e-01			2.775e+01	9.178e+00
SBX(5)	4.873e-12	3.053e-12			3.933e-01	2.881e-01			3.111e+01	1.971e+01
Ext. F.	2.739e-15	1.880e-15			3.968e+01	1.760e+01			2.743e+01	1.394e+01
Logical	3.695e-13	1.670e-13			1.099e+01	7.335e+00			2.703e+01	8.358e-02
UNDX	2.910e-05	1.473e-05			2.080e+01	7.216e+00			2.840e+01	3.606e-01
	$\mathbf{f_{Ras}}$				$\mathbf{f_{Sch}}$				$\mathbf{f_{Ack}}$
CIXL2	2.919e+00	1.809e+00			6.410e+02	2.544e+02			1.378e-08	5.677e-09
BLX(0.3)	2.189e+00	1.417e+00			3.695e+02	1.595e+02			4.207e-08	1.713e-08
BLX(0.5)	3.018e+00	1.683e+00			4.200e+02	1.916e+02			6.468e-08	1.928e-08
SBX(2)	1.844e+01	4.417e+00			1.470e+03	3.827e+02			5.335e-06	1.453e-06
SBX(5)	1.419e+01	3.704e+00			1.104e+03	3.353e+02			9.662e-06	2.377e-06
Ext. F.	2.245e+01	4.914e+00			3.049e+03	2.876e+02			1.797e-07	5.823e-08
Logical	6.325e+01	1.012e+01			2.629e+03	9.749e+01			2.531e-06	7.129e-07
UNDX	1.107e+02	1.242e+01			8.050e+03	3.741e+02			3.551e-02	1.224e-02
	$\mathbf{f_{Gri}}$				$\mathbf{f_{Fle}}$				$\mathbf{f_{Lan}}$
CIXL2	1.525e-02	1.387e-02			1.523e+04	1.506e+04			-2.064e-01	9.346e-02
BLX(0.3)	4.749e-02	4.579e-02			1.570e+04	1.515e+04			-3.003e-01	1.388e-01
BLX(0.5)	3.760e-02	2.874e-02			1.802e+04	1.483e+04			-3.457e-01	1.684e-01
SBX(2)	2.196e-02	1.874e-02			3.263e+04	3.110e+04			-1.939e-01	1.086e-01
SBX(5)	3.128e-02	2.737e-02			3.333e+04	2.973e+04			-1.866e-01	9.080e-02
Ext. F.	1.315e-03	3.470e-03			1.691e+04	1.446e+04			-1.064e-01	5.517e-02
Logical	6.078e-03	6.457e-03			2.718e+04	1.388e+04			-7.396e-08	2.218e-07
UNDX	7.837e-02	4.438e-02			3.469e+04	2.136e+04			-2.130e-01	9.116e-02

Table 3 shows the average values and standard deviations for the $30$ runs performed for each crossover operator. Table 10 in Appendix A shows how, for all the functions, except $f_{Ros}$, the crossover operator has a significant effect on the linear model. The table also shows that the results of the Levene test indicate the inequality of the variances of the results of all the functions, excepting $f_{Fle}$. So, we use the Bonferroni test for $f_{Fle}$, and the Tamhane test for all the others. The results of the multiple comparison test, the ranking established by the tests and the significant level of the differences among the results of the crossovers are shown on Tables 14, 15 and 16 (Appendix A). Figures 5 - 13, in Appendix B, show, in logarithmic scale, the convergence curves for each function.

For $f_{Sph}$ the high value of the determination coefficient shows that the linear model explains much of the variance of the fitness. The best values are obtained with BLX(0.3), BLX(0.5) and CIXL2, in this order. With these operators we obtain precisions around 1e-16. Figure 5 shows that CIXL2 is the fastest in convergence, but it is surpassed by BLX in the last generations.

For $f_{SchDS}$ and $f_{Ros}$ the best results are obtained with CIXL2. For $f_{SchDS}$ the difference in performance with the other crossovers is statistically significant. For $f_{Ros}$ the differences are significant, when CIXL2 is compared with Logical and UNDX. For $f_{SchDS}$ the Figure 6 shows how CIXL2 achieves a quasi-exponential convergence and a more precise final result. For $f_{Ros}$, in the Figure 7 we can see how the speed of convergence of CIXL2 is the highest, although the profile of all the crossovers is very similar with a fast initial convergence followed by a poor evolution due to the high epistasis of the function. The differences in the overall process are small. This fact explains that in the linear model the influence of the factor crossover is not significant and the determination coefficient is small.

For $f_{Ras}$, BLX(0.3) again obtains the best results but without significant difference to the average values obtained with CIXL2 and BLX(0.5). These three operators also obtain the best results for $f_{Sch}$; however, the tests show that there are significant differences between CIXL2 and BLX(0.5), and that there are no differences between BLX(0.5) and BLX(0.3). The latter obtains the best results. Figures 8 and 9 show that BLX is the best in terms of convergence speed followed by CIXL2. The large value of $R^2$ means that the crossover has a significant influence on the evolutive process.

For $f_{Ack}$, CIXL2 obtains significantly better results. In Figure 10 we can see how it also converges faster. The large value of $R^2$ means that the crossover has a significant influence on the evolutive process. For $f_{Gri}$, the Fuzzy operator obtains significantly better results. The following ones, with significant differences between them, are Logical and CIXL2. Figure 11 shows a fast initial convergence of CIXL2, but in the end Logical and Fuzzy obtain better results.

For $f_{Fle}$ the best results are obtained with CIXL2, but the difference is only significant with SBX and UNDX. Figure 12 shows that CIXL2 is the fastest in convergence, but with a curve profile similar to BLX and Fuzzy. For $f_{Lan}$, the best operator is BLX(0.5), with differences that are significant for all the other operators with the exception of BLX(0.3). UNDX and CIXL2 are together in third place. Figure 13 shows that the behavior of all crossovers is similar, except for the Logical crossover that converges to a value far from the other operators.