Algebraic Particle Swarm Optimization for the permutations search space

Particle Swarm Optimization (PSO), though being originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In particular, we focus on the PSO applications to permutation problems. As far as we know, the most popular PSO variants that produce permutation solutions are those based on random key techniques. In this paper, after highlighting the main criticalities of the random key approach, we introduce a totally discrete PSO variant for permutation-based optimization problems. The proposed algorithm, namely Algebraic PSO (APSO), simulates the original PSO design in permutations search space. APSO directly represents the particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization previously, and successfully, introduced in the context of discrete differential evolution schemes. The particularities of the PSO design scheme arouse new challenges for the algebraic framework: the noncommutativity of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues, and two APSO variants are provided. 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, with high statistical evidence, that APSO outperforms its competitors.