NSGA-III: New Sampler for Many Objective Optimization

Optuna v3.2 was released at the end of May. In this article, we will explain one of its new features, the NSGAIIISampler. NSGA-III [1,4] is an improved version of NSGA-II, which is one of the most popular multi-objective optimization algorithms today, for the objective functions with high dimensional outputs (many-objective functions). The new sampler excels at generating diverse solutions, even when the number of objectives becomes larger.

Overview

Multi-objective optimization problems have multiple objective functions to be simultaneously optimized. Unlike single-objective optimization problems, the goal of multi-objective optimization problems is not to find the best (single) optimal solution, but to find the so-called Pareto front, which represents the trade-off between objective function values.

Multi-objective optimization problems have typically targeted a relatively low number of dimensions, two or three to be precise, making them easily visualizable. However, as the demand for optimizing a larger number of objective functions has increased, the challenges associated with objective functions with high dimensional outputs have become apparent. Such problems with objective dimensions higher than three are termed as many-objective optimization problems and have been extensively researched in recent years. NSGA-III is one of those algorithms which has been developed to handle many-objective optimization problems.

In many-objective optimization, several challenges have been identified:

1. Most individuals in each generation become part of the Pareto front, making it necessary to determine their relative superiority or inferiority within the same rank.
2. Designing evaluation metrics for performance and diversity becomes difficult, and computationally high cost.
3. Representing and visualizing the Pareto front becomes challenging.

These challenges arise when dealing with higher-dimensional objective spaces. Recognizing these issues has sparked a growing interest in developing algorithms to address them.

NSGA-III

NSGA-III was proposed as a modified version of NSGA-II, focusing on improvement on the first issue mentioned above. In NSGA-II, the surviving individuals in each generation are selected in the following steps:

1. Individuals are ranked based on the dominance of their objective values, and selected to survive from the top rank.
2. When the predefined number of individuals to survive is not exactly fulfilled, the rest of individuals are selected based on so-called crowding distance, a measure which aims to ensure diversity.

Here, what we call the crowding distance is calculated based on the difference between two adjacent points for each objective value dimension. One of the characteristic part of this metric is that the individual which has the maximum or minimum values for each objective axis is always set to +♾️ because they have only one adjacent point. Therefore, the crowding distance sort based-selection always chooses the individuals with the maximum or minimum values for any axis, and the larger the objective dimension be, the more axis-focussed the solution becomes. NSGA-III attempts to solve the problem by replacing this procedure with the niching procedure. Overall selection process is described as follows:

The figure above visualizes the behavior of each algorithm in a two-dimensional objective space. The red points represent the individuals in the Pareto front, while the blue points and circles represent the individuals in the borderline front. The points indicate the selected individuals by each algorithm, while the circles represent the individuals that were not selected.

1. Individuals were ranked based on the dominance of their objective values, and selected to survive from the top rank.
2. When the predefined number of individuals is not exactly fulfilled, the rest of individuals are selected to guarantee diversity so that they are allocated to the predefined reference points as evenly as possible.

Furthermore, the following figure visualizes the results obtained by running each algorithm on a 9-dimensional test function called DTLZ6, in every three dimensions. In the actual results, the results of NSGA-II (red) are concentrated near the axes, while the results of NSGA-III with default reference points (blue) are more evenly spread across each dimension.

Hands on

As an example, the constrained Binh and Korn function is optimized here.

import optuna


def objective(trial):
    x = trial.suggest_float("x", -15, 30)
    y = trial.suggest_float("y", -15, 30)

    c0 = (x - 5) ** 2 + y**2 - 25
    c1 = -((x - 8) ** 2) - (y + 3) ** 2 + 7.7

    trial.set_user_attr("constraint", (c0, c1))

    v0 = 4 * x**2 + 4 * y**2
    v1 = (x - 5) ** 2 + (y - 5) ** 2

    return v0, v1


def constraints(trial):
    return trial.user_attrs["constraint"]


sampler = optuna.samplers.NSGAIIISampler(constraints_func=constraints)
study = optuna.create_study(directions=["minimize", "minimize"], sampler=sampler)
study.optimize(objective, n_trials=2000)

fig = optuna.visualization.plot_pareto_front(study, include_dominated_trials=False)
fig.show()

Executing the above source code will output the following graph.

Use cases

NSGA-III is a useful algorithm when there are various evaluation criteria, aiming to obtain a set of solutions which covers the Pareto front uniformly and facilitate decision-making. There have been reported cases where NSGA-III yielded better results compared to existing methods in applications.

Crop Configuration [5]

In large-scale agriculture, determining which crops to plant and how to allocate them to the fields is an important issue. In this paper, the author first created a predictive model for yield and prices based on historical data and then optimized the portfolio of cultivated crops with this model and NSGA-III algorithm, considering seven competing objectives: profit per crop, price risk, yield risk, scatteredness of fields with the same crop, the impact of crop rotation, amount of fertilizer and pesticides.

Task allocation [2]

It is an important administrative issue to allocate university staff to teaching tasks so that they do not interfere with research work as much as possible. This study utilizes NSGA-III to allocate tasks to university staff with various specializations and research work schedules and based on seven criteria: imbalance in workload distribution, the average load, the maximum peak load, the staff per module, staff dissatisfaction with teaching allocations, and allocation churn.

Design exploration [3]

In this paper, the authors employed NSGA-III to explore the performance improvement of jamming grippers, a robotic hand which uses granular materials and vacuum pressure to securely grip and manipulate objects of various shapes and sizes. The authors set grasping performance of jamming grippers on different sized cubes and spheres as objectives and examined how the grain morphologies of internally used particles affects them.

Conclusion

In this blog, we introduced a new sampler called NSGAIIISampler, which was added in Optuna v3.2. NSGAIIISampler is an improved algorithm based on the NSGA-II for multi-objective optimization, designed to obtain a more diverse set of solutions even when the dimension of the objectives is large. Additionally, it allows for customized reference points to concentrate the search on specific areas instead of uniformly spreading it. For details in implementation, please refer to the documentation of NSGAIIISampler. When confronted with many objective problems, we encourage you to employ NSGAIIISampler, the new feature, to enhance your optimization strategies.

Reference

[1] K. Deb and H. Jain: “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints,” 2014.

[2] J. E. Fieldsend: “University staff teaching allocation: formulating and optimising a many-objective problem,” 2017

[3] S. G. Fitzgerald, G. W. Delaney, D. Howard, and F. Maire: “Evolving polydisperse soft robotic jamming grippers,” 2022

[4] H. Jain and K. Deb: “An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: handling constraints and extending to an adaptive approach,” 2014.

[5] O. Marko, D. Pavlović, V. Crnojević, and K. Deb: “Optimisation of crop configuration using NSGA-III with categorical genetic operators,” 2019.