
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Parallel Genetic Algorithms Based on a Multiprocessor System FIN and Its Application
MyungMook HAN Shoji TATSUMI Yasuhiko KITAMURA Takaaki OKUMOTO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E78A
No.11
pp.15951605 Publication Date: 1995/11/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: parallel processing, genetic algorithm, multiprocessor, traveling salesman problem,
Full Text: PDF>>
Summary:
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 finegrained parallel genetic algorithm using a multiprocessor system FIN. FIN has a VLSIoriented interconnection network, and is constructed from a viewpoint of fractal geometry so that selfsimilarity is considered in its configuration. The performance of the proposed methods on the Traveling Salesman Problem (TSP), which is an NPhard problem in the field of combinatorial optimization, is compared to that of the simple genetic algorithm and the traditional finegrained parallel genetic algorithm. The results indicate that the proposed methods yield improvement to find better solutions of the TSP.

