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.

This model is a hybrid parallel GA combining the features of both coarse-grained and a fine-grained algorithms [Cant97] [Kirl02] [SJ96].