# American Institute of Mathematical Sciences

• Previous Article
Alliance strategy of construction and demolition waste recycling based on the modified shapley value under government regulation
• JIMO Home
• This Issue
• Next Article
A combined scalarization method for multi-objective optimization problems
doi: 10.3934/jimo.2020009

## Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison

 1 School of science, Southwest University of Science and Technology, Mianyang 621010, China 2 School of Management, Guangzhou University, Guangzhou 510006, China

* Corresponding author: Changzhi Wu, C.Wu@exchange.curtin.edu.au

Received  October 2018 Revised  September 2019 Published  January 2020

In multi-objective evolutionary algorithms (MOEAs), non-domina-ted sorting is one of the critical steps to locate efficient solutions. A large percentage of computational cost of MOEAs is on non-dominated sorting for it involves numerous comparisons. By now, there are more than ten different non-dominated sorting algorithms, but their numerical performance comparing with each other is not clear yet. It is necessary to investigate the advantage and disadvantage of these algorithms and consequently give suggestions to specific users and algorithm designers. Therefore, a comprehensively numerical study of non-dominated sorting algorithms is presented in this paper. Firstly, we design a population generator. This generator can generate populations with specific features, such as population size, number of Pareto fronts and number of points in each Pareto front. Then non-dominated sorting algorithms were tested using populations generated in certain structures, and results were compared with respect to number of comparisons and time consumption. Furthermore, In order to compare the performance of sorting algorithms in MOEAs, we embed them into a specific MOEA, dynamic sorting genetic algorithm (DSGA), and use these variations of DSGA to solve some multi-objective benchmarks. Results show that dominance degree sorting outperforms the other methods, fast non-dominance sorting performs the worst and the other sorting algorithms performs equally.

Citation: Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020009
##### References:

show all references

##### References:
Cases of dominance comparisons
Generate a point belonging to $\mathcal{F}_2$
An example of fixed features population generator
Time consumption for series (ⅰ)
Number of comparisons for series (ⅰ)
Time consumption for series (ⅱ)
Number of comparisons for series (ⅱ)
Time consumption for series (ⅲ)
Number of comparisons for series (ⅲ)
Time consumption for series (ⅳ)
Number of comparisons for series (ⅳ)
Time consumption for series (ⅴ)
Number of comparisons for series (ⅴ)
Average time consumption for algorithms
Average number of comparison for algorithms
Average Comparison efficiency for algorithms
Objective function value space
Numerical performance on SCH
Numerical performance on FON
Numerical performance on KUR
Five series of populations
 Series No. Description $m$ $k$ $N$ Series (ⅰ) fixed $m$ 3 1 $N=(200)$ various $k$ 3 2 $N=(100,100)$ $\sum N=200$ 3 3 $N=(70,70,60)$ 3 4 $N=(50,50,50,50)$ 3 5 $N=(40,40,40,40,40)$ 3 6 $N=(33,33,33,33,33,35)$ Series (ⅱ) fixed $m$ 3 5 $N=(10,10,10,10,10)$ fixed $k$ 3 5 $N=(20,20,20,20,20)$ various $N$ 3 5 $N=(30,30,30,30,30)$ 3 5 $N=(40,40,40,40,40)$ 3 5 $N=(50,50,50,50,50)$ 3 5 $N=(60,60,60,60,60)$ Series (ⅲ) various $m$ 2 5 $N=(20,20,20,20,20)$ fixed $k$ 3 5 $N=(20,20,20,20,20)$ fixed $N$ 4 5 $N=(20,20,20,20,20)$ 5 5 $N=(20,20,20,20,20)$ 6 5 $N=(20,20,20,20,20)$ 7 5 $N=(20,20,20,20,20)$ Series (ⅳ) fixed $m$ 3 1 $N=50$ fixed $k$ 3 1 $N=100$ various $N$ 3 1 $N=150$ 3 1 $N=200$ 3 1 $N=250$ 3 1 $N=300$ Series (ⅴ) fixed $m$ 3 10 $N_i=1,\; i=1,\cdots,k$ various $k$ 3 20 $N_i=1,\; i=1,\cdots,k$ various $N$ 3 30 $N_i=1,\; i=1,\cdots,k$ 3 40 $N_i=1,\; i=1,\cdots,k$ 3 50 $N_i=1,\; i=1,\cdots,k$ 3 60 $N_i=1,\; i=1,\cdots,k$ Series (vi) fixed $m$ 3 5 $N_i$ is a fixed $k$ 3 5 random integer various $N$ 3 5 between 1 and 50
 Series No. Description $m$ $k$ $N$ Series (ⅰ) fixed $m$ 3 1 $N=(200)$ various $k$ 3 2 $N=(100,100)$ $\sum N=200$ 3 3 $N=(70,70,60)$ 3 4 $N=(50,50,50,50)$ 3 5 $N=(40,40,40,40,40)$ 3 6 $N=(33,33,33,33,33,35)$ Series (ⅱ) fixed $m$ 3 5 $N=(10,10,10,10,10)$ fixed $k$ 3 5 $N=(20,20,20,20,20)$ various $N$ 3 5 $N=(30,30,30,30,30)$ 3 5 $N=(40,40,40,40,40)$ 3 5 $N=(50,50,50,50,50)$ 3 5 $N=(60,60,60,60,60)$ Series (ⅲ) various $m$ 2 5 $N=(20,20,20,20,20)$ fixed $k$ 3 5 $N=(20,20,20,20,20)$ fixed $N$ 4 5 $N=(20,20,20,20,20)$ 5 5 $N=(20,20,20,20,20)$ 6 5 $N=(20,20,20,20,20)$ 7 5 $N=(20,20,20,20,20)$ Series (ⅳ) fixed $m$ 3 1 $N=50$ fixed $k$ 3 1 $N=100$ various $N$ 3 1 $N=150$ 3 1 $N=200$ 3 1 $N=250$ 3 1 $N=300$ Series (ⅴ) fixed $m$ 3 10 $N_i=1,\; i=1,\cdots,k$ various $k$ 3 20 $N_i=1,\; i=1,\cdots,k$ various $N$ 3 30 $N_i=1,\; i=1,\cdots,k$ 3 40 $N_i=1,\; i=1,\cdots,k$ 3 50 $N_i=1,\; i=1,\cdots,k$ 3 60 $N_i=1,\; i=1,\cdots,k$ Series (vi) fixed $m$ 3 5 $N_i$ is a fixed $k$ 3 5 random integer various $N$ 3 5 between 1 and 50
