Continuous Surrogate-Based Optimization Algorithms Are Well-Suited for Expensive Discrete Problems

Rickard Karlsson, Laurens Bliek, Sicco Verwer, Mathijs de Weerdt*

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
89 Downloads (Pure)

Abstract

One method to solve expensive black-box optimization problems is to use a surrogate model that approximates the objective based on previous observed evaluations. The surrogate, which is cheaper to evaluate, is optimized instead to find an approximate solution to the original problem. In the case of discrete problems, recent research has revolved around discrete surrogate models that are specifically constructed to deal with these problems. A main motivation is that literature considers continuous methods, such as Bayesian optimization with Gaussian processes as the surrogate, to be sub-optimal (especially in higher dimensions) because they ignore the discrete structure by, e.g., rounding off real-valued solutions to integers. However, we claim that this is not true. In fact, we present empirical evidence showing that the use of continuous surrogate models displays competitive performance on a set of high-dimensional discrete benchmark problems, including a real-life application, against state-of-the-art discrete surrogate-based methods. Our experiments with different kinds of discrete decision variables and time constraints also give more insight into which algorithms work well on which type of problem.

Original languageEnglish
Title of host publicationArtificial Intelligence and Machine Learning - 32nd Benelux Conference, BNAIC/Benelearn 2020, Revised Selected Papers
EditorsMitra Baratchi, Lu Cao, Walter A. Kosters, Jefrey Lijffijt, Jan N. van Rijn, Frank W. Takes
PublisherSpringer
Pages48-63
Number of pages16
ISBN (Print)9783030766399
DOIs
Publication statusPublished - 2021
Event32nd Benelux Conference on Artificial Intelligence and Belgian-Dutch Conference on Machine Learning, BNAIC/Benelearn 2020 - Virtual, Online
Duration: 19 Nov 202020 Nov 2020

Publication series

NameCommunications in Computer and Information Science
Volume1398 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference32nd Benelux Conference on Artificial Intelligence and Belgian-Dutch Conference on Machine Learning, BNAIC/Benelearn 2020
CityVirtual, Online
Period19/11/2020/11/20

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

  • Bayesian optimization
  • Black-box optimization
  • Expensive combinatorial optimization
  • Surrogate models

Fingerprint

Dive into the research topics of 'Continuous Surrogate-Based Optimization Algorithms Are Well-Suited for Expensive Discrete Problems'. Together they form a unique fingerprint.

Cite this