New techniques to improve neighborhood exploration in pareto local search

Pareto Local Search (PLS) is an extension of local search to multiobjective combinatorial optimization problems (MCOPs). It is widely used as a building block in many multiobjective metaheuristics. However, it suffers from poor anytime behavior and long convergence time. In this paper, we focus on improving the neighborhood exploration mechanism to accelerate PLS. In total, we propose three new search strategies, namely, Promising List, Don't Look Bits and Continuing Search and implement them on the multiobjective Traveling Salesman Problem (mTSP) and the multiobjective Unconstrained Binary Quadratic Programming (mUBQP) problem. In Promising List, features of problem structure are utilized to guide the local search. In Don't Look Bits, neighborhood moves that are less promising to produce improving solutions are skipped. In Continuing Search, the agent will start from where previous neighborhood exploration stops to avoid repetitive neighborhood moves. The experimental results verify the effectiveness of the three techniques both individually and collaboratively on most of the test instances. Besides, one proposed PLS variant outperforms two state-of-the-art PLS-based algorithms.