An Improved Algebraic Particle Swarm Optimization for Traveling Salesman problem

Abstract

Particle Swarm Optimization (PSO), introduced by Kennedy and Eberhart in 1995, is a metaheuristic widely used for optimizing functions in continuous search spaces. However, it requires specific adaptations to handle combinatorial problems, such as those involving permutations. The PSO algebraic framework reformulates the algorithm by using algebraic structures, such as symmetric groups, to redefine the operators of sum, subtraction and multiplication by a scalar. These revisions make it possible to adapt PSO to complex combinatorial problems such as
the traveling salesman problem (TSP). By using algebraic operations such as permutation composition and transpositions, this framework improves not only the handling of discrete spaces, but also the convergence of the algorithm towards optimal solutions, this approach enables more efficient exploration of combinatorial search spaces.