Introduction and background
-
We utilize a more generalized method for finding the extremities (“surrogate corners”) to adjust the normalization bounds for \(M\ge 2\) objectives. The implicit assumptions specific to solving bi-objective problems [34] are thus removed.
-
Since the number of corners grows with the number of objectives, we introduce additional selection mechanisms to reduce the number of true evaluations directed towards corner search in lieu of infill search.
-
Lastly, we conduct numerical experiments on problems with up to 5 objectives with a limited budget to demonstrate that the proposed improvements lead to more consistency in achieving competitive results compared to other standard methods.
Methodology
General idea
Corner points in multi-objective problems
Corner search scheme
Corner selection for true evaluation
Algorithm implementation
FEs. | Initialization | D (no. of variables) | M (no. of objectives) | |
---|---|---|---|---|
Problem-specific settings | ||||
ZDT | 200 | 0.5 \(\times \) FE | 6 | 2 |
DTLZ | 200/300/400 | 0.5 \(\times \) FE | 6 | 2/3/5 |
WFG | 200/300/400 | 0.5 \(\times \) FE | 6 | 2/3/5 |
MAF | –/300/400 | 0.5 \(\times \) FE | 6 | –/3/5 |
Pop. size | Gens. | Evolutionary parameters | ||
Evolutionary search settings | ||||
Corner search | 100 | 100 | 0.8 (crossover rate) | 0.2 (mutation rate) |
20 (crossover index) | 30 (mutation index) | |||
Infill search | 100 | 100 | 0.8 (crossover rate) | 0.8 (scaling factor) |
Numerical experiments
Benchmark problems used
Algorithm and experimental settings
-
\(NormR_{ND}\), normalization bounds based on current non-dominated solutions.
-
\(NormR_{A}\), normalization bounds based on full archive.
-
\(NormR_{NDE}\), normalization bounds based on augmented ND solutions with extreme points identified from independent objective search, the method proposed in the preceding work [34].
-
\(NormR_{NDC} (S1)\), the proposed method that augments current ND solutions with corner points to define the normalization bounds. In this variant, all top M corners in the final population of the corner search are evaluated.
-
\(NormR_{NDC} (S2)\) the proposed method that augments current ND solutions with selected corner points to define the normalization bounds. Selective evaluation (as discussed in Sect. 2.4) is applied on the top M solutions in the final population of the surrogate corner search. Thus, among these M points, only those that are non-dominated with respect to the current ND front and lie outside the reference point bounds based on predicted values are evaluated. Silhouette analysis is not used in this variant.
Problems | \(NormR_A\) | \(NormR_{ND}\) | \(NormR_{NDE}\) | \(NormR_{NDC}\) | \(NormR_{NDC}\) | \(NormR_{NDC}\) |
---|---|---|---|---|---|---|
(archive) | (ND) | [34] | (S1) | (S2) | (S3) | |
mDTLZ1 | 0.7011 | 0.7014 | 0.7020 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7009 \(\approx _{1}\) \(\approx _{2}\) | 0.7012 \(\approx _{1}\) \(\approx _{2}\) | 0.7016 \(\approx _{1}\) \(\approx _{2}\) |
mDTLZ2 | 0.9915 | 0.9915 | 0.9915 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.9915 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.9915 \(\approx _{1}\) \(\downarrow _{2}\) | 0.9915 \(\approx _{1}\) \(\approx _{2}\) |
mDTLZ3 | 0.9908 | 0.991 | 0.9906 \(\approx _{1}\) \(\downarrow _{2}\) | 0.9905 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.9905 \(\approx _{1}\) \(\downarrow _{2}\) | 0.9906 \(\approx _{1}\) \(\downarrow _{2}\) |
mDTLZ4 | 0.7918 | 0.8265 | 0.8131 \(\approx _{1}\) \(\approx _{2}\) | 0.7941 \(\approx _{1}\) \(\approx _{2}\) | 0.8179 \(\approx _{1}\) \(\approx _{2}\) | 0.8335 \(\approx _{1}\) \(\approx _{2}\) |
iDTLZ1 | 0.2881 | 0.7007 | 0.7005 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7002 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7005 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7006 \(\uparrow _{1}\) \(\approx _{2}\) |
iDTLZ2 | 0.9715 | 0.9866 | 0.9855 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.9857 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.9862 \(\uparrow _{1}\) \(\approx _{2}\) | 0.9857 \(\uparrow _{1}\) \(\downarrow _{2}\) |
ZDT1 | 0.8649 | 0.4646 | 0.8664 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.8659 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.8659 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.8661 \(\uparrow _{1}\) \(\uparrow _{2}\) |
ZDT2 | 0.5360 | 0.5386 | 0.5387 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5385 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.5386 \(\uparrow _{1}\) \(\approx _{2}\) | 0.5386 \(\uparrow _{1}\) \(\approx _{2}\) |
ZDT3 | 0.7196 | 0.2973 | 0.7193 \(\approx _{1}\) \(\uparrow _{2}\) | 0.6500 \(\downarrow _{1}\) \(\uparrow _{2}\) | 0.7025 \(\downarrow _{1}\) \(\uparrow _{2}\) | 0.7201 \(\approx _{1}\) \(\uparrow _{2}\) |
ZDT6 | 0.4624 | 0.5105 | 0.4961 \(\approx _{1}\) \(\approx _{2}\) | 0.4470 \(\approx _{1}\) \(\downarrow _{2}\) | 0.4736 \(\approx _{1}\) \(\approx _{2}\) | 0.5049 \(\uparrow _{1}\) \(\approx _{2}\) |
DTLZ1 | 0.3111 | 0.7008 | 0.7005 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7002 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7003 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7004 \(\uparrow _{1}\) \(\downarrow _{2}\) |
DTLZ2 | 0.4095 | 0.4198 | 0.4196 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.4195 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.4196 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.4197 \(\uparrow _{1}\) \(\downarrow _{2}\) |
DTLZ3 | 0.0563 | 0.4155 | 0.4137 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.4135 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.4134 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.4133 \(\uparrow _{1}\) \(\downarrow _{2}\) |
DTLZ4 | 0.1478 | 0.1522 | 0.2140 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.1838 \(\approx _{1}\) \(\approx _{2}\) | 0.2043 \(\uparrow _{1}\) \(\approx _{2}\) | 0.1989 \(\uparrow _{1}\) \(\uparrow _{2}\) |
DTLZ7 | 0.5427 | 0.3534 | 0.5447 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5446 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5447 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5447 \(\uparrow _{1}\) \(\uparrow _{2}\) |
WFG1 | 0.1893 | 0.1900 | 0.1841 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.1761 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.1872 \(\approx _{1}\) \(\approx _{2}\) | 0.1867 \(\approx _{1}\) \(\approx _{2}\) |
WFG2 | 0.6617 | 0.6520 | 0.6695 \(\approx _{1}\) \(\approx _{2}\) | 0.6776 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.6506 \(\approx _{1}\) \(\approx _{2}\) | 0.6569 \(\approx _{1}\) \(\approx _{2}\) |
WFG3 | 0.6727 | 0.6655 | 0.6742 \(\approx _{1}\) \(\uparrow _{2}\) | 0.6723 \(\approx _{1}\) \(\uparrow _{2}\) | 0.6718 \(\approx _{1}\) \(\uparrow _{2}\) | 0.6729 \(\approx _{1}\) \(\uparrow _{2}\) |
WFG4 | 0.3476 | 0.3418 | 0.3463 \(\approx _{1}\) \(\uparrow _{2}\) | 0.349 \(\approx _{1}\) \(\uparrow _{2}\) | 0.3474 \(\approx _{1}\) \(\uparrow _{2}\) | 0.3468 \(\approx _{1}\) \(\uparrow _{2}\) |
WFG5 | 0.3646 | 0.3627 | 0.3634 \(\downarrow _{1}\) \(\approx _{2}\) | 0.362 \(\downarrow _{1}\) \(\approx _{2}\) | 0.3639 \(\downarrow _{1}\) \(\approx _{2}\) | 0.3635 \(\downarrow _{1}\) \(\approx _{2}\) |
WFG6 | 0.3644 | 0.3543 | 0.3629 \(\approx _{1}\) \(\approx _{2}\) | 0.3596 \(\approx _{1}\) \(\approx _{2}\) | 0.3587 \(\approx _{1}\) \(\approx _{2}\) | 0.3604 \(\approx _{1}\) \(\approx _{2}\) |
WFG7 | 0.3164 | 0.3129 | 0.3197 \(\approx _{1}\) \(\approx _{2}\) | 0.3254 \(\approx _{1}\) \(\uparrow _{2}\) | 0.3191 \(\approx _{1}\) \(\approx _{2}\) | 0.3222 \(\approx _{1}\) \(\uparrow _{2}\) |
WFG8 | 0.2189 | 0.2103 | 0.2177 \(\approx _{1}\) \(\approx _{2}\) | 0.2096 \(\approx _{1}\) \(\approx _{2}\) | 0.2141 \(\approx _{1}\) \(\approx _{2}\) | 0.2144 \(\approx _{1}\) \(\approx _{2}\) |
WFG9 | 0.3575 | 0.3578 | 0.3445 \(\approx _{1}\) \(\approx _{2}\) | 0.3542 \(\approx _{1}\) \(\approx _{2}\) | 0.3518 \(\approx _{1}\) \(\approx _{2}\) | 0.3526 \(\approx _{1}\) \(\approx _{2}\) |
Summary | Compared to \(NormR_A\) | \(\uparrow _{1}\) 10 \(\downarrow _{1}\) 3 | \(\uparrow _{1}\) 9 \(\downarrow _{1} \)5 | \(\uparrow _{1}\) 9 \(\downarrow _{1} \)2 | \(\uparrow _{1}\) 10 \(\downarrow _{1} \)1 | |
Compared to \(NormR_{ND}\) | \(\uparrow _{2}\) 7 \(\downarrow _{2} \) 6 | \(\uparrow _{2}\) 6 \(\downarrow _{2} \) 10 | \(\uparrow _{2}\) 5 \(\downarrow _{2} 5 \) | \(\uparrow _{2}\) 7 \(\downarrow _{2} 5\) |
Results and discussion
Comparison with conventional normalization methods (archive- and ND-based)
Problems | \(NormR_A\) | \(NormR_{ND}\) | \(NormR_{NDE}\) | \(NormR_{NDC}\) | \(NormR_{NDC}\) | \(NormR_{NDC}\) |
---|---|---|---|---|---|---|
(archive) | (ND) | [34] | (S1) | (S2) | (S3) | |
mDTLZ1 | 0.3009 | 0.3007 | 0.3002 \(\approx _{1}\) \(\approx _{2}\) | 0.2992 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.3010 \(\approx _{1}\) \(\approx _{2}\) | 0.3004 \(\approx _{1}\) \(\approx _{2}\) |
mDTLZ2 | 0.7381 | 0.7068 | 0.7375 \(\downarrow _{1}\) \(\uparrow _{2}\) | 0.7375 \(\downarrow _{1}\) \(\uparrow _{2}\) | 0.7378 \(\downarrow _{1}\) \(\uparrow _{2}\) | 0.7378 \(\downarrow _{1}\) \(\uparrow _{2}\) |
mDTLZ3 | 0.7333 | 0.7325 | 0.7317 \(\downarrow _{1}\) \(\approx _{2}\) | 0.7328 \(\downarrow _{1}\) \(\approx _{2}\) | 0.7324 \(\downarrow _{1}\) \(\approx _{2}\) | 0.7325 \(\downarrow _{1}\) \(\approx _{2}\) |
mDTLZ4 | 0.2140 | 0.2222 | 0.2225 \(\approx _{1}\) \(\approx _{2}\) | 0.2384 \(\approx _{1}\) \(\approx _{2}\) | 0.2511 \(\approx _{1}\) \(\approx _{2}\) | 0.1981 \(\approx _{1}\) \(\approx _{2}\) |
iDTLZ2 | 0.7213 | 0.7348 | 0.7289 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7272 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7268 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7269 \(\uparrow _{1}\) \(\downarrow _{2}\) |
MAF1 | 0.2992 | 0.3074 | 0.3070 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.3057 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.3066 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.3068 \(\uparrow _{1}\) \(\downarrow _{2}\) |
MAF2 | 0.7284 | 0.7286 | 0.7264 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.7259 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.7285 \(\approx _{1}\) \(\approx _{2}\) | 0.7285 \(\approx _{1}\) \(\approx _{2}\) |
MAF3 | 0.7881 | 0.8744 | 0.8631 \(\approx _{1}\) \(\approx _{2}\) | 0.8208 \(\approx _{1}\) \(\downarrow _{2}\) | 0.7863 \(\approx _{1}\) \(\approx _{2}\) | 0.8585 \(\approx _{1}\) \(\approx _{2}\) |
MAF4 | 0.5525 | 0.7227 | 0.6817 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.6695 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.6607 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.6814 \(\uparrow _{1}\) \(\downarrow _{2}\) |
MAF5 | 0.1404 | 0.1404 | 0.1489 \(\approx _{1}\) \(\approx _{2}\) | 0.1479 \(\approx _{1}\) \(\approx _{2}\) | 0.1402 \(\approx _{1}\) \(\approx _{2}\) | 0.1412 \(\approx _{1}\) \(\approx _{2}\) |
MAF6 | 0.0039 | 0.2515 | 0.2493 \(\uparrow _{1}\) \(\approx _{2}\) | 0.2469 \(\uparrow _{1}\) \(\approx _{2}\) | 0.2496 \(\uparrow _{1}\) \(\approx _{2}\) | 0.2489 \(\uparrow _{1}\) \(\approx _{2}\) |
DTLZ1 | 0.2263 | 1.0953 | 1.0963 \(\uparrow _{1}\) \(\approx _{2}\) | 1.0937 \(\uparrow _{1}\) \(\downarrow _{2}\) | 1.0944 \(\uparrow _{1}\) \(\approx _{2}\) | 1.0953 \(\uparrow _{1}\) \(\approx _{2}\) |
DTLZ2 | 0.7163 | 0.7633 | 0.7632 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7620 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.7631 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7632 \(\uparrow _{1}\) \(\approx _{2}\) |
DTLZ3 | 0.0265 | 0.737 | 0.7387 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7366 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7362 \(\uparrow _{1}\) \(\approx _{2}\) | 0.7375 \(\uparrow _{1}\) \(\approx _{2}\) |
DTLZ4 | 0.2176 | 0.2101 | 0.2094 \(\approx _{1}\) \(\approx _{2}\) | 0.2559 \(\approx _{1}\) \(\uparrow _{2}\) | 0.2419 \(\approx _{1}\) \(\uparrow _{2}\) | 0.2322 \(\approx _{1}\) \(\approx _{2}\) |
DTLZ7 | 0.5757 | 0.4774 | 0.5815 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5813 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5814 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5815 \(\uparrow _{1}\) \(\uparrow _{2}\) |
WFG1 | 0.3493 | 0.3382 | 0.3433 \(\approx _{1}\) \(\approx _{2}\) | 0.3315 \(\approx _{1}\) \(\approx _{2}\) | 0.3329 \(\approx _{1}\) \(\approx _{2}\) | 0.3441 \(\approx _{1}\) \(\approx _{2}\) |
WFG2 | 1.1949 | 1.0197 | 1.0345 \(\downarrow _{1}\) \(\approx _{2}\) | 1.0382 \(\downarrow _{1}\) \(\uparrow _{2}\) | 1.0338 \(\downarrow _{1}\) \(\uparrow _{2}\) | 1.0234 \(\downarrow _{1}\) \(\approx _{2}\) |
WFG3 | 0.5190 | 0.5193 | 0.5171 \(\approx _{1}\) \(\approx _{2}\) | 0.5164 \(\approx _{1}\) \(\approx _{2}\) | 0.5194 \(\approx _{1}\) \(\approx _{2}\) | 0.5190 \(\approx _{1}\) \(\approx _{2}\) |
WFG4 | 0.6183 | 0.6200 | 0.6155 \(\approx _{1}\) \(\downarrow _{2}\) | 0.6151 \(\approx _{1}\) \(\downarrow _{2}\) | 0.6174 \(\approx _{1}\) \(\approx _{2}\) | 0.6231 \(\approx _{1}\) \(\approx _{2}\) |
WFG5 | 0.6549 | 0.6509 | 0.6465 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.6538 \(\approx _{1}\) \(\approx _{2}\) | 0.6540 \(\approx _{1}\) \(\approx _{2}\) | 0.6529 \(\approx _{1}\) \(\approx _{2}\) |
WFG6 | 0.6686 | 0.6707 | 0.6586 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.6642 \(\approx _{1}\) \(\downarrow _{2}\) | 0.6686 \(\approx _{1}\) \(\approx _{2}\) | 0.6700 \(\approx _{1}\) \(\approx _{2}\) |
WFG7 | 0.5850 | 0.5746 | 0.5739 \(\approx _{1}\) \(\approx _{2}\) | 0.5786 \(\approx _{1}\) \(\approx _{2}\) | 0.5779 \(\approx _{1}\) \(\approx _{2}\) | 0.5813 \(\approx _{1}\) \(\approx _{2}\) |
WFG8 | 0.3954 | 0.3956 | 0.4020 \(\approx _{1}\) \(\approx _{2}\) | 0.4050 \(\approx _{1}\) \(\approx _{2}\) | 0.4021 \(\approx _{1}\) \(\approx _{2}\) | 0.4103 \(\approx _{1}\) \(\uparrow _{2}\) |
WFG9 | 0.5561 | 0.5714 | 0.5567 \(\approx _{1}\) \(\approx _{2}\) | 0.5418 \(\approx _{1}\) \(\downarrow _{2}\) | 0.5509 \(\approx _{1}\) \(\downarrow _{2}\) | 0.5623 \(\approx _{1}\) \(\approx _{2}\) |
Summary | Compared to \(NormR_A\) | \(\uparrow _{1}\) 8 \(\downarrow _{1} 6\) | \(\uparrow _{1}\) 8 \(\downarrow _{1} 5 \) | \(\uparrow _{1}\) 8 \(\downarrow _{1} 3 \) | \(\uparrow _{1}\) 8 \(\downarrow _{1} 3\) | |
Compared to \(NormR_{ND}\) | \(\uparrow _{2}\) 2 \(\downarrow _{2} 7 \) | \(\uparrow _{2}\) 4 \(\downarrow _{2} 11 \) | \(\uparrow _{2}\) 4 \(\downarrow _{2} 4 \) | \(\uparrow _{2}\) 3 \(\downarrow _{2} 3\) |
Problems |
\(NormR_A\)
|
\(NormR_{ND}\)
|
\(NormR_{NDE}\)
|
\(NormR_{NDC}\)
|
\(NormR_{NDC}\)
|
\(NormR_{NDC}\)
|
---|---|---|---|---|---|---|
(archive) | (ND) | [34] | (S1) | (S2) | (S3) | |
mDTLZ1 | 0.0214 | 0.0213 | 0.0213 \(\downarrow _{1}\) \(\approx _{2}\) | 0.0214 \(\approx _{1}\) \(\approx _{2}\) | 0.0214 \(\approx _{1}\) \(\approx _{2}\) | 0.0213 \(\approx _{1}\) \(\approx _{2}\) |
mDTLZ2 | 0.2329 | 0.2323 | 0.2321 \(\downarrow _{1}\) \(\approx _{2}\) | 0.2321 \(\downarrow _{1}\) \(\approx _{2}\) | 0.2326 \(\downarrow _{1}\) \(\uparrow _{2}\) | 0.2326 \(\downarrow _{1}\) \(\uparrow _{2}\) |
mDTLZ3 | 0.2305 | 0.2303 | 0.2293 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.2293 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.2304 \(\approx _{1}\) \(\approx _{2}\) | 0.2304 \(\approx _{1}\) \(\approx _{2}\) |
mDTLZ4 | 0.0065 | 0.0063 | 0.0043 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.0056 \(\approx _{1}\) \(\approx _{2}\) | 0.0067 \(\approx _{1}\) \(\approx _{2}\) | 0.0063 \(\approx _{1}\) \(\approx _{2}\) |
iDTLZ2 | 0.2189 | 0.2288 | 0.2163 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.2188 \(\approx _{1}\) \(\downarrow _{2}\) | 0.2148 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.2134 \(\downarrow _{1}\) \(\downarrow _{2}\) |
MAF1 | 0.0182 | 0.0216 | 0.0213 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.0212 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.0214 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.0216 \(\uparrow _{1}\) \(\approx _{2}\) |
MAF3 | 1.5865 | 1.59 | 1.5921 \(\uparrow _{1}\) \(\approx _{2}\) | 1.5907 \(\uparrow _{1}\) \(\approx _{2}\) | 1.5896 \(\uparrow _{1}\) \(\approx _{2}\) | 1.5898 \(\uparrow _{1}\) \(\approx _{2}\) |
MAF4 | 0.1473 | 0.224 | 0.1613 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.1632 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.1575 \(\uparrow _{1}\) \(\downarrow _{2}\) | 0.1495 \(\uparrow _{1}\) \(\downarrow _{2}\) |
MAF5 | 0.5568 | 0.5662 | 0.6225 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.6637 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.5664 \(\approx _{1}\) \(\approx _{2}\) | 0.5844 \(\approx _{1}\) \(\approx _{2}\) |
DTLZ1 | 1.3406 | 1.5294 | 1.5272 \(\uparrow _{1}\) \(\approx _{2}\) | 1.5293 \(\uparrow _{1}\) \(\approx _{2}\) | 1.5241 \(\uparrow _{1}\) \(\approx _{2}\) | 1.5317 \(\uparrow _{1}\) \(\approx _{2}\) |
DTLZ2 | 1.1930 | 1.2663 | 1.2835 \(\uparrow _{1}\) \(\uparrow _{2}\) | 1.2820 \(\uparrow _{1}\) \(\uparrow _{2}\) | 1.2854 \(\uparrow _{1}\) \(\uparrow _{2}\) | 1.2853 \(\uparrow _{1}\) \(\uparrow _{2}\) |
DTLZ3 | 0.8338 | 1.1742 | 1.2322 \(\uparrow _{1}\) \(\uparrow _{2}\) | 1.2540 \(\uparrow _{1}\) \(\uparrow _{2}\) | 1.2552 \(\uparrow _{1}\) \(\uparrow _{2}\) | 1.2567 \(\uparrow _{1}\) \(\uparrow _{2}\) |
DTLZ4 | 0.6440 | 0.6128 | 0.6351 \(\approx _{1}\) \(\uparrow _{2}\) | 0.6678 \(\approx _{1}\) \(\uparrow _{2}\) | 0.6294 \(\approx _{1}\) \(\approx _{2}\) | 0.6083 \(\approx _{1}\) \(\approx _{2}\) |
WFG1 | 0.2172 | 0.1979 | 0.1547 \(\approx _{1}\) \(\approx _{2}\) | 0.3349 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.2737 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.2732 \(\uparrow _{1}\) \(\uparrow _{2}\) |
WFG2 | 1.5756 | 1.5729 | 1.5706 \(\downarrow _{1}\) \(\downarrow _{2}\) | 1.5705 \(\approx _{1}\) \(\downarrow _{2}\) | 1.5749 \(\approx _{1}\) \(\approx _{2}\) | 1.5754 \(\approx _{1}\) \(\approx _{2}\) |
WFG3 | 0.3572 | 0.3625 | 0.3695 \(\uparrow _{1}\) \(\approx _{2}\) | 0.3643 \(\uparrow _{1}\) \(\approx _{2}\) | 0.3679 \(\uparrow _{1}\) \(\uparrow _{2}\) | 0.3638 \(\approx _{1}\) \(\approx _{2}\) |
WFG4 | 1.0582 | 1.0612 | 1.0505 \(\approx _{1}\) \(\downarrow _{2}\) | 1.0558 \(\approx _{1}\) \(\approx _{2}\) | 1.0569 \(\approx _{1}\) \(\approx _{2}\) | 1.0688 \(\approx _{1}\) \(\approx _{2}\) |
WFG5 | 1.0765 | 1.0721 | 1.0626 \(\approx _{1}\) \(\approx _{2}\) | 1.0777 \(\approx _{1}\) \(\approx _{2}\) | 1.0615 \(\approx _{1}\) \(\approx _{2}\) | 1.0608 \(\approx _{1}\) \(\approx _{2}\) |
WFG6 | 1.1989 | 1.2186 | 1.2024 \(\approx _{1}\) \(\downarrow _{2}\) | 1.2063 \(\uparrow _{1}\) \(\downarrow _{2}\) | 1.2183 \(\uparrow _{1}\) \(\approx _{2}\) | 1.2176 \(\uparrow _{1}\) \(\approx _{2}\) |
WFG7 | 0.9865 | 0.9853 | 0.9889 \(\approx _{1}\) \(\approx _{2}\) | 0.9816 \(\approx _{1}\) \(\approx _{2}\) | 0.9840 \(\approx _{1}\) \(\approx _{2}\) | 0.9855 \(\approx _{1}\) \(\approx _{2}\) |
WFG8 | 0.8229 | 0.8273 | 0.8176 \(\approx _{1}\) \(\approx _{2}\) | 0.8182 \(\approx _{1}\) \(\approx _{2}\) | 0.8162 \(\approx _{1}\) \(\approx _{2}\) | 0.8271 \(\approx _{1}\) \(\approx _{2}\) |
WFG9 | 0.8900 | 0.904 | 0.8864 \(\approx _{1}\) \(\approx _{2}\) | 0.8771 \(\approx _{1}\) \(\approx _{2}\) | 0.8591 \(\downarrow _{1}\) \(\downarrow _{2}\) | 0.8860 \(\approx _{1}\) \(\approx _{2}\) |
Summary | Compared to \(NormR_A\) | \(\uparrow _{1}\) 8 \(\downarrow _{1}\) 6 | \(\uparrow _{1}\) 10 \(\downarrow _{1}\) 2 | \(\uparrow _{1}\) 9 \(\downarrow _{1} \) 3 | \(\uparrow _{1}\)8 \(\downarrow _{1} \) 2 | |
Compared to \(NormR_{ND}\) | \(\uparrow _{2}\) 4 \(\downarrow _{2} 8\) | \(\uparrow _{2}\) 5 \(\downarrow _{2} 6\) | \(\uparrow _{2}\) 5 \(\downarrow _{2}4\) | \(\uparrow _{2}\) 4 \(\downarrow _{2} 2\) |
-
Comparison with archive-based normalization:
-
For the archive-based normalization, it typically faces challenges when initialized solutions span a much larger range of objective values compared to the PF. As discussed earlier, the implication of using a reference point far away is that the solutions that are not on the PF may have a high contribution, which takes away the selection pressure to drive the solutions to a well converged and diverse PF approximation. On the other hand, if the initialized solutions are close to the PF and span its range well, it has the advantage of identifying good nadir and ideal approximation without additional effort. We observed that the typical scenario reflecting the first situation is common in DTLZ (except DTLZ7) problems and MAF problems. The representative cases of the latter scenario are common in the WFG, ZDT and DTLZ7 problems. From Tables 2, 3 and 4, we observe that the proposed \(NormR_{NDC}\) (S3) either outperforms or achieves equivalent results compared to the archive-based method (\(NormR_A\)) in nearly all cases. This verifies that for the cases where the initial population was far away, the proposed approach was able to provide tighter bounds for the HV infill search by bringing the reference point much closer to the true \(Z^I\) and \(Z^N\).
-
To verify the above case where \(NormR_A\) faced challenges, we observe the search behavior on DTLZ1 closely in Fig. 6. Figure 6a shows the initial solutions for the 2-objective DTLZ1, its normalization bounds (orange box), and the position of the reference point. Evidently, due to the distribution of initial solutions, reference point is placed far away from its PF. In contrast, Fig. 6b shows the normalization bounds and location of the reference point suggested by the proposed strategy (\(NormR_{NDC}\)) using the same initial solutions. It is clear that the performance of the latter is likely to be better than \(NormR_A\) strategy. It is expected that the convergence of \(NormR_{A}\) will be inferior in this case, which indeed is the case as can be seen from Fig. 6c.
-
The two scenarios discussed above are further visualized using 3-objective problems in Figs. 7 and 8. In Fig. 7 for DTLZ7 problem, initial population covers the PF range well, and the solutions are not too far away from the PF. Consequently, the archive-based normalization has the advantage on covering all the four patches of PF, since it can estimate the bounds well from the beginning. The proposed method does not have the scope of improving this performance significantly via corner search, but we can see that it achieves similar PF convergence and diversity (Fig. 7d–f). Notably, the ND-based normalization (\(NormR_{ND}\)) performs much worse here, which will be discussed shortly. The second scenario occurs for problem MAF6 in Fig. 8, wherein it is observed that the initial solutions are far from PF. The performance of the archive-based normalization method suffers in this case (for similar reasons as in Fig. 6), while the proposed method maintains its competitive performance.
-
-
Comparison with ND-based normalization:
-
Though ND-based normalization generally performs well, it faces challenges in the scenario where the initial non-dominated population is concentrated in localized region rather than spanning a good range relative to the PF. In such cases, \(NormR_{ND}\) is not able to easily expand the range to obtain other parts of the PF and the diversity is severely compromised. This is illustrated for DTLZ7 in Fig. 7b, where the final solutions cover only a part of the PF. This is because during the initialization, although the solutions in the archive spans a wide range, the non-dominated solutions were concentrated only around two of the patches. The surrogate corner search in Fig. 7d is able to overcome this situation by supplementing the ND set with other corners spanning a larger range which in turn improved its performance significantly.
-
The performance of the proposed method is also very consistent compared to the ND-based normalization across different number of objectives as evidenced from Tables 2 and 3. In Table 2 for 2-objectives, the last column has 7 problems where \(NormR_{NDC}\) (S3) outperforms \(NormR_{ND}\) significantly. There are 5 problems where the proposed method performs worse. However, it is worth noting that although there are cases where the proposed method performs worse than the ND-based normalization, the gap in performance is marginal. For example, in the DTLZ1 problem in Table 2, the median HV of the ND-based method is 0.7008, while the median HV of the proposed method in the last column is 0.7004. In contrast, for the cases where \(NormR_{ND}\) faces challenge, such as DTLZ7 in Table 2, the gap is significantly larger.
-
In addition, one can observe from Tables 3 and 4 that \(NormR_{NDC}\) (S3) outperforms \(NormR_{ND}\) in only a few problems, while being equivalent in others. However, this does not indicate that the performance of the proposed approach gets worse with increasing number of objectives. In fact, the main takeaway is that for \(NormR_{A}\) and \(NormR_{ND}\) method, there are both typical scenarios where they suffer disadvantages. The proposed strategy is expected to mitigate these disadvantages in both scenarios and generate rather stable performance across a range of problems, rather than always outperforming the other two strategies. In problems with a higher number of objectives, the performance is equivalent in the majority of instances. Overall, it can be clearly seen that for the scenarios that are challenging for \(NormR_{ND}\), the proposed approach is able to adapt and maintain its competitive performance.
-
Among the problems with a higher number of objectives, there are fewer that exhibit biased initial ND front; unlike the ZDT problems in the 2-objective benchmarks (Table 2). Therefore, the performance of \(NormR_{ND}\) and \(NormR_{NDC}\) (S3) tend to be similar. For the 5-objective test problems, \(NormR_{NDC}\) (S3) performs better than \(NormR_{ND}\) for more(4) problems, and worse for fewer (2) problems. For 3-objective cases, it has the same number of better and worse cases (3 each). From the perspective of the experiment setting, 5-objective problems have 200 solutions to train its surrogates while there were 150 solutions for 3-objective problems. Since the number of variables was 6 in both cases, we expect more accurate surrogates to be generated for the 5-objective case. The better surrogate accuracy is likely to lead to offer benefit to surrogate-assisted corner search. However, a crucial thing to note here is that the above numbers are relatively small in comparison to the size of the problem set. For a majority of problems in both 3-objective (19 out of 25) and 5-objective (16 out of 22) sets, the strategies actually perform similar. This is consistent with the principles of experiment design. The main intent of the proposed strategy is to provide competent (best or close to best) performance when either \(NormR_{ND}\) or \(NormR_{A}\) face challenging scenarios such as those discussed above.
-