應用模組搜尋式簡化群體演算法於串並聯系統中一般化多層次冗餘配置問題之研究

Simplified Swarm Optimization with Modular Search for the General Multi-level Redundancy Allocation Problem in Series-parallel Systems

羅銓余

指導教授 ： 葉維彰

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

摘要

可靠度是影響系統正常運作的重要因素，為提高系統的可靠度，冗餘配置問題 (redundancy allocation problem, RAP) 漸漸成為系統在初始規劃、設計及控制階段中重要的工具。近幾年，單層次的冗餘配置問題已相繼發展成多層次冗餘配置問題 (multi-level redundancy allocation problem, MRAP) 與複合多層次冗餘配置問題 (multiple MRAP, MMRAP) 以解決現實生活中更複雜的多層次系統。

然而，上述所提及的兩個多層次問題在設計與建構模型時仍有其侷限，導致運用於現實中存有諸多限制，因而失去普遍性與一般性。為突破問題求解上的侷限，本研究建構了新的多層次冗餘配置問題模型：一般化多層次冗餘配置問題 (general multi-level redundancy allocation problem, GMRAP)，此模型的設計可更廣泛地適用於多種關鍵的系統，如製造系統、電腦伺服器系統及軟體系統。GMRAP不僅是個NP-hard問題，還是個非線性整數規劃與階層最佳化問題，較傳統的RAP, MRAP和MMRAP複雜，容易陷入區域解。為此，本研究提出一個新穎的演算法：模組搜尋式簡化群體演算法 (simplified swarm optimization with modular search, SSO-MS)，此演算法是以SSO為核心透過模組式的尋優方式來處理GMRAP，這也是首次將SSO演算法運用於具有階層 (hierarchy) 結構的冗餘配置問題上。

透過實作與驗證，將SSO-MS演算法與基因演算法 (genetic algorithm, GA) 以及粒子群演算法 (particle swarm optimization, PSO) 進行比較，結果顯示本研究所提出的SSO-MS演算法在三種演算法中具有相當的競爭力與優異的成效。同時，本研究以實例演示並驗證GMRAP，結果顯示其可行性與一般性優於MRAP與MMRAP。

關鍵字

可靠度最佳化 ； 冗餘配置 ； 多層次系統 ； 簡化群體演算

並列摘要

In recent decades, the redundancy allocation problem (RAP) is becoming an increasingly important tool in the initial stages of planning, designing, and controlling of systems. Moreover, the multi-level redundancy allocation problem (MRAP) and multiple multi-level redundancy allocation problem (MMRAP) are extensions derived from the RAP for practical modeling of real-life problems.

However, the two problems mentioned above still have restrictions that may be the best resolution in some special cases, but not in general. Therefore, this paper formulates a new kind of the MRAP called the general multi-level redundancy allocation problem (GMRAP) so as to break the restrictions and generalize previous problems. GMRAP designs are widespread in many critical systems, such as manufacturing systems, computing systems and software systems. GMRAP is not only NP-hard, but a nonlinear integer optimization problem with hierarchy. The complexity of GMRAP is much larger than the traditional RAP, MRAP and MMRAP. Furthermore, a novel algorithm called simplified swarm optimization with modular search (SSO-MS) is proposed to solve the GMRAP in this paper. To the best of our knowledge, this is the first attempt to use SSO for the hierarchal RAP instead of genetic algorithms.

Finally, the result obtained by SSO-MS has been compared with those obtained from genetic algorithms and particle swarm optimization algorithms. Computational results show that the proposed SSO-MS is very competitive and demonstrate the effectiveness and the practical viability of this approach and model.

並列關鍵字

Reliability Optimization ； Redundancy Allocation Problem (RAP) ； Multi-Level System ； Simplified Swarm Optimization (SSO)

參考文獻

[1] Yun, W.Y., Y.M. Song, and H.-G. Kim, Multiple multi-level redundancy allocation in series systems. Reliability Engineering & System Safety, 2007. 92(3): p. 308-313.

[2] Yun, W.Y. and J.W. Kim, Multi-level redundancy optimization in series systems. Computers & Industrial Engineering, 2004. 46(2): p. 337-346.

[3] Yang, B., H. Hu, and S. Guo, Cost-oriented task allocation and hardware redundancy policies in heterogeneous distributed computing systems considering software reliability. Computers & Industrial Engineering, 2009. 56(4): p. 1687-1696.

[4] Massim, Y., A. Zeblah, R. Meziane, M. Benguediab, and A. Ghouraf, Optimal Design and Reliability Evaluation of Multi-State Series-Parallel Power Systems. Nonlinear Dynamics, 2005. 40(4): p. 309-321.

[5] Chern, M.-S., On the computational complexity of reliability redundancy allocation in a series system. Operations Research Letters, 1992. 11(5): p. 309-315.