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

AUTOR(ES)

João Paulo Queiroz dos Santos

DATA DE PUBLICAÇÃO

2009

RESUMO

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

ASSUNTO(S)

q-learning algoritmos genéticos grasp metaheuristics engenharia eletrica q-learning parallel and distributed systems sistemas paralelos e distribuídos genetic algorithm metaheurísticas grasp

Documentos Relacionados

• Algoritmos Evolucionários Aplicados ao Problema do Caixeiro Viajante Multiobjetivo.
• Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos
• Plasticidade sináptica e o problema do caixeiro viajante
• Dempster-Shaferandgeneticalgorithmsinahybridapproachforthecorrespondenceprobleminstereopsis
• Uma abordagem híbrida por Dempster-Shafer e algoritmos genéticos para o problema de correspondência em estereoscopia