Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

2.4 SETUP FOR EXPERIMENTAL INVESTIGATION

In the following sections we present the results of an experimental investigation into the effects of the main parameters of the island and neighborhood models on the optimization process. The experiments have been executed on a fine-grained parallel MasPar MP1 machine having 16k processors arranged as a 2-dimensional 128 × 128 torus with additional diagonal interconnections, i.e., every processor has 8 direct neighbors. This interconnection structure is also called X-net.

The torus is used to implement the different parallel variants of evolutionary algorithms described in Section 2.2. Since we have one individual per processor, the population consists of 16k individuals. To simulate the island model, this population is divided into different numbers of subpopulations (in particular, 1, 4, 16, 64, 256, 1024) by appropriately dividing the grid into subarrays.

Therefore, we can easily measure the effect of the number of islands, while the total population size remains constant.

In Fig. 2.6 four islands are sketched, each with 4096 individuals. The division into subarrays naturally defines a neighborhood between islands, i.e., every island has four direct neighbors (diagonal interconnections are not considered for migration). The migration strategy varies between sending in one, two, three, or all four directions and between sending every 5, 10, 15, or 30 generations. The migration rate is adjusted to the size of the islands by activating ...