A standard technique to study the induced selection pressure without introducing the perturbing effect of variation operators is to let selection be the only active operator, and then monitor the number of best individual copies N(t**) in**
the population [8]. The takeover time is the time it takes for the single best individual to conquer the whole population. The grid is initialized with one cell having the best fitness and all the other having a null fitness. Since no other evolution mechanism but selection takes place, we can observe the way the best individual spreads over the grid by counting generation after generation the number of copies of this one. A shorter takeover time thus means a higher selective pressure. It has been shown that when we move from a panmictic population, as in standard GA, to a spatially structured one of the same size with synchronous updating of the cells, the global selection pressure induced on the entire population is weaker [13].

Links have been established between takeover time and neighborhood size and shape or grid topology. Neighborhood size and shape in a cGA are parameters that have some influence on the takeover time. A larger overlap of local neighborhoods of the same shape speeds up the best individual's spreading over the grid. The influence of the shape is given by Sarma and De Jong through a measure on the neighborhood which represents the spatial dispersion of a cell pattern [13]. Rather than the size of the neighborhood in terms of individuals, the key particularity of a local neighborhood is its radius. The takeover time decreases while the radius increases in a spatially structured population.

We measure the relation between grid topology and selective pressure for rectangular grids where the population size is fixed to 4096. We use the following grid shapes: 64 × 64; 32 × 128; 16 × 256; 8 × 512; 4 × 1024 and 2 × **2048 individuals. The selection strategy is a binary tournament. For**
each cell we randomly choose two individuals in its neighborhood. The best one then replaces the individual of the cell on the grid if it is fitter or with probability 0.5 if fitnesses are equal. Figure 1 shows the average of 103**independant runs**
of growth of N(t**) against generations; the takeover time is** reached when N(t**) is equal to the size of the grid (see Table**
I). The average growth rate ∆(t**), that is the number of new**
best individual copies per time unit, of these curves for four rectangular grid shapes (64×64, 32×128, 16×256,8×**512)**
is plotted in Figure 2. This figure helps us to understand the growth of N(t). The growth rate ∆(t**) is the same for all**
grids for the first generations. Then, the spreading speeds down to reach a constant speed for rectangular grids. This constant is 2lp where p **is the probability of selecting the**
best individual when there is one copy of it in the neighborhood and l **the shortest side of the grid [5]. More accurately,** ∆(t) decreases when l **is filled by copies of the best individual (see Figure 3(b)). Then, the speed becomes constant**
until the best individual has spread over to the other side
(see Figure 3(c)). This explains why the 64 × **64 grid curve**
has no constant period: the two sides are filled at the same time. Finally, the growth rate falls down to zero as the best individual finishes conquering the grid. The results of the experiments we conducted are in agreement with E.Alba and J.Troya observations that narrow grid shapes induce low selective pressure [2]. We will see in the next sections that this behavior can be observed with the AS too.

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

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

