Selection Intensity in Synchronous and Asynchronous Cellular Evolutionary Algorithms for Regular Lattices

In this article we present quantitative models for the selection pressure of cellular evolutionary algorithms on regular one- and two-dimensional lattices. We derive models based on probabilistic difference equations for synchronous and several asynchronous cell update policies. The models are validated using two customary selection methods: binary tournament and linear ranking. Theoretical results are in agreement with experimental values, showing that the selection intensity can be controlled by using different update methods. It is also seen that the usual logistic approximation breaks down for low-dimensional lattices and should be replaced by a polynomial approximation. The dependence of the models on the neighborhood radius is studied for both topologies. We also derive results for two-dimensional lattices with variable grid axes ratio.