Page 107 - 49A Field Guide to Genetic Programming

10.5 Geographically Distributed GP 93

(Koza, Bennett, Hutchings, Bade, Keane, and Andre, 1997; Seok, Lee, and
Zhang, 2000) to the definition of specialised operators (Martin and Poli,
2002). It is even possible to implement a complete GP on FPGAs, as sug-
gested in (Heywood and Zincir-Heywood, 2000; Martin, 2001, 2002; Sidhu,
Mei, and Prasanna, 1998). A massively parallel GP implementation has also
been proposed by Eklund (2001, 2004) although to date all tests with that
architecture have only been performed in simulation.

10.4.4 Sub-machine-code GP

We are nowadays so used to writing programs using high level sequential
languages that it is very easy to forget that, underneath, computers have a
high degree of parallelism. Internally, CPUs are made up of bit-slices which
make it possible for the CPU to process all of the bits of the operands of an
instruction in one go, in a single clock tick.
Sub-machine-code GP (SMCGP) (Poli and Langdon, 1999) is a technique
to speed up GP and to extend its scope by exploiting the internal parallelism
of sequential CPUs. In Boolean classification problems, SMCGP allows the
parallel evaluation of 32 or 64 (depending on the CPU’s word size) fitness
cases per program execution, thereby providing a significant speed-up. This
has made it possible to solve parity problems with up to 4 million fitness
cases (Poli and Page, 2000). SMCGP has also been applied with success
in binary image classification problems (Adorni, Cagnoni, and Mordonini,
2002; Quintana, Poli, and Claridge, 2003). The technique has also been
extended to process multiple fitness cases per program execution in continu-
ous symbolic regression problems where inputs and outputs are real-valued
numbers (Poli, 1999b).

10.5 Geographically Distributed GP

Unless some type of synchronisation is imposed, the parallel forms of GP
in which different parts of a population are evolved by different processing
elements will not be running the same algorithm as the standard single-
CPU version of GP. Therefore, almost certainly, different parallelisations
will produce different answers. However, as we discussed in Section 10.3,
this is not necessarily a bad thing.
Parallelisation itself can bring benefits similar to those hypothesised in
natural populations by Wright (1932). In particular, the population is of-
ten divided into semi-independent sub-populations called demes (Collins,
1992; D’haeseleer and Bluming, 1994; Langdon, 1998; Popovici and De Jong,
2006). The flow of genetic material between demes is restricted by limiting
the exchange of individuals between them. The limit can be on the number
of individuals that are allowed to migrate per generation. Alternatively the