Implementation of a Parallel Gneetic Algorithm on a Cluster of Workstations: The Travellin Salesman Problem, a Case Study

摘要

A parallel version of a Genetic Algorithm is presented and implemented on a cluster of workstations. Even though our alogrithm is general enough to be applied to a wide variety of porblems. We used it to obtain optimal/suboptimal solutions ot the well known Traveling Salesman Problem. The proposed algorithm is implemented suing the Parallel Virtual machie library over a network of workstations, and it is based on a master-salve paradigm and a distributed-memory approach. Tests were performed with clusters of 1,2,4,8, and 16 workstations, using several real problems and population sizes. Results are presented to show how the performance of the alogrithm is affected by variations on the number of slaves, population size, mutation rate, and mutation interval. The results presented show the utility, efficiency and potential value of the propsed algorithm to tackle ismilar NP-Complete problems.