article

ParEGO extensions for multi-objective optimization of expensive evaluation functions

Authors:

Joan Davins-Valldaura,

Saïd Moussaoui,

Guillermo Pita-Gil,

Franck PlestanAuthors Info & Claims

Journal of Global Optimization, Volume 67, Issue 1-2

Pages 79 - 96

https://doi.org/10.1007/s10898-016-0419-3

Published: 01 January 2017 Publication History

Abstract

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.

References

[1]

Auger, A., Bader, J., Brockhoff, D., Zitzler, E.: Hypervolume-based multiobjective optimization: theoretical foundations and practical implications. Theor. Comput. Sci. 425, 75---103 (2012)

Digital Library

[2]

Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York (2004)

Digital Library

[3]

Clausen, J.: Branch and bound algorithms principles and examples. Technical report, Department of Computer Science, University of Copenhagen (1999)

[4]

Coello, C.A.C., Pulido, G.T., Lechuga, M.S.: Handling multiple objectives with particle swarm optimization. IEEE Trans. Evol. Comput. 8(3), 256---279 (2004)

Digital Library

[5]

Coello, C.C., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-objective Problems. Springer, US (2007)

Digital Library

[6]

Collette, Y., Siarry, P.: Multiobjective Optimization: Principles and Case Studies. Springer-Verlag, Berlin/Heidelberg (2004)

[7]

Corne, D.W., Jerram, N.R., Knowles, J.D., Oates, M.J.: Pesa-II: region-based selection in evolutionary multiobjective optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pp. 283---290 (2001)

Digital Library

[8]

Davins-Valldaura, J., Plestan, F., Moussaoui, S., Pita Gil, G.: Design and optimization of nonlinear observers for road curvature and state estimation in autonomous vehicles. IEEE Trans. Intell. Transp. Syst. (submitted paper)

[9]

Davins-Valldaura, J., Plestan, F., Moussaoui, S., Gil, Pita, G.: Observers design for the road curvature estimation in traffic jam pilot system. In: Submitted to European Control Conference. Aalborg, Denmark (2016)

[10]

Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182---197 (2000)

Digital Library

[11]

El Tannoury, C., Moussaoui, S., Plestan, F., Romani, N., Pita Gil, G.: Synthesis and application of nonlinear observers for the estimation of tire effective tadius and rolling resistance of an automotive vehicle. IEEE Trans. Control Syst. Technol. 21(6), 2408---2416 (2013)

[12]

Friedman, J.H.: Multivariate adaptive regression splines. Ann. Stat. 19(1), 1---67 (1991)

[13]

Gutmann, H.M.: A radial basis function method for global optimization. J. Glob. Optim. 19, 201---227 (2001)

Digital Library

[14]

Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evol. Comput. 10(5), 477---506 (2006)

Digital Library

[15]

John, H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Cambridge (1975)

[16]

Jones, D.R.: A taxonomy of global optimization methods based on response surfaces. J. Glob. Optim. 21, 345---383 (2001)

Digital Library

[17]

Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the lipschitz constant. J. Optim. Theory Appl. 79(1), 157---181 (1993)

Digital Library

[18]

Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455---492 (1998)

Digital Library

[19]

Kennedy, J., Eberhart, R.C.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, pp. 1942---1948 (1995)

[20]

Kleijnen, J.: Kriging metamodeling in simulation: a review. Eur. J. Oper. Res. 192(3), 707---716 (2009)

[21]

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)

Digital Library

[22]

Knowles, J., Hughes, E.J.: Multiobjective optimization on a budget of 250 evaluations. In: Evolutionary Multi-Criterion Optimization, vol. 3410. Springer, Berlin/Heidelberg (2005)

Digital Library

[23]

Knowles, J., Nakayama, H.: Meta-modeling in multiobjective optimization. Multiobjective Optim. 5252, 245---284 (2008)

Digital Library

[24]

Mayer, H.: Comparative diagnosis of tyre pressures. In: Proceedings of 3rd IEEE Conference on Control Applications, pp. 627---632. Glasgow, UK (1994)

[25]

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)

[26]

Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087---1092 (1953)

[27]

Minoux, M.: Programation Mathématique : Théorie et Algorithmes, vol. 14. Lavoisier, Paris (1962)

[28]

Müller, W.: Collecting Spatial Data: Optimum Design of Experiments for Random Fields. Springer-Verlag, Berlin/Heidelberg (2007)

[29]

Persson, N., Gustafsson, F., Drevo, M.: Indirect tire pressure monitoring using sensor fusion. In: Proceedings of 2002 SAE World Congress and Exhibition (2002)

[30]

Praveen, C., Duvigneau, R.: Study of some strategies for global optimization using Gaussian process models with application to aerodynamic design. Research report, INRIA (2009)

[31]

Priddy, K., Keller, P.: Artificial Neural Networks: An Introduction. Society of Photo Optical, Tutorial Text Series, vol. 68. SPIE Press (2005)

Digital Library

[32]

Zhang, Q., Liu, B., Liu, E.G.: Design of tire pressure monitoring system based on resonance frequency method. In. In Proceedings of IEEE/ASME International Conference on Advanced Intelligent Mechatronics (2009)

[33]

Regis, R., Shoemaker, C.: Improved strategies for radial basis function methods for global optimization. J. Glob. Optim. 37(1), 113---135 (2007)

