

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

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

## V. Diversity

In this section, we present statistic measures on the evolution of the genotypic diversity in the population. Three kinds of measures are performed : The global average diversity, the vertical/horizontal diversity and the local diversity. The global average diversity measure is made on a set of 50 runs of one instance of QAP for each kind of algorithm. It consists in computing the genotypic diversity between each solutions generation after generation.

$$g D=({\frac{1}{\#r_{c}^{2}c}})^{2}\sum_{r_{1},r2}\sum_{c_{1},c_{2}}d(x_{r_{1}c_{1}},x_{r_{2}c_{2}})$$

where d(x1, x2) is the distance between solutions x1 and x2.

The distance used is inspired from the Hamming distance: It is the number of locations that differ between two solutions divided by their length n.

The results for each generation are averaged on 50 runs.

We obtain a curve representing the evolution of the global diversity in the population through 2000 generations.

The vertical/horizontal diversity measures the average diversity in the columns and in the rows of the grid. The vertical (resp. horizontal) diversity is the sum of the average distance between all solutions in the same column (resp. row) divided by the number of columns (resp. rows):

 $ vD=\frac{1}{\frac{i}{\hbar}r}\frac{1}{\frac{i}{\hbar}c^2}\sum_{r}\sum_{c_1,c_2}d(x_{rc_1},x_{rc_2})$  $ hD=\frac{1}{\frac{i}{\hbar}c}\frac{1}{\frac{i}{\hbar}r^2}\sum_{c}\sum_{r_1,r_2}d(x_{r_1c},x_{r_2c})$  and it can then be a free number. 

where ♯r and ♯c are the number of rows and columns in the grid.

This measure is only made for the cGA with anisotropic selection. As the stochastic tournament selection provides an isotropic diffusion of solutions, the difference between horizontal and vertical diversities is null.