Authors: Jiaqiao Hu Hyeong Soo Chang Michael C Fu Steven I Marcus
Publish Date: 2009/11/20
Volume: 50, Issue: 4, Pages: 575-596
Abstract
Modelbased search methods are a class of optimization techniques that search the solution space by sampling from an underlying probability distribution “model” which is updated iteratively after evaluating the performance of the samples at each iteration This paper aims to improve the sampling efficiency of modelbased methods by considering a generalization where a population of distribution models is maintained and subsequently propagated from generation to generation A key issue in the proposed approach is how to efficiently allocate the sampling budget among the population of models to maximize the algorithm performance We formulate this problem as a generalized max karmed bandit problem and derive an efficient dynamic sample allocation scheme based on Markov decision theory to adaptively allocate computational resources The proposed allocation scheme is then further used to update the current population to produce an improving population of models Our preliminary numerical results indicate that the proposed procedure may considerably reduce the number of function evaluations needed to obtain high quality solutions and thus further enhance the value of modelbased methods for optimization problems that require expensive function evaluations for performance evaluation
Keywords: