# Anisotropic Selection In Cellular Genetic Algorithms David Simoncini David.Simoncini@Unice.Fr S´Ebastien Verel Sebastien.Verel@Unice.Fr Philippe Collard Philippe.Collard@Unice.Fr Manuel Clergue Manuel.Clergue@Unice.Fr

## I3S Laboratory, Cnrs-Universit´E De Nice Sophia Antipolis Abstract

In this paper we introduce a new selection scheme in cellular genetic algorithms (cGAs). Anisotropic Selection **(AS) promotes diversity and allows accurate control of the selective**
pressure. First we compare this new scheme with the classical rectangular grid shapes solution according to the selective pressure: we can obtain the same takeover time with the two techniques although the spreading of the best individual is different. We then give experimental results that show to what extent AS promotes the emergence of niches that support low coupling and high cohesion. Finally, using a cGA
with anisotropic selection on a Quadratic Assignment Problem we show the existence of an anisotropic optimal value for which the best average performance is observed. Further work will focus on the selective pressure self-adjustment ability provided by this new selection scheme.

## Categories And Subject Descriptors

I.2.8 [**Problem Solving, Control Methods, and Search**]:
[Heuristic methods]

## General Terms

Algorithms

## Keywords

Evolutionary computation, combinatorial cptimization

## Introduction

This paper deals with selective pressure and diversity in cellular genetic algorithms (cGAs) which are a subclass of Genetic Algorithms where the population is embedded in a grid. These concepts are closely related to the exploration/exploitation trade-off. Previous studies on cGAs selected the size and the shape of neighborhoods [13], or the shape of the grid [2, 5, 6] as basic parameters to tune the Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. GECCO'06, July 8–12, 2006, Seattle, Washington, USA.

Copyright 2006 ACM 1-59593-186-4/06/0007 ...$5.00.

search process. Altering these structural parameters entails a deep change in the way we deal with the problem. For instance, there is no built-in mean to swap from a rectangular grid to a square grid without misshaping the neighborhood relation. We suggest using anisotropic selection **(AS)**
to promote diversity and to control accurately the selective pressure in genetic search. The main advantage of the anisotropic selection **scheme is that it allows to control the**
exploration/exploitation trade-off without affecting neither the grid topology nor the neighborhood shape; so the cellular genetic algorithm we propose merely works on a square grid and a simple Von Neumann neighborhood shape.

The paper is divided in 6 sections. Section 1 gives a brief definition of cGAs and an overview of existing techniques used to control the exploration/exploitation tradeoff. Section 2 introduces the AS scheme. Section 3 studies the influence of AS on the selective pressure. In Section 4 we compare AS and rectangular grids topologies' influence on the selective pressure. In Section 5 we show how AS promotes the emergence of niches. In Section 6 we use a cGA
on a Quadratic Assignment Problem to measure the correlation between anisotropy and performance. Finally we tie together the results of the previous sections and suggest directions for further research.

## 1. Selection In Cellular Genetic Algorithms

This section presents a brief overview on cellular Genetic Algorithms and a standard technique to measure the selective pressure.

## 1.1 Cellular Genetic Algorithms

Cellular Genetic Algorithms are a subclass of Genetic Algorithms (GAs) in which exploration and population diversity are enhanced thanks to the existence of small overlapped neighborhoods [14]. Such algorithms are specially well suited for complex problems [9]. We assume a twodimensional toroidal grid as a spatial population structure.

Each grid cell contains one individual of the population. The overlapping neighborhoods provide an implicit mechanism for migration of genetic material throughout the grid. A
genetic algorithm is assumed to be running simultaneously on each grid cell, continuously selecting parents from the neighborhood of that grid cell in order to produce an offspring which replaces the current individual.

## 1.2 Takeover Time
