Using a coprocessor to solve the Ant Colony Optimization algorithm
Felipe Tirado, Angélica Urrutia, Ricardo J. Barrientos · 2015
The Ant Colony Optimization (ACO) algorithm is a popular metaheuristic applied to a wide kind of NP-hard problems. It is based on the behavior of ants seeking a path between their colony and a source of food. On the other hand, in recent years the use of compute-intensive coprocessors has been widely studied to accelerate sequential processes through a GPU (Graphic Processing Unit). Recently, Intel has released a GPU-type coprocessor, the Intel Xeon Phi. It is built up to 61 cores connected by a bidirectional ring network with a vector process unit (VPU) on large vector registers. In the present work, we show a novel implementation for the Ant Colony Optimization (ACO) algorithm using a Xeon Phi coprocessor. To prove the efficiency of our algorithm, we solve the Travelling Salesman Problem (TSP). We also exposed the difficulties and key performance factors to deal with the ACO algorithm on a Xeon Phi coprocessor.