A surrogate-based cooperative optimization framework for computationally expensive black-box problems.

*(English)*Zbl 1457.90152Summary: Most parallel surrogate-based optimization algorithms focus only on the mechanisms for generating multiple updating points in each cycle, and rather less attention has been paid to producing them through the cooperation of several algorithms. For this purpose, a surrogate-based cooperative optimization framework is here proposed. Firstly, a class of parallel surrogate-based optimization algorithms is developed, based on the idea of viewing the infill sampling criterion as a bi-objective optimization problem. Each algorithm of this class is called a Sequential Multipoint Infill Sampling Algorithm (SMISA) and is the combination resulting from choosing a surrogate model, an exploitation measure, an exploration measure and a multi-objective optimization approach to its solution. SMISAs are the basic algorithms on which collaboration mechanisms are established. Many SMISAs can be defined, and the focus has been on scalar approaches for bi-objective problems such as the \(\varepsilon \)-constrained method, revisiting the Parallel Constrained Optimization using Response Surfaces (CORS-RBF) method and the Efficient Global Optimization with Pseudo Expected Improvement (EGO-PEI) algorithm as instances of SMISAs. In addition, a parallel version of the Lower Confidence Bound-based (LCB) algorithm is given as a member within the SMISA class. Secondly, we propose a cooperative optimization framework between the SMISAs. The cooperation between SMISAs occurs in two ways: (1) they share solutions and their objective function values to update their surrogate models and (2) they use the sampled points obtained from different SMISAs to guide their own search process. Some convergence results for this cooperative framework are given under weak conditions. A numerical comparison between EGO-PEI, Parallel CORS-RBF and a cooperative method using both, named CPEI, shows that CPEI improves the performance of the baseline algorithms. The numerical results were derived from 17 analytic tests and they show the reduction of wall-clock time with respect to the increase in the number of processors.

##### MSC:

90C30 | Nonlinear programming |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

cooperative optimization; parallel surrogate-based optimization; black-box function; expected improvement; radial basis functions
PDF
BibTeX
XML
Cite

\textit{J. C. García-García} et al., Optim. Eng. 21, No. 3, 1053--1093 (2020; Zbl 1457.90152)

Full Text:
DOI

##### References:

[1] | Beaucaire P, Beauthier Ch, Sainvitu C (2019) Multi-point infill sampling strategies exploiting multiple surrogate models. In: Proceedings of the genetic and evolutionary computation conference companion, GECCO ’19, New York, NY, USA. Association for Computing Machinery, pp 1559-1567 |

[2] | Bischl, B.; Wessing, S.; Bauer, N.; Friedrichs, K.; Weihs, C.; Pardalos, PM; Resende, MGC; Vogiatzis, C.; Walteros, JL, MOI-MBO: multiobjective infill for parallel model-based optimization. Revised Selected Papers, Learning and intelligent optimization: 8th international conference, Lion 8, Gainesville, FL, USA, February 16-21, 2014, 173-186 (2014), Cham: Springer, Cham |

[3] | Blanchard J, Beauthier C, Carletti T (2019) A surrogate-assisted cooperative co-evolutionary algorithm using recursive differential grouping as decomposition strategy. In: 2019 IEEE congress on evolutionary computation, CEC 2019—proceedings, pp 689-696 |

[4] | Dennis, JE; Torczon, V.; Alexandrov, NM; Hussaini, N., Managing approximation models in optimisation, Multidisciplinary design optimisation: state-of-the-art, 330-347 (1997), Philadelphia: SIAM, Philadelphia |

[5] | Díaz-Manríquez A, Toscano-Pulido G, Gómez-Flores W (2011) On the selection of surrogate models in evolutionary optimization algorithms. In: 2011 IEEE congress of evolutionary computation (CEC), pp 2155-2162 |

[6] | Díaz-Manríquez A, Toscano G, Barron-Zambrano JH, Tello-Leal E (2016) A review of surrogate assisted multiobjective evolutionary algorithms. Computational intelligence and neuroscience 2016. Hindawi Publishing Corporation |

[7] | Dixon, LCW; Szegö, G., The global optimization problem: an introduction, Towards Glob Optim, 2, 1-15 (1978) |

[8] | Emmerich, MTM; Giannakoglou, KC; Naujoks, B., Single- and multiobjective evolutionary optimization assisted by Gaussian random field metamodels, IEEE Trans Evol Comput, 10, 4, 421-439 (2006) |

