Overview of NSGA-III (Non-dominated Sorting Genetic Algorithm III), its algorithms and implementation examples

Overview 0f NSGA-III(Non-dominated Sorting Genetic Algorithm III)

NSGA-III is an Evolutionary Algorithm (EA) for Multi-Objective Optimization (MOO), specifically designed to solve problems with more than three objective functions (Many-Objective Optimization). The algorithm is designed to solve problems with more than three objective functions (Many-Objective Optimization).

It is an extended version of NSGA-II (Non-dominated Sorting Genetic Algorithm II) described in “Overview of NSGA-II (Non-dominated Sorting Genetic Algorithm II), algorithm and implementation examples” and is especially designed for solving problems with higher dimensional It aims to control the distribution of solutions appropriately, especially in high-dimensional objective spaces (four or more objectives).

The differences from NSGA-II are as follows.

NSGA-II uses Crowding Distance to maintain solution diversity, but the solution becomes sparse in higher dimensions, and an appropriate distribution of solutions cannot be obtained, NSGA-III uses Reference Points to control the distribution of solutions appropriately and can handle a large number of objective functions.

The algorithm procedure of NSGA-III is as follows

1. Generation of initial population: Randomly generate individuals
2. Reference Points: Design evenly distributed reference points in advance.
3. Crossover & Mutation: Crossover and mutation using genetic algorithms (GA)
4. Non-dominated Sorting: Ranking by dominance-inferiority relationship
5. Environmental Selection: Equalize the distribution of solutions by applying NSGA-III’s characteristic reference point-based selection
6. Update to Next Generation: Repeat a certain number of generations to obtain the optimal solution set (Pareto Front)

Advantages of NSGA-III include

• High dimensional multiobjective optimization is possible (equal solutions can be obtained for 4 or more objectives)
• Efficient search for optimal solutions using nondominated sorting
• Equal distribution of solutions across the Pareto front by utilizing reference points

Some of the challenges of NSGA-III are as follows

• Reference point setup is problem-dependent (requires design of appropriate reference points)
• High computational cost (non-dominated sorting becomes heavier as the number of objective functions increases)

Mounting example

The Pymoo Library is useful for implementing NSGA-III in Python. The following code solves a 3-objective optimization problem (ZDT3) with NSGA-III.

Installing the necessary libraries

pip install pymoo numpy matplotlib

NSGA-III implementation in Python

import numpy as np
import matplotlib.pyplot as plt
from pymoo.algorithms.moo.nsga3 import NSGA3
from pymoo.factory import get_problem, get_reference_directions
from pymoo.optimize import minimize
from pymoo.visualization.scatter import Scatter

# Three-objective optimization problem (DTLZ1)
problem = get_problem("dtlz1", n_var=7, n_obj=3)

# Set reference points (designed for proper distribution of solutions)
ref_dirs = get_reference_directions("das-dennis", 3, n_partitions=12)

# NSGA-III Algorithm Settings
algorithm = NSGA3(pop_size=100, ref_dirs=ref_dirs)

# Perform optimization
res = minimize(problem,
               algorithm,
               ('n_gen', 200),  # Number of generations
               seed=1,
               verbose=True)

# Visualization of results
plot = Scatter()
plot.add(res.F, facecolor="none", edgecolor="r")
plot.show()

Key Points of Implementation

1. Define optimization problem using pymoo: use 3-objective function “DTLZ1” as an example
2. Set up NSGA-III: provide reference points (get_reference_directions). Set population size (pop_size) to 100
3. Run optimization: 200 generations (n_gen=200)
4. Visualize results: Plot Pareto front using Scatter

Result: After running the above code, the 3D Pareto front is plotted in the red box, confirming that the solution obtained by NSGA-III is well distributed.

Application Examples

NSGA-III has been widely applied to problems requiring multi-objective optimization in particular, and is a very effective approach for optimization problems with four or more objective functions. The following are specific examples of NSGA-III applications.

1. Aircraft Design Optimization: In aircraft design, multiple objectives are involved, such as

• Fuel economy: minimize fuel consumption
• Speed: Maximize high-speed performance
• Cost: minimize manufacturing costs
• Safety: maximize safety metrics

NSGA-III optimizes these objective functions simultaneously to obtain the optimal design proposal (Pareto Front). From these design alternatives, the aircraft designer can select the best balance for a particular requirement.

2. Electric Vehicle (EV) Battery Design: NSGA-III can also be very useful in electric vehicle battery design. The following objective functions are involved in the design

• Energy density: maximize battery capacity
• Charge time: minimize charge speed
• Cost: minimize battery manufacturing costs
• Durability: maximize battery life

NSGA-III provides a solution to optimize these multiple objectives, allowing EV manufacturers to select the optimal battery specification.

