Using Parallel Strategies to Speed up Pareto Local Search

Jialong Shi, Qingfu Zhang, Bilel Derbel, Arnaud Liefooghe, Sébastien VérelSEAL 2017 · DOI

TL;DR

This paper tackles the slow convergence of Pareto Local Search (PLS), a fundamental algorithm for multi-objective optimization. They introduce a parallel framework that significantly speeds up PLS by running multiple search processes concurrently, while maintaining solution quality. A novel "trajectory tree" visualization is also presented to better understand PLS behavior.

What Problem Does This Paper Address?

Multi-objective optimization problems (MOPs) involve finding a set of solutions that represent the best possible trade-offs between multiple conflicting objectives. The "Pareto Set" (PS) is the collection of these optimal trade-off solutions. Pareto Local Search (PLS) is a widely used algorithm that helps approximate this PS. However, the standard, sequential PLS can be very slow to find high-quality solutions. While previous work has proposed speed-up strategies, these are typically sequential and don't leverage the power of modern multi-core processors. This paper aims to bridge this gap by developing and evaluating parallel strategies to accelerate PLS.

Methods

The core of the paper is a parallel multi-search framework for PLS. Instead of a single PLS process, they run multiple (L) PLS processes in parallel. Each parallel process is guided by a specific weight vector, effectively decomposing the multi-objective problem into several scalarized sub-problems. These parallel processes maintain their own archives of non-dominated solutions, which are merged at the end to form the final Pareto set approximation.

The authors also propose and investigate alternative components for the PLS algorithm, which can be combined to create different parallel variants. These components include:

  • Selection Step:
    • RND (Random): Randomly selects a solution from the archive.
  • HWF (Highest Weighted-sum Function): Selects the solution with the highest weighted-sum objective function value.
  • Acceptance Criterion:
    • 大 (Dominance): Accepts any non-dominated solution.
  • w>大 (Weighted-sum Dominance): Accepts solutions that are either non-dominated or have a higher weighted-sum value than the current best in the archive.
  • Neighborhood Exploration:
    • * (Best-Improvement): Evaluates all neighbors.
  • 1* (First-Improvement): Stops exploring neighbors once an acceptable one is found.
  • Boundary Setting:
    • UB (Unbounded): No boundaries between parallel processes.
  • B (Bounded): Sets boundaries between parallel processes to prevent excessive overlap and potentially wasted effort.

By combining these alternatives, they create 12 distinct parallel PLS variants.

A novel contribution is the "trajectory tree", a diagram that visualizes the search process of PLS in the objective space. It maps accepted neighboring solutions to their parent solutions, providing insights into the algorithm's behavior and helping to understand why certain variants are more efficient.

Datasets

The experiments were conducted on multiobjective Unconstrained Binary Quadratic Programming (mUBQP) instances. Specifically, they used instances from a previous work [9] with 2 objectives (m=2), varying the number of binary variables (n = {200, 300, 500}) and the correlation coefficient between objectives (ρ = {0.0, 0.5, -0.5}). No new benchmark datasets were introduced.

Key Insights and Ideas

  • Parallelism is Key for Speed: Running multiple PLS processes in parallel, each guided by a different weight vector, is a highly effective way to speed up convergence.
  • Decomposition Works: The strategy of decomposing the multi-objective problem using weight vectors and running independent PLS processes is inspired by MOEA/D frameworks and proves effective.
  • Component Choices Matter: Different combinations of selection, acceptance, and exploration strategies significantly impact the search trajectory and efficiency, as visualized by the trajectory trees.
  • Boundedness Can Improve Speed: Introducing boundaries between parallel search processes (the 'B' strategy) can lead to substantial runtime reductions, even if it slightly impacts solution quality in some cases. This is because it focuses each process on a more defined region of the search space.
  • Visualization is Insightful: The "trajectory tree" is a powerful tool for understanding the dynamics of PLS and for comparing different variants. It reveals how different strategies lead to different search patterns.

Key Results

The experimental results demonstrate that the proposed parallel strategies can significantly speed up PLS.

  • Solution Quality: The hypervolume metric showed that the differences in solution quality between the various parallel PLS variants were relatively small. Variants without boundaries generally achieved slightly higher hypervolume values, suggesting a trade-off between exploration breadth and speed.
  • Runtime: The most significant gains were observed in runtime. Variants incorporating the bounded strategy (PPLS-7 to PPLS-12) were considerably faster than their unbounded counterparts. PPLS-12, the variant with the most advanced strategies (HWF, w>A, 1*, B), achieved the overall smallest runtime.
  • Specific Variants: PPLS-3 (RND, w>A, , UB) and PPLS-4 (HWF, A, , UB) achieved high hypervolumes with reduced runtimes compared to the basic PPLS-1. PPLS-4 showed a notable speedup.

Limitations and Future Work

  • Specific Problem Domain: The experiments were conducted on mUBQP instances with only two objectives. The authors suggest investigating the performance of their proposed approaches on multi-objective combinatorial problems with different characteristics.
  • Scalability: While speedup was demonstrated, further investigation into the scalability of the parallel PLS variants is planned.
  • Parameter Tuning: The paper implicitly relies on the choice of weight vectors and other parameters. Future work could explore adaptive or automated methods for setting these parameters.
  • More Complex Objectives: The paper focuses on unconstrained binary quadratic programming. Extending the framework to constrained problems or other types of combinatorial optimization problems would be valuable.

Summary updated

BibTeX
@inproceedings{shi2017using,
  author = {Jialong Shi and Qingfu Zhang and Bilel Derbel and Arnaud Liefooghe and Sébastien Vérel},
  title = {{Using Parallel Strategies to Speed up Pareto Local Search}},
  booktitle = {SEAL},
  year = {2017},
  doi = {10.1007/978-3-319-68759-9\_6},
}
Figure