Tsinghua Science and Technology  2021, Vol. 26 Issue (4): 417-425    doi: 10.26599/TST.2020.9010006
A Multilevel Splitting Algorithm for Quick Sampling
Liping Wang*(),Wenhui Fan()
Department of Automation, Tsinghua University, Beijing 100084, China.

Abstract

To reduce intermediate levels of splitting process and enhance sampling accuracy, a multilevel splitting algorithm for quick sampling is proposed in this paper. Firstly, the selected area of the elite set is expanded to maintain the diversity of the samples. Secondly, the combined use of an adaptive difference evolution algorithm and a local searching algorithm is proposed for the splitting procedure. Finally, a suite of benchmark functions are used for performance testing. The results indicate that the convergence rate and stability of this algorithm are superior to those of the classical importance splitting algorithm and an adaptive multilevel splitting algorithm.

Received: 29 September 2019      Published: 12 January 2021
Corresponding Authors: Liping Wang     E-mail: wanglp14@mails.tsinghua.edu.cn;fanwenhui@tsinghua.edu.cn
About author: Liping Wang received the BEng degree from Changchun University of Technology in 2006, and the MEng degree from Artillery Academy of PLA in 2009. She is a PhD candidate at Tsinghua University now. Her research interests include simulation of rare event and system engineering.|Wenhui Fan received the PhD degree from Zhejiang University in 1998. He is currently a professor at the Department of Automation and National CIMS Engineering Research Center, Tsinghua University, Beijing, China. His research interests include multidisciplinary collaborative design, simulation, and optimization.
 Fig. 1 Schematic diagram of multilevel splitting algorithm in 3-D space. Fig. 2 Flow diagram of the SADE-L algorithm. Table 1 Parameter settings of the three algorithms. Table 2 Functions used in performance testing. Table 3 Means of the rare event probability $p^$ over 10 runs, the number of intermediate levels T, and the relative error RE of the three algorithms, with $D=$30 and $N=$1000. f𝟏𝟎 in 30-dimension."> Fig. 3 Evolutions of SADE-L, ADAM, and ISp algorithms for function $f𝟏𝟎$ in 30-dimension. Table 4 Means of the rare event probability $p^$ over 10 runs, the number of intermediate levels T, and the relative errors RE of the three algorithms, with $D=𝟓𝟎$ and $N=$1500. f𝟏𝟎 at 50-dimension."> Fig. 4 Evolutions of SADE-L, ADAM, and ISp algorithms for function $f𝟏𝟎$ at 50-dimension.