Page 103 - 49A Field Guide to Genetic Programming

10.4 Running GP on Parallel Hardware 89

intermingle, but rarely interbreed.
The topology of the landscape is often a strong determiner of the spatial
structure of a population. A large, fairly homogenous region, for example,
might give rise to a species being spatially differentiated in two dimensions
due to distance and climate. A river, on the other hand, may give rise to
a linear distribution, especially if there are structures like water falls that
restrict migration, and a river basin with several tributaries could lead to a
tree structure.
In evolutionary computation we can choose whether we want to model
some form of geography. We can run GP on parallel hardware so as to speed
up runs, but without introducing a notion of proximity that limits which
individuals are allowed to mate. Alternatively, we can model some form of
geography, introducing spatial structure as a result.
In the following two sections we will discuss both ideas. It is important
to note, however, that one does not need to use parallel hardware to use ge-
ographically distributed GP populations. Although parallel hardware natu-
rally lends itself to the implementation of physically-distributed populations,
one can obtain similar benefits by using logically-distributed populations in
a single machine.

10.4 Running GP on Parallel Hardware

In contrast to much of computer science, evolutionary computation can be
readily run on parallel computer hardware; indeed it is “embarrassingly par-
allel” (Andre and Koza, 1998). For example, when Openshaw and Turton
(1994) ran GP on a Cray supercomputer they obtained about 30% of its
theoretical peak performance, embarrassing their supercomputer savvy col-
leagues who rarely got better than a few percent out of it.
In Sections 10.4.1–10.4.3 we look at three ways of running GP on par-
allel hardware. Section 10.4.4 shows how to get 32 parallel operations from
standard hardware.

10.4.1 Master–slave GP

If the objective is purely to speed up runs, we may want our parallel GP to
work exactly the same as it did on a single computer. This is possible, but
to achieve it we have to be very careful to ensure that, even if some parts of
the population are evaluated more quickly, parallelisation does not change
how we apply selection and which GP individual crosses over with which.
Probably the easiest way to implement this is the master–slave model.
In the master–slave model (Oussaid`ene, Chopard, Pictet, and Tomassini,
1997) breeding, selection crossover, mutation etc. occur just as they would
on a single computer and only fitness evaluation is spread across a network