求解昂贵黑箱全局优化问题的自适应采样组合响应面方法

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

运筹学学报 ›› 2021, Vol. 25 ›› Issue (2): 1-14.doi: 10.15960/j.cnki.issn.1007-6093.2021.02.001

• • 下一篇

求解昂贵黑箱全局优化问题的自适应采样组合响应面方法

白富生¹^,*(), 冯丹¹, 张柯¹

1. 重庆师范大学数学科学学院, 重庆 401331

收稿日期:2020-09-17 出版日期:2021-06-15 发布日期:2021-05-06
通讯作者: 白富生 E-mail:fsbai@cqnu.edu.cn
作者简介:白富生 E-mail: fsbai@cqnu.edu.cn
基金资助:
国家自然科学基金(11991024);国家自然科学基金(11871128);重庆市自然科学基金(cstc2019jcyj-msxmX0368);重庆市自然科学基金(cstc2018jcyjAX0172)

Combined response surface method with adaptive sampling for expensive black-box global optimization

Fusheng BAI¹^,*(), Dan FENG¹, Ke ZHANG¹

1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China

Received:2020-09-17 Online:2021-06-15 Published:2021-05-06
Contact: Fusheng BAI E-mail:fsbai@cqnu.edu.cn

摘要/Abstract

摘要：

针对昂贵黑箱全局优化问题，提出了可以在迭代中进行自适应采样的组合响应面方法。在响应面方法的框架下，采用三次径向基函数和薄板样条径向基函数的凸组合作为响应面。在算法的初始迭代阶段，将响应面模型和距离指示函数的幂的乘积构成的辅助函数的全局最优点作为新采样点。在接下来的迭代中，如果连续两次迭代中响应面模型的全局最优点之间的距离小于预先给定的阈值，则将当前响应面的全局最优点作为下一个采样点，否则将采用初始迭代阶段的采样策略得到新采样点。分别在7个标准测试问题上和22个标准测试问题上进行了数值实验，计算结果说明了所提算法的有效性。

关键词: 黑箱函数, 全局优化, 响应面方法, 径向基函数

Abstract:

A combined response surface method is presented for expensive black-box global optimization, which can adaptively take sampling points during iterations. Under the framework of response surface method, the convex combination of the cubic radial basis function and the thin plate spline radial basis function is adopted as the response surface. In the initial phase of the algorithm, the global optimizer of the auxiliary function formed by the product of the response surface model and the power of the distance indicator function will be taken as the new sample point. In the following iterations, if the distance between the two response surface models of the two consecutive iterations is smaller than a given threshold, then the global optimizer of the current response surface model will be taken as the next sample point, otherwise the sampling strategy of the initial phase will be adopted. The effectiveness of the proposed algorithm is demonstrated by the results of the numerical experiments carried respectively on 7 standard test problems and 22 standard test problems.

Key words: black-box function, global optimization, response surface method, radial basis function

中图分类号:

O221.2

白富生, 冯丹, 张柯. 求解昂贵黑箱全局优化问题的自适应采样组合响应面方法[J]. 运筹学学报, 2021, 25(2): 1-14.

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.

图/表 8

表1

图1

表2

表3

图2

表4

图3

图4

参考文献 17

