Introduction
Basic concepts of multi-objective optimization and non-dominated sorting
-
Step 1) Initialize the index i to 1.
-
Step 2) Find all solutions which are not dominated by any solution in P and move them from P to \(F_i\); \(i=i+1\).
-
Step 3) If P is empty, stop; otherwise, go to Step 2.
Effectiveness of non-dominated sorting for multi- and many-objective optimization
Effectiveness for multi-objective optimization
Effectiveness for many-objective optimization
Rectifications of Pareto dominance for many-objective optimization
Efficiency of non-dominated sorting for multi- and many-objective optimization
Main non-dominated sorting methods and their time complexity
Methods |
\(N=100\)
|
\(N=500\)
| ||
---|---|---|---|---|
\(M=2\)
|
\(M=3\)
|
\(M=2\)
|
\(M=3\)
| |
FNS | 1.6E+7 | 1.9E+7 | 4.0E+8 | 4.7E+8 |
Generalized Jensen’s sort | 5.0E+5 |
1.1E+6
| 3.8E+6 |
7.9E+6
|
Divide-and-conquer sort | 5.6E+6 | 8.0E+6 | 1.2E+8 | 2.0E+8 |
Deductive sort | 5.2E+6 | 7.7E+6 | 1.2E+8 | 1.9E+8 |
Corner sort | 4.6E+6 | 6.6E+6 | 10.0E+7 | 1.5E+8 |
M-front | 3.8E+6 | 5.1E+6 | 8.8E+7 | 1.1E+8 |
T-ENS | 3.1E+6 | 1.5E+6 | 6.9E+7 | 2.0E+7 |
ENS-SS |
3.9E+5
| 4.2E+6 |
2.6E+6
| 9.8E+7 |
Efficient non-dominated sorting for multi-objective optimization
Methods |
\(N=100\)
|
\(N=500\)
| ||
---|---|---|---|---|
\(M=2\)
|
\(M=3\)
|
\(M=2\)
|
\(M=3\)
| |
FNS | 18.98 | 4.18 | 93.84 | 4.59 |
Generalized Jensen’s sort | 16.98 | 21.13 | 16.73 | 4.82 |
Divide-and-conquer sort | 14.02 | 2.91 | 41.41 | 2.39 |
Deductive sort | 6.94 | 1.82 | 30.47 | 1.98 |
Corner sort | 15.60 | 3.65 | 46.74 | 2.78 |
M-front | 43.18 | 9.39 | 66.51 | 3.41 |
T-ENS | 10.25 | 1.26 | 33.95 |
0.51
|
ENS-SS |
1.00
|
1.00
|
1.00
| 1.00 |
Efficient non-dominated sorting for many-objective optimization
Methods |
\(N=100\)
|
\(N=500\)
| ||
---|---|---|---|---|
\(M=5\)
|
\(M=10\)
|
\(M=5\)
|
\(M=10\)
| |
FNS | 2.1E+7 | 2.8E+7 | 5.3E+8 | 6.6E+8 |
Generalized Jensen’s sort | 4.6E+6 | 6.7E+6 | 4.7E+7 | 8.8E+7 |
Divide-and-conquer sort | 1.0E+7 | 1.4E+7 | 2.5E+8 | 3.1E+8 |
Deductive sort | 1.0E+7 | 1.4E+7 | 2.5E+8 | 3.0E+8 |
Corner sort | 9.2E+6 | 1.4E+7 | 1.9E+8 | 2.5E+8 |
M-front | 1.2E+7 | 2.5E+7 | 2.3E+7 | 5.5E+8 |
ENS-SS | 6.5E+6 | 1.0E+7 | 1.5E+8 | 2.1E+8 |
T-ENS |
1.7E+6
|
2.8E+6
|
1.8E+7
|
2.4E+7
|
Methods |
\(N=100\)
|
\(N=500\)
| ||
---|---|---|---|---|
\(M=5\)
|
\(M=10\)
|
\(M=5\)
|
\(M=10\)
| |
FNS | 3.97 | 4.17 | 11.15 | 10.57 |
Generalized Jensen’s sort | 58.97 | 71.43 | 57.60 | 92.60 |
Divide-and-conquer sort | 2.67 | 2.67 | 6.09 | 5.65 |
Deductive sort | 1.91 | 2.06 | 5.27 | 4.90 |
Corner sort | 3.66 | 3.51 | 7.27 | 6.08 |
M-front | 10.53 | 13.20 | 11.10 | 14.13 |
ENS-SS | 1.13 | 1.36 | 3.14 | 3.32 |
T-ENS |
1.00
|
1.00
|
1.00
|
1.00
|
Methods | 1000 Points | 10,000 Points | ||
---|---|---|---|---|
\(M=5\)
|
\(M=10\)
|
\(M=5\)
|
\(M=10\)
| |
FNS | 2.9E+6 | 3.0E+6 | 2.9E+8 | 3.0E+8 |
Generalized Jensen’s sort | 2.3E+5 |
3.5E+5
|
5.4E+6
|
1.3E+7
|
Divide-and-conquer sort | 8.9E+5 | 1.5E+6 | 5.0E+7 | 1.4E+8 |
Deductive sort | 7.5E+5 | 1.5E+6 | 3.3E+7 | 1.4E+8 |
Corner sort | 5.9E+5 | 1.2E+6 | 2.7E+7 | 1.0E+8 |
M-front | 9.0E+5 | 2.6E+6 | 5.4E+7 | 2.1E+8 |
ENS-SS | 4.9E+5 | 1.0E+6 | 2.7E+7 | 9.4E+7 |
T-ENS |
1.7E+5
| 3.7E+5 | 9.1E+6 | 2.5E+7 |
Methods | 1000 Points | 10,000 Points | ||
---|---|---|---|---|
\(M=5\)
|
\(M=10\)
|
\(M=5\)
|
\(M=10\)
| |
FNS | 7.98 | 4.61 | 12.14 | 4.69 |
Generalized Jensen’s sort | 36.69 | 32.19 | 11.02 | 10.99 |
Divide-and-conquer sort | 3.32 | 2.59 | 3.31 | 2.45 |
Deductive sort | 2.40 | 2.35 | 1.88 | 2.28 |
Corner sort | 2.99 | 2.94 | 2.59 | 3.01 |
M-front | 5.95 | 6.77 | 4.04 | 4.82 |
ENS-SS | 2.00 | 1.46 | 2.37 | 1.39 |
T-ENS |
1.00
|
1.00
|
1.00
|
1.00
|
Approximate non-dominated sorting for many-objective optimization
Problems | KnEA | Two_Arch2 | ||
---|---|---|---|---|
\(M=5\)
|
\(M=10\)
|
\(M=5\)
|
\(M=10\)
| |
DTLZ1 | 0.59 | 0.53 | 0.64 | 0.53 |
DTLZ2 | 0.82 | 0.68 | 0.75 | 0.71 |
DTLZ3 | 0.60 | 0.46 | 0.63 | 0.49 |
DTLZ4 | 0.74 | 0.68 | 0.79 | 0.76 |
DTLZ5 | 0.55 | 0.47 | 0.39 | 0.44 |
DTLZ6 | 0.54 | 0.56 | 0.43 | 0.52 |
DTLZ7 | 0.59 | 0.5 | 0.50 | 0.44 |
WFG1 | 0.60 | 0.56 | 0.66 | 0.55 |
WFG2 | 0.59 | 0.54 | 0.65 | 0.63 |
WFG3 | 0.65 | 0.58 | 0.52 | 0.50 |
WFG4 | 0.75 | 0.72 | 0.74 | 0.76 |
WFG5 | 0.76 | 0.69 | 0.79 | 0.81 |
WFG6 | 0.73 | 0.69 | 0.74 | 0.76 |
WFG7 | 0.76 | 0.71 | 0.79 | 0.81 |
WFG8 | 0.65 | 0.62 | 0.68 | 0.67 |
WFG9 | 0.69 | 0.72 | 0.80 | 0.77 |
Problems |
\(M=5\)
|
\(M=10\)
| ||
---|---|---|---|---|
T-ENS | A-ENS | T-ENS | A-ENS | |
DTLZ1 |
\(4.5969\hbox {E}{-}1\pm 8.82\hbox {E}{-}2\)
|
\(\mathbf{5.0734E }{-}\mathbf{1 }\pm \mathbf{1.25E }{-}\mathbf{1 }\)
|
\(\mathbf{2.7163E }{-}\mathbf{1 }\pm \mathbf{1.41E }{-}\mathbf{1 }\)
|
\(7.9948\hbox {E}{-}2\pm 1.02\hbox {E}{-}1\)
|
DTLZ2 |
\(\mathbf{6.1657E }{-}\mathbf{1 }\pm \mathbf{6.15E }{-}\mathbf{3 }\)
|
\(6.0946\hbox {E}{-}1\pm 8.69\hbox {E}{-}3\)
|
\(8.1704\hbox {E}{-}1\pm 6.24\hbox {E}{-}2\)
|
\(\mathbf{8.4099E }{-}\mathbf{1 }\pm \mathbf{1.18E }{-}\mathbf{2 }\)
|
DTLZ3 |
\(5.6254\hbox {E}{-}2\pm 1.04\hbox {E}{-}1\)
|
\(\mathbf{2.6701E }{-}\mathbf{1 }\pm \mathbf{7.27E }{-}\mathbf{2 }\)
|
\(3.9095\hbox {E}{-}3\pm 1.26\hbox {E}{-}2\)
|
\(\mathbf{6.3055E }{-}\mathbf{2 }\pm \mathbf{7.43E }{-}\mathbf{2 }\)
|
DTLZ4 |
\(\mathbf{6.1858E }{-}\mathbf{1 }\pm \mathbf{6.89E }{-}\mathbf{3 }\)
|
\(6.1811\hbox {E}{-}1\pm 6.61\hbox {E}{-}3\)
|
\(8.0266\hbox {E}{-}1\pm 2.05\hbox {E}{-}2\)
|
\(\mathbf{8.3580E }{-}\mathbf{1 }\pm \mathbf{1 }.\mathbf{66E }{-}\mathbf{2 }\)
|
DTLZ5 |
\(\mathbf{7.4163E }{-}\mathbf{2 }\pm \mathbf{1.80E }{-}\mathbf{2 }\)
|
\(7.3073\hbox {E}{-}2\pm 2.46\hbox {E}{-}2\)
|
\(\mathbf{3.8298E }{-}{} \mathbf {2} \pm \mathbf{1.25E }{-}\mathbf{2 }\)
|
\(3.5344\hbox {E}{-}2\pm 2.08\hbox {E}{-}2\)
|
DTLZ6 |
\(2.4864\hbox {E}{-}2\pm 1.87\hbox {E}{-}2\)
|
\(\mathbf{3.4327E }{-}\mathbf{2 }\pm \mathbf{2.08E }{-}\mathbf{2 }\)
|
\(\mathbf{1.6162E }{-}\mathbf{2 }\pm \mathbf{2.29E }{-}\mathbf{2 }\)
|
\(2.8049\hbox {E}{-}4\pm 8.72\hbox {E}{-}4\)
|
DTLZ7 |
\(1.3594\hbox {E}{-}1\pm 6.57\hbox {E}{-}3\)
|
\(\mathbf{1.4844E }{-}\mathbf{1 }\pm \mathbf{5.74E }{-}\mathbf{3 }\)
|
\(2.2713\hbox {E}{-}2\pm 8.14\hbox {E}{-}3\)
|
\(\mathbf{9.9292E }{-}\mathbf{2 }\pm \mathbf{7.58E }{-}\mathbf{3 }\)
|
WFG1 |
\(9.7626\hbox {E}{-}1\pm 2.32\hbox {E}{-}2\)
|
\(\mathbf{9.8972E }{-}\mathbf{1 }\pm \mathbf{8.03E }{-}\mathbf{3 }\)
|
\(9.4577\hbox {E}{-}1\pm 8.51\hbox {E}{-}2\)
|
\(\mathbf{9.9397E }{-}\mathbf{1 }\pm \mathbf{2.66E }{-}\mathbf{3 }\)
|
WFG2 |
\(\mathbf{9.7379E }{-}\mathbf{1 }\pm \mathbf{4.23E }{-}\mathbf{2 }\)
|
\(9.2167\hbox {E}{-}1\pm 9.42\hbox {E}{-}2\)
|
\(9.8899\hbox {E}{-}1\pm 1.93\hbox {E}{-}3\)
|
\(\mathbf{9.9603E }{-}\mathbf{1 }\pm \mathbf{2.87E }{-}\mathbf{3 }\)
|
WFG3 |
\(5.3516\hbox {E}{-}1\pm 1.40\hbox {E}{-}2\)
|
\(\mathbf{5.6173E }{-}\mathbf{1 }\pm \mathbf{2 }.\mathbf{11E }{-}{} \mathbf {2} \)
|
\(5.3188\hbox {E}{-}1\pm 1.73\hbox {E}{-}2\)
|
\(\mathbf{5.5059E }{-}\mathbf{1 }\pm \mathbf{1.33E }{-}\mathbf{2 }\)
|
WFG4 |
\(\mathbf{5.6356E }{-}\mathbf{1 }\pm \mathbf{9.52E }{-}\mathbf{3 }\)
|
\(5.6327\hbox {E}{-}1\pm 7.44\hbox {E}{-}3\)
|
\(7.7241\hbox {E}{-}1\pm 2.30\hbox {E}{-}2\)
|
\(\mathbf{7.9026E }{-}\mathbf{1 }\pm \mathbf{1.09E }{-}\mathbf{2 }\)
|
WFG5 |
\(\mathbf{5.4986E }{-}\mathbf{1 }\pm \mathbf{5.80E }{-}\mathbf{3 }\)
|
\(5.4724\hbox {E}{-}1\pm 5.75\hbox {E}{-}3\)
|
\(\mathbf{7.6269E }{-}\mathbf{1 }\pm \mathbf{5.32E }{-}\mathbf{3 }\)
|
\(7.5885\hbox {E}{-}1\pm 4.79\hbox {E}{-}3\)
|
WFG6 |
\(\mathbf{5.3199E }{-}\mathbf{1 }\pm \mathbf{2.63E }{-}\mathbf{2 }\)
|
\(5.1521\hbox {E}{-}1\pm 1.53\hbox {E}{-}2\)
|
\(7.2757\hbox {E}{-}1\pm 3.80\hbox {E}{-}2\)
|
\(\mathbf{7.3183E }{-}\mathbf{1 }\pm \mathbf{2.00E }{-}\mathbf{2 }\)
|
WFG7 |
\(6.1116\hbox {E}{-}1\pm 7.31\hbox {E}{-}3\)
|
\(\mathbf{6.1254E }{-}\mathbf{1 }\pm \mathbf{4 }.\mathbf{73E }{-}{} \mathbf {3} \)
|
\(8.2764\hbox {E}{-}1\pm 9.16\hbox {E}{-}3\)
|
\(\mathbf{8.2897E }{-}\mathbf{1 }\pm \mathbf{1.17E }{-}\mathbf{2 }\)
|
WFG8 |
\(\mathbf{3.7022E }{-}\mathbf{1 }\pm \mathbf{2.14E }{-}\mathbf{2 }\)
|
\(3.6682\hbox {E}{-}1\pm 2.72\hbox {E}{-}2\)
|
\(\mathbf{5.9964E }{-}\mathbf{1 }\pm \mathbf{4.96E }{-}\mathbf{2 }\)
|
\(5.8005\hbox {E}{-}1\pm 3.96\hbox {E}{-}2\)
|
WFG9 |
\(4.9760\hbox {E}{-}1\pm 6.52\hbox {E}{-}2\)
|
\(\mathbf{5.2891E }{-}\mathbf{1 }\pm \mathbf{4.38E }{-}\mathbf{2 }\)
|
\(6.8623\hbox {E}{-}1\pm 7.20\hbox {E}{-}2\)
|
\(\mathbf{7.0326E }{-}\mathbf{1 }\pm \mathbf{4.68E }{-}\mathbf{2 }\)
|
Problems |
\(M=5\)
|
\(M=10\)
| ||
---|---|---|---|---|
T-ENS | A-ENS | T-ENS | A-ENS | |
DTLZ1 |
\(\mathbf{8.6562E }{-}\mathbf{1 }\pm \mathbf{2.11E }{-}\mathbf{2 }\)
|
\(8.2886\hbox {E}{-}1\pm 2.08\hbox {E}{-}2\)
|
\(\mathbf{8.7591E }{-}\mathbf{1 }\pm \mathbf{4.92E }{-}\mathbf{2 }\)
|
\(7.9605\hbox {E}{-}1\pm 4.67\hbox {E}{-}2\)
|
DTLZ2 |
\(\mathbf{5.7334E }{-}\mathbf{1 }\pm \mathbf{5.88E }{-}\mathbf{3 }\)
|
\(5.6916\hbox {E}{-}1\pm 7.30\hbox {E}{-}3\)
|
\(4.7341\hbox {E}{-}1\pm 3.09\hbox {E}{-}2\)
|
\(\mathbf{6.7170E }{-}\mathbf{1 }\pm \mathbf{2.89E }{-}\mathbf{2 }\)
|
DTLZ3 |
\(\mathbf{3.0047E }{-}\mathbf{1 }\pm \mathbf{4.14E }{-}\mathbf{2 }\)
|
\(2.4114\hbox {E}{-}1\pm 3.13\hbox {E}{-}2\)
|
\(2.3976\hbox {E}{-}1\pm 1.27\hbox {E}{-}1\)
|
\(\mathbf{2.5976E }{-}\mathbf{1 }\pm \mathbf{5.31E }{-}\mathbf{2 }\)
|
DTLZ4 |
\(\mathbf{5.4961E }{-}\mathbf{1 }\pm \mathbf{1.05E }{-}\mathbf{2 }\)
|
\(5.4904\hbox {E}{-}1\pm 1.15\hbox {E}{-}2\)
|
\(5.4429\hbox {E}{-}1\pm 3.98\hbox {E}{-}2\)
|
\(\mathbf{7.0587E }{-}\mathbf{1 }\pm \mathbf{1.46E }{-}\mathbf{2 }\)
|
DTLZ5 |
\(1.3372\hbox {E}{-}1\pm 7.98\hbox {E}{-}3\)
|
\(\mathbf{1.3770E }{-}\mathbf{1 }\pm \mathbf{8.76E }{-}\mathbf{3 }\)
|
\(5.2870\hbox {E}{-}2\pm 1.55\hbox {E}{-}2\)
|
\(\mathbf{8.0355E }{-}\mathbf{2 }\pm \mathbf{2.34E }{-}\mathbf{2 }\)
|
DTLZ6 |
\(1.1627\hbox {E}{-}1\pm 1.09\hbox {E}{-}2\)
|
\(\mathbf{1.2888E }{-}\mathbf{1 }\pm \mathbf{1.81E }{-}\mathbf{2 }\)
|
\(9.8949\hbox {E}{-}3\pm 1.54\hbox {E}{-}2\)
|
\(\mathbf{5.9620E }{-}\mathbf{2 }\pm \mathbf{1.26E }{-}\mathbf{2 }\)
|
DTLZ7 |
\(1.3042\hbox {E}{-}1\pm 1.65\hbox {E}{-}2\)
|
\(\mathbf{1.4944E }{-}\mathbf{1 }\pm \mathbf{1.16E }{-}\mathbf{2 }\)
|
\(8.4290\hbox {E}{-}2\pm 2.32\hbox {E}{-}2\)
|
\(\mathbf{1.0447E }{-}\mathbf{1 }\pm \mathbf{1.15E }{-}\mathbf{2 }\)
|
WFG1 |
\(9.8852\hbox {E}{-}1\pm 1.22\hbox {E}{-}3\)
|
\(\mathbf{9.8861E }{-}\mathbf{1 }\pm \mathbf{1.48E }{-}\mathbf{3 }\)
|
\(9.9069\hbox {E}{-}1\pm 1.29\hbox {E}{-}3\)
|
\(\mathbf{9.9436E }{-}\mathbf{1 }\pm \mathbf{8.20E }{-}\mathbf{4 }\)
|
WFG2 |
\(9.1682\hbox {E}{-}1\pm 9.08\hbox {E}{-}2\)
|
\(\mathbf{9.5573E }{-}\mathbf{1 }\pm \mathbf{6.89E }{-}\mathbf{2 }\)
|
\(9.9005\hbox {E}{-}1\pm 3.14\hbox {E}{-}3\)
|
\(\mathbf{9.9036E }{-}\mathbf{1 }\pm \mathbf{2.82E }{-}\mathbf{3 }\)
|
WFG3 |
\(\mathbf{5.6637E }{-}\mathbf{1 }\pm \mathbf{1.03E }{-}\mathbf{2 }\)
|
\(5.6437\hbox {E}{-}1\pm 1.20\hbox {E}{-}2\)
|
\(5.6233\hbox {E}{-}1\pm 8.87\hbox {E}{-}3\)
|
\(\mathbf{5.7551E }{-}\mathbf{1 }\pm \mathbf{1.61E }{-}\mathbf{2 }\)
|
WFG4 |
\(5.1069\hbox {E}{-}1\pm 1.00\hbox {E}{-}2\)
|
\(\mathbf{5.1718E }{-}\mathbf{1 }\pm \mathbf{9.87E }{-}\mathbf{3 }\)
|
\(4.9015\hbox {E}{-}1\pm 1.85\hbox {E}{-}2\)
|
\(\mathbf{5.1932E }{-}\mathbf{1 }\pm \mathbf{2.24E }{-}\mathbf{2 }\)
|
WFG5 |
\(4.9430\hbox {E}{-}1\pm 7.43\hbox {E}{-}3\)
|
\(\mathbf{5.0298E }{-}\mathbf{1 }\pm \mathbf{6.10E }{-}\mathbf{3 }\)
|
\(4.7617\hbox {E}{-}1\pm 2.18\hbox {E}{-}2\)
|
\(\mathbf{5.4869E }{-}\mathbf{1 }\pm \mathbf{1.80E }{-}\mathbf{2 }\)
|
WFG6 |
\(\mathbf{4.8227E }{-}\mathbf{1 }\pm \mathbf{1.95E }{-}\mathbf{2 }\)
|
\(4.8073\hbox {E}{-}1\pm 1.32\hbox {E}{-}2\)
|
\(4.5144\hbox {E}{-}1\pm 2.37\hbox {E}{-}2\)
|
\(\mathbf{5.3360E }{-}\mathbf{1 }\pm \mathbf{3.17E }{-}\mathbf{2 }\)
|
WFG7 |
\(5.5479\hbox {E}{-}1\pm 7.28\hbox {E}{-}3\)
|
\(\mathbf{5.6390E }{-}\mathbf{1 }\pm \mathbf{7.92E }{-}\mathbf{3 }\)
|
\(5.2117\hbox {E}{-}1\pm 1.95\hbox {E}{-}2\)
|
\(\mathbf{5.6443E }{-}\mathbf{1 }\pm \mathbf{2.51E }{-}\mathbf{2 }\)
|
WFG8 |
\(3.4962\hbox {E}{-}1\pm 1.44\hbox {E}{-}2\)
|
\(\mathbf{3.6521E }{-}\mathbf{1 }\pm \mathbf{2.29E }{-}\mathbf{2 }\)
|
\(2.8372\hbox {E}{-}1\pm 3.96\hbox {E}{-}2\)
|
\(\mathbf{3.4275E }{-}\mathbf{1 }\pm \mathbf{5.26E }{-}\mathbf{2 }\)
|
WFG9 |
\(\mathbf{4.9517E }{-}\mathbf{1 }\pm \mathbf{7.85E }{-}\mathbf{3 }\)
|
\(4.9494\hbox {E}{-}1\pm 3.12\hbox {E}{-}2\)
|
\(4.5549\hbox {E}{-}1\pm 2.92\hbox {E}{-}2\)
|
\(\mathbf{4.9367E }{-}\mathbf{1 }\pm \mathbf{2.83E }{-}\mathbf{2 }\)
|