Multi-GPU Accelerating Strategies of Ant Colony Optimization Algorithms Using Rank Based and Strong Elitist Versions
Resumo
The most used problem to compare these meta-heuristics is the classical Travelling Salesman Problem (TSP) on a network with sizes from tens to millions of nodes. Nature-based metaheuristics are the main source of optimization techniques to solve this problem. Although there is a zoo of possibilities, Ant Colony Optimization (ACO) is still one of the most efficient, parallel, and simple techniques to implement. The pheromone evaporation rate, α, β and ant number M are the four parameters fitted for finding the best solutions. Candidate list and the use of a source solution are efficient strategies to optimize large problems, but there are other strategies to improve quality solutions such as local search strategies. Among the local search techniques, k-opt search has proved to be very efficient to deal with path-crossing. The initial route is split into k sub-routes connected in (k-1)!2k-1 ways. Thus, 3-opt is an efficient strategy balancing complexity and precision. Moreover, the best α and β are the result of the used strategy. Finally, the solution is improved by accelerating through parallel versions with multi-GPUs. In this article, four ACO algorithms were developed using two variations (Rank Based 3-opt and Strong Elitist 3-opt), each one with two strategies (candidate list and restricted). To test the algorithms, TSPLIB95 was used with test problems between N=51 and 4, 461 nodes in a server with 4 RTX A4000 GPUs. After improving the algorithms and parallelization, the parameters are tuned to get the highest performance improving the local minimum search. Statistical analysis of repetitions shows good stability of the chosen metaheuristics.
