What is non-dominated sorting genetic algorithm III (NSGA-III)?

Key takeaways:

• NSGA-III is an advanced algorithm for solving optimization problems with multiple objectives (three or more).

• It extends the NSGA-II algorithm and uses strategies like non-dominated sorting, crowding distance, and elitism to find the best trade-offs between objectives.

• The algorithm generates a set of reference points to ensure solutions are well-distributed across the objective space.

• Diversity preservation is key, ensuring a spread of solutions across the Pareto front to prevent overcrowding in any part of the space.

• It is widely applied in fields like engineering design, machine learning, environmental sustainability, and robotics.

Non-dominated sorting genetic algorithm III (NSGA-III) is a multi-objective optimization algorithm inspired by genetic algorithms. It is an extension of NSGA-II and is designed to handle problems with three or more objectives.

NSGA-III seeks to identify a group of solutions not dominated by any other solution in terms of many overlapping objectives. It uses a variety of strategies, including non-dominated sorting, crowding distance computation, and elitism, to direct the search toward the Pareto-optimalPareto Optimality (also called Pareto Efficiency) is a concept from economics, decision theory, and game theory that refers to a state of allocation of resources in which it is impossible to make any one individual or preference criterion better off without making at least one individual or criterion worse off. front, which symbolizes the trade-off between many objectives in which no solution is superior to others in all objectives at the same time.

Features of NSGA-III

The key features of NSGA-III include:

1. Non-dominated sorting: Solutions are ranked based on their dominant relationship with other solutions, leading to the identification of Pareto fronts.

2. Crowding distance calculation: Solutions within the same Pareto frontIn optimization problems, the Pareto frontier (or Pareto front) is the set of all Pareto optimal solutions. It visualizes the trade-offs between conflicting objectives. For instance, in a cost-performance trade-off, points on the Pareto frontier represent designs where you cannot improve performance without increasing cost. are further diversified based on their crowding distance, promoting the exploration of the entire Pareto front.

3. Elitism: The best solutions from the current population are preserved and passed to the next generation to maintain diversity and prevent premature convergence.

4. Diversity preservation: NSGA-III encourages spreading solutions across the Pareto front, ensuring a representative set of trade-off solutions.

How NSGA-III Works

The working mechanism of NSGA-III is divided into several steps:

• Initialization: Like any genetic algorithm, NSGA-III starts by generating an initial population of individuals (solutions). These individuals are evaluated based on their objective function values.

• Reference point generation: The algorithm generates a set of reference points. These points are chosen to be evenly distributed across the objective space. The number of reference points is typically a function of the number of objectives.

• Non-dominated sorting and crowding distance: The population is sorted using the non-dominated sorting procedure, and a crowding distance is calculated. However, instead of using crowding distance as a selection criterion (as in NSGA-II), NSGA-III associates each individual with the nearest reference point.

• Selection: Individuals are selected based on their rank and proximity to the reference points. A niche preservation strategy is applied to ensure that solutions are spread out and that no part of the Pareto front is over-represented.

• Genetic operators (crossover and mutation): Genetic operators such as crossover and mutation are applied to the selected population to generate offspring for the next generation. These offspring are evaluated, and the selection process continues until the stopping criteria are met.

• Termination: The algorithm terminates when a predefined number of generations is reached, or when the population converges to the optimal Pareto front.

Here is the flowchart illustration for better understanding.

Applications of NSGA-III

NSGA-III has been successfully applied to a wide range of multi-objective optimization problems, particularly those with many objectives. Some common applications include:

• Engineering design: NSGA-III has been used in various engineering fields to optimize designs involving multiple conflicting criteria, such as minimizing cost while maximizing performance.

• Machine learning and AI: In problems such as hyperparameter optimization or neural network architecture search, where multiple objectives (e.g., accuracy, speed, and memory usage) need to be balanced.

• Environmental and sustainability problems: In sustainability studies, NSGA-III can optimize the trade-offs between environmental, economic, and social factors.

• Robotics: NSGA-III is also useful in multi-objective path planning and control in robotics, where objectives such as time, energy consumption, and safety need to be optimized simultaneously.

Advantages of NSGA-III

• Effective for high-dimensional problems: The reference point-based approach allows NSGA-III to effectively handle problems with many objectives, ensuring a good distribution of solutions across the Pareto front.

• Diversity preservation: By associating solutions with reference points, NSGA-III ensures that the population maintains diversity throughout the optimization process.

• Scalability: NSGA-III is scalable to problems with a large number of objectives and can handle up to hundreds or even thousands of objectives in some cases.

Quiz

A quick quiz to test your understanding of NSGA III.

Conclusion

NSGA-III is a powerful multi-objective evolutionary algorithm designed to handle complex optimization problems involving a large number of objectives. By introducing a reference-point-based approach, NSGA-III ensures a diverse and well-distributed set of solutions on the Pareto front, making it highly suitable for high-dimensional objective spaces. Whether used in engineering, AI, or sustainability, NSGA-III has proven its worth in providing high-quality solutions to challenging real-world problems.