A Pareto-Compliant Surrogate Approach for Multiobjective Optimization

Ilya Loshchilov, Marc Schoenauer, Michèle Sébag1979

TL;DR

This paper introduces a novel "Pareto-Compliant Surrogate Approach" (PARETO-SVM) for multiobjective optimization. Instead of building separate models for each objective, it uses a single, global surrogate model to characterize the Pareto front and dominated regions, aiming to significantly speed up evolutionary optimization processes.

What Problem Does This Paper Address?

Evolutionary Multi-Objective Optimization (EMO) algorithms are powerful for finding a set of optimal trade-off solutions (the Pareto front) for problems with multiple conflicting objectives. However, EMO algorithms often require a very large number of objective function evaluations, making them computationally expensive, especially for complex or real-world problems. Traditional surrogate approaches in EMO typically build a separate predictive model for each objective. This paper addresses the inefficiency of this per-objective modeling by proposing a single, unified surrogate model that captures the global structure of the Pareto front and the dominated region simultaneously. This aims to provide a more efficient way to guide the search and accelerate convergence towards the true Pareto front.

Methods

The core of the proposed method is the "Aggregated Surrogate Model" (ASM), which is built using Support Vector Machines (SVMs). Specifically, it combines ideas from:

  • One-class SVM: Used to characterize the dominated points. This helps in identifying regions of the search space that are unlikely to contain optimal solutions.
  • Support Vector Regression (SVR): Used to "clamp" the Pareto front onto a single value. This helps in approximating the shape and location of the current Pareto front.

The ASM is trained on points belonging to the current Pareto set and points known to be dominated. The goal is to map Pareto points to a specific range and dominated points to a lower range. This unified model is then embedded within an EMO algorithm (referred to as PARETO-SVM) to guide the generation of new candidate solutions, effectively filtering out unpromising offspring and focusing the search on promising areas.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic approach and its theoretical formulation, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Global Surrogate for Multiobjective Problems: The key innovation is the shift from per-objective surrogates to a single, global surrogate that understands the Pareto front's structure. This is a significant departure from many existing EMO surrogate methods.
  • Pareto Compliance: The surrogate model is designed to be "Pareto-compliant," meaning it explicitly tries to distinguish between Pareto-optimal solutions and dominated ones, and guides the search accordingly.
  • Efficiency Through Unified Modeling: By using a single model, the computational overhead of building and querying surrogates is potentially reduced compared to managing multiple models.
  • Potential for Faster Convergence: The ASM's ability to characterize both the Pareto front and the dominated region offers a more holistic view of the search space, which can lead to faster convergence to the true Pareto front.

Key Results

The paper presents the formulation of the ASM and the PARETO-SVM algorithm. While not providing extensive empirical results in this specific paper, it references prior work [3] which showed that SVM-informed MOEAs using 2-10 pre-children could be 1.5-3 times faster than original MOEAs in terms of function evaluations for certain bi-objective problems. The authors also note that the current formulation might lead to premature convergence if the diversity aspect is not handled, as the ASM primarily focuses on Pareto compliance.

Limitations and Future Work

  • Formulation Complexity: The authors acknowledge that the formulation of the ASM optimization problem can be over-constrained, leading to generalization errors. They discuss a modification involving a "k factor" to address this, but suggest further work is needed to fully understand and resolve this issue.
  • Parameter Sensitivity: The new formulation introduces an additional parameter 'D', making the learning problem potentially harder.
  • Diversity Handling: The current ASM formulation does not explicitly address diversity, which can lead to premature convergence, especially with a large number of pre-children.
  • Quality Indicators: The paper raises the question of how to efficiently incorporate quality indicators like hypervolume into the surrogate model. They explore the idea of using hypervolume contribution for fitness estimation of dominated points but note that it's not straightforward and more complex criteria might be needed.
  • Future Work: The authors suggest further research into understanding the phenomenon of the 'k factor' and its relation to the multi-objective landscape. They also highlight the appeal of incorporating other quality indicators into the surrogate model.

Summary updated

Abstract

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
BibTeX
@misc{loshchilov1979pareto,
  author = {Ilya Loshchilov and Marc Schoenauer and Michèle Sébag},
  title = {{A Pareto-Compliant Surrogate Approach for Multiobjective Optimization}},
  year = {1979},
}
Figure