An efficient Bee Colony Optimization algorithm for Traveling Salesman Problem using frequency-based pruning
Li‐Pei Wong, Malcolm Yoke Hean Low, Chin Soon Chong · 2009
In a bee colony, bees perform waggle dance in order to communicate the information of food source to their hive mates. This foraging behaviour has been adapted in a bee colony optimization (BCO) algorithm together with 2-opt local search to solve the traveling salesman problem (TSP). To reduce the high overhead incurred by 2-opt in the BCO algorithm proposed previously, two mechanisms named frequency-based pruning strategy (FBPS) and fixed-radius near neighbour (FRNN) 2-opt are presented. FBPS suggests that only a subset of promising solutions are allowed to perform 2-opt based on the accumulated frequency of its building blocks recorded in a matrix. FRNN 2-opt is an efficient implementation of 2-opt which exploits the geometric structure in a permutation of TSP sequence. Both mechanisms are tested on a set of TSP benchmark problems and the results show that they are able to achieve a 58.42% improvement while maintaining the solution quality at 0.02% from known optimal.