Tackling Permutation-based Optimization Problems with an Algebraic Particle Swarm Optimization Algorithm

Particle Swarm Optimization (PSO), though originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In this paper, we focus on the PSO applications to permutation-based problems. As far as we know, the most popular and general PSO schemes for permutation solutions are those based on random key techniques. After highlighting the main criticalities of the random key approach, we introduce a discrete PSO variant for permutation-based optimization problems. By simulating search moves through a vector space, the proposed algorithm, Algebraic PSO (APSO), allows the original PSO design to be applied to the permutation search space. APSO directly represents both particlepositions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization based on strong mathematical foundations. However, in order to make this new scheme viable, some challenges have to be overcome: the choice of the order of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues. Furthermore, an alternative geometric interpretation of classical PSO dynamics allows to introduce a major APSO variant based on a novel concept of convex combination between permutation objects. In total, four APSO schemes have been introduced. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show that, with high statistical evidence, APSO outperforms its competitors and it reaches results comparable with state-of-the-art on most of the instances considered.