A bee colony optimisation algorithm with a sequential-pattern-mining-based pruning strategy for the travelling salesman problem. (15th July 2020)

• Record Type: Journal Article
• Authors: Choong, Shin Siang; Wong, Li-Pei; Low, Malcolm Yoke Hean; Chong, Chin Soon
• Is Part Of: International journal of bio-inspired computation. Volume 15:Number 4(2020)
• Page Start: 239
• Page End: 253
• Publication Date: 2020-07-15
• Subjects: meta-heuristic -- data mining -- sequential pattern mining -- FBPS -- frequency-based pruning strategy -- frequent-close-pattern-based pruning strategy -- combinatorial optimisation; Biologically-inspired computing -- Periodicals; Computational biology -- Periodicals; 572.0285
• Languages: English
• ISSNs: 1758-0366

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.