A novel set-based particle swarm optimization method for discrete optimization problems

Wei Neng Chen, Jun Zhang*, Henry S.H. Chung, Wen Liang Zhong, Wei Gang Wu, Yu Hui Shi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

372 Citations (Scopus)

Abstract

Abstract-Particle swarm optimization (PSO) is predominately used to find solutions for continuous optimization problems. As the operators of PSO are originally designed in an n-dimensional continuous space, the advancement of using PSO to find solutions in a discrete space is at a slow pace. In this paper, a novel setbased PSO (S-PSO) method for the solutions of some combinatorial optimization problems (COPs) in discrete space is presented. The proposed S-PSO features the following characteristics. First, it is based on using a set-based representation scheme that enables S-PSO to characterize the discrete search space of COPs. Second, the candidate solution and velocity are defined as a crisp set, and a set with possibilities, respectively. All arithmetic operators in the velocity and position updating rules used in the original PSO are replaced by the operators and procedures defined on crisp sets, and sets with possibilities in S-PSO. The S-PSO method can thus follow a similar structure to the original PSO for searching in a discrete space. Based on the proposed S-PSO method, most of the existing PSO variants, such as the global version PSO, the local version PSO with different topologies, and the comprehensive learning PSO (CLPSO), can be extended to their corresponding discrete versions. These discrete PSO versions based on S-PSO are tested on two famous COPs: the traveling salesman problem and the multidimensional knapsack problem. Experimental results show that the discrete version of the CLPSO algorithm based on S-PSO is promising.

Original languageEnglish
Article number5299261
Pages (from-to)278-300
Number of pages23
JournalIEEE Transactions on Evolutionary Computation
Volume14
Issue number2
DOIs
Publication statusPublished - Apr 2010

Keywords

  • Combinatorial optimization problem
  • Discrete space
  • Multidimensional knapsack problem
  • Particle swarm optimization
  • Traveling salesman problem

Fingerprint

Dive into the research topics of 'A novel set-based particle swarm optimization method for discrete optimization problems'. Together they form a unique fingerprint.

Cite this