An efficient Bee Colony Optimization algorithm for Traveling Salesman Problem using frequency-based pruning

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.

I. Introduction

Bees are highly organized social insects. The survival of the entire colony depends on every individual bee. Bees use a systematic task segregation among them to ensure a continued existence of its colony. They perform various tasks such as foraging, reproduction, taking care of young, patrolling, housekeeping and constructing hive. Of these, foraging is a major activity as bees have to ensure an undisrupted supply of food source to the colony.