Approximation of Minimal Cut Sets for a Flow Network via Evolutionary Optimization and Data Mining Techniques

摘要

For the reliability analysis of networks, approaches based on minimal cut sets provide not only the necessary elements to obtain a reliability value but also, insight about the importance of network components. When considering a flow network, flow minimal cut sets - the equivalent of minimal cut sets in the binary case- identification is generally based on the a priori knowledge of binary minimal cut sets. Unfortunately, the enumeration of minimal cut sets is known to be an NP-hard problem. For complex and high density networks, obtaining an exact value of reliability may be prohibitive. Instead an approximation to the true reliability may suffice. In this paper, for the first time minimal cut set approximation for a flow network is done via the development of an optimization problem and an evolutionary algorithm to solve this model. The evolutionary algorithm is based on a data mining technique used to identify potentially optimal set of solutions- a subset of the true set of all cut sets that can be used to create reliability bound and identify critical components.