# American Institute of Mathematical Sciences

March  2021, 17(2): 1001-1023. 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  March 2021 Early access  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, 2021, 17 (2) : 1001-1023. 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}$
 [1] Zhongqiang Wu, Zongkui Xie. A multi-objective lion swarm optimization based on multi-agent. Journal of Industrial & Management Optimization, 2022  doi: 10.3934/jimo.2022001 [2] Henri Bonnel, Ngoc Sang Pham. Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions. Journal of Industrial & Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789 [3] Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097 [4] Yuan-mei Xia, Xin-min Yang, Ke-quan Zhao. A combined scalarization method for multi-objective optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2669-2683. doi: 10.3934/jimo.2020088 [5] Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055 [6] Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095 [7] Shungen Luo, Xiuping Guo. Multi-objective optimization of multi-microgrid power dispatch under uncertainties using interval optimization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021208 [8] Adriel Cheng, Cheng-Chew Lim. Optimizing system-on-chip verifications with multi-objective genetic evolutionary algorithms. Journal of Industrial & Management Optimization, 2014, 10 (2) : 383-396. doi: 10.3934/jimo.2014.10.383 [9] Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial & Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130 [10] Han Yang, Jia Yue, Nan-jing Huang. Multi-objective robust cross-market mixed portfolio optimization under hierarchical risk integration. Journal of Industrial & Management Optimization, 2020, 16 (2) : 759-775. doi: 10.3934/jimo.2018177 [11] Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021051 [12] Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089 [13] Danthai Thongphiew, Vira Chankong, Fang-Fang Yin, Q. Jackie Wu. An on-line adaptive radiation therapy system for intensity modulated radiation therapy: An application of multi-objective optimization. Journal of Industrial & Management Optimization, 2008, 4 (3) : 453-475. doi: 10.3934/jimo.2008.4.453 [14] Yu Chen, Yonggang Li, Bei Sun, Chunhua Yang, Hongqiu Zhu. Multi-objective chance-constrained blending optimization of zinc smelter under stochastic uncertainty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021169 [15] Xiliang Sun, Wanjie Hu, Xiaolong Xue, Jianjun Dong. Multi-objective optimization model for planning metro-based underground logistics system network: Nanjing case study. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021179 [16] Ping-Chen Lin. Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm. Journal of Industrial & Management Optimization, 2012, 8 (3) : 549-564. doi: 10.3934/jimo.2012.8.549 [17] Jian Xiong, Zhongbao Zhou, Ke Tian, Tianjun Liao, Jianmai Shi. A multi-objective approach for weapon selection and planning problems in dynamic environments. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1189-1211. doi: 10.3934/jimo.2016068 [18] Dušan M. Stipanović, Claire J. Tomlin, George Leitmann. A note on monotone approximations of minimum and maximum functions and multi-objective problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 487-493. doi: 10.3934/naco.2011.1.487 [19] Hamed Fazlollahtabar, Mohammad Saidi-Mehrabad. Optimizing multi-objective decision making having qualitative evaluation. Journal of Industrial & Management Optimization, 2015, 11 (3) : 747-762. doi: 10.3934/jimo.2015.11.747 [20] Tien-Fu Liang, Hung-Wen Cheng. Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method. Journal of Industrial & Management Optimization, 2011, 7 (2) : 365-383. doi: 10.3934/jimo.2011.7.365

2020 Impact Factor: 1.801