Varying the Population Density

This model, presented in [LK02], is inspired in percolation theory and employs a "seeding" mechanism, which provides a means of systematically increasing the population size until the carrying capacity of the lattice is reached.

Figure 1. Demes formed by “connected nearest neighbors”. a) two small demes have formed; b) a percolating cluster has formed spanning from one boundary of the lattice to another.

Initially, a relatively small number of individuals (solutions) occupy small isolated patches (demes). These individuals are added to the lattice based on a specified probability and time interval. So at the beginning a large number of small demes are formed. As the run progresses, the demes slowly merge; additional randomly generated individuals are added to the lattice. This process allows a natural formation of demes, eliminating the need for pre-specifying the size and number of demes. The selection pressure can be also adjusted via the seeding method and migration schemes.

Figure 2. a) before migration; b) after migration.

As the density increases, the small isolated demes gradually merge to form larger connected demes.

The model proposed by the authors in [LK02] is a hybrid parallel GA combining the features of both coarse-grained and a fine-grained algorithms [Cant97] [SJ96].

Kirley has recently used this concept for developing his Cellular Genetic Algorithm with Disturbances (CGAD) [Kirl02]:

The Cellular Genetic Algorithm with Disturbances (CGAD)

Kirley proposes in [Kirl02] a cGA in which some "disasters" may occur into the population. The main idea consists in applying disasters of random magnitude to randomly selected points of the population. These disasters consist in killing all the individuals located in a region of the lattice, so their positions become empty, and will be filled with copies of the neighbors individuals along the evolution. This way, changes in landscape connectivity are exploited, to make populations and gene pools highly adaptive. In [Kirl02], the dynamical consequences of local spatial interactions and the emergence of spatio-temporal patterns, generated by simulated disturbance events were examined.

In Figure 3 it can be seen how the CGAD slightly outperforms a regular cGA when solving the Rastrigin function. The parameters used in the CGAD for the disaster size and its frequency are 15 and 0.5, respectively.

Figure 3. Comparison of the performance of CGAD versus a standard (without desasters) cGA.

Kirley solves in this paper with his CGAD static, dynamic and multi-objective problems, achieving good results in all of them.