Article: Favourable subpopulation migration strategy for travelling salesman problem Journal: International Journal of Business Intelligence and Data Mining (IJBIDM) 2022 Vol.20 No.3 pp.299 - 326 Abstract: Most of the existing migration strategies are complex in nature which results in high computation time. Since the introduction of parallel genetic algorithms, they are known for obtaining better optimal solutions at the cost of more computation. Migration has played a significant role in maintaining genetic diversity of the population. This paper aims to propose a new migration strategy that improves the performance of the parallel genetic algorithm in solving NP hard problems. In order to assess its behaviour, various travelling salesman problem datasets are considered since it is a perfect example of an NP hard problem. The algorithm is based on an island model approach where one subpopulation is nurtured by the other subpopulations by taking turns during the migration process to progressively reach the optimal solution. In turn, the nurtured subpopulation provides a feedback loop to the subpopulation with poor fitness value based on certain criteria to be met. An extensive study was conducted to understand the optimal parameters values in which the proposed algorithm works best. Inderscience Publishers - linking academia, business and industry through research

Title: Favourable subpopulation migration strategy for travelling salesman problem

Authors: Abhishek Chandar; Akshay Srinivasan; G. Paavai Anand

Addresses: Department of Computer Science and Engineering, SRM Institute of Computer Science and Technology, Chennai, Tamil Nadu, 600026, India ' Department of Computer Science and Engineering, SRM Institute of Computer Science and Technology, Chennai, Tamil Nadu, 600026, India ' Department of Computer Science and Engineering, SRM Institute of Computer Science and Technology, Chennai, Tamil Nadu, 600026, India

Abstract: Most of the existing migration strategies are complex in nature which results in high computation time. Since the introduction of parallel genetic algorithms, they are known for obtaining better optimal solutions at the cost of more computation. Migration has played a significant role in maintaining genetic diversity of the population. This paper aims to propose a new migration strategy that improves the performance of the parallel genetic algorithm in solving NP hard problems. In order to assess its behaviour, various travelling salesman problem datasets are considered since it is a perfect example of an NP hard problem. The algorithm is based on an island model approach where one subpopulation is nurtured by the other subpopulations by taking turns during the migration process to progressively reach the optimal solution. In turn, the nurtured subpopulation provides a feedback loop to the subpopulation with poor fitness value based on certain criteria to be met. An extensive study was conducted to understand the optimal parameters values in which the proposed algorithm works best.

Keywords: parallel genetic algorithm; PGA; migration strategy; travelling salesman problem; TSP; convergence rate; parallelisation; favourable subpopulation; FASP; migration.

DOI: 10.1504/IJBIDM.2022.122155

International Journal of Business Intelligence and Data Mining, 2022 Vol.20 No.3, pp.299 - 326

Received: 13 Jul 2020
Accepted: 01 Oct 2020
Published online: 11 Apr 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Favourable subpopulation migration strategy for travelling salesman problem

Keep up-to-date