[9] | Forrester, AIJ; Keane, AJ, Recent advances in surrogate-based optimization, Prog Aerosp Sci, 45, 1-3, 50-79 (2009) |

[10] | García-Ródenas R, Linares LJ, López-Gómez JA (2017) A cooperative brain storm optimization algorithm. In: 2017 IEEE congress on evolutionary computation (CEC), pp 838-845 |

[11] | García-Ródenas, R.; Linares, LJ; López-Gómez, JA, A memetic chaotic gravitational search algorithm for unconstrained global optimization problems, Appl Soft Comput J, 79, 14-29 (2019) |

[12] | Ginsbourger, D.; Riche, R.; Carraro, L.; Tenne, Y.; Goh, C-K, Kriging is well-suited to parallelize optimization, chapter 6, Computational intelligence in expensive optimization problems, 131-162 (2010), Berlin: Springer, Berlin |

[13] | Gutmann, H-M, A radial basis function method for global optimization, J Glob Optim, 19, 3, 201-227 (2001) · Zbl 0972.90055 |

[14] | Haftka, RT; Villanueva, D.; Chaudhuri, A., Parallel surrogate-assisted global optimization with expensive functions—a survey, Struct Multidiscip Optim, 54, 1, 3-13 (2016) |

[15] | Hansen N, Finck S, Ros R, Auger A (2009) Real-parameter black-box optimization benchmarking 2009: noiseless functions definitions. Technical Report RR-6829, INRIA |

[16] | Horn D, Bischl B (2016) Multi-objective parameter configuration of machine learning algorithms using model-based optimization. In: 2016 IEEE symposium series on computational intelligence (SSCI), pp 1-8 |

[17] | Jagannathan, R., On some properties of programming problems in parametric form pertaining to fractional programming, Manag Sci, 12, 7, 609-615 (1966) · Zbl 0143.21602 |

[18] | Jakobsson, S.; Patriksson, M.; Rudholm, J.; Wojciechowski, A., A method for simulation based optimization using radial basis functions, Optim Eng, 11, 4, 501-532 (2010) · Zbl 1243.65068 |

[19] | Johnson, ME; Moore, LM; Ylvisaker, D., Minimax and maximin distance designs, J Stat Plan Inference, 26, 131-148 (1990) |

[20] | Jones, DR; Schonlau, M.; Welch, WJ, Efficient global optimization of expensive black-box functions, J Glob Optim, 13, 4, 455-492 (1998) · Zbl 0917.90270 |

[21] | Krige, DG, A statistical approach to some basic mine valuation problems on the Witwatersrand, J Chem Met Min Soc S Afr, 52, 6, 119-139 (1951) |

[22] | Krityakierne, T.; Akhtar, T.; Shoemaker, CA, SOP: parallel surrogate global optimization with Pareto center selection for computationally expensive single objective problems, J Glob Optim, 66, 3, 417-437 (2016) · Zbl 1356.90136 |

[23] | Liu, B.; Zhang, Q.; Gielen, G., A Gaussian process surrogate model assisted evolutionary algorithm for medium scale expensive optimization problems, IEEE Trans Evol Comput, 18, 2, 180-192 (2014) |

[24] | Liu, J.; Song, W-P; Han, Z-H; Zhang, Y., Efficient aerodynamic shape optimization of transonic wings using a parallel infilling strategy and surrogate models, Struct Multidiscip Optim, 55, 3, 925-943 (2017) |

[25] | Lophaven SN, Nielsen H, Sndergaard J (2002) DACE—a MATLAB kriging toolbox |

[26] | Martinez Zapotecas S, Coello Coello C (2013) MOEA/D assisted by rbf networks for expensive multi-objective optimization problems. In: Genetic and evolutionary computation conference, GECCO ’13, Amsterdam, The Netherlands, July 6-10, 2013, pp 1405-1412 |

[27] | Müller J (2012) User guide for Modularized Surrogate Model Toolbox |

[28] | Omidvar, MN; Yang, M.; Mei, Y.; Li, X.; Yao, X., DG2: a faster and more accurate differential grouping for large-scale black-box optimization, IEEE Trans Evol Comput, 21, 6, 929-942 (2017) |

[29] | Parr, JM; Keane, AJ; Forrester, AIJ; Holden, CME, Infill sampling criteria for surrogate-based optimization with constraint handling, Eng Optim, 44, 10, 1147-1166 (2012) |

