Surrogate-assisted multi-objective combinatorial optimization based on decomposition and walsh basis

Geoffrey Pruvost, Bilel Derbel, Arnaud Liefooghe, Sébastien Vérel, Qingfu ZhangGECCO 2020 · DOI

TL;DR

This paper introduces a novel framework for tackling computationally expensive multi-objective combinatorial optimization problems (MCOPs) by combining decomposition-based evolutionary algorithms with Walsh basis surrogates. The proposed approach aims to efficiently explore complex search spaces by using cheap surrogate models to guide the search for optimal trade-offs between conflicting objectives, outperforming a non-surrogate baseline.

What Problem Does This Paper Address?

Many real-world optimization problems involve multiple, conflicting objectives (e.g., maximizing performance while minimizing cost) and discrete decision variables (combinatorial optimization). Evaluating the quality of a potential solution for these problems can be extremely time-consuming or computationally expensive. This is particularly true for multi-objective combinatorial optimization problems (MCOPs). Traditional evolutionary algorithms struggle with such expensive evaluations because they require a large number of function calls to find a good set of trade-off solutions (the Pareto front). While surrogate models (or meta-models) offer a way to approximate expensive objective functions with cheaper models, their application to MCOPs with discrete variables is less explored than in continuous domains. This paper addresses this gap by developing and analyzing a surrogate-assisted evolutionary algorithm specifically designed for these challenging MCOPs.

Methods

The core of the proposed method, termed S-cmo (Surrogate-assisted Combinatorial Multiobjective Optimization), is built upon two key components:

  • Decomposition-based MOEA (MOEA/D): This framework breaks down the multi-objective problem into a set of single-objective sub-problems, each optimized using a scalarization function (Chebyshev in this case) and guided by a weight vector. This allows for cooperative evolution and leveraging of information across sub-problems.
  • Walsh Basis Surrogates: For each objective function, a surrogate model is built using Walsh functions. Walsh functions are a set of orthogonal functions well-suited for decomposing pseudo-boolean functions (binary strings). The surrogate model approximates the true objective function using a linear combination of Walsh functions up to a specified order. The coefficients of this model are estimated using Lasso regression, a sparse linear regression technique that helps handle a large number of potential Walsh basis functions.

The S-cmo framework then integrates these components. In each generation, Walsh surrogate models are trained on all previously evaluated solutions. A pool of offspring is generated, and a single candidate solution is selected for expensive evaluation based on the surrogate model's predictions. This selected solution is then used to update the population and the training data for the surrogates.

Two main strategies are explored for generating the offspring pool and selecting a solution for evaluation:

  • Pool Generation:
    • Filter: Generates offspring using standard variation operators (crossover, mutation) and then selects one based on surrogate predictions.
  • Substitute: Uses a separate MOEA/D instance to optimize the trained surrogate models themselves, generating a more "promising" pool of candidates.
  • Selection for Evaluation:
    • Local: Selects the offspring that performs best for the current sub-problem's scalarizing function.
  • Global: Selects the offspring that performs best across all sub-problems' scalarizing functions.

This leads to four main variants: Filter-Local, Filter-Global, Substitute-Local, and Substitute-Global.

Datasets

The paper uses Multi-objective NK Landscapes as benchmark problems. These are synthetic problems designed to model multi-objective, multi-modal combinatorial optimization. They are characterized by:

  • n: The length of the binary string (decision variables), with values tested at 25 and 50.
  • k: The number of epistatic interactions, controlling the degree of non-linearity and ruggedness of the landscape, with values tested at 0, 1, and 2.
  • m: The number of objectives, fixed at 2 (bi-objective).

These landscapes are generated with correlated objectives and allow for tuning the complexity and ruggedness of the search space.

Key Insights and Ideas

  • Walsh surrogates are effective for MCOPs: The study demonstrates that Walsh basis models can be successfully adapted to approximate objectives in MCOPs, providing a cheap alternative to expensive evaluations.
  • Decomposition is a flexible framework: Leveraging MOEA/D as the underlying evolutionary framework proves to be a robust choice for integrating surrogate models and handling multi-objective aspects.
  • Substitute strategy is generally superior: The "Substitute" pool generation strategy, which uses an optimizer to find promising solutions on the surrogate models, generally outperforms the "Filter" strategy. This suggests that actively optimizing the surrogate model itself is more beneficial than simply relying on random variation.
  • Global selection is often better, but not always: The "Global" selection strategy (choosing the best across all sub-problems) tends to perform better overall, likely due to its opportunistic nature. However, the "Local" strategy can sometimes lead to more balanced approximation sets.
  • Over-optimizing surrogates can be detrimental: Aggressively optimizing the surrogate models (e.g., with a high search engine effort g or a high Walsh order d) can lead to wasted evaluations if the surrogate is not perfectly accurate. This highlights the importance of balancing exploration and exploitation.
  • Walsh order matters, but not always linearly: While a higher Walsh order generally leads to a more accurate model, there's a point of diminishing returns. For complex landscapes, a slightly underestimated order can sometimes yield better results, especially with limited budgets, due to the difficulty of accurately estimating coefficients for high-order models.

Key Results

  • Substitute-Global variant is the best performer: Across most configurations and budgets, the combination of the "Substitute" pool generation and "Global" selection strategy achieved the best average hypervolume values, indicating superior approximation quality.
  • Significant improvement over baseline: The best S-cmo variants consistently outperformed the non-surrogate MOEA/D baseline, especially at higher budgets. For instance, at 1500 evaluations, the best variants achieved significantly better hypervolume values.
  • Anytime performance is crucial: The paper emphasizes the importance of anytime performance, showing how surrogate-assisted algorithms can provide good solutions even with limited evaluations.
  • Impact of Walsh order: For the hardest instances (n=50, k=2), the performance difference between surrogate-assisted variants and the baseline became more pronounced as the Walsh order increased. However, the optimal order was not always the highest possible, with d=2 often providing a good balance.
  • Accuracy vs. Performance: While model accuracy is important, it doesn't always directly correlate with hypervolume performance, especially for very small budgets. An underestimated order can be a viable strategy when computational resources are extremely limited.

Limitations and Future Work

  • Parameter tuning: The paper acknowledges that finding the optimal parameters for the S-cmo variants (e.g., pool size λ, search engine effort g, Walsh order d) can be challenging and instance-dependent.
  • No uncertainty measure: Walsh surrogates, unlike some other models (e.g., Kriging), do not inherently provide an uncertainty measure for their predictions. This can make aggressive optimization of the surrogate risky.
  • Adaptive strategies: The authors suggest future work on developing adaptive landscape-aware techniques that can automatically adjust parameters and components of both the Walsh surrogates and the decomposition framework.
  • Online adaptation: Investigating online approaches that adapt the algorithm's behavior during the search process, rather than relying on fixed offline settings, is a promising direction.
  • Alternative surrogate models: While Walsh functions are effective, exploring other discrete surrogate models or hybrid approaches could be beneficial.
  • Dynamic order selection: The possibility of dynamically adjusting the Walsh order during the optimization process is also mentioned as a future research avenue.

Summary updated

BibTeX
@inproceedings{pruvost2020surrogate,
  author = {Geoffrey Pruvost and Bilel Derbel and Arnaud Liefooghe and Sébastien Vérel and Qingfu Zhang},
  title = {{Surrogate-assisted multi-objective combinatorial optimization based on decomposition and walsh basis}},
  booktitle = {GECCO},
  year = {2020},
  doi = {10.1145/3377930.3390149},
}
Figure