TY - JOUR
T1 - An optimal sample allocation strategy for partition-based random search
AU - Chen, Weiwei
AU - Gao, Siyang
AU - Chen, Chun-Hung
AU - Shi, Leyuan
PY - 2014/1
Y1 - 2014/1
N2 - 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.
AB - 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.
KW - Global optimization
KW - Optimal sample allocation
KW - Partition-based random search
UR - http://www.scopus.com/inward/record.url?scp=84892435788&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84892435788&origin=recordpage
U2 - 10.1109/TASE.2013.2251881
DO - 10.1109/TASE.2013.2251881
M3 - RGC 21 - Publication in refereed journal
SN - 1545-5955
VL - 11
SP - 177
EP - 186
JO - IEEE Transactions on Automation Science and Engineering
JF - IEEE Transactions on Automation Science and Engineering
IS - 1
M1 - 6497538
ER -