Please wait a minute...
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.
Download: PDF (1189 KB)      HTML
Export: BibTeX | EndNote (RIS)      

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.



Key wordsrare event simulation      splitting method      elite set      adaptive differential evolution      local searching     
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.
Cite this article:

Liping Wang,Wenhui Fan. A Multilevel Splitting Algorithm for Quick Sampling. Tsinghua Science and Technology, 2021, 26(4): 417-425.

URL:

http://tst.tsinghuajournals.com/10.26599/TST.2020.9010006     OR     http://tst.tsinghuajournals.com/Y2021/V26/I4/417

Fig. 1 Schematic diagram of multilevel splitting algorithm in 3-D space.
Fig. 2 Flow diagram of the SADE-L algorithm.
NDρSADE-LρADAMαISp
Part 11000300.50.50.5
Part 21500500.50.50.5
Table 1 Parameter settings of the three algorithms.
fFunction
f1Shifted Sphere Function
f2Shifted Schwefel’S Problem 1.2
f3Shifted and Rotated High Conditioned Elliptic Function
f4Shifted Schwefel’s Problem 1.2 with Noise in Fitness
f5Schwefel’s Problem 2.6 with Global Optimum on Bounds
f6Shifted Rosenbrock’s Function
f7Shifted Rotated Griewank’s Function without Bounds
f8Shifted and Rotated Ackley’s Function with Global Optimum on Bounds
f9Shifted Rastrigin’s Function
f10Shifted and Rotated Rastrigin’s Function
f11Shifted Rotated Weierstrass Function
f12Schwefel’s Problem 2.13
f13Expanded Extended Griewank’s plus Rosenbrock’s Function
f14Expanded Rotated Extended Scaffe’s F6
f15Hybrid Composition Function 1
f16Rotated Hybrid Composition Function 1
f17Rotated Hybrid Composition Function 1 with Noise in Fitness
f18Rotated Hybrid Composition Function 2
f19Rotated Hybrid Composition Function 2 with a Narrow Basin for the Global Optimum
f20Rotated Hybrid Composition Function 2 with the Global Optimal on the Bounds
f21Rotated Hybrid Composition Function 3
f22Rotated Hybrid Composition Function 3 with High Condition Number Matrix
f23Non-Continuous Rotated Hybird Composition Function 3
f24Rotated Hybrid Composition Function 4
Table 2 Functions used in performance testing.
fγp^TRE (%)
A1A2A3A1A2A3A1A2A3
f173 9006.80×10-32.29×10-38.03×10-5781320.686.5183.21
f2100 0002.62×10-24.27×10-37.62×10-968274.685.3280.27
f32.65×1091.19×10-11.94×10-22.61×10-1036322.813.3428.97
f4110 0006.30×10-33.86×10-41.94×10-107133213.6020.8299.13
f553 5008.60×10-12.84×10-22.79×10-524141.074.0295.37
f63.78×10106.82×10-22.64×10-54.70×10-6513185.7488.2499.99
f738608.07×10-16.62×10-36.90×10-627173.334.92100
f821.032.34×10-51.30×10-62.24×10-615181845.3972.9489.39
f96802.45×10-33.16×10-42.96×10-68111824.119.6079.62
f106802.39×10-32.87×10-47.36×10-68121627.385.8649.04
f11421.59×10-42.90×10-53.05×10-513141519.646.70100
f121.4×1061.20×10-31.72×10-41.36×10-58121613.0514.5785.01
f13301.03×10-46.70×10-121.09×10-61236194.767.4993.70
f1413.503.27×10-42.53×10-67.20×10-811182515.9611.8399.99
f1512307.10×10-32.71×10-46.14×10-76122018.118.0899.99
f1612501.28×10-25.93×10-48.44×10-75112021.3017.3785.92
f1716301.95×10-26.87×10-33.81×10-756213.238.8399.99
f18900.201.90×10-3×3.78×10-118×3425.36×27.42
f19900.301.55×10-3×3.37×10-108×3115.54×54.52
f20900.403.86×10-3×9.76×10-108×301.17×35.88
f2113815.68×10-46.86×10-57.35×10-611131611.867.3273.00
f2218001.16×10-21.43×10-37.65×10-10672915.484.8799.52
f2313707.75×10-42.01×10-53.42×10-710142125.195.98100
f2414501.20×10-31.39×10-54.05×10-118153312.8514.2299.91
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.
fγp^TRE (%)
A1A2A1A2A1A2
f175 0008.30×10-10×30×30.49×
f280 0002.08×10-101.25×10-11323510.2111.51
f34.6×1092.57×10-106.38×10-11323411.3554.38
f410 0006.66×10-10×31×18.18×
f534 0003.43×10-101.17×10-12323813.449.78
f64×10109.49×10-10×30×15.24×
f715501.39×10-10×33×28.17×
f821.207.62×10-101.54×10-13314228.1698.30
f98308.53×10-102.01×10-14304517.429.71
f108308.60×10-105.18×10-14304420.7325.47
f11653.47×10-104.77×10-10323218.948.33
f122.8×1061.98×10-106.25×10-12333627.117.44
f13507.89×10-101.07×10-19316113.2910.81
f1422.201.24×10-108.22×10-11333445.3799.04
f159901.67×10-109.54×10-14334323.4517.72
f167309.76×10-101.12×10-15304829.5121.84
f1712503.66×10-10×32×35.44×
f189004.96×10-10×32×19.54×
f198501.55×10-10×33×11.38×
f208803.78×10-10×32×15.31×
f2113707.18×10-105.05×10-11313519.3812.32
f2214504.25×10-105.97×10-12323616.3817.65
f2313605.67×10-104.99×10-12323612.798.16
f2414303.61×10-103.72×10-14324529.5374.87
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.
[1]   Kahn H. and Harris T. E., Estimation of particle transmission by random sampling, National Bureau of Standards Applied Mathematics Series, vol. 12, pp. 27-30, 1951.
[2]   Botev Z. I., An algorithm for rare-event probability estimation using the product rule of probability theory, , 2008.
[3]   Wadman W. S., Squillante M. S., and Ghosh S., Accelerating splitting algorithms for power grid reliability estimation, in Proc. 2016 Winter Simulation Conf., Washington, DC, USA, 2016, pp. 1757-1768.
[4]   Louvin H., Dumonteil E., Lelièvre T., Rousset M., and Diop C. M., Adaptive multilevel splitting for Monte Carlo particle transport, EPJ Web of Conferences, vol. 153, p. 06006, 2017.
[5]   Wang L. P. and Fan W. H., A multi-level splitting algorithm based on differential evolution, Int. J. Model. Simul. Sci. Comput., vol. 9, no. 2, p. 1850021, 2018.
[6]   Morio J., Pastel R., and Le Gland F., An overview of importance splitting for rare event simulation, Eur. J. Phys., vol. 31, no. 5, pp. 1295-1303, 2010.
[7]   Bréhier C. E. and Lelièvre T., On a new class of score functions to estimate tail probabilities of some stochastic processes with adaptive multilevel splitting, Chaos, vol. 29, no. 3, p. 033126, 2019.
[8]   Aristoff D., Lelièvre T., Mayne C. G., and Teo I., Adaptive multilevel splitting in molecular dynamics simulations, ESAIM: Proceedings and Surveys, vol. 48, pp. 215-225, 2015.
[9]   Suo X. S., Yu X. Q., and Li H. S., Subset simulation for multi-objective optimization, Appl. Math. Model., vol. 44, pp. 425-445, 2017.
[10]   Suganthan P. N., Hansen N., Liang J. J., Deb K., Chen Y. P., Auger A., and Tiwari S., Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization. Singapore: Nanyang Technological University, 2005.
No related articles found!