A genetic algorithm to solve the robust design problem for a Flow Network with Node Failure
DOI:
https://doi.org/10.14738/tnc.84.8949Keywords:
Flow Network, robust design, node failure, genetic algorithmAbstract
The robust design problem in a flow network is defined as search optimal node capacity that can be assigned such that the network still survived even under the node’s failure. This problem is considered as an NP-hard. So, this paper proposes a genetic algorithm-based approach to solve it for a flow network with node failure. The proposed based genetic approach is used to assign the optimal capacity for each node to minimize the total capacities and maximize the network reliability. The proposed approach takes the capacity for each critical node should have the maximum capacity (usually equals to the demand value) to alleviate that the reliability to drop to zero. Three network examples are used to show the efficiency of our algorithm. Also, the results obtained by our approach are compared with those obtained by the previous approximate algorithm.
References
Ming J. zuo, Zhigang Tian and Hong-Zhong Huang, An efficient method for reliability evaluation of multistate networks given all minimal path vectors, IIE Transactions, 2007. 39: p. 811-817.
Aggarwal K. K. and Rai Suresh, Reliability evaluation in computer communication networks, IEEE Transactions on Reliability, 1981. 30(1).
A. Younes, Spanning trees and reliability of computer networks, Egyptian Informatics Journal, 2005. 6(1).
A. Younes and M. R. Hassan, A genetic algorithm for reliability evaluation of a stochastic-flow network with node failure, International Journal of Computer Science and Security (IJCSS), 2011. 4(6): p. 528-537.
Lin J., Jane C. and Yuan J., On reliability evaluation of a capacitated-flow network in terms of minimal path sets, Networks, 1995. 25: p.131-138.
Y. K. Lin, A simple algorithm for reliability evaluation of a stochastic-flow network with node failure, Computer and Operations Research, 2001. 28: p. 1277-1285.
Y. K. Lin, Reliability evaluation for an information network with node failure under cost constraint, IEEE Transactions on Systems, Man Cybernetics, part A: System and Humans, 2007. 37(2): p. 180-188.
Y. K. Lin, System reliability of a limited-flow network in multicommodity case, IEEE Transactions on Reliability, 2007. 56(1): p.17-25.
Satitsatian Sarintip and Kapur Kailash C., An algorithm for lower reliability bounds of multistate two-terminal networks, IEEE Transactions on Reliability, 2006. 55(2): p. 199-206.
S. G. Chen and Y. K. Lin, Capacity assignment for a stochastic-flow network based on structural importance, Asian Int. Workshop Adv. Reliab. Model. Taichung, Taiwan, 2008.
A. F. Zantuti, Algorithms for capacities and flow assignment problem in computer networks, 19th International Conference on Systems Engineering, 2008. p. 315-318.
Shin-Guang Chen and Yi-Kuei Lin, An Approximate Algorithm for the Robust Design in a Stochastic-Flow Network, Communications in Statistics-Theory and Methods, 2010. 39: p. 2440-2454.
Y. Niu, X. Xu, C. He, D. Ding and Z. Liu, Capacity Reliability Calculation and Sensitivity Analysis for a Stochastic Transport Network in IEEE Access, 2020. 8: p. 133161-133169.
Shin-Guang Chen, An optimal capacity assignment for robust design problem in capacitated flow networks Applied Mathematical Modelling ,2012. 36: p. 5272-5282.
D. L. Deeter and A. E. Smith, Heuristic Optimization of Network Design Considering All – Terminal Reliability in proc. Reliability and Maintainability Symp , 1997. p. 194-199.
Berna Dengiz Fulya Altiparmak and Alice E. Smith, Local search genetic algorithm for optimal design of reliable network IEEE Transactions on Evolutionary Computation, 1997. 1: p. 179-188.
Fulya Altiparmak Berna Dengiz and Alice E. Smith, Reliability Optimization of Computer Communication Networks Using Genetic Algorithms, 1998. p. 4676-4681.
C. A. Coello and A. D. Christiansen, Multi-objective optimization of trusses using genetic algorithms, Computers and Structures, 2000. 75(6): p. 647-660.
K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, A fast and elitist multi objective genetic algorithm, NSGA-II. IEEE Transactions on Evolutionary Computation, 2002. 6(2): p. 182-198.
H. A. Taboada, J. F. Espiritu and J. F. Coit, MOMS-GA: a multi-objective multi-state genetic algorithm for system reliability optimization design problems, IEEE Transactions on Reliability, 2008. 57(1): p. 182-191.
A. Azaron, C. Perkgoz, H. Katagiri, K. Kato and M. Sakawa, Multi-objective reliability optimization for dissimilar-unit cold-stand by systems using a genetic algorithm, Computers and Operations Research, 2009. 36(5): p. 1562-1571.
M. R. Hassan and H. Abdou, Multi-objective components assignment problem subject to lead-time constraint, Indian Journal of Science and Technology, 2018. 11(21): p. 1-9.
Ahmed Y. Hamed, Monagi H. Alkinani and M. R. Hassan, A Genetic Algorithm to Solve Capacity Assignment Problem in a Flow Network, Computers, Materials & Continua, 2020. 64(3): p. 1579-1586.
Mitsuo Gen and Runwei Cheng, Genetic Algorithms and Engineering Optimization, Wiley Series in Engineering Design and Automation, 2000. http://dx.doi.org/10.14738/tnc.84.8949 10
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Noha Hamdy, Moatamad Refaat Hassan, Mohamed Eid Hussein

This work is licensed under a Creative Commons Attribution 4.0 International License.