Uma análise experimental de abordagens topológicas aplicadas ao problema do caixeiro-viajante através de otimização por nuvem de partículas

Abstract

Resumo: O algoritmo do Particle Swarm Optimization (PSO), inspirado em comportamentos sociais naturais é uma metaheurística que tem sido aplicada com sucesso na resolução de problemas de otimização combinatória. Este trabalho tem como objetivo apresentar o algoritmo PSO com busca local e path relinking, que tem apresentados resultados promissores, porém se diferencia de versões anteriores, pois incorpora duas diferentes estratégias. A primeira estratégia se refere à forma de comunicação entre as partículas, sendo propostas as topologias Focal, Von Neumann e Clan. A qualidade das topologias propostas são testadas na comparação com as topologias Global e Local, geralmente utilizadas no algoritmo PSO. A segunda estratégia é a dispersão da nuvem e tem como objetivo procurar melhores regiões no espaço de busca. Tal proposta é validade na aplicação ao Problema do Caixeiro-Viajante.

Abstract: The Particle Swarm Optimization algorithm (PSO), inspired by natural social behavior is a metaheuristic that has been successfully applied in solving combinatorial optimization problems. This work aims to present the PSO algorithm using local search and path relinking, which has shown promising results, but differs from earlier versions, it incorporates two different strategies. The first strategy refers to the means of communication between the particles being proposed Focal, Von Neumann and Clan topologies. The quality of the proposed topologies are tested in comparison with the global and local topologies, typically used in the PSO algorithm. The second strategy is the dispersion of the cloud and aims to seek better regions in the search space. This proposal is valid in application to the Traveling Salesman Problem.