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.

Palavras-chave: Multi-GPU, Ant Colony Optimization algorithms, metaheuristics, local search, high performance
Publicado
17/10/2023
ÁVILA, Andrés I.; AEDO, Juan Manuel; GONZÁLEZ-FLORES, Mariela. Multi-GPU Accelerating Strategies of Ant Colony Optimization Algorithms Using Rank Based and Strong Elitist Versions. In: WORKSHOP ON APPLICATIONS FOR MULTI-CORE ARCHITECTURES - INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 35. , 2023, Porto Alegre/RS. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 68-76.