1	Myers R H , Montgomery D C . Response Surface Methodology: Process and Product Optimization Using Designed Experiments[M]. New York: Wiley, 1995.
2	Khuri A I , Cornell J A . Response Surfaces[M]. New York: Marcel Dekker Inc., 1987.
3	Jones D R , Schonlau M , Welch W J . Efficient global optimization of expensive black-box functions[J]. Journal of Global Optimization, 1998, 13 (4): 455- 492. doi: 10.1023/A:1008306431147
4	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
5	Regis R G , Shoemaker C A . Constrained global optimization of expensive black box functions using radial basis functions[J]. Journal of Global Optimization, 2005, 31, 153- 171. doi: 10.1007/s10898-004-0570-0
6	Regis R , Shoemaker C . A stochastic radial basis function method for the global optimization of expensive functions[J]. INFORMS Journal on Computing, 2007, 19, 497- 509. doi: 10.1287/ijoc.1060.0182
7	Xiang H , Li Y , Liao H , et al. An adaptive surrogate model based on support vector regression and its application to the optimization of railway wind barriers[J]. Structural and Multidisciplinary Optimization, 2017, 55, 701- 713. doi: 10.1007/s00158-016-1528-9
8	Crino S , Brown D E . Global optimization with multivariate adaptive regression splines[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37 (2): 333- 340. doi: 10.1109/TSMCB.2006.883430
9	Jie H , Wu Y , Ding J . An adaptive metamodel-based global optimization algorithm for blackbox type problems[J]. Engineering Optimization, 2015, 47 (11): 1459- 1480. doi: 10.1080/0305215X.2014.979814
10	Zhou Z , Bai F S . An adaptive framework for costly black-box global optimization based on radial basis function interpolation[J]. Journal of Global Optimization, 2018, 70 (4): 757- 781. doi: 10.1007/s10898-017-0599-5
11	Powell M J D. The theory of radial basis function approximation in 1990[D]. Oxford: Oxford University, 1992.
12	Dixon L C W , Szegö G P . Towards Global Optimisation[M]. Amsterdam: North-Holland Publishing Company, 1978.
13	Schoen F . A wide class of test functions for global optimization[J]. Journal of Global Optimization, 1993, 3 (2): 133- 137. doi: 10.1007/BF01096734
14	Törn A , Zilinskas A . Global Optimization[M]. Berlin: Springer-Verlag, 1989.
15	Surjanovic S, Bingham D. Virtual library of simulation experiments: Test functions and datasets[EB/OL]. (2020-08-25)[2013-03-23]. http://www.sfu.ca/~ssurjano.
16	Dolan E D , Moré J J . Benchmarking optimization software with performance profiles[J]. Mathematical Programming, 2001, 91 (2): 201- 213.
17	Moré J J , Wild S M . Benchmarking derivative-free optimization algorithms[J]. SIAM Journal on Optimization, 2009, 20 (1): 172- 191.

径向基函数	$ \phi (r) $	$ m_\phi $	$ p( x) $(当$ m = m_\phi $)
三次函数	$ r^3 $	1	$ b^{\rm T} x + a $
薄板样条函数	$ {r^2}\log r $	1	$ b^{\rm T}x + a $
线性函数	$ r $	0	$ a $
多二次函数	$ \sqrt{r^2+\gamma^2}, \gamma > 0 $	0	$ a $
高斯函数	$ \exp (-\gamma {r^2}), \gamma >0 $	$ -1 $	$ \{0\} $

测试问题	Branin	Rastrigin2	Schoen3	Schoen4	Schoen4X	Schoen4Y	Shubert
维数	2	2	3	4	4	4	2
最优值	0.397, 9	-2	9.954, 2	9.954, 2	-965.353, 3	-976.652, 2	-186.730, 9

测试问题	AMGO		自适应采样组合响应面算法
测试问题	均值	标准差	均值	标准差
Branin	0.403, 6	0.005, 4	0.403, 2	0.017, 3
Rastrigin2	-1.617, 0	0.490, 5	-2.000, 0	0.000, 0
Schoen3	10.551, 8	0.408, 4	10.224, 0	0.015, 7
Schoen4	11.235, 6	0.813, 5	15.938, 5	4.996, 6
Schoen4X	273.679, 2	287.659, 0	-371.900, 9	769.190, 0
Schoen4Y	-39.429, 5	255.351, 3	127.513, 6	529.889, 6
Shubert	-134.079, 6	54.127, 0	-135.051, 5	45.200, 0

测试问题	最小值	最大值	维数	三次响应面算法	自适应采样组合响应面算法
Ackley15	0	2.181 1×10	15	>200	>200
Ackley30	0	2.174 0×10	30	>200	>200
Ackley8	0	2.201 2×10	8	175(1)	>200
Branin	0.397 9	3.081 3×10²	2	20.37 (30)	19.37 (30)
Easom	-1	0	2	>200	>200
Goldstein-Price	3	1.015 7×10⁶	2	2.43 (30)	2.37 (30)
Hartman3	-3.862 8	-3.847 9×10^-5	3	58.67 (30)	58.47 (30)
Hartman6	-3.323 4	-5.715 1×10^-7	6	104.43 (23)	64.62 (21)
Levy20	0	2.915 6×10³	20	45.50 (18)	45.88 (19)
Rastrigin2	-2	6.373 0	2	29.44 (21)	22.25 (27)
Rosenbrock10	0	6.593 1×10⁶	10	25.07 (30)	24.77 (30)
Rosenbrock20	0	1.248 9×10⁷	20	45.50 (30)	46.33 (30)
Schoen3	9.954 2	8.980 8×10	3	81.80 (30)	40.60 (30)
Schoen4	9.954 2	8.980 8×10	4	130.29 (28)	58.90 (10)
Schoen4X	-965.353 3	9.892 8×10²	4	155.30 (10)	118.47 (17)
Schoen4Y	-967.652 2	9.991 4×10²	4	>200	133 (3)
Schoen5	9.954 2	8.980 8×10	5	158 (9)	107.88 (25)
Schoen5X	-965.353 3	9.951 6×10²	5	>200	104.50 (2)
Schoen5Y	-967.652 2	9.984 9×10²	5	>200	141 (4)
Shubert	-186.730 9	1.656 6×10²	2	96.63 (19)	105.33 (12)
Sphere27	0	7.077 9×10²	27	57(30)	57.70 (30)
Zakharov11	0	2.339 2×10⁷	11	27.87 (30)	28.37 (30)

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

求解昂贵黑箱全局优化问题的自适应采样组合响应面方法

Combined response surface method with adaptive sampling for expensive black-box global optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 17

相关文章 10

编辑推荐

Metrics

本文评价