Acellular evolutionary algorithm (cEA) is a kind ofevolutionary 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 ofthe individual, which encodes a tentative optimization, learning, or search problem solution. The essential idea of this model is to provide the EA populationwith a special structure defined as a connected graph, in which each vertex is an individual who communicates with hisnearest neighbors. Particularly, individuals are conceptually set in a toroidalmesh, and are only allowed to recombine with close individuals. This leadsto a kind of locality known as "isolation by distance". The set of potential matesof an individual is called its "neighborhood". It is known that, in this kindof algorithm, similar individuals tend to cluster creating niches, and these groupsoperate as if they were separate sub-populations (islands). There is noclear borderline between adjacent groups, and close niches could be easilycolonized by competitive niches and potentially merge solution contents during the process. Simultaneously, farther niches can be affected more slowly.
A cellular evolutionary algorithm (cEA) usually evolves a structured bidimensionalgrid 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, althoughthe 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 isplaced) is defined in terms of theManhattan 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 twomost commonly used neighborhoods are L5, also called theVon Neumann or NEWS (North, East, West and South) neighborhood, and C9, also known as the Moore neighborhood. Here, L stands for "linear" while C stands for "compact".
In cEAs, the individuals can only interact with their neighbors in the reproductivecycle where the variation operators are applied. This reproductivecycle is executed inside the neighborhood of each individual and, generally,consists in selecting two parents among its neighbors according to a certaincriterion, applying the variation operators to them (recombination and mutationfor example), and replacing the considered individual by the recentlycreated offspring following a given criterion, for instance, replace if the offspringrepresents a better solution than the considered individual.
In a regularsynchronous 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.
According to the update policy of the population used, anasynchronous cEA may also be defined and is a well-known issue incellular automata. In asynchronous cEAs the order in which the individuals in the grid are update changes depending on the choice of criterion: line sweep, fixed random sweep, new random sweep, and uniform choice. All four proceed using the newly computed individual (or the original if better) for the computations of its neighbors.
The overlap of the neighborhoods provides an implicit mechanism of solution migrationto the cEA. Since the best solutions spread smoothly through thewhole population, genetic diversity in the population is preserved longer thanin non structured EAs. This soft dispersion of the best solutions through thepopulation is one of the main issues of the good tradeoff betweenexplorationandexploitation that cEAs perform during the search. This tradeoff can be tuned (and by extension the genetic diversity level alongthe evolution) by modifying (for instance) the size of the neighborhood used, asthe overlap degree between the neighborhoods grows according to the size ofthe neighborhood.
A cEA can be seen as acellular automaton (CA) with probabilisticrewritable rules, where the alphabet of the CA is equivalent to the potentialnumber of solutions of the problem. Hence, knowledge from research in CAs can be applied to cEAs.
Cellular EAs are very amenable to parallelism, thus usually found in the literature ofparallel 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 onFPGAs orGPUs.
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.
Seehere for a complete description on the fundamentals for the understanding, design, and application of cEAs.