带隐藏约束昂贵黑箱问题的自适应代理优化方法

doi:10.15960/j.cnki.issn.1007-6093.2024.01.007

Abstract

Abstract:

A surrogate optimization method with adaptive transition search strategy is proposed for expensive black-box problems with hidden constraints. In the sub-steps of the transition search, a variance related to the number of evaluated points is used for the generation of trial points by random perturbation to better balance the local and global searches. In order to better approximate the real black box objective function, an adaptively combined objective surrogate model is adopted. The effectiveness of the proposed algorithm is demonstrated by the results of the numerical experiments carried out on 50 test problems.

Key words: expensive black-box problems, global optimization, hidden constraints, surrogate optimization

CLC Number:

O221.2

Fusheng BAI, Mi LAN. An adaptive surrogate optimization method for expensive black-box problems with hidden constraints[J]. Operations Research Transactions, 2024, 28(1): 89-100.

Figures/Tables 6

测试问题	SHEBO	ASHEBO-v1	ASHEBO-v2	测试问题	SHEBO	ASHEBO-v1	ASHEBO-v2
(1, 2)	8.741 0$ \times10^0 $	8.479 9$ \times10^0 $	8.345 2$ \times10^0 $	(6, 10)	7.116 5$ \times10^0 $	6.512 1$ \times10^0 $	7.416 6$ \times10^0 $
(2, 2)	7.915 6$ \times10^{-2} $	6.720 6$ \times10^{-2} $	6.639 4$ \times10^{-2} $	(7, 10)	$ - $1.203 8$ \times10^1 $	-1.277 9$ \times10^1 $	-1.278 0$ \times10^1 $
(3, 2)	$ - $2.147 8$ \times10^2 $	-2.148 0$ \times10^2 $	-2.148 0$ \times10^2 $	(8, 10)	5.823 9$ \times10^{-1} $	5.404 0$ \times10^{-1} $	5.391 2$ \times10^{-1} $
(4, 2)	$ - $1.459 9$ \times10^2 $	-1.722 7$ \times10^2 $	-1.751 8$ \times10^2 $	(9, 10)	5.040 9$ \times10^0 $	4.667 4$ \times10^0 $	4.223 1$ \times10^0 $
(5, 2)	$ - $114.950 0$ \times10^2 $	$ - $95.397 0$ \times10^1 $	$ - $89.059 0$ \times10^1 $	(10, 10)	8.583 2$ \times10^{-6} $	8.583 3$ \times10^{-6} $	8.583 2$ \times10^{-6} $
(6, 2)	8.068 5$ \times10^0 $	7.859 7$ \times10^0 $	7.792 6$ \times10^0 $	(1, 20)	8.140 9$ \times10^0 $	8.051 6$ \times10^0 $	8.055 3$ \times10^0 $
(7, 2)	$ - $1.214 9$ \times10^1 $	$ - $1.214 9$ \times10^1 $	-1.299 4$ \times10^1 $	(2, 20)	7.885 2$ \times10^{-2} $	6.137 4$ \times10^{-2} $	3.291 2$ \times10^{-2} $
(8, 2)	5.309 7$ \times10^{-1} $	5.267 0$ \times10^{-1} $	5.277 0$ \times10^{-1} $	(3, 20)	$ - $2.144 0$ \times10^3 $	-2.148 0$ \times10^3 $	-2.148 0$ \times10^3 $
(9, 2)	3.802 2$ \times10^0 $	3.756 1$ \times10^0 $	3.597 5$ \times10^0 $	(4, 20)	$ - $90.236 0$ \times10^1 $	-182.530 0$ \times10^2 $	$ - $79.707 0$ \times10^1 $
(10, 2)	9.578 3$ \times10^{-7} $	9.541 7$ \times10^{-7} $	9.541 1$ \times10^{-7} $	(5, 20)	$ - $3.463 8$ \times10^3 $	-5.340 5$ \times10^3 $	-6.159 9$ \times10^3 $
(1, 5)	6.606 3$ \times10^0 $	6.605 7$ \times10^0 $	6.441 8$ \times10^0 $	(6, 20)	7.575 5$ \times10^0 $	7.268 7$ \times10^0 $	7.028 8$ \times10^0 $
(2, 5)	9.791 4$ \times10^{-2} $	9.340 2$ \times10^{-2} $	8.848 5$ \times10^{-2} $	(7, 20)	$ - $1.214 9$ \times10^1 $	$ - $1.207 4$ \times10^1 $	$ - $1.206 9$ \times10^1 $
(3, 5)	$ - $5.369 9$ \times10^2 $	-5.369 9$ \times10^2 $	-5.369 9$ \times10^2 $	(8, 20)	6.451 2$ \times10^{-1} $	6.128 7$ \times10^{-1} $	6.092 5$ \times10^{-1} $
(4, 5)	$ - $1.214 7$ \times10^2 $	$ - $1.167 5$ \times10^2 $	-1.237 8$ \times10^2 $	(9, 20)	7.777 5$ \times10^0 $	5.524 1$ \times10^0 $	7.442 5$ \times10^0 $
(5, 5)	$ - $5.730 1$ \times10^2 $	-5.874 2$ \times10^2 $	-7.048 3$ \times10^2 $	(10, 20)	1.812 0$ \times10^{-5} $	1.812 0$ \times10^{-5} $	1.812 0$ \times10^{-5} $
(6, 5)	7.057 3$ \times10^0 $	7.052 6$ \times10^0 $	7.219 0$ \times10^0 $	(1, 30)	8.840 5$ \times10^0 $	8.058 8$ \times10^0 $	8.269 7$ \times10^0 $
(7, 5)	$ - $1.192 7$ \times10^1 $	$ - $1.177 4$ \times10^1 $	$ - $1.162 3$ \times10^1 $	(2, 30)	7.134 0$ \times10^{-2} $	2.973 4$ \times10^{-2} $	2.100 4$ \times10^{-2} $
(8, 5)	5.284 2$ \times10^{-1} $	5.017 6$ \times10^{-1} $	5.039 0$ \times10^{-1} $	(3, 30)	$ - $3.222 0$ \times10^3 $	-3.222 0$ \times10^3 $	$ - $3.221 9$ \times10^3 $
(9, 5)	4.371 6$ \times10^0 $	4.220 5$ \times10^0 $	4.438 3$ \times10^0 $	(4, 30)	$ - $105.710 0$ \times10^2 $	-168.440 0$ \times10^2 $	$ - $60.843 0$ \times10^1 $
(10, 5)	3.815 4$ \times10^{-6} $	3.815 9$ \times10^{-6} $	3.815 7$ \times10^{-6} $	(5, 30)	$ - $3.307 9$ \times10^3 $	-4.007 4$ \times10^3 $	-4.986 3$ \times10^3 $
(1, 10)	6.819 2$ \times10^0 $	6.715 1$ \times10^0 $	6.661 1$ \times10^0 $	(6, 30)	7.877 6$ \times10^0 $	7.335 0$ \times10^0 $	7.405 7$ \times10^0 $
(2, 10)	8.077 6$ \times10^{-2} $	8.023 0$ \times10^{-2} $	5.035 0$ \times10^{-2} $	(7, 30)	$ - $1.215 0$ \times10^1 $	-1.219 6$ \times10^1 $	-1.215 0$ \times10^1 $
(3, 10)	$ - $1.074 0$ \times10^3 $	-1.074 0$ \times10^3 $	$ - $1.074 0$ \times10^3 $	(8, 30)	6.593 3$ \times10^{-1} $	6.419 8$ \times10^{-1} $	6.366 5$ \times10^{-1} $
(4, 10)	$ - $1.093 3$ \times10^2 $	-1.239 1$ \times10^2 $	-1.181 6$ \times10^2 $	(9, 30)	9.222 8$ \times10^0 $	9.589 0$ \times10^0 $	9.219 2$ \times10^0 $
(5, 10)	$ - $2.862 3$ \times10^3 $	-2.977 2$ \times10^3 $	-2.877 9$ \times10^3 $	(10, 30)	2.765 7$ \times10^{-5} $	2.765 7$ \times10^{-5} $	2.765 7$ \times10^{-5} $

