Page 108 - 49A Field Guide to Genetic Programming

94 10 Fast and Distributed Genetic Programming

(a) (b)

Figure 10.2: Spatially structured GP populations. (a) Toroidal grid of
demes, where each deme (a node) contains a sub-population, and demes
periodically exchange a small group of high-fitness individuals using a grid
of communication channels. (b) Fine-grained distributed GP, where each
grid cell contains one individual and where the selection of a mating partner
for the individual in the centre cell is performed by executing a tournament
among randomly selected individuals (e.g., the individuals shaded) in its
3 × 3 neighbourhood.

demes may be considered to be arranged in a “geographical” topology that
constrains which demes can trade individuals. For example, it may be that
with limited migration between compute nodes, the evolved populations on
adjacent nodes will diverge, and that this increased diversity may lead to
better solutions. Fernandez, Tomassini, and Vanneschi (2003), for exam-
ple, report that distributing individuals between subpopulations offers an
advantage in terms of quality of solutions and computational effort.
When Koza first started using GP on a network of Transputers (Andre
and Koza, 1996), Andre experimentally determined the best migration rate
for their problem. He suggested Transputers arranged in an asynchronous
2-D toroidal square grid (such as the one in Figure 10.2a) should exchange
2% of their population with their four neighbours.
Densely connected grids have been widely adopted in parallel GP. Usu-
ally they allow innovative partial solutions to spread quickly. However, the
GA community reported better results from less connected topologies, such
as arranging the compute nodes’ populations in a ring, so that they could
transfer genes only between themselves and their two neighbours (Stender,
1993). Potter (1997) argues in favour of spatial separation in populations
and fine-grained distributed forms of GP (see Figure 10.2b). Whitley (2001)
gives some guidance on parallel genetic algorithms.