close
Skip to main content
Springer Nature Link
Log in

Development of an adaptive infill criterion for constrained multi-objective asynchronous surrogate-based optimization

  • Published:
Save article
View saved research
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The use of surrogate modeling techniques to efficiently solve a single objective optimization (SOO) problem has proven its worth in the optimization community. However, industrial problems are often characterized by multiple conflicting and constrained objectives. Recently, a number of infill criteria have been formulated to solve multi-objective optimization (MOO) problems using surrogates and to determine the Pareto front. Nonetheless, to accurately resolve the front, a multitude of optimal points must be determined, making MOO problems by nature far more expensive than their SOO counterparts. As of yet, even though access to of high performance computing is widely available, little importance has been attributed to batch optimization and asynchronous infill methodologies, which can further decrease the wall-clock time required to determine the Pareto front with a given resolution. In this paper a novel infill criterion is developed for generalized asynchronous multi-objective constrained optimization, which allows multiple points to be selected for evaluation in an asynchronous manner while the balance between design space exploration and objective exploitation is adapted during the optimization process in a simulated annealing like manner and the constraints are taken into account. The method relies on a formulation of the expected improvement for multi-objective optimization, where the improvement is formulated as the Euclidean distance from the Pareto front taken to a higher power. The infill criterion is tested on a series of test cases and proves the effectiveness of the novel scheme.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Reproduced from Forrester et al. [11]. (Color figure online)

Fig. 2

Reproduced from Keane [22]

Fig. 3
Fig. 4

Reproduced from Knowles [23]. (Color figure online)

Fig. 5
Fig. 6

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. Depending on whether it is the intent to improve upon the existing Pareto front (Fig. 2, hatched area) or refine the existing front (Fig. 2, gray area), the limits of the integrals are slightly different. Here, improvement upon the Pareto is presented. For further details on this matter, see [22].

  2. Theoretically the method can be rewritten for any number of objectives. However this method, as any other, is subjected to the curse of dimensionality (no-free-lunch theorem). In practice, defining the computational domain outside the Pareto front for more than two objectives can be become cumbersome [4] and is for most methods the limiting factor in their applicability.

  3. For a higher number of objectives, the multinomial theorem leads to the desired solution.

  4. Keane’s formulation is characterized by the absence of a definition of the improvement, but the presence of an analytical form of the expected improvement, which relies on the calculation of the centroid of the prediction outside the Pareto front and determining the distance to the nearest point on the front. Here the improvement is analytically defined as the Euclidean distance from the front. However, this leads to the absence of an analytical formulation of the expected improvement, unless the improvement is taken to an even power, as seen above. The calculation of the improvement relies on MCI where the distance of each sample is taken to the nearest point on the front.

  5. The addition of a point leads to a reduction of the improvement that can be made at the point to zero, thus GMOEI\(^{(1,0,2)}(\mathbf{x }_1,\mathbf{x }_2)=\)GMOEI\(^{(1,0,1)}(\mathbf{x }_1)=\)GMOEI\(^{(1,0,1)}(\mathbf{x }_2)\) if \(\mathbf{x }_1=\mathbf{x }_2\).

  6. The attainment surface was formally defined by Fonseca and Fleming and corresponds to the Pareto front [10]. Both terms are interchangeably used in the optimization community, but in the context of metrics the former is preferred.