References 15

1	Carter R G , Gablonsky J M , Patrick A , et al. Algorithms for noisy problems in gas transmission pipeline optimization[J]. Optimization and Engineering, 2001, 2 (2): 139- 157. doi: 10.1023/A:1013123110266
2	Ji C , Dames E , Wang Y L , et al. Propagation and extinction of premixed C5-C12 n-alkane flames[J]. Combustion Flame, 2010, 157 (2): 277- 287. doi: 10.1016/j.combustflame.2009.06.011
3	Booker A J , Dennis J E , Frank P D , et al. A rigorous framework for optimization of expensive functions by surrogates[J]. Structural Optimization, 1999, 17 (1): 1- 13. doi: 10.1007/BF01197708
4	Juliane M , Marcus D . Surrogate optimization of computationally expensive black-box problems with hidden constraints[J]. INFORMS Journal on Computing, 2019, 31 (4): 689- 702. doi: 10.1287/ijoc.2018.0864
5	Myers R H , Montgomery D C . Response Surface Methodology: Process and Product Optimization Using Designed Experiments[M]. New York: Wiley, 1995.
6	Digabel S L . Algorithm 909: NOMAD: Nonlinear optimization with the MADS algorithm[J]. ACM Transactions on Mathematical Software, 2011, 37 (4): 1- 15.
7	Mueller J , Shoemaker C A . Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms forcomputationally expensive black-box global optimization problems[J]. Journal of Global Optimization, 2014, 60 (2): 123- 144. doi: 10.1007/s10898-014-0184-0
8	Gutmann H M . A radial basis function method for global optimization[J]. Journal of Global Optimization, 2001, 19 (3): 201- 227. doi: 10.1023/A:1011255519438
9	白富生, 冯丹, 张柯. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法[J]. 运筹学学报, 2021, 25 (2): 1- 14. doi: 10.15960/j.cnki.issn.1007-6093.2021.02.001
10	Powell M J D. The theory of radial basis function approximation in 1990[M]//Advances in Numerical Analysis, Oxford: Oxford University Press, 105-210.
11	Jie H , Wu Y , Ding J . An adaptive metamodel-based global optimization algorithm for black-box type problems[J]. Engineering Optimization, 2015, 47 (11): 1459- 1480. doi: 10.1080/0305215X.2014.979814
12	Regis R G , Shoemaker C A . Combining radial basis function surrogates dynamic coordinate search in high dimensional expensive black-box optimization[J]. Engineering Optimzation, 2013, 45 (5): 529- 555. doi: 10.1080/0305215X.2012.687731
13	Juliane M , Marcus D . Online supplement for Surrogate optimization of computationally expensive black-box problems with hidden constraints[J]. INFORMS Journal on Computing, 2019, 31 (4): 689- 702. doi: 10.1287/ijoc.2018.0864
14	Dolan E D , Moré J J . Benchmarking optimization software with performance profiles[J]. Mathematical Programming, 2001, 91 (2): 201- 213.
15	Moré J J , Wild S M . Benchmarking derivative-free optimization algorithms[J]. SIAM Journal on Optimization, 2009, 20 (1): 172- 191. doi: 10.1137/080724083

