

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

We experiment our algorithm on the instances nug30 (30 variables), tho40 (40 variables) and sko49 (49 variables) from QAPLIB.

## Set Up

We use a population of 400 individuals placed on a square grid (20 × 20). Each individual is reprensented by a permutation of N where N is the size of an individual. The algorithm uses a crossover that preserves the permutations:
- Select two individuals p1 and p2 as genitors.

- Choose a random position i.

- Find j and k so that p1(i) = p2(j) and p2(i) = p1(k). - exchange positions i and j from p1 and positions i and k from p2.

- repeat N/3 times this procedure where N is the size of an individual.

This crossover is an extended version of the UPMX
crossover proposed in [8]. The mutation operator consist in randomly selecting two positions from the individual and

| Anisotropic selection   | Stochastic tournament selection   |      |      |              |      |      |
|-------------------------|-----------------------------------|------|------|--------------|------|------|
| Instance                | Perf                              | Val  | TO   | Perf         | Val  | TO   |
| Nug30                   | 6156.318.6                        | 0.92 | 65.7 | 6152.618.5   | 0.85 | 79.6 |
| Tho40                   | 242788988.4                       | 0.94 | 75.3 | 2431151177.2 | 0.8  | 70.4 |
| Sko49                   | 23537.255.5                       | 0.92 | 65.7 | 23550.358    | 0.8  | 70.4 |

exchanging those positions. The crossover rate is 1 and we do a mutation per individual. We perform 200 runs for each tuning of the two selection operators. An elitism replacement procedure guarantees the individuals to stay on the grid if they are fitter than their offspring. Each run stops after 2000 generations for nug30 and tho40, and after 3000 generations for sko49.

## Iv. Performances

In this section we present performance results on the Quadratic Assignment Problem for a cGA using stochastic tournament and anisotropic selection operators. In [11] the authors show that there is an optimal value of α parameter for the anisotropic selection that gives optimal performance. We want to see if the same behaviour is observed with the stochastic tournament selection and then to compare the performance obtained for these two operators.

Figures 3, 4 and 5 show performance obtained with the anisotropic and the stochastic selection operator on the QAP instances nug30, tho40 and sko49. We measure the performance by averaging the best solution found on each run for each value of anisotropy degree and stochastic rate.

When the rate of the stochastic tournament selection and the anisotropic degree are null, the two algorithms are the same : A standard cGA with binary tournament selection. The selective pressure drops when the values of the control parameters of the two algorithms increase. In both cases we see that as the selective pressure drops, performance increases until a threshold value. Once this value is reached, the performance decreases. These threshold values give the best exploration/exploitation trade-off for this problem. In the following, the threshold values of parameters α and r are denoted αo and ro.

Table 1 gives αo and ro for each instance of QAP and their corresponding takeover times (TO). Best performances are in bold and differences between performances of the two algorithms are statistically significant for each instance according to the Student's t-test. Differences in takeover times are also statistically significant. The algorithm using stochastic tournament selection is the best for nug30, and the one using anisotropic selection is the best for tho40 and sko49. The threshold values stand in the same ranges for all instances: αo ∈ {0.92, 0.94} and ro ∈ {0.8, 0.85}.

The differences in takeover times indicate that the selective pressure on the population is different for the two methods for the settings that give the best average performance. These differences can be explained by the way the algorithm explores the search space and exploits good solutions.