Reference Line Guided Pareto Local Search for Bi-Objective Traveling Salesman Problem
Chao Xia, Xinye Cai, Zhun Fan, Muhammad Sulaman · 2017
In this paper, a reference line guided Pareto local search (RLG-PLS) is proposed for combinatorial bi-objective optimization problems (CBOPs). RLG-PLS uses a set of predefined reference lines to guide the search direction and maintain the diversity of the population. Two populations are evolving in RLG-PLS, i.e., 1) the external population (EP) maintains the nondominated solutions that are closest to the reference lines; and 2) a starting population (SP) stores all the starting solutions for Pareto local search. At each generation, Pareto local search is applied to search the neighborhood of each solution in SP and these neighborhood solutions are also used to update EP and then, SP is updated with the newly added solutions from EP. When no nondominated solutions can be found (i.e., SP is empty), new reference lines are inserted to guide the Pareto local search for more new nondominated solutions. In the experimental studies, RLG-PLS is compared with MOEA/D-LS (WS, TCH, PBI), NSGA-II-LS and MOMAD on bi-objective travelling salesman problem (BOTSP). The experimental results show that RLG-PLS outperforms all the compared algorithms.