Digital Library

[34]

Rios, L., Sahinidis, N.: Derivative-free optimization: a review of algorithms and comparison of software implementations. J. Glob. Optim. 56(3), 1247---1293 (2013)

[35]

Sen, K., Stoffa, P.: Global optimization methods in geophysical inversion. Cambridge University Press, London (2013)

[36]

Simpson, T., Mauery, T., Korte, J., Mistree, F.: Comparison of response surface and kriging models for multidisciplinary design. Proceedings of 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization vol. 1, pp. 381---391 (1998)

[37]

Smith, R.L.: Efficient monte carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32(6), 1296---1308 (1984)

Digital Library

[38]

Smola, A.J., Schölkopf, B.: A tutorial on support vector regression. Stat. Comput. 14(3), 199---222 (2004)

Digital Library

[39]

Stein, M.: Interpolation of Spatial Data: Some Theory for Kriging. Springer, New York (1999)

[40]

Velupillai, S., Guveng, L.: Tire pressure monitoring. IEEE Control Syst. Mag. 27(6), 22---25 (2007)

[41]

Voutchkov, I., Keane, A.: Multi-objective optimization using surrogates. Comput. Intell. Optim. Adapt. Learn. Optim. 7, 155---175 (2010)

[42]

Zitzler, E., Knowles, J., Thiele, L.: Quality assessment of pareto set approximations. In: Branke, J., Deb, K., Miettinen, K., Sowiski, R. (eds.) Multiobjective Optimization. Lecture Notes in Computer Science, vol. 5252, pp. 373---404. Springer, Berlin (2008)

Digital Library

[43]

Zitzler, E., Laumanns, M., Thiele, L.: Spea 2: Improving the strength pareto evolutionary algorithm. Technical report (2001)

[44]

Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7, 117---132 (2002)

Digital Library

Cited By

Khosravi HOlajire TRaihan AAhmed I(2024)A data driven sequential learning framework to accelerate and optimize multi-objective manufacturing decisionsJournal of Intelligent Manufacturing10.1007/s10845-024-02337-y35:8(4087-4112)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10845-024-02337-y
Dooley SSukthanker RDickerson JWhite CHutter FGoldblum MOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Rethinking bias mitigationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669373(74366-74393)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669373
Loka NCouckuyt IGarbuglia FSpina DVan Nieuwenhuyse IDhaene T(2022)Bi-objective Bayesian optimization of engineering problems with cheap and expensive cost functionsEngineering with Computers10.1007/s00366-021-01573-739:3(1923-1933)Online publication date: 25-Jan-2022
https://dl.acm.org/doi/10.1007/s00366-021-01573-7
Show More Cited By

ParEGO extensions for multi-objective optimization of expensive evaluation functions
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Pareto Artificial Life Algorithm for Multi-Objective Optimization

Most engineering optimization uses multiple objective functions rather than single objective function. To realize an artificial life algorithm based multi-objective optimization, this paper proposes a Pareto artificial life algorithm that is capable of ...
Multi objective optimization of computationally expensive multi-modal functions with RBF surrogates and multi-rule selection

GOMORS is a parallel response surface-assisted evolutionary algorithm approach to multi-objective optimization that is designed to obtain good non-dominated solutions to black box problems with relatively few objective function evaluations. GOMORS uses ...
Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front

In evolutionary multi-objective optimization (EMO), the convergence to the Pareto set of a multi-objective optimization problem (MOP) and the diversity of the final approximation of the Pareto front are two important issues. In the existing definitions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 67, Issue 1-2

January 2017

440 pages

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khosravi HOlajire TRaihan AAhmed I(2024)A data driven sequential learning framework to accelerate and optimize multi-objective manufacturing decisionsJournal of Intelligent Manufacturing10.1007/s10845-024-02337-y35:8(4087-4112)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s10845-024-02337-y
Dooley SSukthanker RDickerson JWhite CHutter FGoldblum MOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Rethinking bias mitigationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669373(74366-74393)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669373
Loka NCouckuyt IGarbuglia FSpina DVan Nieuwenhuyse IDhaene T(2022)Bi-objective Bayesian optimization of engineering problems with cheap and expensive cost functionsEngineering with Computers10.1007/s00366-021-01573-739:3(1923-1933)Online publication date: 25-Jan-2022
https://dl.acm.org/doi/10.1007/s00366-021-01573-7
Saadatpour MJavaheri SAfshar ASandoval Solis S(2021)Optimization of selective withdrawal systems in hydropower reservoir considering water quality and quantity aspectsExpert Systems with Applications: An International Journal10.1016/j.eswa.2021.115474184:COnline publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1016/j.eswa.2021.115474
Trivedi VRamteke M(2021)Using following heroes operation in multi-objective differential evolution for fast convergenceApplied Soft Computing10.1016/j.asoc.2021.107225104:COnline publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1016/j.asoc.2021.107225
Aghamohammadi NSalomon SYan YPurshouse R(2017)On the Effect of Scalarising Norm Choice in a ParEGO implementation9th International Conference on Evolutionary Multi-Criterion Optimization - Volume 1017310.1007/978-3-319-54157-0_1(1-15)Online publication date: 19-Mar-2017
https://dl.acm.org/doi/10.1007/978-3-319-54157-0_1

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents