(N) or South (S) and pew the probability of choosing the cells East (E) or West (W). Let α ∈ [−1; 1] be the control parameter that will determine the probabilities pns and pew.

This parameter will be called the *anisotropic degree*. The probabilities pns and pew can be described as:

$$p_{n s}={\frac{(1-p_{c})}{2}}(1+\alpha)$$ $$p_{e w}={\frac{(1-p_{c})}{2}}(1-\alpha)$$

Thus, when α = −1 we have pew = 1 − pc and pns = 0.

When α = 0, we have pns = pew and when α = 1, we have pns = 1 − pc and pew = 0. In the following, the probability pc remains fixed at 15
.

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

Figure 1 shows a Von Neumann Neighborhood with the probabilities to select each cell as a function of α.

The Anisotropic Selection operator works as follows. For each cell it selects k individuals in its neighborhood (k ∈ [1; 5]). The k individuals participate to a tournament and the winner replaces the old individual if it has a better fitness or with probability 0.5 if the fitnesses are equal. When α = 0, the anisotropic selection is equivalent to a standard tournament selection and when α = 1 or α = −1 the anisotropy is maximal and we have an uni-dimensional neighborhood with three neighbors only. In the following, considering the grid symmetry, we will consider α ∈ [0; 1]
only: when α is in the range [-1;0] making a rotation of 90◦
of the grid is equivalent to considering α in the range [0;1].

## Ii. Takeover Time

A common analytical approach to measure the selective pressure is the computation of the takeover time [9] [14]. It is the time needed for the best solution to colonize the whole population when the only active evolutionary operator is selection [5]. When the takeover time is short, it means that the best solution's propagation speed in the population is high. So, worse solutions' life time in the population is short and thus the selective pressure is strong. On the other hand, when the takeover time is high, it means that the best solution colonizes slowly the population, giving a longer lifetime to worse solutions. In that case, the selective pressure is low. So the selective pressure in the population is inversely proportionnal to the takeover time.

In order to measure the takeover time, we place one solution of fitness 1 on a 20×20 grid. All the other solutions have a null fitness. Then we run the process and measure the time needed for the solution of fitness 1 to spread over the whole grid.

We measured average takeover times over 1000 simulations for a cGA using a stochastic tournament selection, and for one using the anisotropic selection. The simulations are made on square grids of side 20. Figure 2 shows the results of these simulations. The takeover time increases when α increases in the case of a cGA using the anisotropic selection (figure 2(a)). So the selective pressure is inversely proportional to α. On figure 2(b) we can see that the takeover time increases as long as the probability r to select the worst solution in the stochastic tournament grows. This means that the selective pressure in the population is inversely proportional to r for a cGA using a stochastic tournament selection.

The slope of the curve representing the takeover time as a function of α (fig. 2(a)) for values close to 1 is more important than the one of the curve representing the takeover time as a function of r (fig. 2(b)). We can also notice that in the case of a cGA using stochastic tournament selection, the takeover time is defined when the probability to select the best solution is 0. The best solution still can colonize the population in this case since the two candidates for the tournament are selected by a random draw with replacement. In the case of a cGA using anisotropic selection, the takeover time is not defined for α = 1.The anisotropic degree α is a continuous parameter and the curve representing the takeover time as a function of α is not bounded.

## Iii. The Quadratic Assignment Problem

This section presents the Quadratic Assignment Problem
(QAP) which is known to be difficult to optimize. The QAP is an important problem in theory and practice as well. It was introduced by Koopmans and Beckmann in 1957 and is a model for many practical problems [7]. The QAP can be described as the problem of assigning a set of facilities to a set of locations with given distances between the locations and given flows between the facilities. The goal is to place the facilities on locations in such a way that the sum of the products between flows and distances is minimal.

Given n facilities and n locations, two n × n matrices D = [dij ] and F = [fkl] where dij is the distance between locations i and j and fkl the flow between facilities k and l, the objective function is:

$$\Phi=\sum_{i}\sum_{j}d_{p(i)p(j)}f_{ij}$$  where $p(i)$ gives the location of facility $i$ in the current permutation $p$. Nugent, Vollman and Ruml proposed a set of problem 
instances of different sizes noted for their difficulty [2]. The instances they proposed are known to have multiple local optima, so they are difficult for a genetic algorithm.