A Bee Colony Optimization algorithm with Frequent-closed-pattern-based Pruning Strategy for Traveling Salesman Problem

Bees perform waggle dance in order to communicate the information of food source to their hive mates. This unique foraging behaviour has been computationally realized as an algorithmic tool named the Bee Colony Optimization (BCO) algorithm to solve different types of Combinatorial Optimization Problems such as Traveling Salesman Problem (TSP). In order to enhance the performance of the BCO algorithm, it is integrated with a local optimization approach and a pruning strategy named as the Frequency-based Pruning Strategy (FBPS), which allows a subset of bees to undergo the local optimization and hence reduces the high processing overhead of the local optimization. Although the local optimization and the FBPS enhance the performance of the BCO algorithm, the FBPS becomes not scalable when building blocks in various sizes are considered in its pruning operation. This paper proposes a pruning strategy which employs the bi-directional extension (BIDE) based frequent closed pattern mining algorithm. It is named as the Frequent-closed-pattern-based Pruning Strategy (FCPBPS). The FCPBPS consists of two major operations: solutions accumulation and pruning operation. Solutions generated by bees are accumulated throughout the BCO algorithm execution. Based on the accumulated solutions, a set of frequent closed patterns in various sizes is mined using the BIDE algorithm. This set of frequent closed patterns is used in the FCPBPS pruning operation such that only relatively better bees (i.e. bees that produce solution which contains many of these frequent closed patterns) are allowed to undergo the local optimization. A total of 18 selected symmetric TSP benchmark problems range from 318 cities to 1291 cities are used as the testbed of this research. On average, the experimental results show that the FCPBPS requires 20.2% lesser computational time compared to the FBPS, to yield similar best-so-far TSP tour lengths.