Uma implementação paralela híbrida para o problema do caixeiro viajante usando algoritmos genéticos, GRASP e aprendizagem por reforço

The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed

As metaheurísticas são técnicas conhecidas para a resolução de problemas de otimização, classificados como NP-Completos e vêm obtendo sucesso em soluções aproximadas de boa qualidade. Elas fazem uso de abordagens não determinísticas que geram soluções que se aproximam do ótimo, mas no entanto, sem a garantia de que se encontre o ótimo global. Motivado pelas dificuldades em torno da resolução destes problemas, este trabalho propôs o desenvolvimento de métodos paralelos híbridos utilizando a aprendizagem por reforço e as metaheurísticas GRASP e Algoritmos Genéticos. Com a utilização dessas técnicas em conjunto, objetivou-se então, contribuir na obtenção de soluções mais eficientes. Neste caso, ao invés de utilizar o algoritmo Q-learning da aprendizagem por reforço, apenas como técnica de geração das soluções iniciais das metaheurísticas, este também aplicado de forma cooperativa e competitiva com o Algoritmo Genético e o GRASP, em uma implementação paralela. Neste contexto, foi possível verificar que as implementações realizadas neste trabalho apresentaram resultados satisfatórios, tanto na parte de cooperação e competição entre os algoritmos Q-learning, GRASP a Algoritmos Genéticos, quanto na parte de cooperação e competição entre grupos destes três algoritmos. Em algumas instâncias foi encontrado o ótimo global; quando não encontrado, conseguiu-se chegar bem próximo de seu valor. Neste sentido foi realizada uma análise do desempenho da abordagem proposta e verificou-se um bom comportamento em relação aos quesitos que comprovam a eficiência e o speedup (ganho de velocidade com o processamento paralelo) das implementações realizadas