Balancing Exploitation and Exploration in Discrete Optimization via Simulation Through a Gaussian Process-Based Search

• 成果类型: Article
• 署名作者: Sun, Lihua; Hong, L. Jeff; Hu, Zhaolin
• 署名单位: Tongji University; City University of Hong Kong; City University of Hong Kong
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2014.1315
• 发表日期: 2014
• 页码: 1416-1438
• 关键词: global optimization; algorithm

摘要

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.