

![0_image_0.png](0_image_0.png) 

![0_image_1.png](0_image_1.png) 

## Neighborhoods.

The local diversity measure is computed on one single run for each kind of algorithm. It is the genotypic diversity observed in the neighborhood of each cell of the grid. It is represented as "snapshots" of the population, where a dark point represents a high degree of diversity in the neighborhood, and a clear point represents a low degree of diversity in the neighborhood.

Figure 9 represents the local diversity along generations for a cGA with standard binary tournament selection. We can see on snapshots of generations 300 and 500 the formation of circles. Each circle contains copies of good solutions found locally. The frontier between the areas from which good solutions colonize the grid are the only sites on the grid where the crossover operator still can have some effect. At generation 1000 the genotypic diversity on the grid is null
, the population has been colonized by one solution, and performance will not improve anymore.

Figure 10 represents the local diversity along generations for a cGA with stochastic tournament selection. The probability of selecting the best participant to the tournament is decreasing from top to bottom. The first thing we notice is that the propagation mode of good solutions is the same as for the cGA using a standard binary tournament selection. The only difference is the speed of propagation of good solutions monitored by the r parameter. As long as we give less chances to the best solution in the neighborhood to be selected, it will take more time before the algorithm converges. The areas where crossovers can help to explore the search space and to improve performance are bigger when r increases. The crossover operator does not have any effect in the white zones of the grid since there is no more genotypic diversity in such areas. For r = 1, we see that at generation 1500 the diversity is still very high and the algorithm does not exploit good solutions because the selective pressure on the population is too low.

Figure 11 represents the local diversity along generations for a cGA with anisotropic selection. Values of α increase from top to bottom. By monitoring the anisotropy degree, we can influence on the dynamics of propagation of good solutions. For low values of α, good solutions roughly propagate in circles as for a cGA using binary tournament selection. When α reaches values close to 1, the good solutions tend to colonize the columns of the grid. The diversity is conserved between the columns, which indicate that the algorithm converge toward different solutions in each columns. Thus, the anisotropic selection favors the formation of subpopulations in the columns of the grid [11]. Crossovers between subpopulations then allow the algorithm to explore the search space, as long as the probability of selecting participants from different columns for the tournament is not too low (i.e. α is not too high). When α is too high, the selective pressure on the population is too low and negatively affects performance.

## Vi. Discussion

In this section we summarize and discuss the results on takeover time, performance and genotypic diversity and we compare the cGAs using anisotropic selection and stochastic tournament selection. Two cGAs using different selection operators have been tested on instances of QAP. The two selection operators allow to control the selective pressure on the population. The analysis of takeover time and genotypic diversity show the influence of the two operators on the selective pressure.

When looking at the performance on QAP, we can see that on each instance and for both methods, the performance increases as the selective pressure drops down until a threshold value of the control parameter. After this value, the performance decreases as the selective pressure continue to drop down. The threshold values of the control parameter stand in the same range on all instances for both of the methods.