Abstract
Partition-based random search (PRS) provides a class of effective algorithms for global optimization. In each iteration of a PRS algorithm, the solution space is partitioned into subsets which are randomly sampled and evaluated. One subset is then determined to be the promising subset for further partitioning. In this paper, we propose the problem of allocating samples to each subset so that the samples are utilized most efficiently. Two types of sample allocation problems are discussed, with objectives of maximizing the probability of correctly selecting the promising subset (P{CSPS}) given a sample budget and minimizing the required sample size to achieve a satisfied level of (P{CSPS}), respectively. An extreme value-based prospectiveness criterion is introduced and an asymptotically optimal solution to the two types of sample allocation problems is developed. The resulting optimal sample allocation strategy (OSAS) is an effective procedure for the existing PRS algorithms by intelligently utilizing the limited computing resources. Numerical tests confirm that OSAS is capable of increasing the (P{CSPS}) in each iteration and subsequently improving the performance of PRS algorithms.
Note to Practitioners-Global optimization problems raise in many engineering and automation applications, and are generally challenging to solve. Examples include those in manufacturing, logistics, semiconductors, healthcare delivery, etc. Random search algorithms provide an effective alternative to tackle the problems. A class of these algorithms is partition-based, meaning the solution space is partitioned into subsets in each iteration and samples from each subset are used to determine promising subsets to focus the search on. An intelligent strategy for allocating the sample budget can achieve a more efficient utilization of the limited computing resources. The optimal sample allocation strategy (OSAS) proposed in this paper is a very useful addition to the existing procedures of partition-based random search. OSAS can increase the probability of choosing the correct subset as a promising one in each iteration, or achieve the same confidence level using fewer samples. Thus, it improves algorithm performance and convergence speed, and provides better solution quality. The procedure is easy to implement, and therefore is a good choice in solving practical problems, such as the buffer allocation problem in manufacturing which is demonstrated in this paper.