Set-Based Discrete Particle Swarm Optimization Based on Decomposition for Permutation-Based Multiobjective Combinatorial Optimization Problems

Xue YU, Wei-Neng CHEN, Tianlong GU, Huaxiang ZHANG, Huaqiang YUAN, Sam KWONG, Jun ZHANG

Research output: Journal PublicationsJournal Article (refereed)peer-review

61 Citations (Scopus)

Abstract

This paper studies a specific class of multiobjective combinatorial optimization problems (MOCOPs), namely the permutation-based MOCOPs. Many commonly seen MOCOPs, e.g., multiobjective traveling salesman problem (MOTSP), multiobjective project scheduling problem (MOPSP), belong to this problem class and they can be very different. However, as the permutation-based MOCOPs share the inherent similarity that the structure of their search space is usually in the shape of a permutation tree, this paper proposes a generic multiobjective set-based particle swarm optimization methodology based on decomposition, termed MS-PSO/D. In order to coordinate with the property of permutation-based MOCOPs, MS-PSO/D utilizes an element-based representation and a constructive approach. Through this, feasible solutions under constraints can be generated step by step following the permutation-tree-shaped structure. And problem-related heuristic information is introduced in the constructive approach for efficiency. In order to address the multiobjective optimization issues, the decomposition strategy is employed, in which the problem is converted into multiple single-objective subproblems according to a set of weight vectors. Besides, a flexible mechanism for diversity control is provided in MS-PSO/D. Extensive experiments have been conducted to study MS-PSO/D on two permutation-based MOCOPs, namely the MOTSP and the MOPSP. Experimental results validate that the proposed methodology is promising.
Original languageEnglish
Pages (from-to)2139-2153
JournalIEEE Transactions on Cybernetics
Volume48
Issue number7
Early online date7 Aug 2017
DOIs
Publication statusPublished - Jul 2018
Externally publishedYes

Bibliographical note

This work was supported in part by the National Natural Science Foundation of China under Grant 61622206, Grant 61379061, and Grant 61332002, in part by the Natural Science Foundation of Guangdong under Grant 2015A030306024, and in part by the “Guangdong Special Support Program” under Grant 2014TQ01X550.

Keywords

  • Combinatorial optimization
  • decomposition
  • multiobjective optimization
  • particle swarm optimization (PSO)
  • permutation-based
  • set-based

Fingerprint

Dive into the research topics of 'Set-Based Discrete Particle Swarm Optimization Based on Decomposition for Permutation-Based Multiobjective Combinatorial Optimization Problems'. Together they form a unique fingerprint.

Cite this