臺灣博碩士論文加值系統

網路可靠度在決策支援資訊上是非常重要的。蒙地卡羅模擬法是其中一種評估不同種類網路結構之網路可靠度的一種方法。本文比較與分析三種蒙地卡羅模擬法，用來評估兩端點二元狀態之網路可靠度。第一種蒙地卡羅模擬法是在已知最小路徑下求網路可靠度。第二種蒙地卡羅模擬法是在已知最小切割下求取網路可靠度。第三種方法是在未知任何最小路徑或最小切割的資訊下去評估網路可靠度。從結果得知在未知任何最小路徑或最小切割的資訊下，直接評估網路可靠度的速度是在已知最小路徑或最小切割之下的195倍。另外我們亦結合粒子群演算法與蒙地卡羅模擬法，利用這兩種方法去解決在滿足可靠度的下界限制之下，最小化花費的成本。與先前文獻做比較得知，結合此兩種方法能求出比先前文獻所求的結果更佳。

Network reliability is very important for the decision support information. Monte Carlo Simulation (MCS) is one of the optimal algorithms to estimate the network reliability for different kinds of network configuration. This thesis has compared and analyzed three Monte Carlo simulation (MCS) methods for estimating the two-terminal network reliability of a binary-state network: (1) MCS1 simulates the network reliability in terms of known MPs, (2) MCS2 estimates the network reliability in terms of known MCs; and (3) MCS3 estimates the network reliability directly without knowing any information of MPs or MCs. Our simulation results show that the direct estimation without knowing any information of MPs or MCs can speedup about 195 times when compared with other traditional approaches which require MPs or MCs information. In addition, we also combine particle swarm optimization (PSO) and MCS to solve cost minimization problem under reliability constraints. Compared with previous works to solve this problem, the result of PSO combine with MCS can get the better solution.

中文摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Statement and Objectives 3
1.3 Overview of This Thesis 4
Chapter 2 Literature Review 5
2.1 Algorithms of System Networks’ Reliability 5
2.2 Monte Carlo simulation (MCS) for system network reliability 6
2.3 The related application of particle swarm optimization algorithm 9
Chapter 3 Research Methodology 10
3.1 Acronyms, notations, nomenclature and assumptions 10
3.1.1 Acronyms 10
3.1.2 Notations 11
3.1.3 Nomenclature 12
3.1.4 Assumptions 13
3.2 MCS method in terms of known all MPs to estimate two-terminal network reliability 13
3.2.1 Depth first search to find all MPs 14
3.2.2 MCS1: Procedure of knowing all MPs to estimate two-terminal network reliability 16
3.3 MCS method in terms of known all MCs to estimate two-terminal network reliability 17
3.3.1 Search all MCs of a network via Yeh’s algorithm 17
3.3.2 MCS2: Procedure of knowing all MCs to estimate two-terminal network reliability 18
3.4 MCS method without knowing MPs/MCs to estimate two-terminal network reliability 19
3.4.1 MCS3: Procedure of without knowing all MPs/MCs to estimate the two- terminal network reliability 19
3.4.2 Part of MP/MC information from MCS3 21
3.5 PSO combines with MCS to minimize cost under reliability constraints 23
3.5.1 Introduction to particle swarm optimization (PSO) 23
3.5.2 Model formulation of PSO combines with MCS to minimize cost under reliability constraint 24
Model Formulation 24
Heuristic method to find a particle’s initial solution 25
Penalty function 27
PSO combines with MCS to minimize cost under reliability constraint 28
Chapter 4 Result and Discussion 31
4.1 Illustrative example 31
4.2 Comparison and discussion 34
4.2.1 Results of three MCS methods with different replications 34
4.2.2 Percentage of finding MPs/MCs 46
4.2.3 Percentage of finding MP/MC with different arc reliability 49
4.3 The research of PSO combines with MCS 54
Chapter 5 Conclusion & Further Research 61
Reference 64

