Fast Algorithm for Solving Cost Minimization Problem of Complex System with Unknown Constrained Reliability Function

doi:10.3969/j.cnki.jdxb.2016.04.005

Abstract

Abstract:

Aiming at the cost minimization problems of modern networks with unknown constrained reliability function，a fast solving algorithm is proposed based on the Monte Carlo Simulation (MCS) technique and the Support Vector Machine (SVM) technique.The proposed algorithm uses MCS technique to obtain the reliability values of complex network，and then uses Quantum Particle Swarm Optimization (DPSO) algorithm to search for the global optimal minimal value. With the reliability information previously obtained by MCS，the online SVM evaluation model of network reliability is constructed to determine the feasibility of the subsequent solutions，reducing the MCS simulating frequencies and solving time.Experiment results verify that，compared with Yeh's method and with 0.01 reliability simulation precision，the MCS frequencies and the solving time decrease by almost one order of magnitude.

Key words: complex network, cost minimization, Monte Carlo simulation, support vector machine, QPSO algorithm

CHEN Li，WANG Jingqin . Fast Algorithm for Solving Cost Minimization Problem of Complex System with Unknown Constrained Reliability Function[J]. Journal of Jishou University（Natural Sciences Edition), DOI: 10.3969/j.cnki.jdxb.2016.04.005.

References

[1] ZIO E，PODOFILLINI L,ZILLE V.A Combination of Monte Carlo Simulation and Cellular Automata for Computing the Availability of Complex Network Systems[J].Reliability Engineering & System Safety，2006，91(2)：181-190.
[2] LADYMAN J，LAMBERT J,WIESNER K.What is a Complex System？[J].European Journal for Philosophy of Science，2013，3(1)：33-67.
[3] PAGANI G A，AIELLO M.The Power Gridas a Complex Network：A Survey[J].Physica A：Statistical Mechanics and Its Applications，2013,11(1)：2 688-2 700.
[4] COIT D W，SMITH A E.Reliability Optimization of Series-Parallel Systems Using a Genetic Algorithm[J].IEEE Transactions on Reliability，1996，45(2)：254-260；266.
[5] TAVAKKOLI-MOGHADDAM R，SARARI J，SASSANI F.Reliability Optimization of Series-Parallel Systems with a Choice of Redundancy Strategies Using a Genetic Algorithm[J].Reliability Engineering and System Safety，2008,93(4)：550-556.
[6] KUMAR R，IZUI K,YOSHIMURA M，et al.Multi-Objective Hierarchical Genetic Algorithms for Multilevel Redundancy Allocation Optimization[J].Reliability Engineering and System Safety，2009，94(4):819-904.
[7] COELHO L D S.An Efficient Particle Swarm Approach for Mixed-Integer Programming in Reliability-Redundancy Optimization Applications[J].Reliability Engineering and System Safety，2009，94(4):830-837.
[8] 阮渊鹏,何桢.基于MCS-CA的考虑共因失效的复杂系统可靠性评估[J].系统工程与电子技术，2013,35(4)：900-904.
[9] YEH W C，EL KHADIRI M.A New Universal Generating Function Method for Solving the Single Quick-Path Problem in Multi-State Flow Networks[J].IEEE Transactions on Systems，Man and Cybernetics，2012，42(6)：1 476-1 484.
[10] KAMAT S J，RILEY M W.Determination of Reliability Using Event-Based Monte Carlo Simulation[J].IEEE Transactions on Reliability，1975，24(1)：73-75.
[11] YEH W C.A New Monte Carlo Method for the Network[C]∥International Conference on Information Technology and Applications，2002.
[12] YEH W C，LIN Y C，CHUNG Y Y，et al.A Particle Swarm Optimization Approach Based on Monte Carlo Simulation for Solving the Complex Network Reliability Problem[J].IEEE Transactions on Reliability，2010,59(1)：212-221.
[13] CANCELA H,ROBLEDO F,RUBINO G,et al.Monte Carlo Estimation of Diameter-Constrained Network Reliability Conditioned by Pathsets and Cutsets[J].Computer Communications，2013,36(6):611-620.
[14] RAMIREZ-MARQUEZ J E，COIT D W.A Monte-Carlo Simulation Approach for Approximating Multi-State Two-Terminal Reliability[J].Reliability Engineering & System Safety，2005,87(2):253-264.
[15] WANG Yong,LI Lin.Heterogeneous Redundancy Allocation for Series-Parallel Multi-State Systems Using Hybrid Particle Swarm Optimization and Local Search[J].IEEE Transactions on Systems，Man and Cybernetics，2012，42(2)：464-474.