Estudos acerca do ACO na solução do TSP e uma nova abordagem

Abstract

Resumo: A otimização é uma das áreas da matemática aplicada que possui maior visibilidade e relevância atualmente, principalmente dentro de grandes empresas, onde modelos matemáticos podem ser o diferencial que irá manter a empresa a frente da concorrência. Os modelos tornam-se cada vez mais complexos, fazendo com que métodos determinísticos sejam inadequados diante da demanda computacional necessária para encontrar uma solução, tendo em vista a tecnologia atual. Surgem então métodos que não prometem soluções perfeitas, mas boas o suficiente e que podem ser executados em tempo hábil. Por muito tempo as meta-heurísticas foram destaque na área da otimização, e por mais que outros métodos promissores estejam surgindo, alguns dos melhores resultados presentes na literatura foram obtidos por meta-heurísticas e suas adaptações. Neste trabalho é sugerida uma abordagem diferente para a otimização por colônia de formigas (ACO), que é uma meta-heurística com grande destaque na solução do problema do caixeiro viajante (TSP). No algoritmo original do ACO, as formigas constroem, uma a uma, circuitos dentro de um grafo que com o tempo serão melhorados pra gerar uma possível solução do TSP. A adaptação proposta toma o algoritmo do ACO e faz as devidas alterações para simular uma movimentação simultânea de todas as formigas, com a expectativa de que caminhos curtos recebam naturalmente maiores quantidades de feromônios. Neste trabalho são mostrados os testes realizados para averiguar quais os parâmetros ideais a serem utilizados e então comparar resultados com o algoritmo original para concluir quais as vantagens e desvantagens nesta adaptação. Palavras-chaves: Meta-heurística; Sistema de colônia de formigas; Problema do caixeiro viajante.

Abstract: Optimization is one of the fields in applied mathematics with most visibility and relevance nowadays, mainly inside great companies, where mathematical models could be the reason to keep the company ahead of the competition. As the models complexity increases, deterministic methods becomes worse at solving them, in view of the huge computational demand required to find a solution. Methods that doesn't ensure the optimal answer comes up, the solutions are close enough to the optimum and can be found in much faster times. For a long time meta heuristics have been in spotlight on optimization, other promising methods exists, but some of the best results in literature came from meta heuristics and its variations. In this work is suggested a new approach to the ant colony optimization algorithm (ACO), which is a benchmark meta heuristic on solving the traveling salesman problem (TSP). On the original ACO, one by one, the ants construct their circuits in a graph, these circuits will be enhanced as the time passes in order to obtain a solution for the TSP. The suggested approach adapts the ACO, making necessary alterations to simulate a simultaneous movimentation between the ants, it is expected that edges in shorter solutions to naturally have greater pheromones amounts accumulated. Tests were made to estimate the best parameter configuration to be used and the suggested algorithm results were compared to the original ACO verifying the advantages and disadvantages presents in this adaptation.