Implementando em FPGA um algoritmo genético para a busca de soluções para o problema do caixeiro viajante

Abstract

The Traveling Salesman Problem that seeks to find the lowest cost route between several cities in a set, going through each one only once and returning to the starting city. There are several applications for this problem such as process planning, cell manufacturing, route management, matrix structure and even the assembly of printed circuit boards. Finding an exact solution is costly in time and processing, for which there are approximate methods. However, some PCV applications have a microsecond response requirement. In these cases, parallelism is a strong option for acceleration. Within the approximate methods, the metaheuristic Genetic Algorithm stands out for its parallelization capacity. In this work, a reconfigurable architecture in FPGA was implemented, which represents the meta-heuristic genetic algorithm, capable of seeking solutions to the traveling salesman problem. The implementation took place in a microcontroller combined with reconfigurable logic blocks and was carried out in a kit FPGA Spartan 3E. Finally, experiments were conducted which proved a linear increase runtime as the number of cities in the problem increased.