IEEE Trans Cybern. 2018 Jul;48(7):2139-2153. doi: 10.1109/TCYB.2017.2728120. Epub 2017 Aug 7.
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.
本文研究了一类特定的多目标组合优化问题（MOCOPs），即基于排列的 MOCOPs。许多常见的 MOCOPs，例如多目标旅行商问题（MOTSP）、多目标项目调度问题（MOPSP），都属于此类问题，它们可能非常不同。然而，由于基于排列的 MOCOPs 具有内在的相似性，即它们的搜索空间结构通常呈排列树状，因此本文提出了一种基于分解的通用多目标集粒子群优化方法，称为 MS-PSO/D。为了与基于排列的 MOCOPs 的性质相协调，MS-PSO/D 采用了基于元素的表示和构造方法。通过这种方法，可以按照排列树状结构逐步生成约束下的可行解。并且在构造方法中引入了与问题相关的启发式信息，以提高效率。为了解决多目标优化问题，采用了分解策略，根据一组权重向量将问题转化为多个单目标子问题。此外，MS-PSO/D 提供了一种灵活的多样性控制机制。本文对 MOTSP 和 MOPSP 这两个基于排列的 MOCOPs 进行了广泛的实验，以研究 MS-PSO/D。实验结果验证了所提出的方法是有前途的。
