Favourable subpopulation migration strategy for travelling salesman problem. (31st March 2022)

• Record Type: Journal Article
• Authors: Chandar, Abhishek; Srinivasan, Akshay; Anand, G. Paavai
• Is Part Of: International journal of business intelligence and data mining. Volume 20:Number 3(2022)
• Page Start: 299
• Page End: 326
• Publication Date: 2022-03-31
• Subjects: parallel genetic algorithm -- PGA -- migration strategy -- travelling salesman problem -- TSP -- convergence rate -- parallelisation -- favourable subpopulation -- FASP -- migration; 006.312
• Languages: English
• ISSNs: 1743-8187

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.