Synchronous and Asynchronous cEA

We can make a classification in sequential cEAs depending on if the whole population is actualized by the new one at the same time or not. The cEA of the first case are called synchronous, while those belonging to the later case are asynchronous.

In generational or synchronous cEA, the whole old population is replaced simultaneously by the offspring population at the end of each generation. We can achieve this by computing the full new generation incrementally onto a temporary population, and then replace the full old population with the new one. In Figure 1 we can see how does synchronous cEA work:

Figure 1. Synchronous cEA |

In the case of asynchronous algorithms, the individuals of the population are replaced by theirs offspring sequentially during the generation. So in this asynchronous cEAs we do not have to wait all the individuals to reproduce for replacing the old individuals of the population with the new ones. This way, one individual can match with the offspring of his neighbors to reproduce (see Figure 2).

Figure 2. Asynchronous cEA |

There are many ways for sequentially updating the cells of a cEA with a population on a 2D grid [SR99]. Here we will consider the following [AGTR02]:

- Uniform choice (UC): This
is the most general way for sequentially updating the cells. It lies in an
independent random ordering of updates in time, which consists in randomly
choosing the cell to be updated next, with replacement. This corresponds to
a binomial distribution for the update probability. The limiting case of such
distribution for large
*n*is the Poisson distribution (where n is the number of cells, or individuals, in the grid). - Fixed line sweep (LS): This is the simplest method. On it, grid cells are updated sequentially , line by line of the 2D grid.
- Fixed random sweep (FRS): In the FRS update, the next cell to be updated is chosen with uniform probability without replacement; this will produce a certain update sequence , where means that cell number p is updated at time q and is a permutation of the n cells. The same permutation is then used for the following update cycles.
- New random sweep (NRS): The NRS method works like FRS, except that a random new cell permutation is chosen anew for each sweep through the array.

A time step must be defined
to be the action of updating n times, which corresponds

to updating all the n
cells in the grid for LS, FRS and NRS, and possibly

less than n different cells in the uniform choice
method, since some cells might

be updated more than once. It should be noted that, with the exception of

fixed line sweep, the other asynchronous updating policies are non-deterministic,

representing an additional source of non-determinism besides that of the genetic

operators. An asynchronous parallel implementation could be easily derived for

these algorithms.

Synchronous vs. asynchronous

In Figure 1 we display the mean number of evaluations needed for all the algorithms described above to solve three different problems: a multimodal and deceptive (MMDP), a highly epistatic (P-PEAKS), and an irregular with continuous optimization (FMS) one [AGTR02].

Figure 3. A sample run of each update
method for the MMDP, P-PEAKS, and for the FMS problem. |

In Figure 4 we display a graph of the evolution of the diversity (Entropy) for MMTP and P-PEAKS problems [AGTR02].

Figure 4. A sample curve of the entropy
of each update method for the MMDP (a) and for the P-PEAKS problem (b). |

Alba et al. concluded in [AGTR02] that, for any size of the search grid, the synchronous update policy is the best in terms of percentage of hits, because it always provides an equal or larger success rate with respect to any of the asynchronous policies.

However, considering the number of evaluations needed to locate the optimum (efficiency) the opposite conclusion is obtained: asynchronous methods are faster (sometimes much faster) than the synchronous one. A simple asynchronous policy such that Line Sweep (LS) provides the faster convergence for two of the problems (MMDP and P-PEAKS), while it shows a high and desirable success rate (similar to that of the synchronous update). In the hard FMS problem, Fixed Random Sweep got a considerably faster solution, and can be pointed out as a good approach.

Globally stated, fast convergence means local optima in evolutionary algorithms, but cellular EA’s in general, and the Line Sweep policy in particular, offers a good tradeoff solution to this problem without bothering researchers with a large number of parameters to be tuned (maybe only the ratio between the size of the grid and the neighborhood being used [AT00]).