Jornal Internacional de Swarm Intelligence e Computação Evolutiva

Abstrato

Um estudo comparativo de métodos proeminentes baseados na otimização por enxame de partículas para resolver o problema do caixeiro viajante

Akhand MAH, Shaik Imran Hossain e Shahina Akter

Os métodos computacionais inspirados em fenómenos naturais têm ganho muito interesse nos últimos anos. Entre os algoritmos desenvolvidos, a otimização por enxame de partículas (PSO), que imita o comportamento de bandos de aves ou cardumes de peixes, parece ser o método mais famoso devido à sua simplicidade e também ao desempenho. Uma série de métodos baseados em PSO foram desenvolvidos para o problema do caixeiro viajante (TSP), o problema combinatório mais popular. O objetivo do estudo é fazer um estudo comparativo de vários métodos baseados em PSO proeminentes na resolução de TSP. O estudo é importante porque diferentes métodos baseados em PSO foram desenvolvidos por diferentes investigadores e testados em diferentes conjuntos de problemas. Portanto, a descrição dos métodos proeminentes baseados em PSO de forma semelhante revela características distintas dos indivíduos. Além disso, os resultados experimentais num conjunto de dados de referência comum do TSP revelarão o desempenho de cada método. Neste estudo, os métodos foram testados num grande número de TSPs de referência e os resultados foram comparados entre si, bem como a otimização de colónias de formigas (ACO), o método proeminente para resolver o TSP. Os resultados experimentais revelaram que o PSO auto-tentativo melhorado (ESTPSO) e o PSO provisório de velocidade (VTPSO) superaram o ACO; e o PSO auto-tentativo (STPSO) é competitivo com o ACO. Por outro lado, a análise experimental revelou que o ESTPSO é computacionalmente mais pesado que outros e o VTPSO demorou menos tempo a resolver um problema de benchmark. As razões por detrás do desempenho e dos requisitos de tempo de cada método individual são explicadas e o VTPSO é considerado o método baseado em PSO mais eficaz para resolver o TSP.