PARALLEL GENETIC ALGORITHMS BASED ON A MULTIPROCESSOR SYSTEM FIN AND ITS APPLICATION

Genetic Algorithm (GA) is the method of approaching optimization probl em by modeling and simulating the biological evolution. As the genetic algorithm is rather time consuming, the use of a parallel genetic alg orithm can be advantage. This paper describes new methods for fine-gra ined 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 T raveling Salesman Problem (TSP), which is an NP-hard problem in the fi eld of combinatorial optimization, is compared to that of the simple g enetic algorithm and the traditional fine-grained parallel genetic alg orithm. The results indicate that the proposed methods yield improveme nt to find better solutions of the TSP.