[30] | Potter MA, Jong KAD (1994) A cooperative coevolutionary approach to function optimization. In: Proceedings of the international conference on evolutionary computation. The Third conference on parallel problem solving from nature: parallel problem solving from nature, pp 249-257 |

[31] | Regis, RG; Shoemaker, CA, Constrained global optimization of expensive black box functions using radial basis functions, J Glob Optim, 31, 1, 153-171 (2005) · Zbl 1274.90511 |

[32] | Regis, RG; Shoemaker, CA, A stochastic radial basis function method for the global optimization of expensive functions, INFORMS J Comput, 19, 4, 497-509 (2007) · Zbl 1241.90192 |

[33] | Regis, RG; Shoemaker, CA, Improved strategies for radial basis function methods for global optimization, J Glob Optim, 37, 1, 113-135 (2007) · Zbl 1149.90120 |

[34] | Regis, RG; Shoemaker, CA, Parallel radial basis function methods for the global optimization of expensive functions, Eur J Oper Res, 182, 2, 514-535 (2007) · Zbl 1178.90279 |

[35] | Regis, RG; Shoemaker, CA, Parallel stochastic global optimization using radial basis functions, INFORMS J Comput, 21, 3, 411-426 (2009) · Zbl 1243.90160 |

[36] | Rezaveisi, M.; Sepehrnoori, K.; Johns, RT, Tie-simplex-based phase-behavior modeling in an IMPEC reservoir simulator, SPE J, 19, 2, 327-339 (2014) |

[37] | Ródenas, RG; López, ML; Verastegui, D., Extensions of Dinkelbach’s algorithm for solving non-linear fractional programming problems, Top, 7, 1, 33-70 (1999) · Zbl 0932.90043 |

[38] | Schonlau M (1997) Computer experiments and global optimization. Ph.D. thesis, University of Waterloo, Waterloo, Ontario, Canada |

[39] | Sóbester, A.; Leary, SJ; Keane, AJ, A parallel updating scheme for approximating and optimizing high fidelity computer simulations, Struct Multidiscip Optim, 27, 5, 371-383 (2004) |

[40] | Srinivas N, Krause A, Kakade S, Seeger M (2010) Gaussian process optimization in the bandit setting: no regret and experimental design. In: Proceedings of the 27th international conference on international conference on machine learning, ICML’10, Madison, WI, USA. Omnipress, pp 1015-1022 |

[41] | Tian, J.; Tan, Y.; Zeng, J.; Sun, C.; Jin, Y., Multi-objective infill criterion driven Gaussian process-assisted particle swarm optimization of high-dimensional expensive problems, IEEE Trans Evol Comput, 23, 3, 459-472 (2019) |

[42] | Torn A, Zilinskas A (1989) Global optimization, vol 350. Lecture Notes in Computer Science, Springer, Berlin · Zbl 0752.90075 |

[43] | Viana, FA; Haftka, RT; Watson, LT, Efficient global optimization algorithm assisted by multiple surrogate techniques, J Glob Optim, 56, 2, 669-689 (2013) · Zbl 1275.90072 |

[44] | Vu, KK; D’Ambrosio, C.; Hamadi, Y.; Liberti, L., Surrogate-based methods for black-box optimization, Int Trans Oper Res, 24, 3, 393-424 (2017) · Zbl 1366.90196 |

[45] | Wang, Y.; Liu, H.; Wei, F.; Zong, T.; Li, X., Cooperative coevolution with formula-based variable grouping for large-scale global optimization, Evol Comput, 26, 4, 569-596 (2018) |

[46] | Wolpert, DH; Macready, WG, No free lunch theorems for optimization, IEEE Trans Evol Comput, 1, 1, 67-82 (1997) |

[47] | Ye, KQ; Li, W.; Sudjianto, A., Algorithmic construction of optimal symmetric Latin hypercube designs, J Stat Plan Inference, 90, 145-159 (2000) · Zbl 1109.62329 |

[48] | Yi, M.; Xiaodong, L.; Xin, Y.; Omidvar, MN, A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization, ACM Trans Math Soft, 42, 2, 1-24 (2016) |

[49] | Zhan, D.; Qian, J.; Cheng, Y., Pseudo expected improvement criterion for parallel EGO algorithm, J Glob Optim, 68, 3, 641-662 (2017) · Zbl 1377.90069 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.