[1] S.J. Kamat, M.W. Riley, “Dtermination of reliability using event-based Monte Carlo simulation”, IEEE Transactions on Reliability, 1976, 24, pp 254-255.
[2] W.C. Yeh, “A simple algorithm to search for all MCs in networks”, European Journal of Operation Research, 2006, 174(3), pp 1694-1705.
[3] John Y. Lin, Charles E. Donaghey, “Monte Carlo simulation to determine minimal cut sets and system reliability”, Proceedings of the 1993 Annual Reliability and Maintainability Symposium, Atlanta, GA, USA.
[4] W.C. Yeh, “A MCS-RSM approach for network reliability to minimise the total cost”, International Journal of Advanced Manufacturing Technology, 2003, 22, pp 681–688.
[5] J. Lu, “Studies on the Monte Carlo simulation methods for estimating network reliability”, Master dissertation of the National Tsing Hua University, R.O.C., 1992.
[6] S. Soh and S. Rai, “Experimental results on preprocessing of path/cut term in the sum of disjoint products technique”, IEEE Transactions on Reliability, 1993, 42, pp 24-33.
[7] S. Kuo, S. Lu, and F. Yeh, “Determining terminal pair reliability based on edge expansion diagrams using OBDD”, IEEE Transactions on Reliability, 1999, 48(3), pp 234–246.
[8] J. Kennedy and R.C. Eberhart, C., “Particle Swarm Optimization”, Proceedings of IEEE International Conference on Neural Networks, NJ, USA, 1995, pp 1942−1948.
[9] A Allahverdi and FS Al-Anzi, “A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application”, Computers & Operation Research, 2006, 33(4), pp 1056–1080.
[10] C.H. Lin, “A squeeze Response Surface Methodology to Construct Approximate Reliability Function of Complex Networks”, Master thesis, Department of the National Tsing Hua University, R.O.C., 2007.
[11] ST Soh and S.Rai, “Experimental results on preprocessing of path cut terms in sum of disjoint products technique”, IEEE Transactions on Reliability, 1993, 42(1), pp 24-33.
[12] ST Soh and SE Rai, “CAREL:computer-aided reliability evaluator for distributed computing networks”, IEEE Transactions on Parallel and Distributed Systems, 1991, 2(2), pp 199-213.
[13] W.C. Yeh, “An improved sum-of-disjoint-products technique for the symbolic network reliability analysis with known minimal paths”, Reliability Engineering and System Safety, 2007, 92(2), pp 260-268.
[14] W.C. Yeh, C.H. Lin and Y.C. Lin, “A MCS Based Neural Network Approach to Extract Network Approximate Reliability Function”, Proceedings of Asia Simulation conference, Seoul, Korea, 2007, 11, pp 287−297.
[15] H. Wang and H. Pham, “Survey of reliability and availability evaluation of complex networks using Monte Carlo techniques”, Microelectronics and Reliability, 1997, 37(2), pp 187–209.
[16] T. Aven, “Availability evaluation of oil gas-production and transportation systems”, Reliability Engineering and System Safety, 1987, 18, pp 35-44.
[17] K. Aggarwal, J. Gupta and K. Misra, “A simple method for reliability evaluation of a communication system”, IEEE Transactions on Communications, 1988, 23, pp 563-566.
[18] M.A. Samad, “An efficient algorithm for simultaneously deducing minimal paths as well as cuts of a communication-network”, Microelectronics and Reliability, 1987, 27, pp 437-441.
[19] W.J. Ke and S.D. Wang, “Reliability evaluation for distributed computing networks with imperfect nodes”, IEEE Transactions on Reliability, 1997, 46, pp 342-349.
[20] P. Doulliez and E. Jalnoulle, “Transportation network with random arc capacities”, RAIRO, Rech. Operations Research, 1972, 3, pp 45-60.
[21] B. Roy and N.A. Ronald, “Reliability Evaluation of Engineering Systems Concepts and Techniques”, Plenum Press, New York, 1992.
[22] A.S. Bustamante, “Monte Carlo methods, in Reliability Engineering”, Proceedings of the ISPRA, 1988.
[23] L.L. Levy and A.H. Moore, “A Monde Carlo technique for obtaining system reliability confidence limits from component test data”, IEEE Transactions on Reliability, 1967, 16, pp 69-72.
[24] R.E. Rice and A.H. Moore, “A Monte Carlo techniques for estimating lower confidence limits on system reliability using pass-fail data”, IEEE Transactions on Reliability, 1983, 32, pp 366-369.
[25] G.S. Fishman, “A Monte Carlo sampling plan for estimating network reliability”, Operations Research, 1986, 34, pp 581-594.
[26] P. Kubat, “Estimation of reliability for communication/computer networks simulation/analytical approach”, IEEE Transactions on Communications, 1989, 37, pp 927-933.
[27] C.J. Colbourn, “The combinatorics of network reliability”, Oxford University Press, New York, 1987.
[28] A. Hoyland and M. Rausand, “System reliability theory: models and statistical methods”, John Wiley & Sons, Inc., 1994.
[29] A. Aggarwal and R.E. Barlow, “A survey of network reliability and domination theory”, Operations Research, 1984, 22, pp 478-492.
[30] M.O. Ball, “Computational complexity of network reliability analysis: an overview”, IEEE Transactions on Reliability, 1986, 35, pp 230-239.
[31] J.Y. Lin and C.E. Donaghey, “Monte Carlo simulation to determine minimal cut sets and system reliability”, Proceedings of the 1993 Annual Reliability and Maintainability Symposium, Atlanta, GA, USA.
[32] J.E. Ramirez-Marquez and D.W. Coit, “A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability”, Reliability Engineering and System Safety,2005, 87(2), pp 253-264.
[33] C.M. Rocco and E. Zio, “Solving advanced network reliability problems by means of cellular automata and Monte Carlo sampling”, Reliability Engineering and System Safety, 2005, 89(2), pp 219-226.
[34] H. Yoshida, K. Kawata, Y. Fukuyama and Y. Nakanishi, “A particle swarm optimization for reactive power and voltage control considering voltage security assessment”, IEEE Transactions on Power Systems, 2000, 15, pp 1232–1239.
[35] F. Van den Bergh, A.P. Engelbecht, “Cooperative learning in neural networks using particle swarm optimizers”, South African Computer Journal, 2000, 26, pp 84–90.
[36] L.W. Yeh, “Optimal Procurement Policies for Multiproduct Multi-supplier with Capacity Constraint and Price Discount”, Master thesis, Department of Industrial Engineering and Management, Yuan Ze University, Taiwan, ROC, 2003.
[37] M.F. Tasgetiren and Y.C. Liang, “A binary particle swarm optimization algorithm for lot sizing problem”, Journal of Economic and Social Research, 2003, 5(2), pp 1–20.
[38] M.F. Tasgetiren, M. Sevkli, Y.C. Liang and G. Gencyilmaz, “Particle swarm optimization algorithm for single machine total weighted tardiness problem”, Proceedings of the 2004 Congress on Evolutionary Computation, Portland, Oregon, 2004, pp. 1412–1419.
[39] G.C. Onwubolu and M. Clerc, “Optimal operating path for automated drilling operations by a new heuristic approach using particle swarm optimization”, International Journal of Production Research, 2004, 42(3), pp 473–491.
[40] M.F. Tasgetiren, Y.C. Liang, M. Sevkli and G. Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing”, European Journal of Operational Research, 2007, 177(3), pp 1930–1947.
[41] J. Moore and R. Chapman, “Application of particle swarm to multiobjective optimization”, Department of Computer Science and Software Engineering, Auburn University, 1999.
[42] T.C. Chen, “Penalty Guided PSO for Reliability Design Problems”, Trends in Artificial Intelligence, 2006, pp 777-786.