research-article

Constraint handling in efficient global optimization

Authors:

Samineh Bagheri,

Wolfgang Konen,

Richard Allmendinger,

Jürgen Branke,

Jonathan Fieldsend,

Domenico Quagliarella,

Karthik SindhyaAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 673 - 680

https://doi.org/10.1145/3071178.3071278

Published: 01 July 2017 Publication History

Abstract

Real-world optimization problems are often subject to several constraints which are expensive to evaluate in terms of cost or time. Although a lot of effort is devoted to make use of surrogate models for expensive optimization tasks, not many strong surrogate-assisted algorithms can address the challenging constrained problems. Efficient Global Optimization (EGO) is a Kriging-based surrogate-assisted algorithm. It was originally proposed to address unconstrained problems and later was modified to solve constrained problems. However, these type of algorithms still suffer from several issues, mainly: (1) early stagnation, (2) problems with multiple active constraints and (3) frequent crashes. In this work, we introduce a new EGO-based algorithm which tries to overcome these common issues with Kriging optimization algorithms. We apply the proposed algorithm on problems with dimension d ≤ 4 from the G-function suite [16] and on an airfoil shape example.

References

[1]

I. H. A. Abbot and A. E. von Doenhoff. 1959. Theory of wing sections, including a summary of airfoil data. Dover Publications, New York.

[2]

C. Audet, A. J. Booker, Dennis, Jr, P. D. Frank, and D. W. Moore. 2000. A Surrogate-Model-Based Method For Constrained Optimization. In AIAA/ISSMO. 2000--4891.

[3]

S. Bagheri, W. Konen, and T. Bäck. 2016. Online selection of surrogate models for constrained black-box optimization. In IEEE SSCI'2016. 1--8.

[4]

A. J. Booker, J. E. Dennis, P. D. Frank, D. B. Serafini, V. Torczon, and M. W. Trosset. 1999. A rigorous framework for optimization of expensive functions by surrogates. Structural Optimization 17, 1 (1999), 1--13.

[5]

M. Drela. 1989. XFOIL: An Analysis and Design System for Low Reynolds Number Airfoils. In Conference on Low Reynolds Number Airfoil Aerodynamics. University of Notre Dame. http://web.mit.edu/drela/Public/papers/xfoil_sv.pdf

[6]

M. Drela and M. B. Giles. 1987. Viscous-Inviscid Analysis of Transonic and Low Reynolds Number Airfoils. AIAA Journal 25, 10 (Oct. 1987), 1347--1355.

[7]

C. Durantin, J. Marzat, and M. Balesdent. 2016. Analysis of multi-objective Kriging-based methods for constrained global optimization. Computational Optimization and Applications 63, 3 (2016), 903--926.

Digital Library

[8]

A. I. Forrester and A. J. Keane. 2009. Recent advances in surrogate-based optimization. Progress in Aerospace Sciences 45, 1 (2009), 50--79.

[9]

K.C. Giannakoglou. 2002. Design of optimal aerodynamic shapes using stochastic optimization methods and computational intelligence. Progress in Aerospace Sciences 38, 1 (2002), 43 -- 76.

[10]

R. B. Gramacy and H. K. H. Lee. 2011. Optimization under unknown constraints. In Bayesian Statistics. Vol. 9. 229--247.

[11]

R. Hicks and P. A. Henne. 1978. Wing Design by Numerical Optimization. Journal of Aircraft 15, 7 (1978), 407--412.

[12]

R. Hussein and K. Deb. 2016. A Generative Kriging Surrogate Model for Constrained and Unconstrained Multi-objective Optimization. In GECCO '16. ACM, New York, NY, USA, 573--580.

Digital Library

[13]

E. Iuliano and D. Quagliarella. 2015. Evolutionary Optimization of Benchmark Aerodynamic Cases using Physics-based Surrogate Models. In AIAA SciTech. American Institute of Aeronautics and Astronautics, 1721--1736.

[14]

D. R. Jones, M. Schonlau, and W. J. Welch. 1998. Efficient Global Optimization of Expensive Black-Box Functions. J. of Global Optimization 13, 4 (Dec. 1998), 455--492.

Digital Library

[15]

D. G. Krige. 1951. A statistical approach to some basic mine valuation problems on the Witwatersrand. Journal of the Southern African Institute of Mining and Metallurgy 52, 6 (1951), 119--139.

[16]

J. Liang, T. P. Runarsson, E. Mezura-Montes, M. Clerc, P. Suganthan, C. Coello, and K. Deb. 2006. Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization. Journal of Applied Mechanics 41, 8 (2006).

[17]

J. Mockus. 1977. On Bayesian Methods for Seeking the Extremum and their Application. In IFIP Congress. 195--200.

[18]

J. Parr, C. M. Holden, A. I. Forrester, and A. J. Keane. 2010. Review of efficient surrogate infill sampling criteria with constraint handling. In 2nd International Conference on Engineering Optimization. 1--10.

[19]

J. M. Parr, A. J. Keane, A. I. Forrester, and C. M. Holden. 2012. Infill sampling criteria for surrogate-based optimization with constraint handling. Engineering Optimization 44, 10 (2012), 1147--1166.

[20]

Victor Picheny. 2014. A stepwise uncertainty reduction approach to constrained global optimization. In International Conference on Artificial Intelligence and Statistics. Reykjavik, Iceland, 787--795.

[21]

D. Quagliarella, G. Petrone, and G. Iaccarino. 2014. Optimization Under Uncertainty Using the Generalized Inverse Distribution Function. In AISTATS, W. Fitzgibbon (Ed.). Computational Methods in Applied Sciences, Vol. 34. Springer, NL, 171--190.

