Systems, Man, and Cybernetics

 

Home

• [P205] A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems
  Author(s): Jun Zhang, Wei-Neng Chen, Wen-Liang Zhong
  
  

  Abstract
  Particle swarm optimization (PSO) is predominately used to find solutions in continuous space. To explore the utility of PSO in the discrete space, this paper proposes a novel set-based PSO (S-PSO) method for combinatorial optimization problems (COPs). The proposed algorithm describes the discrete solution domains of COPs based on the concept of sets. A possible solution to the problem is mapped to a crisp set, and the velocity in S-PSO is defined as a set with possibilities. All arithmetic operators in the velocity and position updating rules in the original PSO are replaced by the operators defined on crisp sets and sets with possibilities in the proposed S-PSO. Based on S-PSO, 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 discrete versions. These discrete PSO variants based on S-PSO are tested on two famous COPs: the traveling salesman problem (TSP) and the 0-1 knapsack problem (0-1 KP). Experimental results show that the discrete version of the CLPSO algorithm based on the proposed S-PSO is promising.

  
   

Full Text (PDF)