References

  1. Chevalier, C.: Fast Computation of the Multi-Points Expected Improvement with Applications in Batch Selection (2013). https://doi.org/10.1007/978-3-642-44973-4_7

  2. Conn, A.R., Gould, N.I.M., Toint, P.L.: Comprehensive Description of the Mathematical Algorithms Used in LANCELOT, pp. 102–132. Springer, Berlin (1992). https://doi.org/10.1007/978-3-662-12211-2_3

  3. 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). https://doi.org/10.1007/s10898-013-0118-2

    Article  MathSciNet  MATH  Google Scholar 

  4. Couckuyt, I., Dhaene, T., Demeester, P.: ooDACE toolbox: a flexible object-oriented kriging implementation. J. Mach. Learn. Res. 15(1), 3183–3186 (2014)

    MATH  Google Scholar 

  5. 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). https://doi.org/10.1109/4235.996017

    Article  Google Scholar 

  6. Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable Test Problems for Evolutionary Multiobjective Optimization, pp. 105–145. Springer, London (2005). https://doi.org/10.1007/1-84628-137-7_6

    Book  MATH  Google Scholar 

  7. Emmerich, M., Deutz, A., Klinkenberg, J.W.: The computation of the expected improvement in dominated hypervolume of pareto front approximations. Report technical report 4-2008, Leiden Institute of Advanced Computer Science (2008)

  8. Fonseca, C.M., Fleming, P.J.: Genetic algorithms for multiobjective optimization: formulation discussion and generalization. In: Forrest, S. (ed.) Genetic Algorithms: Proceedings of the Fifth International Conference. Morgan Kaufmann, San Mateo, CA (1993)

  9. Fonseca, C.M., Fleming, P.J.: An overview of evolutionary algorithms in multiobjective optimization. Evol. Comput. 3(1), 1–16 (1995). https://doi.org/10.1162/evco.1995.3.1.1

    Article  Google Scholar 

  10. Fonseca, C.M., Fleming, P.J.: On the performance assessment and comparison of stochastic multiobjective optimizers. In: Voigt, H.M., Ebeling, W., Rechenberg, I., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature—PPSN IV, pp. 584–593. Springer, Berlin (1996)

    Chapter  Google Scholar 

  11. Forrester, A., Sobester, A., Keane, A.: Engineering Design Via Surrogate Modelling: A Practical Guide. Wiley, New York (2008)

    Book  Google Scholar 

  12. Gentle, J.E.: Computational Statistics. Springer, New York (2009). https://doi.org/10.1007/978-0-387-98144-4

    Book  MATH  Google Scholar 

  13. Ginsbourger, D., Janusevskis, J., Le Riche, R.: Dealing with asynchronicity in parallel Gaussian process based global optimization. Report (2011). https://hal.archives-ouvertes.fr/hal-00507632. Accessed 17 Feb 2020

  14. Ginsbourger, D., Le Riche, R., Carraro, L.: Kriging Is Well-Suited to Parallelize Optimization, pp. 131–162. Springer, Berlin (2010). https://doi.org/10.1007/978-3-642-10701-6_6

    Book  Google Scholar 

  15. Horn, J., Nafpliotis, N., Goldberg, D.E.: A niched pareto genetic algorithm for multiobjective optimization. In: Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, vol. 1, pp. 82–87 (1994). https://doi.org/10.1109/ICEC.1994.350037

  16. Janusevskis, J., Le Riche, R., Ginsbourger, D.: Parallel expected improvements for global optimization: summary, bounds and speed-up. Report (2011). https://hal.archives-ouvertes.fr/hal-00613971. Accessed 17 Feb 2020

  17. Janusevskis, J., Le Riche, R., Ginsbourger, D., Girdziusas, R.: Expected improvements for the asynchronous parallel global optimization of expensive functions: potentials and challenges. In: Hamadi, Y., Schoenauer, M. (eds.) Learning and Intelligent Optimization, pp. 413–418. Springer, Berlin (2012)

    Chapter  Google Scholar 

  18. Jeong, S., Obayashi, S.: Efficient global optimization (EGO) for multi-objective problem and data mining. In: 2005 IEEE Congress on Evolutionary Computation, vol. 3, pp. 2138–2145 (2005). https://doi.org/10.1109/CEC.2005.1554959

  19. Jones, D.R.: Direct Global Optimization Algorithm, pp. 431–440. Springer, Boston (2001). https://doi.org/10.1007/0-306-48332-7_93

    Book  Google Scholar 

  20. Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455–492 (1998). https://doi.org/10.1023/A:1008306431147

    Article  MathSciNet  MATH  Google Scholar 

  21. Kaiser, H.F., Dickman, K.: Sample and population score matrices and sample correlation matrices from an arbitrary population correlation matrix. Psychometrika 27(2), 179–182 (1962). https://doi.org/10.1007/BF02289635

    Article  MathSciNet  MATH  Google Scholar 

  22. Keane, A.J.: Statistical improvement criteria for use in multiobjective design optimization. AIAA J. 44(4), 879–891 (2006). https://doi.org/10.2514/1.16875

    Article  Google Scholar 

  23. Knowles, J.: Parego: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comput. 10(1), 50–66 (2005). https://doi.org/10.1109/TEVC.2005.851274

    Article  Google Scholar 

  24. Knowles, J., Corne, D.: The pareto archived evolution strategy: a new baseline algorithm for pareto multiobjective optimisation. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), vol. 1 (1999). https://doi.org/10.1109/CEC.1999.781913

  25. Marmin, S., Chevalier, C., Ginsbourger, D.: Differentiating the multipoint expected improvement for optimal batch design. In: Pardalos, P., Pavone, M., Farinella, G.M., Cutello, V. (eds.) Machine Learning, Optimization, and Big Data, pp. 37–48. Springer, Berlin (2015)

    Chapter  Google Scholar 

  26. McKay, M.D., Beckman, R.J., Conover, W.J.: A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21(2), 239–245 (1979). https://doi.org/10.2307/1268522

    Article  MathSciNet  MATH  Google Scholar 

  27. Mockus, J., Tiesis, V., Zilinskas, A.: The application of Bayesian methods for seeking the extremum. In: Szego L.D.G. (eds.) Towards Global Optimization 2: Proceedings of a Workshop at the University of Cagliari, Italy, October 1974, vol. 2, pp. 117–129 (1978)

  28. Morris, M.D., Mitchell, T.J.: Exploratory designs for computational experiments. J. Stat. Plan. Inference 43(3), 381–402 (1995). https://doi.org/10.1016/0378-3758(94)00035-T

    Article  MATH  Google Scholar 

  29. Osyczka, A., Kundu, S.: A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm. Struct. Optim. 10(2), 94–99 (1995). https://doi.org/10.1007/BF01743536

    Article  Google Scholar 

  30. Parr, J.M., Keane, A.J., Forrester, A.I.J., Holden, C.M.E.: Infill sampling criteria for surrogate-based optimization with constraint handling. Eng. Optim. 44(10), 1147–1166 (2012). https://doi.org/10.1080/0305215X.2011.637556

    Article  MATH  Google Scholar 

  31. Ponweiser, W., Wagner, S., Vincze, M.: Clustered multiple generalized expected improvement: a novel infill sampling criterion for surrogate models. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 3515–3522 (2008). https://doi.org/10.1109/CEC.2008.4631273

  32. Quinonero-Candela, J., Rasmussen, C.E.: A unifying view of sparse approximate Gaussian process regression. J. Mach. Learn. Res. 6, 1939–1959 (2005)

    MathSciNet  MATH  Google Scholar 

  33. Rasmussen, C.E., Williams, C.K.I.: Gaussian Processes for Machine Learning. The MIT Press, Cambridge (2006)

    MATH  Google Scholar 

  34. Riquelme, N., Von Lücken, C., Barán, B.: Performance metrics in multi-objective optimization. In: XLI Latin American Computing Conference (CLEI) (2015)

  35. Sasena, M., Papalambros, P., Goovaerts, P.: Exploration of meta-modeling sampling criteria for constrained global optimization. Eng. Optim. 34, 263–278 (2002)

    Article  Google Scholar 

  36. Schonlau, M., Welch, W.J., Jones, D.R.: Global versus local search in constrained optimization of computer models. In: Lecture Notes Monograph Series, vol. 34, pp. 11–25. Institute of Mathematical Statistics, Hayward, CA (1998). https://doi.org/10.1214/lnms/1215456182

  37. Srinivas, N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput. 2(3), 221–248 (1994). https://doi.org/10.1162/evco.1994.2.3.221

    Article  Google Scholar 

  38. Stein, M.: Interpolation of Spatial Data. Springer, New York (1999)

    Book  Google Scholar 

  39. Sóbester, A., Leary, S.J., Keane, A.J.: A parallel updating scheme for approximating and optimizing high fidelity computer simulations. Struct. Multidiscip. Optim. 27(5), 371–383 (2004). https://doi.org/10.1007/s00158-004-0397-9

    Article  Google Scholar 

  40. Van Veldhuizen, D.A., Lamont, G.B.: On measuring multiobjective evolutionary algorithm performance. In: Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), vol. 1, pp. 204–211 (2000). https://doi.org/10.1109/CEC.2000.870296

  41. Voutchkov, I., Keane, A.: Multi-Objective Optimization Using Surrogates, pp. 155–175. Springer, Berlin (2010)

    MATH  Google Scholar 

  42. Wagner, T., Emmerich, M., Deutz, A., Ponweiser, W.: On expected-improvement criteria for model-based multi-objective optimization. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) Parallel Problem Solving from Nature, PPSN XI, pp. 718–727. Springer, Berlin (2010)

    Google Scholar 

  43. Zhang, Q., Liu, W., Tsang, E., Virginas, B.: Expensive multiobjective optimization by moea/d with Gaussian process model. IEEE Trans. Evol. Comput. 14(3), 456–474 (2010). https://doi.org/10.1109/TEVC.2009.2033671

    Article  Google Scholar 

  44. Zhigljavsky, A., Zilinskas, A.: Selection of a covariance function for a Gaussian random field aimed for modeling global optimization problems. Optim. Lett. 13, 249–259 (2019). https://doi.org/10.1007/s11590-018-1372-5

    Article  MathSciNet  MATH  Google Scholar 

  45. Zilinskas, A.: A statistical model-based algorithm for ‘black-box’ multi-objective optimisation. Int. J. Syst. Sci. 45, 82–93 (2014). https://doi.org/10.1080/00207721.2012.702244

    Article  MathSciNet  MATH  Google Scholar 

  46. Zilinskas, A., Calvin, J.: Bi-objective decision making in global optimization based on statistical models. J. Glob. Optim. 74, 599–609 (2019). https://doi.org/10.1007/s10898-018-0622-5

    Article  MathSciNet  MATH  Google Scholar 

  47. Zitzler, E., Deb, K., Thiele, F.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173–195 (2000). https://doi.org/10.1162/106365600568202

    Article  Google Scholar 

  48. Zitzler, E., Thiele, F., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003). https://doi.org/10.1109/TEVC.2003.810758

    Article  Google Scholar 

  49. Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature—PPSN V, pp. 292–301. Springer, Berlin (1998)

    Chapter  Google Scholar 

