Algebraic Particle Swarm Optimization for the permutations search space

Particle Swarm Optimization (PSO), though beingoriginally introduced for continuous search spaces, has beenincreasingly applied to combinatorial optimization problems. Inparticular, we focus on the PSO applications to permutationproblems. As far as we know, the most popular PSO variants thatproduce permutation solutions are those based on random keytechniques. In this paper, after highlighting the main criticalitiesof the random key approach, we introduce a totally discretePSO variant for permutation-based optimization problems. Theproposed algorithm, namely Algebraic PSO (APSO), simulatesthe original PSO design in permutations search space. APSOdirectly represents the particle positions and velocities as permutations.The APSO search scheme is based on a generalalgebraic framework for combinatorial optimization previously,and successfully, introduced in the context of discrete differentialevolution schemes. The particularities of the PSO design schemearouse new challenges for the algebraic framework: the noncommutativityof the velocity terms, and the rationale behind thePSO inertial move. Design solutions have been proposed for boththe issues, and two APSO variants are provided. Experimentshave been held to compare the performances of the APSOschemes with respect to the random key based PSO schemes inliterature. Widely adopted benchmark instances of four popularpermutation problems have been considered. The experimentalresults clearly show, with high statistical evidence, that APSOoutperforms its competitors.