Anytime Pareto local search

Jérémie Dubois-Lacoste*, Manuel López-Ibáñez, Thomas Stützle

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

259 Downloads (Pure)

Abstract

Pareto Local Search (PLS) is a simple and effective local search method for tackling multi-objective combinatorial optimization problems. It is also a crucial component of many state-of-the-art algorithms for such problems. However, PLS may be not very effective when terminated before completion. In other words, PLS has poor anytime behavior. In this paper, we study the effect that various PLS algorithmic components have on its anytime behavior. We show that the anytime behavior of PLS can be greatly improved by using alternative algorithmic components. We also propose Dynagrid, a dynamic discretization of the objective space that helps PLS to converge faster to a good approximation of the Pareto front and continue to improve it if more time is available. We perform a detailed empirical evaluation of the new proposals on the bi-objective traveling salesman problem and the bi-objective quadratic assignment problem. Our results demonstrate that the new PLS variants not only have significantly better anytime behavior than the original PLS, but also may obtain better results for longer computation time or upon completion.

Original languageEnglish
Pages (from-to)369-385
Number of pages17
JournalEuropean Journal of Operational Research
Volume243
Issue number2
DOIs
Publication statusPublished - 1 Jun 2015

Keywords

  • Anytime optimization
  • Multi-objective optimization
  • Pareto local search
  • Quadratic assignment problem
  • Traveling salesman problem

Fingerprint

Dive into the research topics of 'Anytime Pareto local search'. Together they form a unique fingerprint.

Cite this