Parallel Genetic Algorithms Based on a Multiprocessor System FIN and Its Application

Myung-Mook HAN  Shoji TATSUMI  Yasuhiko KITAMURA  Takaaki OKUMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.11   pp.1595-1605
Publication Date: 1995/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
parallel processing,  genetic algorithm,  multiprocessor,  traveling salesman problem,  

Full Text: PDF>>
Buy this Article

Genetic Algorithm (GA) is the method of approaching optimization problem by modeling and simulating the biological evolution. As the genetic algorithm is rather time consuming, the use of a parallel genetic algorithm can be advantage. This paper describes new methods for fine-grained parallel genetic algorithm using a multiprocessor system FIN. FIN has a VLSI-oriented interconnection network, and is constructed from a viewpoint of fractal geometry so that self-similarity is considered in its configuration. The performance of the proposed methods on the Traveling Salesman Problem (TSP), which is an NP-hard problem in the field of combinatorial optimization, is compared to that of the simple genetic algorithm and the traditional fine-grained parallel genetic algorithm. The results indicate that the proposed methods yield improvement to find better solutions of the TSP.