Aplicação de meta learning para escolha da melhor meta-heurística em problemas de caixeiro viajante

Abstract

O presente trabalho tem como objetivo empregar e avaliar estratégias de aprendizado de máquina para escolher meta-heurísticas promissoras para o problema do Traveling Salesman Problem (TSP), o qual caracteriza-se por ser um problema de otimização combinatorial. Na grande maioria das instâncias de TSP não se sabe qual é a solução ótima. Heurísticas e meta-heurísticas são comumente usadas nos problemas de TSP para encontrar soluções de qualidade em um curto período de tempo. Uma vez que diferentes meta-heurísticas podem produzir soluções de qualidade variada, ocorre que não há uma melhor meta-heurística para todas as instâncias. Desse modo, este trabalho explora o uso de métodos de aprendizagem de máquina para criar uma meta-heurística de aprendizagem (meta learning), a fim de identificar quais meta-heurísticas são mais promissoras para solucionar instâncias especificas do TSP, definidas por conjuntos de características (meta features). Com a realização dos experimentos, observou-se que os modelos de meta learning podem prever com precisão quais meta-heurísticas são mais adequadas para diferentes cenários do TSP. Os resultados obtidos dos experimentos também mostram que os métodos de aprendizado utilizados no modelo tem um impacto importante na qualidade das soluções obtidas.