Multi-objective test problems
 Pro. $n$ Variable Objective bounds functions SCH 1 $[-5,10]$ $\begin{array}{l}f_1(x)=x^2 \\f_2(x)=(x-2)^2\end{array}$ FON 3 $[-4,4]$ $\begin{array}{l}f_1(x)=1-\exp(-\sum_{i=1}^3(x_i-\frac{1}{\sqrt{3}})^2)\\f_2(x)=1-\exp(-\sum_{i=1}^3(x_i+\frac{1}{\sqrt{3}})^2)\end{array}$ KUR 3 $[-5,5]$ $\begin{array}{l}f_1(x)=\sum_{i=1}^{n-1}(-10\exp(-0.2\sqrt{x_i^2+x_{i+1}^2}\; ))\\ f_2(x)=\sum_{i=1}^n(|x_i|^{0.8}+5\sin^3(x_i))\end{array}$
 Pro. $n$ Variable Objective bounds functions SCH 1 $[-5,10]$ $\begin{array}{l}f_1(x)=x^2 \\f_2(x)=(x-2)^2\end{array}$ FON 3 $[-4,4]$ $\begin{array}{l}f_1(x)=1-\exp(-\sum_{i=1}^3(x_i-\frac{1}{\sqrt{3}})^2)\\f_2(x)=1-\exp(-\sum_{i=1}^3(x_i+\frac{1}{\sqrt{3}})^2)\end{array}$ KUR 3 $[-5,5]$ $\begin{array}{l}f_1(x)=\sum_{i=1}^{n-1}(-10\exp(-0.2\sqrt{x_i^2+x_{i+1}^2}\; ))\\ f_2(x)=\sum_{i=1}^n(|x_i|^{0.8}+5\sin^3(x_i))\end{array}$

2019 Impact Factor: 1.366