Non-dominated Sorting Genetic Algorithm (NSGA-II)

Significant changes were applied to the original NSGA to create NSGA-II. The only common feature between the two was adopting non-dominated sorting. NSGA-II has Pareto archive $P$ and population $Q$ for genetic search just like Strength Pareto Evolutionarily Algorithm (SPEA). However, it uses Pareto archive more aggressively. In NSGA-II, the number of individuals in archive $P$ is $N$, and it is equal to the number of individuals in population $Q$. On the other hand, in SPEA, the best number of individuals in archive $P$ is generally perceived as one-fourth of the individuals in $Q$. Genetic operators of crossover and mutation are performed on population $Q^t$, and the selection for extracting the next generation was applied on set union $P^t\cup Q^t$, creating $p^{t+1}$. The selection consists of two mechanisms: “non-dominated sorting” and “crowding distance sorting.” $Q^{t+1}$ was generated from $P^{t+1}$ by means of selection, the so called “Mating selection.”

Meanwhile, Zitzler improved his SPEA. SPEA2 was proposed in 2001. SPEA2 was an improvement over SPEA in the following areas:

• the fitness calculation mechanism was modified to ensure effective convergence to the Pareto front,

• the archive $P$ has same number of individuals as population $Q$, and

• a new method of reducing individuals in the archive (archive truncation method) is used.

The second point mentioned above is the same as the mechanism used in NSGA-II. In addition, SPEA2 and NSGA-II have the following common points between them:

• crossover and mutation is done in searching population $Q$,

• archive for the next generation $p^{t+1}$ is selected from $P^t\cup Q^t$, and

• the next searching population $Q^{t+1}$ is selected from $P^{t+1}$.

In other words, the outline of the algorithm is similar in both NSGA-II and SPEA2, and the differences exist only in the definition of fitness, the reducing mechanism of the archive, and the selection for $P^{t+1}$. Today, these two algorithms are the main methods for the Multi-Objective Genetic Algorithm. It is also said that the performance of the two is almost even.