3. supply chain optimization: NSGA-III can also be used in supply chain design. The main objectives will be to

• Cost reduction: minimize purchasing and transportation costs
• Inventory optimization: minimize inventory holding costs
• Lead time: minimize delivery time
• Risk management: minimize supply instability

NSGA-III optimizes these multiple trade-offs and helps companies design optimal supply chains.

4. green building design: Environmental considerations are also an important objective in building design, and NSGA-III can help optimize the following goals

• Energy efficiency: minimize building energy consumption
• Greenhouse gas emissions: minimize CO2 emissions
• Construction costs: minimize initial costs
• Indoor environmental quality: optimize indoor temperature and humidity

NSGA-III provides the optimal solution for sustainable building design.

5. financial portfolio optimization: In the financial industry, multiple objective functions need to be considered in the optimization of an investment portfolio, such as

• Return maximization: maximize the return on an investment
• Risk minimization: minimize the risk (volatility) of an investment
• Liquidity: Optimize the ease with which assets can be bought and sold.
• Cost: minimize trading fees and taxes

NSGA-III can simultaneously optimize these objectives and provide investors with the best portfolio options.

6. renewable energy generation system design: NSGA-III is also used in the design of renewable energy generation systems (wind and solar). Objective functions include the following

• Maximize power generation: Maximize the efficiency of power generation systems.
• Cost: minimize installation and operating costs
• Environmental impact: Maximize CO2 reduction
• Space Efficiency: Maximize the efficiency of space utilization at the installation site

With NSGA-III, an optimal power generation system can be designed with these objectives in mind.

7. Optimal design of healthcare and medical equipment: Multiple objectives exist in the design of medical equipment.

• Maximize diagnostic accuracy: Optimize the diagnostic accuracy of medical devices.
• Cost: Minimize manufacturing costs.
• Durability: Maximize the durability and longevity of medical devices
• Ease of use: Optimize ease of operation and user interface.

NSGA-III enables a design that simultaneously optimizes these multiple objectives and contributes to improving the quality of the final medical device.

reference book

This section describes reference books related to NSGA-III (Non-dominated Sorting Genetic Algorithm III).

1. “Multi-Objective Optimization Using Evolutionary Algorithms”

Author: Kalyanmoy Deb
Abstract: This book details the theory and practice of multi-objective optimization using evolutionary algorithms, covering a variety of multi-objective optimization methods including NSGA-II and NSGA-III algorithms. This book is a must-read for in-depth study of

2. “Evolutionary Algorithms for Solving Multi-Objective Problems”

Author: Carlos A. Coello Coello, A. D. C. (David) Chan
Abstract: This book focuses on evolutionary algorithms for solving multi-objective problems and provides a detailed description of various algorithms, including NSGA-III. The book covers a wide range of topics from basic theory of evolutionary algorithms to practical applications, making it useful in practice.

3. “Genetic Algorithms in Search, Optimization, and Machine Learning”

Author: David E. Goldberg
Abstract: A pioneering book on evolutionary algorithms, this book explains the theory and implementation of optimization using genetic algorithms (GAs), and is very useful for understanding the background of multi-objective optimization as it relates to NSGA-III.

4. “Practical Genetic Algorithms”

Authors: Randy L. Haupt, Sue Ellen Haupt
Abstract: Focuses on specific approaches to using genetic algorithms in practice and includes a practical guide that is also useful for implementing NSGA-III. 4. learn how to apply evolutionary algorithms to real-world problems.

5. “Introduction to Evolutionary Algorithms”

Authors: A.E. Eiben, J.E. Smith
Abstract: This book provides a broad overview of evolutionary algorithms, from the basics to applications, and helps the reader gain an understanding of the theoretical background and implementation of multi-objective optimization algorithms such as NSGA-III.

6. “Handbook of Evolutionary Computation.”

Editors: Thomas Bäck, David B. Fogel, Zbigniew Michalewicz
Description: A detailed guide to evolutionary computation, covering extensive coverage of the theory, implementation, and applications of genetic and multi-objective optimization algorithms, including chapters on modern algorithms such as NSGA-III and how to apply them in practice.

7. “An Introduction to MultiAgent Systems”

Author: Michael Wooldridge
Abstract: This book provides a basic understanding of evolutionary algorithms as well as multi-agent systems (MAS) and how evolutionary optimization algorithms such as NSGA-III apply to systems with multiple agents working together to find a solution.

References.

Deb, K., & Jain, H. (2014). “An Evolutionary Many-Objective Optimization Algorithm Using a Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints”.

IEEE Transactions on Evolutionary Computation, 18(4), 577-601.

Kalyanmoy Deb – “Multi-Objective Optimization Using Evolutionary Algorithms” (2001).
Carlos A. Coello Coello et al – “Evolutionary Algorithms for Solving Multi-Objective Problems” (2007)