×

zbMATH — the first resource for mathematics

Targeting solutions in Bayesian multi-objective optimization: sequential and batch versions. (English) Zbl 1432.90138
Summary: Multi-objective optimization aims at finding trade-off solutions to conflicting objectives. These constitute the Pareto optimal set. In the context of expensive-to-evaluate functions, it is impossible and often non-informative to look for the entire set. As an end-user would typically prefer a certain part of the objective space, we modify the Bayesian multi-objective optimization algorithm which uses Gaussian Processes and works by maximizing the Expected Hypervolume Improvement, to focus the search in the preferred region. The cumulated effects of the Gaussian Processes and the targeting strategy lead to a particularly efficient convergence to the desired part of the Pareto set. To take advantage of parallel computing, a multi-point extension of the targeting criterion is proposed and analyzed.

MSC:
90C29 Multi-objective and goal programming
62F15 Bayesian inference
65K05 Numerical mathematical programming methods
Software:
SPACE; ParEGO; EGO; SMS-EMOA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Auger, A., Bader, J., Brockhoff, D., Zitzler, E.: Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point. In: Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms, pp 87-102. ACM (2009) · Zbl 1369.68293
[2] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Hypervolume-based multiobjective optimization: theoretical foundations and practical implications, Theor. Comput. Sci., 425, 75-103 (2012) · Zbl 1242.90205
[3] Auger, A., Hansen, N.: Performance evaluation of an advanced local search evolutionary algorithm. In: IEEE Congress on Evolutionary Computation, vol. 2, p 2005. IEEE (2005)
[4] Bechikh, S.; Kessentini, M.; Said, Lb; Ghédira, K., Chap. 4: preference incorporation in evolutionary multiobjective optimization: a survey of the state-of-the-art, Adv. Comput., 98, 141-207 (2015)
[5] Beume, N.; Naujoks, B.; Emmerich, M., Sms-emoa: multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[6] Binois, M.; Ginsbourger, D.; Roustant, O., Quantifying uncertainty on Pareto fronts with Gaussian process conditional simulations, Eur. J. Oper. Res., 243, 2, 386-394 (2015) · Zbl 1346.90730
[7] Branke, J., Deb, K., Dierolf, H., Osswald, M.: Finding knees in multi-objective optimization. In: International Conference on Parallel Problem Solving from Nature, pp 722-731. Springer (2004)
[8] Branke, J.; Deb, K.; Miettinen, K.; Slowiński, R., Multiobjective Optimization: Interactive and Evolutionary Approaches, vol. 5252 (2008), Berlin: Springer, Berlin · Zbl 1147.68304
[9] Buchanan, J.; Gardiner, L., A comparison of two reference point methods in multiple objective mathematical programming, Eur. J. Oper. Res., 149, 1, 17-34 (2003) · Zbl 1035.90078
[10] Chevalier, C., Ginsbourger, D.: Fast computation of the multi-points expected improvement with applications in batch selection. In: International Conference on Learning and Intelligent Optimization, pp 59-69. Springer (2013)
[11] Couckuyt, I.; Deschrijver, D.; Dhaene, T., Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization, J. Glob. Optim., 60, 3, 575-594 (2014) · Zbl 1303.90093
[12] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[13] Deb, K., Sundar, J.: Reference point based multi-objective optimization using evolutionary algorithms. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp 635-642. ACM (2006)
[14] Emmerich, M., Deutz, A., Klinkenberg, J.W.: Hypervolume-based expected improvement: monotonicity properties and exact computation. In: IEEE Congress on Evolutionary Computation (CEC), 2011, pp 2147-2154. IEEE (2011)
[15] Emmerich, M., Yang, K., Deutz, A., Wang, H., Fonseca, C.M.: A multicriteria generalization of Bayesian global optimization. In: Advances in Stochastic and Deterministic Global Optimization, pp 229-242. Springer (2016) · Zbl 1355.90071
[16] Feliot, P.: Une approche Bayesienne pour L’optimisation multi-objectif sous contraintes. PhD thesis, Universite Paris-Saclay (2017)
[17] Feliot, Paul; Bect, Julien; Vazquez, Emmanuel, User Preferences in Bayesian Multi-objective Optimization: The Expected Weighted Hypervolume Improvement Criterion, Machine Learning, Optimization, and Data Science, 533-544 (2019), Cham: Springer International Publishing, Cham
[18] Frazier, P.I., Clark, S.C.: Parallel global optimization using an improved multi-points expected improvement criterion. In: INFORMS Optimization Society Conference, Miami FL, vol. 26 (2012)
[19] Gal, T.; Stewart, T.; Hanne, T., Multicriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications, vol. 21 (1999), Berlin: Springer, Berlin
[20] Gaudrie, D., Le Riche, R., Enaux, B., Herbert, V.: Budgeted multi-objective optimization with a focus on the central part of the pareto front-extended version. arXiv:1809.10482 (2018)
[21] Ginsbourger, D., Janusevskis, J., Le Riche, R.: Dealing with asynchronicity in parallel gaussian process based global optimization. In: 4th International Conference of the ERCIM WG on computing and statistics (ERCIM’11) (2011)
[22] Ginsbourger, D., Riche, R.L.: Towards GP-based optimization with finite time horizon. Technical report, Centre d’Hydrogéologie et de Géothermie de Neuchâtel (2009)
[23] Ginsbourger, D., Le Riche, R., Carraro, L.: Kriging is well-suited to parallelize optimization. In: Computational Intelligence in Expensive Optimization Problems, pp 131-162. Springer (2010)
[24] Horn, D., Wagner, T., Biermann, D., Weihs, C., Bischl, B.: Model-based multi-objective optimization: taxonomy, multi-point proposal, toolbox and benchmark. In: International Conference on Evolutionary Multi-Criterion Optimization, pp 64-78. Springer (2015)
[25] Ishibuchi, H., Hitotsuyanagi, Y., Tsukamoto, N., Nojima, Y.: Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space. In: International Conference on Parallel Problem Solving from Nature, pp 91-100. Springer (2010)
[26] Janusevskis, J., Riche, R.L., Ginsbourger, D.: Parallel expected improvements for global optimization: summary, bounds and speed-up. Technical report, Institut Fayol, École des Mines de Saint-Étienne (2011)
[27] Janusevskis, J., Le Riche, R., Ginsbourger, D., Girdziusas, R.: Expected improvements for the asynchronous parallel global optimization of expensive functions: potentials and challenges. In: Learning and Intelligent Optimization, pp 413-418. Springer (2012)
[28] Jones, Dr; Schonlau, M.; Welch, W., Efficient Global Optimization of expensive black-box functions, J. Glob. Optim., 13, 4, 455-492 (1998) · Zbl 0917.90270
[29] Kalai, Ehud; Smorodinsky, Meir, Other Solutions to Nash’s Bargaining Problem, Econometrica, 43, 3, 513 (1975) · Zbl 0308.90053
[30] Keane, Aj, Statistical improvement criteria for use in multiobjective design optimization, AIAA J., 44, 4, 879-891 (2006)
[31] Knowles, J., ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems, IEEE Trans. Evol. Comput., 10, 1, 50-66 (2006)
[32] Marmin, S., Chevalier, C., Ginsbourger, D.: Differentiating the multipoint expected improvement for optimal batch design. In: International Workshop on Machine Learning, Optimization and Big Data, pp 37-48. Springer (2015)
[33] Marmin, S., Chevalier, C., Ginsbourger, D.: Efficient batch-sequential bayesian optimization with moments of truncated gaussian vectors. arXiv:1609.02700 (2016)
[34] Miettinen, K., Nonlinear Multiobjective Optimization, vol. 12 (1998), Berlin: Springer, Berlin
[35] Molchanov, I., Theory of Random Sets, vol. 19 (2005), Berlin: Springer, Berlin · Zbl 1109.60001
[36] Pardalos, Pm; Žilinskas, A.; Žilinskas, J., Non-convex Multi-Objective Optimization (2017), Berlin: Springer, Berlin · Zbl 1372.90004
[37] Parr, J.: Improvement criteria for constraint handling and multiobjective optimization. PhD thesis, University of Southampton (2013)
[38] Picheny, V., Multiobjective optimization using Gaussian process emulators via stepwise uncertainty reduction, Stat. Comput., 25, 6, 1265-1280 (2015) · Zbl 1331.90102
[39] Ponweiser, W., Wagner, T., Biermann, D., Vincze, M.: Multiobjective optimization on a limited budget of evaluations using model-assisted S-metric selection. In: International Conf. on Parallel Problem Solving from Nature, pp 784-794. Springer (2008)
[40] Ribaud, M.: Krigeage pour la conception de turbomachines: grande dimension et optimisation robuste. PhD thesis Université de Lyon (2018)
[41] Sawaragi, Y.; Nakayama, H.; Tanino, T., Theory of Multiobjective Optimization, vol. 176 (1985), Amsterdam: Elsevier, Amsterdam · Zbl 0566.90053
[42] Schonlau, M.: Computer experiments and global optimization. PhD thesis, University of Waterloo (1997)
[43] Svenson, J.: Computer experiments: multiobjective optimization and sensitivity analysis. PhD thesis, The Ohio State University (2011)
[44] Svenson, J.; Santner, Tj, Multiobjective Optimization of Expensive Black-Box Functions via Expected Maximin Improvement, 32-32 (2010), Ohio: The Ohio State University Columbus, Ohio
[45] Triantaphyllou, E.: Multi-criteria decision making methods. In: Multi-Criteria Decision Making Methods: a Comparative Study, pp 5-21. Springer (2000) · Zbl 0980.90032
[46] While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, IEEE Trans. Evol. Comput., 16, 1, 86-95 (2012)
[47] Wierzbicki, A.: The use of reference objectives in multiobjective optimization. In: Multiple Criteria Decision Making Theory and Application, pp 468-486. Springer (1980) · Zbl 0435.90098
[48] Wierzbicki, A.: Reference point approaches. In: Gal, T., Stewart, T., Hanne, T. (eds.) Multicriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications, pp 237-275. Springer (1999) · Zbl 0978.90085
[49] Yang, K.; Emmerich, M.; Deutz, A.; Bäck, T., Multi-objective Bayesian global optimization using expected hypervolume improvement gradient, Swarm Evol. Comput., 44, 945-956 (2019)
[50] Yang, K., Emmerich, M., Deutz, A., Fonseca, C.M.: Computing 3-D expected hypervolume improvement and related integrals in asymptotically optimal time. In: International Conference on Evolutionary Multi-Criterion Optimization, pp 685-700. Springer (2017)
[51] Yang, K., Li, L., Deutz, A., Bäck, T., Emmerich, M.: Preference-based multiobjective optimization using truncated expected hypervolume improvement. In: 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD), pp 276-281. IEEE (2016)
[52] Zeleny, M.: The theory of the displaced ideal. In: Multiple Criteria Decision Making Kyoto 1975, pp 153-206. Springer (1976)
[53] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms empirical results, Evol. Comput., 8, 2, 173-195 (2000)
[54] Zitzler, E.: Evolutionary algorithms for multiobjective optimization: methods and applications. Citeseer (1999)
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.