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

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

摘要/Abstract

摘要：

针对带隐藏约束的昂贵黑箱全局优化问题, 提出采用自适应转换搜索策略的代理优化方法。在转换搜索子步中采用与已估值点个数相关的标准差在当前最优点附近通过随机扰动生成候选点, 以更好地平衡局部搜索和全局搜索。为更好地近似真实黑箱目标函数, 采用了自适应组合目标代理模型。在50个测试问题上进行了数值实验, 计算结果说明了所提算法的有效性。

关键词: 昂贵黑箱问题, 全局优化, 隐藏约束, 代理优化

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

中图分类号:

O221.2

白富生, 兰秘. 带隐藏约束昂贵黑箱问题的自适应代理优化方法[J]. 运筹学学报, 2024, 28(1): 89-100.

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.

图/表 6

表1

图1

表2

表3

表4

SHEBO与ASHEBO算法得到的平均最优值"

测试问题	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} $

表4

图2

参考文献 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]	黄小利, 高岳林, 张博, 刘霞. 一种求解二次约束二次规划问题的自适应全局优化算法[J]. 运筹学学报, 2022, 26(2): 83-100.
[2]	白富生, 冯丹, 张柯. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法[J]. 运筹学学报, 2021, 25(2): 1-14.
[3]	陈佳利, 张莹, 王胜刚, 谢笑盈. 一个新的填充函数及其在数据拟合问题中的应用[J]. 运筹学学报, 2021, 25(1): 81-88.
[4]	赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24(4): 63-73.
[5]	陈永, 王薇, 徐以汎. 具有间断扩散性质的线性约束全局优化随机算法[J]. 运筹学学报, 2020, 24(1): 88-100.
[6]	王伟祥, 尚有林, 王朵. 求解带箱子集约束的非光滑全局优化问题的填充函数方法[J]. 运筹学学报, 2019, 23(1): 28-34.
[7]	郑跃, 庄道元, 万仲平. 求解弱线性双层规划问题的一种全局优化方法[J]. 运筹学学报, 2017, 21(3): 86-94.
[8]	石礼堂, 陈伟. 非线性无约束优化问题的滤子填充函数算法[J]. 运筹学学报, 2017, 21(1): 55-64.
[9]	胡铨, 王薇. 求解带箱式约束全局优化问题的滤子填充函数方法[J]. 运筹学学报, 2016, 20(3): 57-67.
[10]	戴彧虹，刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1): 69-92.
[11]	汤丹. 基于模拟退火的CRS算法[J]. 运筹学学报, 2011, 15(4): 124-128.
[12]	张丽丽, 李建宇, 李兴斯. 全局优化问题的一类积分型最优性条件 (英)[J]. 运筹学学报, 2011, 15(1): 1-10.