{'fraction_non_alphanumeric': 0.05366762525821216, 'fraction_numerical': 0.025517436915225403, 'mean_word_length': 4.186974789915967, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Self-Adaptive Binary-Addition-Tree Algorithm-Based Novel Monte Carlo Simulation for Binary-State Network Reliability Approximation

The Monte Carlo simulation (MCS) is a statistical methodology used in a large number of applications. It uses repeated random sampling to solve problems with a probability interpretation to obtain high-quality numerical results. The MCS is simple and easy to develop, implement, and apply. However, its computational cost and total runtime can be quite high as it requires many samples to obtain an accurate approximation with low variance. In this paper, a novel MCS, called the self-adaptive BAT-MCS, based on the binary-adaption-tree algorithm (BAT) and our proposed self-adaptive simulation-number algorithm is proposed to simply and effectively reduce the run time and variance of the MCS. The proposed self-adaptive BAT-MCS was applied to a simple benchmark problem to demonstrate its application in network reliability. The statistical characteristics, including the expectation, variance, and simulation number, and the time complexity of the proposed self-adaptive BAT-MCS are discussed. Furthermore, its performance is compared to that of the traditional MCS extensively on a large-scale problem.


INTRODUCTION
Monte Carlo methods (MCSs) are a broad class of computational algorithms and statistical methodologies that are too complex to solve analytically [1]. MCSs play a crucial role in enormous modern and dynamics complex applications including engineering [2], physical sciences [3], climate change and radiative forcing [4], computational biology [5], computer graphics, applied statistics [6], artificial intelligence for games [7], design and visuals [8], search and rescue [9], finance and business, and law [10].
Various binary-state networks are used in real-world applications such network resilience [11], wireless sensor network [12], pipe networks [13], the internet of things [14], and social networks [15], and such networks are constantly growing. For example, social networks have more than 27 billion users [16]. Network reliability, an important index for evaluating network performance, represents the probability that a network is currently functioning successfully. However, it is NP-hard to calculate the exact binary-state network reliability [17,18,19,20], making the MCS an effective and popular tool for estimating the reliability of all types of networks.
The basic idea behind using the MCS to estimate binary-state network reliability is to generate enough numbers randomly for all network components to obtain simulated results for a certain number of replications [21]. The results are then averaged to obtain an approximate reliability value for decision support in modern networks, which change dynamically and rapidly [22,23].
In general, the MCS is easier to use than an exact-solution algorithm for obtaining the network reliability [24]. However, the results obtained from the MCS are not real answers but approximate reliabilities with a variance, which decreases with increasing simulation number [25,26]. Moreover, the MCS requires a random number for each component in a simulation, and multiple replications for each design alternative affects its efficiency [27,28]. If the number of random variates is large, the total cost of MCS can be exorbitantly high [1,8]. Therefore, it is necessary to develop more efficient and robust MCSs through optimization for efficiency while calculating an acceptable approximate reliability [26,27].
The binary-addition-tree algorithm (BAT) is an emerging search method for solving optimization problems [28]. The BAT has been implemented to calculate the exact reliability of different types of networks directly [28,29,30] and solve various practical problems, including resilience assessment [31], predicting the spread of wildfires [32] and propagation probability of computer viruses [33].
Because BAT is easy to program, flexible to make-to-fit, and more efficient than traditional search methods, including the depth-first search (DFS) [34], breadth-first search (BFS) [35], and universal generating function methodology (UGFM) [36], a new MCS called the BAT-MCS is proposed based on the self-adaptive BAT by integrating BAT [28], MCS [25], and our proposed selfadaptive simulation-number algorithm to obtain a robust estimator of the binary-state network reliability efficiently.
Our study aimed to develop a simple, efficient, and robust MCS based on the self-adaptive BAT.
We experimentally show that the proposed self-adaptive BAT-MCS can overcome the NP-hard obstacle by finding an accurate and robust solution efficiently rather than finding an exact reliability value.
The remainder of this paper is organized as follows. Section 2 introduces the required acronyms, notations, nomenclature, and assumptions used in this study. Section 3 introduces the two fundamental modules of the proposed self-adaptive BAT-MCs, BAT [28] and MCS [25], together with the path-based layered search algorithm (PLSA) [37]. Section 4 discusses the proposed novel self-adaptive simulation-number algorithm, lower and upper bounds of each super vector, pseudocode to combine the self-adaptive BAT and MCS, and statistical characteristics of the selfadaptive BAT-MCS. Section 5 presents the step-by-step implementation of the proposed selfadaptive BAT-MCS based on a simple benchmark network. Section 5 also describes the computational experiment performed on a large-scale network to analyze the relationships among the estimators, number of coordinates in the super vector obtained from the BAT, number of simulations in the MCS using the proposed self-adaptive simulation-number algorithm, and component reliabilities. Finally, Section 6 concludes the paper.

ACRONYMS, NOTATIONS, NOMENCLATURE, AND ASSUMPTIONS
Important acronyms, notations, assumptions, and nomenclatures related to the proposed BAT-MCS are presented in this section. =0 if X = (1, 1, 1, 0, 0). D : arc state distribution listed D(a) = Pr(a) for all a ∈ E, e.g., D is listed in Table 1.   Figure 1 is a binary-state network if D is as given in Table 1. Figure 2, where X = (1, 1, 1, 0, 0) in Figure 1. X << X * : obtained sequence of vector X is earlier than that of vector X * in BAT X << X * : obtained sequence of vector X is earlier than or equal to that of vector X * in BAT X < X * : X(a) < X * (a) for all a ∈ E X ≤ X * : X(a) ≤ X * (a) for all a ∈ E δ : number of coordinates in super vectors obtained from the self-adaptive BAT-MCS

Nomenclature
Binary-state network: A network with binary-state arcs only, that is, the state of each arc is either zero or one.

Reliability:
The probability that a network is operating successfully.
Disconnected vector: X is a disconnected vector if nodes 1 and n are disconnected in G(X). [38] 1. Networks have no parallel arcs or loops.

Assumptions
2. Nodes are all completely reliable and connected.
3. Arcs have two states and all states are statistically independent.

REVIEW OF BAT, PLSA, AND MCS
The proposed self-adaptive BAT-MCS uses the BAT [28] to generate super vectors [30], PLSA to filter out all feasible super vectors by verifying their connectivity [37], and MCS to calculate the approximate probability of each feasible super vector [24,25]. Hence, the BAT, PLSA, and MCS and their important statistical characteristics are reviewed briefly in this section.

BAT
A binary-state vector has m binary-state coordinates, and the value of each coordinate is either zero or one, denoting that the corresponding arc fails or works, respectively. The (binary) BAT proposed by Yeh [28] aims to generate all possible m-tuple binary-state vectors, regardless of whether it is feasible or infeasible based simply on the binary addition operator.
The procedure adopted by the BAT to generate all vectors is analogous to adding one to a binary code from the first coordinate and gradually moving to the last coordinate [28,30] in the binary-state vector. The general procedure for BAT is explained in the following pseudocode [28]: Algorithm: BAT Input: m.
STEP B0. Let i = 1 and X be a m-tuple vector zero.
Let i be the index of the current coordinate and X be the current vector. STEP B0 initializes i to one and all values of the coordinates in the current vector X to zero. The main body of the BAT is the loop from STEP B1 to STEP B2, and it updates X repeatedly to generate each vector by adding one to X(ai), that is, the current coordinate.
The value of X(ai) is changed to one and a new X is found in the loop if X(ai) = 0. Otherwise, X(ai) is changed from one to zero and moved to the next coordinate to repeat the above process until X(ai) is changed from zero to one. If i = m, this loop terminates because the current X becomes a zero vector, and all the vectors are already found.
The BAT is very simple because its pseudocode has only three statements. The time complexity of the BAT has been proven to be O (2 m+1 ) in [39]. Hence, as O (2 m+1 ) and the total number of vectors is 2 m , the BAT is very efficient in generating all vectors. In addition, vector X is updated repeatedly without introducing any new vector, that is, the BAT is space-efficient [28]. In addition, the function F(X) can be made-to-fit, for example, the cost, probability [32], time [40], weight, etc., based on the problem and calculate F(X) after a new X obtained in STEP B1, that is, the BAT is easy to customize [30].
Thus, the BAT is easy to code, flexible to make-to-fit, and efficient in both runtime and space.
For example, in the five-arc binary-state network shown in the example network in Figure 1, , each vector is a 5-tuple, the first vector is X = (0, 0, 0, 0, 0), and i = 1 in STEP B0. Using binary addition, by adding one to the current coordinate, that is, the first coordinate, the new X = (1, 0, 0, 0, 0) is obtained as the second vector and the new i is still equal to zero in STEP B1. After the new X is generated, there is no need to store the current X, thereby saving computer memory. Because i = 1 and X(a1) = 1 in (1, 0, 0, 0, 0), we need to change X(a1) to zero, move to the next coordinate by changing i from 1 to 2, and return to STEP B1 to repeat the same process until the current coordinate value is changed to 1 to generate a new X. The complete process of the BAT illustrated in Figure 1 is presented in Table 2.

PLSA
The reason for the high flexibility of the BAT to make-to-fit for various problems is in STEP B1 described in Section 3.1. We can calculate the function value of any new X found in STEP B1 based on the problem objective. In the network reliability problem, our goal is to calculate the network reliability, and the reliability function (1) From Eq.
(1), we need to verify the connectivity of each vector X obtained in STEP B1 from the BAT. To achieve this target efficiently, the PLSA was employed [28,30]. The PLSA, first proposed in [28], originated from the layered-search algorithm (LSA) proposed in [37] to find d simple paths, called d-MPs in [37], in acyclic networks. Owing to the efficiency and simplicity of the LSA, different versions of LSAs, the PLSA [37], GLSA [39], and TLSA [41], were proposed to validate the connectivity between two nodes, many nodes, and all nodes, respectively. Hence, the PLSA was employed to validate weather nodes 1, and n was connected by at least one path in this study.
The pseudocode for the PLSA is presented below.

Input:
A state vector X.
Output: X is connected or disconnected in G(X).
STEP P2. If n ∈ L i , halt and X is connected.

STEP P3.
If L i = ∅, halt and X is disconnected. Otherwise, let i = i + 1, Li = ∅, and go to STEP P1.
Based on the simple concept that nodes 1 and n are connected if the current layer contains the node n proposed in the LSA [37], the PLSA can determine whether X is connected by validating whether nodes 1 and n are connected in G(X). Because each layer has at least one node and there are n nodes, there are at most n layers. Hence, the time complexity of PLSA is only O(n).
For example, let X = (1, 1, 1, 1, 1) in Figure 1, that is, G(X) = G. Based on the PLSA, we can verify the connectivity of X using the procedure listed in Table 3. Table 3. Verify the connectivity of X using the PLSA.

MCS and its important statistical characteristics
The MCS is a powerful and popular modeling method used to obtain approximate solutions for highly nonlinear, high-dimensional, and very complex problems [1-11]. Many MCS have been proposed, and the crude MCS implemented in [24,25] was used here to calculate the approximate binary-state network reliability because of its simplicity and popularity. The MCS pseudocode is provided as follows [24,25]: , the source node 1, the sink node n, and the number of simulations Nsim.

Output:
The approximated reliability RMCS.

STEP M2.
If j < m, let j = j + 1 and go to STEP M1.
In addition, the total number of MCS simulations Nsim satisfies the following equation, which can be used to obtain the relative error ε in the confidence interval (1−α)% [24,25]: Eqs.
(2)-(4) are important statistical characteristics of MCS, and their proofs can be obtained in textbooks on the MCS [29,30]. Let Nsim = 8. The MCS is explained using the binary-state network shown in Figure 1, and its state distribution is listed in Table 1. The results are listed in Table 4: X2 = X8 for Nsim = 8. Hence, the MCS may have many duplications if Nsim is increased and may not have sufficient number of events or vectors to realistically model problems.

Super Family and Basic Idea of the Proposed Self-Adaptive BAT-MCS
The super vector S is a special sub-vector, the value of whose ith coordinate denotes the state of the ith arc for i = 1, 2, …, δ and ||S|| = δ ≤ m [30]. Because is connected and if we can rewrite Eq. (5) as Eq. (9).
( ) and is connected Also, from Eq. (8) and Eq. (9) the network reliability R(G) can be redefined as in Eq. (10): The proposed BAT-MCS aims to efficiently solve Eq. (10) efficiently. Because and the factoring theorem [42] gives Eq. (9) can be rewritten as in Eq. (11): where It is still NP-hard to calculate R(G(D S)) in Eq. (13). Hence, the basic idea of the proposed algorithm is to use BAT to find all super vectors and the MCS to calculate the approximate reliability of R(G(DS)) corresponding to Ω||S||(S) for each super vector S.

Lower and Upper Bounds of Super Vectors
Let ||S|| = δ.  we have Because For example, in For example, if S = (1, 0) in Figure 1, we have Pr(S) = p 1 × q2 = 0.9 × 0.2 = 0.18, based on Table   1. G(DS) is depicted in Figure 3, and DS is listed in Table 5

Self-Adaptive Simulation-Number Algorithm
The number of multiple simulation replications is a critical factor determining MCS performance, including the quality and variance of solutions and efficiency [24,25]. More than millions of random variates may be required in one simulation to obtain an accurate estimator [43]. Hence, to reduce variance and maximize the probability of correct selection, it is crucial to ensure that these critical events have more simulation numbers than less important events.
A novel self-adaptive algorithm is proposed to self-adaptively allocate simulation numbers to different events based on their importance.
where * sim sim Eq. (23) can be used to allocate the number of simulations for critical and non-critical events.

Statistical Characteristics of the Self-Adaptive BAT-MCS
The statistical characteristics of the proposed self-adaptive BAT-MCS are discussed in this section. Eq. (2) and Eq. (20) imply that the estimator obtained from the self-adaptive BAT-MCS is also unbiased and consistent with that obtained from the traditional MCS. Hence, we focus only on the variance because it is a measure of the quality and robustness of the obtained estimators.

Pseudocode and Time Complexity
The pseudocode for calculating the approximate reliability of binary-state networks using the proposed self-adaptive BAT-MCS by integrating the lower and upper bounds of super vectors presented in Section 4.1 and the self-adaptive simulation-number algorithm discussed in Section 4.2 is presented here.

Input:
A binary-state network G(V, E, D), the source node 1, and the sink node n.

Output:
The approximate reliability RBAT-MCS under pregiven values δ, Pr(a) for all a∈E, and Nsim.

STEP 3.
If L(X) is connected, let R BAT-MCS = RBAT-MCS + Pr(X) and go to STEP 1.

STEP 4.
If U(X) is disconnected, go to STEP 1.

STEP 9.
If j < m, let j = j + 1 and go to STEP 8.

STEP 13.
If i < k, let i = i + 1 and go to STEP 7. Otherwise, halt.
The first loop from STEP 0 to STEP 5 is based on the BAT and used to find the super vectors.
The second loop from STEP 6 to STEP 13 is mainly based on the MCS and used to calculate the reliability of each feasible super vector with the proposed self-adaptive simulation-number algorithm. The number of super vectors found is 2 δ because the number of their coordinates are all equal to δ and the value of each coordinate, that is, X(ai) for i = 1, 2, …, δ, is either 0 or 1. Hence, the total time complexity is O(n2 δ + 2 (δ + 1) ) = O(n2 δ ) for STEPs 1 and 2, where O(nδ) results from the PLSA [37] and O(2 δ+1 ) from the BAT [39].
After all the super vectors in F δ are found, the MCS is implemented for each of them. The number of MCS simulations is Nsim, and each simulation needs to generate the values of (m − δ) coordinates, that is, Si(aj) for j = (δ + 1), (δ + 2), …, m. Additionally, the PLSA is implemented to verify the connectivity of Si after extending it from a δ-tuple to an m-tuple vector for each simulation [28]. Thus, in terms of the time complexity, the efficiency of the proposed BAT-MCS is higher than that of the BAT if δ << m and very close to that of the MCS if δ is very small.

Step-By-Step BAT-MCS Procedure
As mentioned in Section 1, calculating the binary-state network reliability is both NP-hard and #P-hard [17,18]. The simplest and most cited benchmark network in network reliability research is depicted in Figure 1 [17, 18, 28, 39]. To help readers realize the proposed self-adaptive BAT-MCS easily, the self-adaptive BAT-MCS is tested, as shown in Figure 1, to exemplify the procedure of the self-adaptive BAT-MCS for calculating the approximate binary-state network reliability.

STEP 2.
Because i = δ = 2, go to STEP 7. Note that the part for the self-adaptive simulationnumber algorithm, i.e., STEP 6, is skipped.
: : The complete procedure is listed in Table 7 and the final approximated reliability R * = 0.53. Table 7. BAT-MCS procedure for Figure 1 and Table 1. 0) 0.18 0.69576 1 0.25661 1 0.95894 0 (1, 0, 1, 1, 0 12821 1 (1, 1, 1, 0, 1 The super vector (0, 0) was removed from Table 7 because (0, 0) ∈ U2. Hence, the proposed lower-bound and upper-bound methods reduce the number of super vectors. Comparing the results in Table 4 with those in Table 7, no duplications are observed using the proposed self-adaptive BAT-MCS. This is because there are no duplicate super vectors obtained from the BAT, and using super vectors separates the problem into disjoint subproblems to reduce the probability of duplications.
Hence, the proposed BAT-MCS can reduce the number of simulations, decrease the probability of duplications, and reduce the variance.

Computation Experiments on a Large-Scale Network
To investigate the practical performance of the proposed self-adaptive BAT-MCS and the effects of δ, N sim , and Pr(a) on the performance of self-adaptive BAT-MCS, an extension test was conducted on a large-scale benchmark network, which is widely employed to verify the performance of new algorithms (Figure 4). In Figure 4, we have n = 10, m = 21, and the number of vectors is 2 m = 2,097,152 [17,18].  Table 8, Table 11, and Table 13. In addition, the best values are shown in bold. Table 8 shows that the value of ||F δ||/||Ωδ|| decreases with increasing δ, e.g., ||F8||/||Ω8|| = 85.9375%

Simulation Number
and ||F20||/||Ω20|| = 21.3581%. Hence, the benefit of using the lower and the upper bounds of the super vectors tends to increase from small δ to large δ.  Table 9 shows that the value of n sim(S) decreases with the number of δ. Without using the proposed self-adaptive simulation algorithm, each super vector S needs to be simulated even if S ∉ F||S||. Hence, n sim(S) = Nsim/2 δ can be less than one if Nsim < 2 δ . Thus, it is difficult to increase the δ to improve the variance without using the proposed self-adaptive simulation algorithm.  Hence, selecting an appropriate δ is the critical concern in the proposed algorithm. Note that the number of vectors is 2 m = 2,097,152 only, that is, any MCS with more than 2,097,152 simulations can be replaced by the BAT.  For δ = 1, 3, and 5, the proposed algorithm has a better average ̅ , after which ̅ MCS is better than ̅ BAT−MCS . Hence, a smaller δ can improve ̅ BAT−MCS . This observation confirms that the critical concern in the proposed algorithm is to find the optimal δ to obtain a better result, as discussed at the end of Section 5.2.1. Table 11. Results of ̅ based on δ and p. δ   (4), it follows that the larger is the N sim , the better is the ̅ . Hence, the best average ̅ = 0.015946 is obtained at N sim = 2 19 , and the ̅ obtained at N sim = 2 19 is better than that obtained using smaller N sim for all δ, for example, ̅ BAT−MCS = 0.000346 and 0.000120 at N sim = 2 17 and 2 19 , respectively, for δ = 1. Table 9 and Table 10 show that for a fixed N sim , a smaller δ gives a larger average n sim (S) for all super vectors S ∈ F ||S|| , thus obtaining better results. Hence, the best average ̅ = 0.001058 for all p is obtained at δ = 1. Table 12 list the average values of n sim (S) from Table 9 and Table 10 that are less than 5, and these values may not have enough samples to describe the entire space solution completely. Hence, there is a gap between the values of dark cells and normal cells.

The dark cells in
For each N sim , there is at least one and up to three ̅ BAT−MCS values that are better than ̅ MCS at δ = 1, 3, and 5. This further confirms the conclusion obtained from Table 11 that the proposed algorithm gives better results than the MCS for lower δ than larger δ.   Table 13 and Table 14 list the � of the obtained R MCS and R BAT-MCS for different δ and p and different δ and N sim using the MCS and proposed self-adaptive BAT-MCS, respectively. Table 11 and Table 12, it is clear in both Table 13 and Table 14 that δ = 19 always gives better � than smaller δ. This is a consequence of Eq. (27). It implies that the variance between the proposed algorithm and the MCS increases with an increase in δ.

Unlike in
Moreover, the best average � is 0.002934, obtained at p = 0.9 (Table 13), and 0.001405, obtained at N sim = 2 19 (Table 14). The former may be a result of the characteristics shown in Figure   4, and the latter results from Eq. (4) and Eq. (25), that is, a larger N sim has a smaller �.
From the above discussions, it is clear that the proposed algorithm has a robust estimator because of its low variance.   Table 15 and Table 16 list the average runtime � required to obtain the R MCS and R BAT-MCS for each run. The best and best average � are both obtained p = 0.1 and δ = 13 results in the best average � . In addition, the proposed algorithm is faster than the MCS for δ < 17. Table 15 shows that δ = 13 always has the best � and the best average � for different p. Table   16 shows that the best and best average � for all δ are both obtained at N sim = 2 11 , which was the smallest N sim tested because a smaller N sim requires less runtime. However, the δ corresponding to the best � is different for various N sim values. For example, the best � = 0.002000 occurs at δ = 7 for N sim = 2 11 , but the best � = 0.006867 occurs at δ = 11 for N sim = 2 13 .

Average Run Time �
Thus, the proposed algorithm also outperforms the MCS in the runtime for δ < 17 for all p and all N sim .    The discussed experimental results indicate that the proposed self-adaptive BAT-MCS outperforms the MCS in terms of quality, variance, and runtime for suitable δ values.

CONCLUSIONS
This paper presented a novel MCS, called the self-adaptive BAT-MCS, to calculate binary-state network reliability. Experimental results showed that the proposed self-adaptive BAT-MCS based on BAT, MCS, proposed lower/upper bounds for super vectors, and proposed self-adaptive simulationnumber algorithm outperformed the MCS in terms of quality, variance, and runtime for suitable δ values.
Compared with the traditional MCS, the proposed self-adaptive BAT-MCS is simple, efficient, and robust in terms of time complexity, solution quality, and variance as shown experimentally.