Stochastic Pareto local search : Pareto neighbourhood exploration and perturbation strategies

M.M. Drugan, D. Thierens

Research output: Contribution to journalArticleAcademicpeer-review

45 Citations (Scopus)
78 Downloads (Pure)

Abstract

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.
Original languageEnglish
Pages (from-to)727-766
JournalJournal of Heuristics
Volume18
Issue number5
DOIs
Publication statusPublished - Oct 2012
Externally publishedYes

Keywords

  • Stochastic Pareto local search
  • Pareto neighbourhood improvement strategies
  • Pareto neighbourhood perturbation strategies
  • Path-guided mutation

Fingerprint

Dive into the research topics of 'Stochastic Pareto local search : Pareto neighbourhood exploration and perturbation strategies'. Together they form a unique fingerprint.

Cite this