A SIMPLE PARALLELIZING SCHEME OF GENETIC ALGORITHM ON DISTRIBUTED-MEMORY MULTIPROCESSORS
Jongho Nang · International Journal of High Speed Computing · 1994
This paper proposes a simple and efficient parallelizing scheme of the genetic algorithm on distributed-memory multiprocessor that maintains the execution behaviours of sequential genetic algorithm. In this parallelizing scheme, the global population is evenly partitioned into several subpopulations, each of which is assigned to the processor to be evolved in parallel. An interprocessor communication pattern, called AAB (All-To-All Broadcasting), is used at each generation in order to exchange the informations on all individuals evolved in all other processors. It allows the processor to reproduce the individuals in a global sense, in other words, the sequential execution behaviours can be maintained in the parallelized genetic algorithm. This paper shows that the genetic algorithms employing widely used selection schemes such as proportionate selection, ranking selection and tournament selection can be efficiently parallelized on distributed-memory multiprocessor using the proposed parallelizing scheme. Some experimental speedups on AP1000 are also presented to show the usefulness of the proposed parallelizing scheme.