Integration of Preferences in Decomposition Multiobjective Optimization

Ke Li, Renzhi Chen, Geyong Min, Xin YaoIEEE Trans. Cybernetics 2018 · DOI

Abstract

Rather than a whole Pareto-optimal front, which demands too many points (especially in a high-dimensional space), the decision maker (DM) may only be interested in a partial region, called the region of interest (ROI). In this case, solutions outside this region can be noisy to the decision-making procedure. Even worse, there is no guarantee that we can find the preferred solutions when tackling problems with complicated properties or many objectives. In this paper, we develop a systematic way to incorporate the DM's preference information into the decomposition-based evolutionary multiobjective optimization methods. Generally speaking, our basic idea is a nonuniform mapping scheme by which the originally evenly distributed reference points on a canonical simplex can be mapped to new positions close to the aspiration-level vector supplied by the DM. By this means, we are able to steer the search process toward the ROI either directly or interactively and also handle many objectives. Meanwhile, solutions lying on the boundary can be approximated as well given the DM's requirements. Furthermore, the extent of the ROI is intuitively understandable and controllable in a closed form. Extensive experiments on a variety of benchmark problems with 2 to 10 objectives, fully demonstrate the effectiveness of our proposed method for approximating the preferred solutions in the ROI.

Introduction

In Multiobjective Optimization Problems (MOPs), the goal is typically to find the Pareto-optimal front (PF)—the set of solutions where no objective can be improved without degrading another. However, as the number of objectives increases, the PF grows exponentially in size. Providing a Decision Maker (DM) with a massive set of trade-off points often leads to cognitive overload and includes many irrelevant solutions.

Visualizing the Region of Interest (ROI) and the aspiration level $z^r$ on a Pareto Front.

Most DMs are interested only in a specific Region of Interest (ROI) based on their aspiration levels. While decomposition-based algorithms like MOEA/D are effective, they usually distribute search points evenly across the entire PF. Existing methods to bias these algorithms toward an ROI are often ad-hoc, lacking precise control over the ROI size or losing critical boundary information that provides context for the DM.

The Nonuniform Mapping Scheme (NUMS)

The core contribution of this work is the Nonuniform Mapping Scheme (NUMS), which "warps" the search space of decomposition-based evolutionary algorithms toward a user’s preferred region.

Reference Point Warping and Control

NUMS takes an evenly distributed set of reference points on a canonical simplex and applies a nonlinear power-function mapping. This shifts the density of points toward a "pivot point" defined by the DM's aspiration levels. Crucially, the authors derive a closed-form relationship (Theorem 1) linking a user-defined parameter $\tau$ (the relative size of the ROI) to the internal mapping exponent $\eta$. This allows a DM to intuitively specify the desired search area (e.g., "within 20% of the total front area") while the algorithm handles the underlying mathematics.

Boundary Preservation

A key feature of NUMS is its ability to preserve information about the PF's boundaries. By using a "flag" mechanism, the algorithm can either concentrate all search points within the ROI or maintain a subset of points on the boundary. This dual approach provides high-resolution solutions in the preferred region while still illustrating the global limits of the problem, which is vital for normalizing DM expectations.

Reference point distributions showing (a) uniform, (b) biased toward the center with boundary preservation, and (c) biased toward the center without boundary.

Subproblem Reformulation

To ensure the search effectively targets the aspiration level—even when goals are overly ambitious or unattainable—the authors utilize a modified Tchebycheff function. This function incorporates the aspiration-level vector as an anchor, steering the population toward the ROI regardless of the PF's geometry.

Experimental Evaluation

The method was rigorously tested using the DTLZ and WFG benchmark suites across 2, 3, 5, 8, and 10 objectives. These benchmarks include complex PF shapes such as sharp convex/concave regions and disconnected segments.

Key Results

  • Superior ROI Approximation: Using the Preference-based Hypervolume (R-HV) metric, NUMS-assisted algorithms (e.g., MOEA/D-STM, NSGA-III) consistently outperformed state-of-the-art preference algorithms like R-NSGA-II.
  • High-Dimensional Stability: In many-objective scenarios (8 and 10 objectives), NUMS maintained a well-distributed set of solutions within the ROI, whereas competing methods often suffered from extreme crowding or failed to converge.
  • Robustness: The scheme proved effective whether the DM's aspiration levels were attainable (inside the PF) or unattainable (beyond the PF).

Conclusion

NUMS provides a mathematically precise and intuitively controllable framework for preference-based multiobjective optimization. By bridging abstract weight vectors with real-world aspiration levels, it reduces cognitive load for DMs without sacrificing global context. Future research will explore extending NUMS to handle multiple disjoint ROIs and applying the scheme to discrete combinatorial optimization problems.

Summary updated

BibTeX
@article{li2018integration,
  author = {Ke Li and Renzhi Chen and Geyong Min and Xin Yao},
  title = {{Integration of Preferences in Decomposition Multiobjective Optimization}},
  journal = {IEEE Trans. Cybernetics},
  year = {2018},
  doi = {10.1109/tcyb.2018.2859363},
}
Figure