Guided Pareto Local Search based frameworks for biobjective optimization


Abstract

Guided Pareto Local Search (GPLS) is an extension to the Guided Local Search algorithm to contain multiobjective combinatorial optimization. GPLS is shown to improve the convergence of the underlying Pareto local search algorithms. This paper demonstrates the potential of GPLS to be an effective searching technique that can be a central part of a multi-phase or hybrid frameworks. To confirm this, two simple frameworks based on GPLS are proposed: iGPLS and mGPLS. Both frameworks only require an initial set of diverse solutions. While GPLS starts from a randomly (or heuristically) generated solution, iGPLS starts with the initial diverse solution set. On the other hand, mGPLS is a parallel version of GPLS, in which each GPLS run starts independently from a solution in the initial set. The application of these frameworks to the biobjective 0/1 knapsack problem reveals the effectiveness of the GPLS based frameworks, demonstrated by achieving state-of-the-art results.