An optimal sample allocation strategy for partition-based random search

Weiwei Chen, Siyang Gao, Chun-Hung Chen, Leyuan Shi

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

51 Citations (Scopus)

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 (PCSPS) given a sample budget and minimizing the required sample size to achieve a satisfied level of PCSPS, 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 PCSPS in each iteration and subsequently improving the performance of PRS algorithms. © 2013 IEEE.
Original languageEnglish
Article number6497538
Pages (from-to)177-186
JournalIEEE Transactions on Automation Science and Engineering
Volume11
Issue number1
DOIs
Publication statusPublished - Jan 2014
Externally publishedYes

Research Keywords

  • Global optimization
  • Optimal sample allocation
  • Partition-based random search

Fingerprint

Dive into the research topics of 'An optimal sample allocation strategy for partition-based random search'. Together they form a unique fingerprint.

Cite this