research </tiltle> <style type="text/css"> @import url(dimensionMinMax.css) screen; </style> </head> <body> <div> <h1>On the influence of selection operators on performances in cellular Genetic Algorithms</h1> <h2>Abstract</h2> <p> In this paper, we study the influence of the selective pressure on the performance of cellular genetic algorithms. Cellular genetic algorithms are genetic algorithms where the population is embedded on a toroidal grid. This structure makes the propagation of the best so far individual slow down, and allows to keep in the population potentially good solutions. We present two selective pressure reducing strategies in order to slow down even more the best solution propagation. We experiment these strategies on a hard optimization problem, the Quadratic Assignment Problem, and we show that there is a threshold value of the control parameter for both which gives the best performance. This optimal value does not find explanation on the selective pressure only, measured either by takeover time or diversity evolution. This study makes us conclude that we need other tools than the sole selective pressure measures to explain the performance of cellular genetic algorithms. </p> <h2>Introduction</h2> <p> The selective pressure can be seen as the ability for solutions to survive in the population. When the selective pressure is high, only the best solutions survive and colonize the population, allowing less time for the algorithm to explore the search space. Thus, the selective pressure has an impact on the exploration/exploitation trade-off: When it is too low, good solutions' influence on the population is so weak that the algorithm can't converge and behave as a random search in the search space. When it is too strong, the algorithm converges quickly and as soon as it is stuck in a local optimum it won't be able to find better solutions. </p> <p> Cellular Genetic Algorithms (cGA) are a subclass of Evolutionary Algorithms in which the population is embedded on a bidimensional toroidal grid. Each cell of the grid contains one individual (solution) and the stochastic operators are applied within the neighborhoods of each cell. The existence of such small overlapped neighborhoods guarantee the propagation of solutions through the grid and enhance exploration and population diversity \cite{SpiessensM91}. Such a kind of algorithms is especially well suited for complex problems with multiple local optima \cite{JongS95}. To avoid the algorithm to converge toward one local optimum, one should apply the right selective pressure on the population and find the best balance between exploitation of good solutions and exploration of the search space. </p> <p> Section 1 presents a state of the art on selective pressure in cGAs and introduces two selection operators. Section 2 compares the influence of the selection operators on the selective pressure. Section 3 gives a description of the benchmark used to analyze the algorithms. Section 4 presents a comparative study of performance of the algorithms. Section 5 is a study on the evolution of the genotypic diversity in the populations. Finally in section 6 we summarize and discuss the results of the paper. </p> </div> </body> </html>