The overlapped neighborhoods allow to control the diffusion of phenotypic and genotypic informations through the population.

Figures 10 and 11 show that the algorithm with stochastic tournament or anisotropic selection exploit differently the structure of the grid. When using the anisotropic selection, the algorithm can favor the propagation of solutions vertically. This structuration creates subpopulations in the columns of the grid, and solutions can occasionally share information with adjacent subpopulations. On the other side, the stochastic tournament selection provides an isotropic propagation of solutions. The algorithm can control the speed of the propagation by decreasing the probability to select the best participant to the tournament as genitor. The snapshots and the figures 6 and 7 show that the genotypic diversity in the population is influenced by the exploitation of the grid structure.

The selection operator plays an important role in the exploration of the search space and in the exploitation of solutions.

The two operators we compare allow to control the selective pressure. For ro and αo the selective pressure induced on the population gives the best ratio between exploration and exploitation. But this ratio is dependant of the exploration and exploitation dynamics of the algorithm. Thus, it is dependant of the selection operator used. The measures on genotypic diversity and the snapshots show these differences whether the algorithm uses the stochastic tournament or the anisotropic selection. Thus, the selective pressure needed to find the best exploration/exploitation trade-off is dependant of the transmission mode of information through the grid. Furthermore, the existence of a threshold value for the parameter which controls the selective pressure do not find explanation in the statistic measures on genotypic diversity and takeover time.

A study of the relations between topologic, phenotypic and genotypic distances should give a better explanation of performance and as a consequence should explain the takeover time and diversity during the search process. In order to explain performance of cGAs, we need to study the transmission mode of the informations through the grid since the ratio between exploration and exploitation seems to rely on it.

## Conclusion And Perspectives

This paper presents a comparative study of two selection operators, the anisotropic selection and the stochastic tournament selection, that allow a cellular Genetic Algorithm to control the selective pressure on the population. A study on the influence of the selection operators on the selective pressure is made by measuring the takeover time and the genotypic diversity. We analyse the average performance obtained on three instances of the well-known Quadratic Assignment Problem. A threshold value for the parameters of both of the selection operators that gives optimal performance has been put in evidence. These threshold values give the adequate selective pressure on the population for the QAP. However, the selective pressure is different for the two methods. A study on the genotypic diversity shows that the dynamic of diffusion of informations through the grid is different when using the stochastic tournament or the anisotropic selection operator. The anisotropic selection favors the formation of subpopulations in the columns of the grid, whereas the stochastic tournament selection slows down the propagation speed of the good solutions. The selection operator have some influence on the dynamic of transmission of the information through the grid and the ratio between exploration and exploitation is not sufficient to explain the performance of a cGA.

Nevertheless, we show that even if it is different for the anisotropic selection and the stochastic tournament selection, the selective pressure has some influence on performances. Further works will analyze the dynamic of diffusion of the information through the grid and explain the existence of a threshold value for the two cGAs by studying statistic measures on the relations between topologic, genotypic and phenotypic distances.

REFERENCES
[1] E. Alba and J. M. Troya. Cellular evolutionary algorithms: Evaluating the influence of ratio. In *PPSN*, pages 29–38, 2000.

[2] J. R. C.E. Nugent, T.E. Vollman. An experimental comparison of techniques for the assignment of techniques to locations. *Operations* Research, 16:150–173, 1968.

[3] M. Giacobini, E. Alba, A. Tettamanzi, and M. Tomassini. Modeling selection intensity for toroidal cellular evolutionary algorithms. In GECCO, pages 3–11, 2004.

[4] M. Giacobini, A. Tettamanzi, and M. Tomassini. Modelling selection intensity for linear cellular evolutionary algorithms. In P. L. et al.,
editor, Artificial Evolution, Sixth International Conference, Evolution Artificielle, EA 2003, Lecture Notes in Computer Science, pages 345– 356, Marseille, France, October 2003. Springer.

[5] D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In *FOGA*, pages 69–93, 1990.

[6] K. A. D. Jong and J. Sarma. On decentralizing selection algorithms.

In *ICGA*, pages 17–23, 1995.

[7] T. Koopmans and M. Beckmann. Assignment problems and the location of economic activities. *Econometrica*, 25(1):53–76, 1957.

[8] V. V. Migkikh, A. P. Topchy, V. M. Kureichik, and A. Y. Tetelbaum.

Combined genetic and local search algorithm for the quadratic assignment problem.

[9] G. Rudolph. On takeover times in spatially structured populations:
Array and ring. Proceedings of the SecondAsia-Pacific Conference on Genetic Algorithms and Applications (APGA '00), pages 144–151, 2000.

[10] J. Sarma and K. A. De Jong. An analysis of the effects of neighborhood size and shape on local selection algorithms. In *PPSN*, pages 236–244, 1996.

[11] D. Simoncini, P. Collard, S. Verel, and M. Clergue. From cells to islands: An unified model of cellular parallel genetic algorithms. In S. E. Yacoubi, B. Chopard, and S. Bandini, editors, ACRI 2006, 7th International Conference, pages 248–257, Perpignan, France, sept 2006. Lecture Notes in Computer Science 4173.

[12] D. Simoncini, S. Verel, P. Collard, and M. Clergue. Anisotropic selection in cellular genetic algorithms. In M. K. et al., editor, Genetic and Evolutionary Computation - GECCO-2006, pages 559– 566, Seatle, 8-12 July 2006. ACM.

[13] P. Spiessens and B. Manderick. A massively parallel genetic algorithm:
Implementation and first analysis. In *ICGA*, pages 279–287, 1991.

[14] J. Sprave. A unified model of non-panmictic population structures in evolutionary algorithms. *Proceedings of the congress on Evolutionary* computation, 2:1384–1391, 1999.