Cellular evolutionary algorithm

A cellular evolutionary algorithm (cEA) is a kind of evolutionary algorithm (EA) in which individuals cannot mate arbitrarily, but every one interacts with its closer neighbors on which a basic EA is applied (selection, variation, replacement).

The cellular model simulates natural evolution from the point of view of
the individual, which encodes a tentative (optimization, learning, search) problem solution. The essential idea of this model is to provide the EA population
with a special structure defined as a connected graph, in which each vertex is an individual who communicates with his
nearest neighbors. Particularly, individuals are conceptually set in a toroidal
mesh, and are only allowed to recombine with close individuals. This leads us
to a kind of locality known as ''isolation by distance''. The set of potential mates
of an individual is called its ''neighborhood''. It is known that, in this kind
of algorithm, similar individuals tend to cluster creating niches, and these groups
operate as if they were separate sub-populations (islands). Anyway, there is no
clear borderline between adjacent groups, and close niches could be easily
colonized by competitive niches and maybe merge solution contents during the process. Simultaneously,
farther niches can be affected more slowly.

Introduction

A cellular evolutionary algorithm (cEA) usually evolves a structured bidimensional
grid of individuals, although other topologies are also possible. In this grid, clusters of similar individuals are naturally created during evolution, promoting exploration in their boundaries, while exploitation is mainly performed by direct competition and merging inside them.

The grid is usually 2D toroidal structure, although
the number of dimensions can be easily extended (to 3D) or reduced (to 1D, e.g. a ring).
The neighborhood of a particular point of the grid (where an individual is
placed) is defined in terms of the ''Manhattan'' distance from it to others in the population. Each point of the grid has a neighborhood that overlaps the neighborhoods of nearby individuals. In the basic algorithm, all the neighborhoods have the same size and identical shapes. The two
most commonly used neighborhoods are L5, also called
''Von Neumann'' or NEWS (North, East, West and South), and C9, also known as ''Moore'' neighborhood. Here, ''L'' stands for ''Linear'' while ''C'' stands for ''Compact''.

In cEAs, the individuals can only interact with their neighbors in the reproductive
cycle where the variation operators are applied. This reproductive
cycle is executed inside the neighborhood of each individual and, generally,
consists in selecting two parents among its neighbors according to a certain
criterion, applying the variation operators to them (recombination and mutation
for example), and replacing the considered individual by the recently
created offspring following a given criterion, for instance, replace if the offspring
represents a better solution than the considered individual.

Synchronous versus asynchronous

In a regular synchronous cEA, the algorithm proceeds from the very first top left individual to the right and then to the several rows by using the information in the population to create a new temporary population. After finishing with the bottom-right last individual the temporary population is full with the newly computed individuals, and the replacement step starts. In it, the old population is completely and synchronously replaced with the newly computed one according to some criterion. Usually, the replacement keeps the best individual in the same position of both populations, that is, elitism is used.

We must notice that according to the update policy of the population used, we could also define an asynchronous cEA. This is also a well-known issue in cellular automata. In asynchronous cEAs the order in which the individuals in the grid are update changes depending on the criterion used: line sweep, fixed random sweep, new random sweep, and uniform choice. These are the four most usual ways of updating the population. All of them keep using the newly computed individual (or the original if better) for the computations of its neighbors immediately. This makes the population to hold at any time individual in different states of evolution, defining a very interesting new line of research.

The overlap of the neighborhoods provides an implicit mechanism of solution migration
to the cEA. Since the best solutions spread smoothly through the
whole population, genetic diversity in the population is preserved longer than
in non structured EAs. This soft dispersion of the best solutions through the
population is one of the main issues of the good tradeoff between ''exploration''
and ''exploitation'' that cEAs perform during the search. It is then easy to see
that we could ''tune this tradeoff'' (and hence, tune the genetic diversity level along
the evolution) by modifying (for instance) the size of the neighborhood used, as
the overlap degree between the neighborhoods grows according to the size of
the neighborhood.

A cEA can be seen as a cellular automaton (CA) with probabilistic
rewritable rules, where the alphabet of the CA is equivalent to the potential
number of solutions of the problem. Hence, if we see cEAs as a kind of CA,
it is possible to import knowledge from the field of CAs to cEAs, and in fact this is an interesting open research line.

Parallelism

Cellular EAs are very amenable to parallelism, thus usually found in the literature of parallel metaheuristics. In particular, fine grain parallelism can be used to assign independent threads of execution to every individual, thus allowing the whole cEA to run on a concurrent or actually parallel hardware platform. In this way, large time reductions can be obtained when running cEAs on FPGAs or GPUs.

However, it is important to stress that cEAs are a model of search, in many senses different from traditional EAs. Also, they can be run in sequential and parallel platforms, reinforcing the fact that the model and the implementation are two different concepts.

Se
here
for a complete description on the fundamentals for the understanding, design, and application of cEAs.

See also

* Cellular automaton
* Dual-phase evolution
* Enrique Alba
* Evolutionary algorithm
* Metaheuristic
* Parallel metaheuristic

References

E. Alba, B. Dorronsoro, ''Cellular Genetic Algorithms''
Springer-Verlag, , 2008
* A.J. Neighbor, J.J. Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: A New Cellular Genetic Algorithm for Multiobjective Optimization, International Journal of Intelligent Systems, 24:726-746, 2009
* E. Alba, B. Dorronsoro, F. Luna, A.J. Neighbor, P. Bouvry, L. Hogie
A Cellular Multi-Objective Genetic Algorithm for Optimal Broadcasting Strategy in Metropolitan MANETs
Computer Communications, 30(4):685-697, 2007
* E. Alba, B. Dorronsoro
Computing Nine New Best-So-Far Solutions for Capacitated VRP with a Cellular GA
Information Processing Letters, Elsevier, 98(6):225-230, 30 June 2006
* M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba
The Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices
IEEE Transactions on Evolutionary Computation, IEEE Press, 9(5):489-505, 2005
* E. Alba, B. Dorronsoro
The Exploration/Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms
IEEE Transactions on Evolutionary Computation, IEEE Press, 9(2)126-142, 2005

External links

The site on Cellular Evolutionary Algorithms

NEO Research Group at University of Málaga, Spain

{{Evolutionary computation

Evolutionary algorithms