A Parallel and Distributed Genetic Algorithm on Loosely-Coupled Multiprocessor Systems
Takashi Matsumura, Morikazu Nakamura, Juma Okech, Kenji Onaga · 1998
In this paper we consider a parallel and distributed computation of genetic algorithms on loosely-coupled multiprocessor systems. Genetic Algorithms are stochastic algorithms whose search methods model some natural phenomena. Genetic algorithms are relatively easy for finding the optimum solution or an approximately optimum value of NP-complete problems. Parallelizing of Genetic Algorithms has two ideas, one is to obtain a better solution avoiding local optimums according to distributing subpopulations, the other is high speed execution. Loosely-coupled multiprocessor systems are more suitable for massively parallel processing and also more easily VLSI implementation than tightly-coupled ones. However, communication overhead on parallel processing is more serious for loosely-coupled ones. We propose in this paper a parallel and distributed execution method of genetic algorithm on loosely-coupled multiprocessor systems of fixed network topologies in which each processor element carries out genetic operations on its own chromosome set and communicates with only the neighbors in order to save communication overhead. We evaluate the proposed method on the multiprocessor systems with ring, torus, and hypercube topologies for benchmark problem instances. From the results, we find that the ring topology is more suitable for the proposed parallel and distributed execution since more variety of chromosomes in the ring is kept than that in the others. Moreover, we also propose a new network topology called cone which is a hierarchical connection of ring topologies. We show its effectiveness by experimental evaluation. Contents 1