Parallelizing cGAs - MIMD Machines

Initially cEAs were designed to run in massively parallel computers. Nowadays this kind of EAs is still studied in the literature due to theirs special characteristics but, since these massively parallel computers are disappearing at present, the majority of the research in these algorithms is focused on the sequential case, because when we try to make parallel implementations of cEAs we find two important difficulties, which are characteristics of cEAs:

We can see in Figure 1 how cEAs have a very large number of sub-algorithms, with small pop size each and a high coupling degree. In contrast, we can see an easily parallelizable EA -dEA- with smaller number of sub-algorithms running on bigger populations and with medium coupling degree.

Figure 1. The structured-population genetic algorithm cube

However we can find in the literature many studies trying to parallelize cEAs. The motivation for these works are the possibility of facing problems which are limited in CPU, getting better solutions in less time, making profitable the available hardware resources, etc. A handicap may be the complexity of parallelizing the cEA because they have a very high connectivity among individuals.

Following we will expose six different strategies for parallelizing fine-grained EAs. The first two approximations are parallel fine-grained panmictic EAs (not decentralized), while the other four correspond to parallel cEAs:

Figure 3. Baluja's architecture of subpopulations, arrangement #1. Subpopulation 5 and 10 are shown enlarged. They randomly select 1 chromosome from the 2 chromosomes in each of their 8 closest neighbors, 4 from the left neighbors, and 4 from the right. They also incorporate their own two chromosomes into the population. From this population two chromosomes are probabilistically chosen for breeding. The 8 chromosomes not selected are discarded.


Figure 4. Baluja's architecture of subpopulations, arrangement #2. A two dimensional array of processors is assumed. Each processor contributes one of its two chromosomes to each of its 8 nearest neighbors. A sample population for processor (x,y) is shown. The processors are connected in a toroid.


back to home