TY - JOUR
T1 - Multi-Objective Bayesian Global Optimization using expected hypervolume improvement gradient
AU - Yang, Kaifeng
AU - Emmerich, Michael
AU - Deutz, André
AU - Bäck, Thomas
N1 - Funding Information:
Kaifeng Yang acknowledges financial support from the China Scholarship Council (CSC), CSC No. 201306370037 .
Publisher Copyright:
© 2018 The Authors
PY - 2019/2
Y1 - 2019/2
N2 - The Expected Hypervolume Improvement (EHVI) is a frequently used infill criterion in Multi-Objective Bayesian Global Optimization (MOBGO), due to its good ability to lead the exploration. Recently, the computational complexity of EHVI calculation is reduced to O(n log n) for both 2-D and 3-D cases. However, the optimizer in MOBGO still requires a significant amount of time, because the calculation of EHVI is carried out in each iteration and usually tens of thousands of the EHVI calculations are required. This paper derives a formula for the Expected Hypervolume Improvement Gradient (EHVIG) and proposes an efficient algorithm to calculate EHVIG. The new criterion (EHVIG) is utilized by two different strategies to improve the efficiency of the optimizer discussed in this paper. Firstly, it enables gradient ascent methods to be used in MOBGO. Moreover, since the EHVIG of an optimal solution should be a zero vector, it can be regarded as a stopping criterion in global optimization, e.g., in Evolution Strategies. Empirical experiments are performed on seven benchmark problems. The experimental results show that the second proposed strategy, using EHVIG as a stopping criterion for local search, can outperform the normal MOBGO on problems where the optimal solutions are located in the interior of the search space. For the ZDT series test problems, EHVIG still can perform better when gradient projection is applied.
AB - The Expected Hypervolume Improvement (EHVI) is a frequently used infill criterion in Multi-Objective Bayesian Global Optimization (MOBGO), due to its good ability to lead the exploration. Recently, the computational complexity of EHVI calculation is reduced to O(n log n) for both 2-D and 3-D cases. However, the optimizer in MOBGO still requires a significant amount of time, because the calculation of EHVI is carried out in each iteration and usually tens of thousands of the EHVI calculations are required. This paper derives a formula for the Expected Hypervolume Improvement Gradient (EHVIG) and proposes an efficient algorithm to calculate EHVIG. The new criterion (EHVIG) is utilized by two different strategies to improve the efficiency of the optimizer discussed in this paper. Firstly, it enables gradient ascent methods to be used in MOBGO. Moreover, since the EHVIG of an optimal solution should be a zero vector, it can be regarded as a stopping criterion in global optimization, e.g., in Evolution Strategies. Empirical experiments are performed on seven benchmark problems. The experimental results show that the second proposed strategy, using EHVIG as a stopping criterion for local search, can outperform the normal MOBGO on problems where the optimal solutions are located in the interior of the search space. For the ZDT series test problems, EHVIG still can perform better when gradient projection is applied.
KW - Bayesian global optimization
KW - Expected hypervolume improvement
KW - Expected hypervolume improvement gradient
KW - Kriging stopping criterion
UR - http://www.scopus.com/inward/record.url?scp=85055425828&partnerID=8YFLogxK
U2 - 10.1016/j.swevo.2018.10.007
DO - 10.1016/j.swevo.2018.10.007
M3 - Article
AN - SCOPUS:85055425828
SN - 2210-6502
VL - 44
SP - 945
EP - 956
JO - Swarm and Evolutionary Computation
JF - Swarm and Evolutionary Computation
ER -