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

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.

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.