径向基函数	$ \phi (r) $
三次(Cubic)函数	$ r^3 $
薄板样条(Thin plate spline)函数	$ {r^2}\log r $
线性(Linear)函数	$ r $
多二次(Multiquadric)函数	$ \sqrt {{r^2} + {\gamma ^2}} $, $ \gamma > 0 $
高斯(Gaussian)函数	$ \exp ({ - \gamma {r^2}}) $, $ \gamma > 0 $

测试问题	目标函数	隐藏约束	上下界约束
问题1	Ackley	Alpine01	$ [-10, 10]^d $
问题2	Bird	Rana	$ [-3\pi, 3\pi]^d $
问题3	Eggcrate	Giunta	$ [0, 10]^d $
问题4	Hansen	Alpine02	$ [0, 10]^d $
问题5	Rastrigin	Levy03	$ [-5, 5]^d $
问题6	Ackley	Levy03	$ [-5, 5]^d $
问题7	Alpine01	Schwefel26	$ [-12, 12]^d $
问题8	Wavy	Alpine01	$ [-\pi, \pi]^d $
问题9	Ackley	Vincent	$ [0.25, 10]^d $
问题10	Weierstrass	Vincent	$ [0.25, \pi]^d $

算法	ASHEBO-v1	ASHEBO-v2	ASHEBO*-v1	ASHEBO-*v2	ASHEBO**-v1	ASHEBO**-v2
$ Q $	80%	$ 74% $	66%	60%	72%	66%

[1]	Xiaoli HUANG, Yuelin GAO, Bo ZHANG, Xia LIU. An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems [J]. Operations Research Transactions, 2022, 26(2): 83-100.
[2]	Fusheng BAI, Dan FENG, Ke ZHANG. Combined response surface method with adaptive sampling for expensive black-box global optimization [J]. Operations Research Transactions, 2021, 25(2): 1-14.
[3]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[4]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[5]	ZHAO Dan, GAO Yuelin. Non-parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2020, 24(4): 63-73.
[6]	CHEN Yong, WANG Wei, XU Yifan. An stochastic algorithm for global optimization with linear constraints based on intermittent diffusion [J]. Operations Research Transactions, 2020, 24(1): 88-100.
[7]	WANG Weixiang, SHANG Youlin, WANG Duo. Filled function method for solving non-smooth box constrained global optimization problems [J]. Operations Research Transactions, 2019, 23(1): 28-34.
[8]	TIAN Mingyu, YANG Yongjian. A global optimization algorithm for polynomial programming [J]. Operations Research Transactions, 2018, 22(4): 79-88.
[9]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.
[10]	ZHENG Yue, ZHUANG Daoyuan, WAN Zhongping. A global optimization method for solving the weak linear bilevel programming problems [J]. Operations Research Transactions, 2017, 21(3): 86-94.
[11]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[12]	HU Quan, WANG Wei. A filled function method based on filter for global optimization with box constraints [J]. Operations Research Transactions, 2016, 20(3): 57-67.
[13]	LV Yibing, WAN Zhongping. A global optimization method for solving the linear semivectorial bilevel programming problem [J]. Operations Research Transactions, 2015, 19(2): 29-36.
[14]	YE Min, WU Zhiyou, ZHANG Liang. Necessary global optimality conditions and optimization methods for cubic polynomial optimization problems with linear constraints [J]. Operations Research Transactions, 2015, 19(2): 15-28.
[15]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.

An adaptive surrogate optimization method for expensive black-box problems with hidden constraints

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 15

Related Articles 15

Recommended Articles

Metrics

Comments