Cellular evolutionary algorithm
A Cellular Evolutionary Algorithm (cEA) is a kind of evolutionary algorithm (EA) in which individuals cannot mate arbitrarly, 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. Particulary, 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.
 | This section may have been copied and pasted from another location, possibly in violation of Wikipedia's copyright policy. |
Introduction to Cellular Evolutionary Algorithms
In a Cellular Evolutionary Algorithm (cEA), the population is usually structured in a bidimensional grid of individuals, although other topologies are also possible. In it, the boundary individuals of the grid are connected to the individuals located in the opposite borders in the same row/column, depending on the case. The resulting effect is a toroidal grid, so that all the individuals have exactly the same number of neighbors.
As we said before, the grid used is usually bidimensional, although the number of dimensions can be easily extended (or reduced) to three or more. The neighborhood of a particular point of the grid (where an individual is placed) is defined in terms of the Manhattan distance between the considered point of the grid and the others in the population. Each point of the grid has a neighborhood that overlaps the neighborhoods of nearby individuals; all the neighborhoods have the same size and identical shape inthe basic algorithm. The two most commonly used neighborhoods are: (i) L5 , also called Von Neumann or NEWS neighborhood (after North, East, West y South); and (ii) 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.
We must notice that according to the update policy of the population used, we can distinguish between synchronous and asynchronous cEAs. This is also a well-known issue in cellular automata.
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 set of chromosomes in the search space, that is, to the potential number of solutions to the problem. Hence, if we see cEAs as a kind of CA, it is possible to import analytic tools and existing models and proposals from the field of CAs to cEAs in order to better understand these structured EAs and to improve their performance, and in fact this is an interesting open research line.
See here for a complete description on the fundamentals for the understanding, design, and application of cEAs.
References
External links
Enrique.alba1 (talk) 14:27, 15 October 2011 (UTC)