# American Institute of Mathematical Sciences

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}$
 [1] 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 [2] 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 [3] 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 [4] 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 [5] Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019130 [6] 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 [7] 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 [8] Han Yang, Jia Yue, Nan-jing Huang. Multi-objective robust cross-market mixed portfolio optimization under hierarchical risk integration. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018177 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] Zongmin Li, Jiuping Xu, Wenjing Shen, Benjamin Lev, Xiao Lei. Bilevel multi-objective construction site security planning with twofold random phenomenon. Journal of Industrial & Management Optimization, 2015, 11 (2) : 595-617. doi: 10.3934/jimo.2015.11.595 [15] Lorena Rodríguez-Gallego, Antonella Barletta Carolina Cabrera, Carla Kruk, Mariana Nin, Antonio Mauttone. Establishing limits to agriculture and afforestation: A GIS based multi-objective approach to prevent algal blooms in a coastal lagoon. Journal of Dynamics & Games, 2019, 6 (2) : 159-178. doi: 10.3934/jdg.2019012 [16] Zixue Guo, Fengxuan Song, Yumeng Zheng, Zefang He. An improved fuzzy linear weighting method of multi-objective programming problems and its application. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020175 [17] Masoud Mohammadzadeh, Alireza Arshadi Khamseh, Mohammad Mohammadi. A multi-objective integrated model for closed-loop supply chain configuration and supplier selection considering uncertain demand and different performance levels. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1041-1064. doi: 10.3934/jimo.2016061 [18] Azam Moradi, Jafar Razmi, Reza Babazadeh, Ali Sabbaghnia. An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (2) : 855-879. doi: 10.3934/jimo.2018074 [19] Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200 [20] Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

2018 Impact Factor: 1.025