Solving travelling salesman problem using iterative discrete flower pollination algorithms: a parallel processing perspective

Abstract

There has been a growing rate of new nature inspired meta-heuristic algorithms that have been developed for sub-optimally solving NP-Hard Problems. This has led to the development of the Flower Pollination Algorithm (FPA) by Yang in 2012, which has been able to outperform various common meta-heuristics. Due to its relative age it is still underdeveloped as compared to common meta-heuristics such as, the Genetic Algorithm (GA), Simulated Annealing (SA), and the Ant Colony Optimisation (ACO). This research investigates various parallel methods in order to design, implement and test a parallel iterative Discrete Flower Pollination Algorithm (PiDFPA) that can further optimise the FPA, and to investigate the performance of the PiDFPA on large maps in comparison to common parallelised meta-heuristic algorithms in the context of the Symmetrical Travelling Salesman Problem (TSP). Results within this research show that the PiDFPA is able to achieve the optimal tour length for small maps and is also able to overcome the weakness of the iDFPA when applied to large maps, where the PiDFPA is able to outperform its benchmark counterparts, the Parallel Ant Colony Optimisation (PACO) and the Parallel Genetic Algorithm (PGA), in terms of convergence rate and accuracy. An analysis is also done on the complexity as well as efficiency of the iDFPA and the suggested PiDFPA showing that the PiDFPA is able to exponentially increase the speedup of the iDFPA for TSPs as the map size increases. This is largely due to the adjustment of control variables that allow the PiDFPA to dynamically adjust its exploitation and exploration probability between each iteration along with minimizing communication overhead between agents by making use of the Nvidia CUDA grid architecture