Introduction
Welcome to this blog post on Non-dominated sorting genetic algorithm II (NSGA-II), a fast and elitist algorithm for multi-objective optimization problems. In the field of optimization, many real-world problems involve multiple conflicting objectives that need to be simultaneously optimized. Traditional single-objective optimization approaches are insufficient in handling such scenarios, as they often lead to a single optimal solution that neglects the trade-offs between different objectives.
To address this challenge, multi-objective optimization algorithms have been developed to find a set of solutions, known as the Pareto front, which represents a trade-off between conflicting objectives. NSGA-II is one of the most widely used and influential algorithms in this domain. It incorporates innovative features to improve the convergence speed and maintain diversity among the solutions.
NSGA-II
NSGA-II is a powerful evolutionary algorithm specifically designed to solve multi-objective optimization problems. Developed by Deb et al. (2002)1, it has since gained significant recognition and popularity in the field of optimization.
NSGA-II algorithm follows the general flow of a Genetic Algorithm (GA), as implied by its name. In order to gain a better understanding of NSGA-II, let us delve into its steps different with GA:
Non-dominated sorting
NSGA-II uses a non-dominated sorting technique to classify individuals into different fronts based on their dominance relationship, which we denote it as nondomination rank. Dominance refers to the ability of one solution to outperform another solution in at least one objective without being worse in any other objective. In minimization problem, we say solution $x$ dominates solution $y$ if:
\[f_i(x) \leq f_i(y) \quad \forall i \in \{1, 2, 3, \dots , m \}\] \[f_i(x) < f_i(y) \quad \exists i \in \{1, 2, 3, \dots , m \}\]where the number of objective functions is $m$ and $f_i( \cdot )$ is the objective value of $i$th objective function. Let’s delve into the non-dominated sorting through its pseudocode.
Fast non-dominated sorting in NSGA-II (Deb et al., 2002)1
NSGA-II calculates the nondomination rank of the solutions through non-dominated sorting.
Crowding distance assignment
To maintain diversity among solutions, NSGA-II assigns a crowding distance to individuals within each front. The crowding distance measures the density of solutions surrounding an individual in the objective space, allowing the algorithm to favor solutions that are less crowded. Let’s delve into the crowding distance assignment through its pseudocode.
Crowding distance assignment (Deb et al., 2002)1
NSGA-II calculates the crowding of the solutions in the same front through crowding distance assignment.
Selection
While GA compares the prioritization of solutions based on a single objective value, NSGA-II compares the prioritization of solutions using the non-domination rank and the crowding distance obtained from the aforementioned steps. We say solution $x$ is selected compared to solution $y$ (i.e., $x \prec_{n} y$) if:
$x_{rank} < y_{rank} \quad$ or
$x_{rank} = y_{rank} \quad$ and $\quad x_{distance} > y_{distance}$
where $x_{rank}$ is the nondomination rank of $x$ and $x_{distance}$ is the crowding distance of $x$.
Elitism
NSGA-II keeps superior solutions through elitism by preserving the best individuals from the previous generation in the current population. This guarantees that the best solutions are not lost over generations and helps in maintaining a good level of convergence.
Elitism procedure in NSGA-II (Deb et al., 2002)1
The NSGA-II algorithm iteratively repeats the steps of selection, variation (i.e., crossover and mutation), and elitism until a termination criterion is met, typically a predefined number of generations or a satisfactory level of convergence.
Example of NSGA-II flowchart
NSGA-II’s strength lies in its ability to efficiently converge to a diverse set of high-quality solutions along the Pareto front. By striking a balance between exploration and exploitation, it provides decision-makers with a comprehensive set of trade-off solutions, enabling them to make informed decisions based on their preferences and objectives.