Parallel Nest-Site Selection Algorithm for Traveling Salesman Problems

摘要

The Nest-Site Selection (NeSS) algorithm is a combinatorial optimization algorithm inspired by the nest-site selection behavior of honeybee swarms. NeSS uses a number of devoted bees committed to a nest-site, called quorum mechanism, as a stopping criterion of the algorithm instead of the maximum cycle number (MCN). It is generally reached before the MCN that is used in typical swarm intelligence algorithms. Therefore, this mechanism helps the algorithm to converge more quickly. However, there are a number of time-sensitive optimization applications that need solutions within a specific time frame. This paper thus proposes a parallel framework of the NeSS algorithm to improve the performance and efficiency of the algorithm. In the original NeSS algorithm, explorer bees, committed bees, observers, and resting bees are four types of bees that work as a separate and independent entity. The task of each bee in the original NeSS algorithm is sequential executed. In this work, the bees in the same group perform their task simultaneously. A parallel NeSS program is developed using the C language and the OpenMP library. We use the Traveling Salesman Problems (TSP), which is a classic combinatorial problem, to evaluate the scalability performance of the proposed parallel framework by varying number of processors and number of cities in the TSP.