# 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  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] 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 [2] Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109 [3] Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013 [4] Bilel Elbetch, Tounsia Benzekri, Daniel Massart, Tewfik Sari. The multi-patch logistic equation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021025 [5] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [6] Liang Huang, Jiao Chen. The boundedness of multi-linear and multi-parameter pseudo-differential operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020291 [7] Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364 [8] Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171 [9] Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034 [10] Hongguang Ma, Xiang Li. Multi-period hazardous waste collection planning with consideration of risk stability. Journal of Industrial & Management Optimization, 2021, 17 (1) : 393-408. doi: 10.3934/jimo.2019117 [11] Hongyu Cheng, Shimin Wang. Response solutions to harmonic oscillators beyond multi–dimensional brjuno frequency. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020222 [12] Nicholas Geneva, Nicholas Zabaras. Multi-fidelity generative deep learning turbulent flows. Foundations of Data Science, 2020, 2 (4) : 391-428. doi: 10.3934/fods.2020019 [13] Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 [14] Gi-Chan Bae, Christian Klingenberg, Marlies Pirner, Seok-Bae Yun. BGK model of the multi-species Uehling-Uhlenbeck equation. Kinetic & Related Models, 2021, 14 (1) : 25-44. doi: 10.3934/krm.2020047 [15] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [16] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 [17] Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021005 [18] A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441 [19] Feimin Zhong, Jinxing Xie, Yuwei Shen. Bargaining in a multi-echelon supply chain with power structure: KS solution vs. Nash solution. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020172 [20] Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002

2019 Impact Factor: 1.366