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

• Ano de defesa: 2009
• Autor(a) principal: Santos, João Paulo Queiroz dos
• Orientador(a): Melo, Jorge Dantas de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio Grande do Norte
• Programa de Pós-Graduação: Programa de Pós-Graduação em Engenharia Elétrica
• Departamento: Automação e Sistemas; Engenharia de Computação; Telecomunicações
• País: BR
• Palavras-chave em Português: Metaheurísticas GRASP; Algoritmos genéticos; Q-learning; Sistemas paralelos e distribuídos
• Palavras-chave em Inglês: GRASP metaheuristics; Genetic algorithm; Q-learning; Parallel and distributed systems
• Área do conhecimento CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
• Link de acesso: https://repositorio.ufrn.br/jspui/handle/123456789/15221

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