利用累加窮舉簡化群體演算法求解通用網路可靠度冗餘配置問題

A Novel Binary-addition Simplified Swarm Optimization for Generalized Reliability Redundancy Allocation Problem

陳任軒(Jen-Hsuan Chen)

指導教授 ： 葉維彰

國立清華大學/工學院/工業工程與工程管理學系/碩士(2021年)

摘要

網路系統常見於生活中各種應用，例如：電網、物聯網 (IoT)、瓦斯網路，然而許多系統皆暴露在失效的風險之下，因此網路系統的可靠度提升亦變得更加重要。可靠度冗餘配置問題 (Reliability redundancy allocation problem, RRAP) 是著名的可靠度設計工具，然而，當系統從常見的串並聯結構擴展為更複雜的網路結構後，RRAP亦需有相應發展才能有效解決網路系統的可靠度問題。本研究基於此將RRAP擴展為通用網路可靠度冗餘配置問題(Generalized reliability redundancy allocation problem, GRRAP) 以用於通用網路 (general network) 結構的系統，使RRAP得以轉換為網路可靠度最佳化問題，並使用累加窮舉演算法 (Binary Addition Tree Algorithm) 計算網路可靠度 (network reliability) 精確值。
由於RRAP為NP-hard問題，為求解比RRAP更為複雜的GRRAP，本研究提出累加窮舉簡化群體演算法 (Binary-addition simplified swarm optimization, BSSO) ，BSSO結合了BAT演算法的精確特性與SSO演算法的效率，利用多狀態BAT重組並篩選出可行的整數變數組合，能夠有效的縮小解空間加快找到高品質解的時間，此外，亦改良了多狀態BAT在列舉變數組合時耗費大量時間的問題，在面對有重量、體積限制的RRAP問題時，能有效避免掉多餘的運算過程以節省計算效能與時間。在研究的最後，BSSO也與基因演算法(Genetic Algorithm, GA)、粒子群最佳化演算法 (Particle Swarm Optimization, PSO) 及簡化群體演算法(Simplified Swarm Optimization, SSO) 進行比較，並在六個不同網路結構及大小的問題集中皆得到四個演算法中最佳的解品質

關鍵字

可靠度冗餘配置問題 ； 網路可靠度 ； 累加窮舉演算法 ； 簡化群體演算法 ； 柔性演算

並列摘要

Network systems are commonly used in various fields, such as power grid, Internet of Things (IoT), and gas networks. Systems are often associated with many risks and failures, so system reliability optimization has been the focus of research in the past. Reliability redundancy allocation problem (RRAP) is a well-known reliability design tool, which needs to be developed when the system is extended from the series-parallel structure to a more general network structure. Therefore, this study proposes a novel RRAP called General RRAP (GRRAP) to be applied to general network systems. In the network reliability evaluation, this study uses the Binary Addition Tree Algorithm (BAT) to calculate the exact value of network reliability
Since GRRAP is an NP-hard problem, a new algorithm called Binary-addition simplified swarm optimization (BSSO) is also proposed in this study. BSSO combines the accuracy of the BAT algorithm and the efficiency of the SSO algorithm. Using multi-state BAT to recombine and filter the integer variable combinations in advance can effectively reduce the solution space and speed up the time to find high-quality solutions. This study also improved the multi-state BAT to eliminate redundant computational procedures in the computation process, thus improving computational efficiency and saving time.
The experimental results show that BSSO outperforms three well-known algorithms, includes Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Simplified Swarm Optimization (SSO), on six different network benchmarks.

並列關鍵字

Reliability redundancy allocation problem (RRAP) ； Network reliability ； Binary-addition tree (BAT) ； Simplified swarm algorithm (SSO) ； Soft computing

參考文獻

[1] Kuo, W. and V.R. Prasad, "An annotated overview of system-reliability optimization". IEEE Transactions on reliability, vol. 49, no. 2, pp. 176-187, 2000

[2] Choi, T.-M., X. Wen, X. Sun, and S.-H. Chung, "The mean-variance approach for global supply chain risk analysis with air logistics in the blockchain technology era". Transportation Research Part E: Logistics and Transportation Review, vol. 127, pp. 178-191, 2019

[3] Colbourn, C.J., The combinatorics of network reliability. 1987: Oxford University Press, Inc.

[4] Tillman, F.A., C.-L. Hwang, and W. Kuo, "Determining component reliability and redundancy for optimum system reliability". IEEE Transactions on Reliability, vol. 26, no. 3, pp. 162-165, 1977

[5] Dhingra, A.K., "Optimal apportionment of reliability and redundancy in series systems under multiple objectives". IEEE Transactions on reliability, vol. 41, no. 4, pp. 576-582, 1992