Balancing exploitation and exploration in discrete optimization via simulation through a gaussian process-based search
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 1416-1438 |
Journal / Publication | Operations Research |
Volume | 62 |
Issue number | 6 |
Online published | 15 Oct 2014 |
Publication status | Published - Nov 2014 |
Link(s)
Abstract
Random search algorithms are often used to solve discrete optimization-via-simulation (DOvS) problems. The most critical component of a random search algorithm is the sampling distribution that is used to guide the allocation of the search effort. A good sampling distribution can balance the trade-off between the effort used in searching around the current best solution (which is called exploitation) and the effort used in searching largely unknown regions (which is called exploration). However, most of the random search algorithms for DOvS problems have difficulties in balancing this trade-off in a seamless way. In this paper we propose a new scheme that derives a sampling distribution from a fast fitted Gaussian process based on previously evaluated solutions. We show that the sampling distribution has the desired properties and can automatically balance the exploitation and exploration trade-off. Furthermore, we integrate this sampling distribution into a random research algorithm, called a Gaussian process-based search (GPS) and show that the GPS algorithm has the desired global convergence as the simulation effort goes to infinity. We illustrate the properties of the algorithm through a number of numerical experiments.
Research Area(s)
- Exploitation and exploration, Gaussian process-based search, Optimization-via-simulation
Citation Format(s)
Balancing exploitation and exploration in discrete optimization via simulation through a gaussian process-based search. / Sun, Lihua; Hong, L. Jeff; Hu, Zhaolin.
In: Operations Research, Vol. 62, No. 6, 11.2014, p. 1416-1438.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review