Open AccessISLAND MIGRATION MODEL WITH PARALLEL MUTATION STRATEGIES FOR COMPUTING THE TRAVELING SALESMAN PROBLEM ON MULTICOMPUTER PLATFORM
Author(s) -
Plаmеnkа Borovskа,
Subhi A. Bahudaila,
Milena Lazarova
Publication year - 2014
Publication title -
computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.184
H-Index - 11
eISSN - 2312-5381
pISSN - 1727-6209
DOI - 10.47839/ijc.6.1.431
Subject(s) - travelling salesman problem , computer science , scalability , parallel computing , variable (mathematics) , computation , mutation , genetic algorithm , parallel algorithm , mathematical optimization , algorithm , mathematics , machine learning , gene , mathematical analysis , biochemistry , chemistry , database
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.