PPLS/D: Parallel Pareto Local Search Based on Decomposition

作     者：Shi, Jialong Zhang, Qingfu Sun, Jianyong 

作者机构：Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON CYBERNETICS》 (IEEE Trans. Cybern.)

年 卷 期：2020年第50卷第3期

页      面：1060-1071页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ANR/RGC Joint Research Scheme - Research Grants Council of Hong Kong France National Research Agency [A-CityU101/16] 

主　　题：Multiobjective combinatorial optimization parallel metaheuristic Pareto local search unconstrained binary quadratic programming traveling salesman problem 

摘      要：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.