6533b839fe1ef96bd12a58be

RESEARCH PRODUCT

A hybrid metaheuristic for the cyclic antibandwidth problem

subject

description

We propose a hybrid artificial bee colony algorithm for the cyclic antibandwidth problem.We present a computational comparison of different parameter settings.We derive a fine-tuning hybrid artificial bee colony algorithm.The proposal is very competitive with the state-of-the-art algorithm for the cyclic antibandwidth problem. In this paper, we propose a hybrid metaheuristic algorithm to solve the cyclic antibandwidth problem. This hard optimization problem consists of embedding an n-vertex graph into the cycle Cn, such that the minimum distance (measured in the cycle) of adjacent vertices is maximized. It constitutes a natural extension of the well-known antibandwidth problem, and can be viewed as the dual problem of the cyclic bandwidth problem.Our method hybridizes the artificial bee colony methodology with tabu search to obtain high-quality solutions in short computational times. Artificial bee colony is a recent swarm intelligence technique based on the intelligent foraging behavior of honeybees. The performance of this algorithm is basically determined by two search strategies, an initialization scheme that is employed to construct initial solutions and a method for generating neighboring solutions. On the other hand, tabu search is an adaptive memory programming methodology introduced in the eighties to solve hard combinatorial optimization problems. Our hybrid approach adapts some elements of both methodologies, artificial bee colony and tabu search, to the cyclic antibandwidth problem. In addition, it incorporates a fast local search procedure to enhance the local intensification capability. Through the analysis of experimental results, the highly effective performance of the proposed algorithm is shown with respect to the current state-of-the-art algorithm for this problem.