Cellular evolutionary algorithm

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.

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).

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).

This makes the population to hold at any time individual in different states of evolution, defining a very interesting new line of research.

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.

Example evolution of a cEA depending on the shape of the population, from squared (left) to unidimensional ring (right). Darker colors mean better solutions. Observe how shapes different from the traditional square keep diversity (higher exploration) for a longer time. Four snapshots of cEAs at generations 0-50-100-150.
Example models of neighborhoods in cellular EAs: linear, compact, diamond and... any other!
The ratio between the radii of the neighborhood to the topology defines the exploration/exploitation capability of the cEA. This could be even tuned during the run of the algorithm, giving the researcher a unique mechanism to search in very complex landscapes.