Back to search

University of British Columbia

A rubric for algorithm selection in optimization of black-box functions

Abstract

dc:description

When optimizing black-box functions, little information is available to assist the user in selecting an optimization approach. It is assumed that prior to optimization, the input dimension d of the objective function, the average running time tf of the objective function and the total time T allotted to solve the problem, are known. The intent of this research is to explore the relationship between the variables d, tf, and T and the performance of five optimization algorithms: Genetic Algorithm, Nelder-Mead, NOMAD, Efficient Global Optimization, and Knowledge Gradient for Continuous Parameters. The performance of the algorithms is measured over a set of functions with varying dimensions, function call budgets, and starting points. Then a rubric is developed to assist the optimizer in selecting the most appropriate algorithm for a given optimization scenario. Based on the information available prior to optimization, the rubric estimates the number of function calls available to each algorithm and the amount of improvement each algorithm can make on the objective function under the function call constraint. The rubric reveals that Bayesian Global Optimization algorithms require substantially more time than the competing algorithms and are therefore limited to fewer function call budgets. However, if the objective function requires a large running time, this difference becomes negligible. With respect to improvement, the rubric suggests that Derivative Free Optimization algorithms are preferred at lower dimensions and higher budgets, while Bayesian Global Optimization algorithms are expected to perform better at higher dimensions and lower budgets. A test of the claims of the rubric reveals that the estimate of function call budget is accurate and reliable, but the improvement is not estimated accurately. The test data demonstrates large variability for the measure of improvement. It appears that the variables d, tf, and T are insufficient for describing the expected performance of the assessed algorithms, since variables such as function type and starting point are unaccounted for.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sremac, Stefan

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 2.5 Canada
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/53956

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Sremac, Stefan. A rubric for algorithm selection in optimization of black-box functions. master's thesis, University of British Columbia, 2015. http://hdl.handle.net/2429/53956