Title: A bee colony optimisation algorithm with a sequential-pattern-mining-based pruning strategy for the travelling salesman problem
Authors: Shin Siang Choong; Li-Pei Wong; Malcolm Yoke Hean Low; Chin Soon Chong
Addresses: School of Computer Sciences, Universiti Sains Malaysia, 11800 USM, Penang, Malaysia ' School of Computer Sciences, Universiti Sains Malaysia, 11800 USM, Penang, Malaysia ' Singapore Institute of Technology, 10 Dover Drive, 138683, Singapore ' Singapore Institute of Manufacturing Technology, A*Star, 2 Fusionopolis Way, 138634, Singapore
Abstract: The unique foraging behaviour of bees via waggle dance has been computationally realised as an algorithm named bee colony optimisation (BCO) to solve different types of combinatorial optimisation problems such as travelling salesman problem (TSP). In order to enhance the performance of BCO, local optimisation can be integrated. However, local optimisation incurs high processing overhead especially when all solutions are allowed to undergo the local optimisation. This paper proposes a pruning strategy based on the top-k sequential patterns (TKS) mining algorithm. Specifically, TKS is employed to identify the frequent building blocks along the optimisation process. A total of 19 TSP benchmark problem instances ranging from 318 cities to 1,291 cities were used as the test bed. The proposed pruning strategy shows a significant reduction in terms of the computational time to yield TSP solutions with similar tour length as compared with two state-of-the-art approaches.
Keywords: meta-heuristic; data mining; sequential pattern mining; FBPS; frequency-based pruning strategy; frequent-close-pattern-based pruning strategy; combinatorial optimisation.
International Journal of Bio-Inspired Computation, 2020 Vol.15 No.4, pp.239 - 253
Accepted: 13 Jan 2020
Published online: 20 Jul 2020 *