Typical Variation Operators in cEA

The first step in a cEA generation is fitness assignment, which is done simultaneously for all individuals. This fitness assignment process consists on selecting a value to each individual according to its proximity to the problem solution.

After this first step the three next genetic operators take place locally within a small neighborhood:


Selection is a process in which individuals are selected to reproduce, generating offsprings for the next generation. Usually, the best individuals (those having higher fitness values) will have a greater probability for being selectd. In nature, an individual undergo two different selection pressures before producing its offspring, i.e., survival to adult state and find of its mates. Selection of EAs models these processes. Some "luck" (random effect) is usually involved too. The selection process is the step that guides the evolutionary algorithm towards ever-better solutions.

We will expose some different selection schemes. We focus on cEAs with a single topology, the frequently used two dimensional torus. A typical example would be a N x N grid in which a single individual exists at each grid point and interacts with its neighbors on nearby grid points.

Since we are studying just the case of cellular EAs, all the presented selection methods are variants of local selection [Wrigh69] wherein every individual resides inside a constrained environment called the local neighborhood. Individuals interact only with individuals inside this region. The neighborhood can be seen as the group of potential mating partners. The selection methods used in cEAs are typically the same that those used in panmictic EAs. The main selection methods used in the literature are:


Reproduction is the mechanism that allows us to obtain offsprings from one (asexual) or more (sexual) parents. Among reproduction operators the following stand out:


Replacement schemes are used by evolutionary algorithms to determine how the new individuals will be assimilated into the population. Replace worst and replace most-similar are the only really useful replacement schemes. Sometimes replace-parent can be effective, but usually when the parents are similar to the offspring, and this is just replace-most-similar. Some examples of replacement policies are given below:

Depending on when the replacement policy is applied we can stand out two different kinds of cEA:

back to home