Download references

Acknowledgements

The authors would like to thank prof. dr. ir. Jan Vierendeels; his input, supervision, guidance and support during this research has been of critical value.

Author information

Authors and Affiliations

  1. Department of Electromechanical, Systems and Metal Engineering, Ghent University, Sint-Pietersnieuwstraat 41, 9000, Ghent, Belgium

    Jolan Wauters & Joris Degroote

  2. Flanders Make, Lommel, Belgium

    Jolan Wauters & Joris Degroote

  3. Computational Engineering and Design Group, University of Southampton, Boldrewood Innovation Campus, Burgess Rd, Southampton, SO16 7QF, UK

    Andy Keane

Authors
  1. Jolan Wauters
    View author publications

    Search author on:PubMed Google Scholar

  2. Andy Keane
    View author publications

    Search author on:PubMed Google Scholar

  3. Joris Degroote
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Jolan Wauters.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Conducted as part of the SBO research project 140068 EUFORIA (Efficient Uncertainty quantification For Optimization in Robust design of Industrial Applications) under the financial support of the IWT, the Flemish agency of Innovation through Science and Technology.

Appendix: Test functions

Appendix: Test functions

  • Zitzler et al.’s first test function (ZDT1), \({\mathcal {F}}_1\), has a convex optimal front with \(m=6\) and \(x_i\in [0,1]\). The front is formed with \(g(\mathbf{x })=1\) [47].

    $$\begin{aligned} f_1(x_1){}&= x_1 \nonumber \\ g(x_2, \ldots ,x_m){}&= 1+9\cdot \sum _{i=2}^{m}x_i/(m-1) \nonumber \\ h(f_1,g){}&= 1-\sqrt{f_1/g} \nonumber \\ f_2(\mathbf {x}){}&= g \cdot h \end{aligned}$$
    (31)

  • Zitzler et al.’s second test function (ZDT2), \({\mathcal {F}}_2\), has a non-convex optimal front with \(m=6\) and \(x_i\in [0,1]\). The front is formed with \(g(\mathbf{x })=1\) [47].

    $$\begin{aligned} f_1(x_1){}&= x_1 \nonumber \\ f_2(\mathbf {x}){}&= g \cdot h \nonumber \\ g(x_2, \ldots ,x_m){}&= 1+9\cdot \sum _{i=2}^{m}x_i/(m-1) \nonumber \\ h(f_1,g){}&= 1-(f_1/g)^2 \end{aligned}$$
    (32)

  • Zitzler et al.’s third test function (ZDT3), \({\mathcal {F}}_3\), has a non-continuous convex front caused by the introduction of the sine function in \(h(\mathbf{x })\) with \(m=6\) and \(x_i\in [0,1]\). The front is formed with \(g(\mathbf{x })=1\) [47].

    $$\begin{aligned} f_1(x_1){}&= x_1 \nonumber \\ f_2(\mathbf {x}){}&= g \cdot h \nonumber \\ g(x_2, \ldots ,x_m){}&= 1+9\cdot \sum _{i=2}^{m}x_i/(m-1) \nonumber \\ h(f_1,g){}&= 1-\sqrt{f_1/g}-(f_1/g)\text {sin}(10\pi f_1) \end{aligned}$$
    (33)

  • Zitzler et al.’s fourth test function (ZDT4), \({\mathcal {F}}_4\), has a convex front with \(m=6\) and \(x_i\in [0,1]\). There is a multitude of local fronts formed with \(g(\mathbf{x })=1.25\) and a global one with \(g(\mathbf{x })=1\) [47].

    $$\begin{aligned} f_1(x_1){}&= x_1 \nonumber \\ f_2(\mathbf {x}){}&= g \cdot h \nonumber \\ g(x_2, \ldots ,x_m){}&= 1+10(m-1)+\sum _{i=2}^{m}((10x_i-5)^2-10\text {cos}(4\pi (10x_i-5))) \nonumber \\ h(f_1,g){}&= 1-\sqrt{f_1/g} \end{aligned}$$
    (34)

  • Zitzler et al.’s sixt test function (ZDT6), \({\mathcal {F}}_6\), has a strong non-uniformity of the search space with the Pareto front found in the lowest density region with \(m=6\) and \(x_i\in [0,1]\). The global front is formed with \(g(\mathbf{x })=1\) [47].

    $$\begin{aligned} f_1(x_1){}&= 1-\text {exp}(-4x_1)\text {sin}^6(6\pi x_1) \nonumber \\ f_2(\mathbf {x}){}&= g \cdot h \nonumber \\ g(x_2, \ldots ,x_m){}&= 1+9\cdot \left( \sum _{i=2}^{m}x_i/(m-1)\right) ^{0.25} \nonumber \\ h(f_1,g){}&= 1-(f_1/g)^2 \end{aligned}$$
    (35)

  • Osyczka and Kundu constrained test problem [29] (OSY). The Pareto front is made up out of 5 sections with different constraints active. The parameter combinations are given in Table 4.

    $$\begin{aligned} f_1(\mathbf {x}){}&= \frac{-(10x_1-2)^2}{60} -\frac{(10x_2-2)^2}{300}-\frac{4x_3^2}{75} -\frac{(3x_4-2)^2}{150}-\frac{4x_5^2}{75}+1 \nonumber \\ f_2(\mathbf {x}){}&= \frac{5x_1^2}{9}+\frac{5x_2^2}{9}+\frac{(4x_3+1)^2}{300} +\frac{x_4^2}{5}+\frac{5x_5^2}{36}+\frac{5x_6^2}{9} \nonumber \\ g_1(\mathbf {x}){}&= 10x_1+10x_2-2\ge 0 \nonumber \\ g_2(\mathbf {x}){}&= 6-10x_1-10x_2\ge 0 \nonumber \\ g_3(\mathbf {x}){}&= 2+10x_1-10x_2\ge 0 \nonumber \\ g_4(\mathbf {x}){}&= 2-10x_1+30x_2\ge 0 \nonumber \\ g_5(\mathbf {x}){}&= 4-(4x_3-2)^2-6x_4\ge 0 \nonumber \\ g_6(\mathbf {x}){}&= (4x_5-2)^2+10x_6-4\ge 0 \end{aligned}$$
    (36)
Table 4 Solution of the Osyczka and Kundu constrained test problem [29] taken from Deb et al. [6]
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wauters, J., Keane, A. & Degroote, J. Development of an adaptive infill criterion for constrained multi-objective asynchronous surrogate-based optimization. J Glob Optim 78, 137–160 (2020). https://doi.org/10.1007/s10898-020-00903-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10898-020-00903-1

Keywords