[22]

R. G. Regis. 2014. Constrained optimization by radial basis function interpolation for high-dimensional expensive black-box problems with infeasible initial points. Engineering Optimization 46, 2 (2014), 218--243.

[23]

T. P. Runarsson and X. Yao. 2000. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation 4, 3 (2000), 284--294.

Digital Library

[24]

T. P. Runarsson and X. Yao. 2005. Search biases in constrained evolutionary optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 35, 2 (2005), 233--243.

Digital Library

[25]

M. J. Sasena, P. Papalambros, and P. Goovaerts. 2002. Exploration of meta-modeling sampling criteria for constrained global optimization. Engineering optimization 34, 3 (2002), 263--278.

[26]

M. J. Sasena, P. Y. Papalambros, and P. Goovaerts. 2001. The Use of Surrogate Modeling Algorithms to Exploit Disparities in Function Computation Time within Simulation-Based Optimization. In 4th World Congress of Structural and Multidisciplinary Optimization. 5--11.

[27]

M. Schonlau, W. J. Welch, and D. R. Jones. 1998. Global versus local search in constrained optimization of computer models. Lecture Notes-Monograph Series, Vol. 34. Institute of Mathematical Statistics, Hayward, CA, 11--25.

[28]

D. Villanueva, R. Le Riche, G. Picard, and R. Haftka. 2012. Surrogate-based agents for constrained optimization. In AIAA Non-Deterministic Approaches Conference. 1935--1951.

Cited By

Amini SVannieuwenhuyse IMorales-Hernández A(2025)Constrained Bayesian Optimization: A ReviewIEEE Access10.1109/ACCESS.2024.352287613(1581-1593)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2024.3522876
Fan SHong XLiao ZRen CYang YWang JYang Y(2025)Adaptive sampling Bayesian algorithm for constrained black‐box optimization problemsAIChE Journal10.1002/aic.18715Online publication date: 2-Jan-2025
https://doi.org/10.1002/aic.18715
Rahi KSingh HRay TLi XHandl J(2024)Towards solving expensive optimization problems with heterogeneous constraint costsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664105(2032-2040)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664105
Show More Cited By

Constraint handling in efficient global optimization
1. Mathematics of computing
  1. Mathematical analysis
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A Kriging-based constrained global optimization algorithm for expensive black-box functions with infeasible initial points

In many engineering optimization problems, the objective and the constraints which come from complex analytical models are often black-box functions with extensive computational effort. In this case, it is necessary for optimization process to use ...
Efficient global optimization for combinatorial problems
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Real-world optimization problems may require time consuming and expensive measurements or simulations. Recently, the application of surrogate model-based approaches was extended from continuous to combinatorial spaces. This extension is based on the ...
Artificial Bee Colony Algorithm with Distant Savants for constrained optimization
Abstract
Most of the scientific and engineering problems are defined as constrained optimization functions. It can be very difficult due to their complex structures. Artificial Bee Colony Algorithm (ABC) is a remarkable metaheuristic developed ...
Highlights
- An artificial bee colony algorithm for constraint optimization is proposed.
- ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Engineering and Physical Sciences Research Council
Finnish Funding Agency for Innovation

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
439
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)4

Reflects downloads up to 10 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Amini SVannieuwenhuyse IMorales-Hernández A(2025)Constrained Bayesian Optimization: A ReviewIEEE Access10.1109/ACCESS.2024.352287613(1581-1593)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2024.3522876
Fan SHong XLiao ZRen CYang YWang JYang Y(2025)Adaptive sampling Bayesian algorithm for constrained black‐box optimization problemsAIChE Journal10.1002/aic.18715Online publication date: 2-Jan-2025
https://doi.org/10.1002/aic.18715
Rahi KSingh HRay TLi XHandl J(2024)Towards solving expensive optimization problems with heterogeneous constraint costsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664105(2032-2040)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664105
Kleijnen JAngün Evan Nieuwenhuyse Ivan Beers W(2024)Constrained optimization in simulation: efficient global optimization and Karush-Kuhn-Tucker conditionsJournal of Global Optimization10.1007/s10898-024-01448-3Online publication date: 29-Nov-2024
https://doi.org/10.1007/s10898-024-01448-3
Ragueneau QLaurent LLegay ALarroque TCrambuer R(2024)A constrained Bayesian Optimization framework for structural vibrations with local nonlinearitiesStructural and Multidisciplinary Optimization10.1007/s00158-024-03747-567:4Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1007/s00158-024-03747-5
Tian HIerapetritou M(2024)A surrogate‐based framework for feasibility‐driven optimization of expensive simulationsAIChE Journal10.1002/aic.1836470:5Online publication date: 9-Feb-2024
https://doi.org/10.1002/aic.18364
Xu WJiang YSvetozarevic BJones CKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Constrained efficient global optimization of expensive black-box functionsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620011(38485-38498)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620011
Dickey AWasko M(2023)Digital Disparities in Patient Adoption of TelemedicineInternational Journal of Healthcare Information Systems and Informatics10.4018/IJHISI.31804318:1(1-21)Online publication date: 10-Feb-2023
https://dl.acm.org/doi/10.4018/IJHISI.318043
Wang XJin YSchmitt SOlhofer M(2023)Recent Advances in Bayesian OptimizationACM Computing Surveys10.1145/358207855:13s(1-36)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3582078
Ribeiro LParente Ede Melo A(2023)Alternative variable-fidelity acquisition functions for efficient global optimization of black-box functionsStructural and Multidisciplinary Optimization10.1007/s00158-023-03607-866:7Online publication date: 13-Jun-2023
https://dl.acm.org/doi/10.1007/s00158-023-03607-8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten