ISLAND MIGRATION MODEL WITH PARALLEL MUTATION STRATEGIES FOR COMPUTING THE TRAVELING SALESMAN PROBLEM ON MULTICOMPUTER PLATFORM
DOI:
https://doi.org/10.47839/ijc.6.1.431Keywords:
Euclidean TSP, parallel genetic algorithm, island model, chromosomes migration, mutation rate, multicomputer, parallel programming with MPI, parallel profiling, parallel performanceAbstract
This paper investigates the efficiency of a model of parallel genetic computation of the traveling salesman problem with circular periodic chromosomes migration. The parallel model is verified by MPI-based program implementation on a multicomputer platform. The correlation of the application and architectural spaces has been investigated by exploring the impact of the scalability of the application and the parallel machine size over the efficiency of the parallel system. Performance profiling, evaluation and analysis have been made for different numbers of cities and different sizes of the multicomputer platform. The paper also investigates the impact of the mutation strategy on the solution quality of coarse-grained parallel genetic algorithm with circular periodic migration for the traveling salesman problem. We propose an approach to improve the quality of solution by applying parallel variable mutation rates for the local evolutions in the concurrent processes. A series of experiments has been carried out with parallel fixed and variable mutation rates in order to estimate the efficiency of the suggested approach. The best quality solutions have been obtained for the strategy with parallel fixed mutation rates.References
Traveling Salesman Problem www.tsp.gatech.edu
R. Haupt, S. Haupt, Practical Genetic Algorithms, John Wiley & Sons, 2004.
Genetic algorithms for TSP http://www.tsp.umu.se/~top/travel.html
P. Borovska, “Solving the TSP in Parallel by Genetic Algorithm on Multicomputer Cluster”, International Conference on Computer Systems and Technologies (CompSysTech’06), June 2006, Veliko Turnovo, Bulgaria.
L. Wang, A. Maciejewski, H. Siegel, V. Roychowdhury, and B. Eldridge, “A study of five parallel approaches to a genetic algorithm for the traveling salesman problem”, Intelligent Automation and Soft Computing, Vol.11, No.4, 2005, pp. 217?234.
W. Rand, R. Riolo, “The Problem with a Self Adaptive Mutation Rate in Some Environments”, Proc. of the 2005 Conference on Genetic and evolutionary computation GECCO'05, 2005, pp.1493-1500.
Y. Maeda, Q. Li, “Parallel Genetic Algorithm with Adaptive Genetic Parameters Tuned by Fuzzy Reasoning”, International Journal of Innovative Computing, Information and Control, Vol.1, No.1, ICIC International, March 2005, pp. 95-107.
E. Cantu-Paz, “On the Effects of Migration on the Fitness Distribution of Parallel Evolutionary Algorithms”, Workshop on Parallel Processing and Evolutionary Computation, Las Vegas, July 8th, 2000.
E. Cantu-Paz, D. Goldberg, “On the scalability of Parallel Genetic Algorithms”, Evolutionary Computation, Vol.7, No.2, 1999, pp. 429-449.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
