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.

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

Santucci, Valentino
;
2019-01-01

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
fi-167(1-2)06.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: NON PUBBLICO - Accesso chiuso
Dimensione 312.02 kB
Formato Adobe PDF
312.02 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
tackling-permutation-based.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 290.38 kB
Formato Adobe PDF
290.38 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12071/13742
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact