Page 102 - 49A Field Guide to Genetic Programming

88 10 Fast and Distributed Genetic Programming

10.3 Parallel and Distributed GP are Not

Equivalent

There are two important aspects of parallel evolutionary algorithms which
are equally important but are often confused. The first is the traditional
aspect of parallel computing. That is, we port an existing algorithm onto
a supercomputer so that it runs faster. The second aspect comes from the
biological inspiration for evolutionary computation.
In nature everything happens in parallel. Individuals succeed or fail in
producing and raising children at the same time as other members of their
species. These individuals are spread across oceans, lakes, rivers, plains,
forests, mountain chains, etc. It was this geographic spread that led Wright
(1932) to propose that geography and changes to it are of great importance
to the formation of new species and, so, to natural evolution as a whole.
Suppose a species occupies a range of hills. Individuals need not be able
to move from one end of the range to another in their lifetime, but their
descendents might. Wright (1932) proposed a mathematical model that can
predict the amount of mixing between descendents across the entire range
is needed to keep the whole population together as a single species. Based
on his model, he predicted that only a few migrants per generation between
hill tops are sufficient.
Now suppose the sea level rises. What was once a continuous range
of hills becomes a chain of islands. Suppose members of this species have
limited ability to swim. If the islands are close and the ocean currents are
sometimes favourable, it may be that every year a few individuals cross
between neighbouring islands. This may be enough to constrain diversifi-
cation and allow the population to remain a single species. However, if the
gaps between island become larger, the chance of an individual occasionally
crossing the sea and breeding becomes remote. On each island, then, the
sub-populations begin to diverge and over time new species, specific to each
island, are formed (Darwin, 1859).
In nature, changes in conditions across regions can lead to correspond-
ing differences in spatially distributed populations. Sometimes this can lead
to new species, as in the example above. In other cases the variation can
be gradual enough that there is no clear delineation that could be called a
species boundary, but geographically distant individuals are unable or un-
willing to mate, fulfilling a key property of different species. A particularly
dramatic example of this is a ring species. The Larus gulls, for example, live
along a ring that roughly follows the Arctic Circle. With one exception the
variants can interbreed all along its range, despite often having differences
significant enough that they have received different names. The key excep-
tion is in Europe, where the “ends” of the range meet. There the Herring
Gull (Larus argentatus) and the Lesser Black-backed Gull (Larus fuscus)