Shi Jialong, Zhang Qingfu, Sun Jianyong
IEEE Trans Cybern. 2020 Mar;50(3):1060-1071. doi: 10.1109/TCYB.2018.2880256. Epub 2018 Nov 29.
Pareto local search (PLS) is a basic building block in many metaheuristics for a multiobjective combinatorial optimization problem. In this paper, an enhanced PLS variant called parallel PLS based on decomposition (PPLS/D) is proposed. PPLS/D improves the efficiency of PLS using the techniques of parallel computation and problem decomposition. It decomposes the original search space into L subregions and executes L parallel processes searching in these subregions simultaneously. Inside each subregion, the PPLS/D process is guided by a unique scalar objective function. PPLS/D differs from the well-known two phase PLS in that it uses the scalar objective function to guide every move of the PLS procedure in a fine-grained manner. In the experimental studies, PPLS/D is compared against the basic PLS and a recently proposed PLS variant on the multiobjective unconstrained binary quadratic programming problems and the multiobjective traveling salesman problems with, at most, four objectives. The experimental results show that regardless of whether the initial solutions are randomly generated or generated by heuristic methods, PPLS/D always performs significantly better than the other two PLS variants.
帕累托局部搜索（PLS）是许多用于多目标组合优化问题的元启发式算法中的基本组成部分。本文提出了一种基于分解的增强型PLS变体，称为并行PLS（PPLS/D）。PPLS/D利用并行计算和问题分解技术提高了PLS的效率。它将原始搜索空间分解为L个子区域，并同时执行L个并行进程在这些子区域中进行搜索。在每个子区域内，PPLS/D进程由一个独特的标量目标函数引导。PPLS/D与著名的两阶段PLS的不同之处在于，它使用标量目标函数以细粒度的方式引导PLS过程的每一步移动。在实验研究中，将PPLS/D与基本PLS以及最近提出的一种PLS变体在多目标无约束二元二次规划问题和最多具有四个目标的多目标旅行商问题上进行了比较。实验结果表明，无论初始解是随机生成的还是通过启发式方法生成的，PPLS/D总是比其他两种PLS变体表现得明显更好。
