-
Simon KentDimitris C. Dracopoulos
-
Simon Kent
Despite its advantages, one drawback of Genetic Programming is the considerable execution time which can be required to produce a solution. The nature of the Genetic Programming process lends itself to the possibility of parallelisation. Koza[2] has carried out some work on parallel GP using transputers, however there has generally been relatively little work in this area (unlike genetic algorithms for which several parallel implementations exist).
This paper investigates two implementations of parallel Genetic Programming, using the Bulk Synchronous Parallel (BSP) model of parallel computation. The first uses a global approach where the GP process is explicitly parallelised by dividing the task amongst a number of processors. The second approach adopts a coarse grained approach in which the ratio between communication and computation is reduced. The aim is to speedup the GP process, and to evaluate BSP as to its suitability as a model for use in producing parallel GP implementations.
It is shown that considerable speedup of the GP execution can be achieved and that the BSP model is very suitable for parallelisation of similar algorithms. Using the implemented BSP GP system, higher speedups can be achieved in large problems. In addition, the time required to parallelise evolutionary algorithms with the BSP model is insignificant, compared with the achieved speedups, when the problem is a complex and time consuming. The BSP Oxford library proved to be very suitable and efficient for the parallelisation of the GP process, so as to suggest its use for evolutionary algorithms.