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.

Algebraic Particle Swarm Optimization for the permutations search space

Santucci, Valentino
2017-01-01

Abstract

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.
2017
9781509046010
Artificial Intelligence; Computer Networks and Communications; Computer Science Applications1707 Computer Vision and Pattern Recognition; Signal Processing
File in questo prodotto:
File Dimensione Formato  
cec2017.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 861.71 kB
Formato Adobe PDF
861.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
0main_cec2017.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 331.06 kB
Formato Adobe PDF
331.06 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/11088
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact