www.gp-field-guide.org.uk
Contents Top Previous Next

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 ? 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. ? 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 diversification 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 (Darwin1859).

In nature, changes in conditions across regions can lead to corresponding 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 unwilling 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 exception is in Europe, where the "ends" of the range meet. There the Herring Gull (Larus argentatus) and the Lesser Black-backed Gull (Larus fuscus) 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 geographically distributed GP populations. Although parallel hardware naturally lends itself to the implementation of physically-distributed populations, one can obtain similar benefits by using logically-distributed populations in a single machine.


www.gp-field-guide.org.uk
Contents Top Previous Next