(3.235.245.219) 您好!臺灣時間:2021/05/10 01:51
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊若筠
研究生(外文):JO-YUN YANG
論文名稱:混合基因與禁忌搜尋於具相關性失效之隨機流量網路可靠度最佳化
論文名稱(外文):Maximizing Network Reliability for Stochastic-flow Networks with Correlated Failures Using a Hybrid GA-TS Algorithm
指導教授:林義貴林義貴引用關係
指導教授(外文):Yi-Kuei Lin
口試委員:林義貴
口試委員(外文):Yi-Kuei Lin
口試日期:2013-10-30
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2013
畢業學年度:102
語文別:英文
論文頁數:74
中文關鍵詞:網路可靠度最佳化隨機流量網路資源配置相關性失效混合基因與禁忌搜尋演算法柔性計算
外文關鍵詞:Network reliability optimizationStochastic-flow networkResource assignmentCorrelated failuresHybrid GA-TS algorithmSoft computing algorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:101
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
真實世界中,許多系統,如電力系統、電腦系統與運輸系統等,可藉由模擬成由傳輸邊及節點所組成的隨機流量網路(stochastic-flow network),以分析該系統之績效。其中網路可靠度可定義為d單位的需求可以成功地藉由此網路自發送端傳送至接受端之機率。而從一個品質管理的觀點來看,網路可靠度最佳化(network reliability optimization)為對許多系統管理者所欲達成之目標。因此如何自現有之資源中,配置一組資源於網路之邊或節點上,使得網路可靠度最佳,為網路可靠度最佳化重要議題之一。
儘管有大量的文獻探討著網路可靠度最佳化的議題,然而大多數的研究並沒有考量到相關性失效(correlated failure)的因素之於網路可靠度最佳化的關係。在現實世界中,大規模的災害將會對網路造成相當範圍的損害並產生相關性失效。而此相關性失效將有可能對於網路可靠度造成影響。
本論文以隨機流量網路為網路模型並提出考量相關性失效因素的資源配置問題。同時,對於此問題我們發展出一個混合基因與禁忌搜尋演算法(hybrid GA-TS algorithm),利用該演算法有效地找出具有最大網路可靠度值的最佳資源配置(resource assignment)。另外,我們採用了三個基準電腦網路進行實驗並針對數個柔性計算(soft computing algorithms)包括混合基因與禁忌搜尋演算法與粒子群最佳化演算法、蟻群最佳化演算法、基因演算法、禁忌搜尋演算法比較其計算效率。而從實驗結果發現在求解該考量相關性失效因素的資源配置問題下,本論文所提出的混合基因與禁忌搜尋演算法和其他柔性計算相比,可以擁有較好的品質和更有效的計算效率獲得最佳網路可靠度。
Many real-life systems such as electric power systems, computer systems, and transportation systems can be characterized as stochastic-flow networks (SFN) composed of both sets of arcs and nodes to analyzing its performance. Network reliability is defined as the probability that d units of demand are successfully transmitted from a source node to a sink node. From a perspective on quality management, network reliability optimization is the goal for most of system supervisors. Thus, how to determine the optimal resource assignment from a set of resources to maximize network the reliability is an important issue.
Despite the numerous researches on the topic of network reliability optimization, virtually most of the previous researches didn’t discuss network reliability optimization with the consideration of correlated failures. In the real world, a large-scale disaster may cause widespread damage to lead to correlated failures for the networks. And correlated failures may influence the network reliability.
This thesis is based on SFN model and proposes the resource assignment problem with correlated failures (RACF problem). And we develop a hybrid GA-TS algorithm (HGTA) to efficiently search the optimal resource assignment with the maximal network reliability. Three benchmark computer networks for the RACF problem are adopted to compare the computing efficiency of HGTA with those of other soft computing algorithms including PSO, ACO, GA, and TS. And the experimental results show the proposed HGTA has better quality and better computational efficiency than other algorithms for obtaining the maximal network reliability.
摘要 I
ABSTRACT II
ACKNOWLEDGMENTS III
CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES VII
Chapter 1 INTRODUCTION 1
1.1. Background and motivation 1
1.2. Research objectives 3
1.3. Overview of this thesis 4
Chapter 2 LITERATURE REVIEW 6
2.1. Network reliability analysis 6
2.2. Network reliability optimization 6
2.3. Correlated failures 8
2.4. Soft computing algorithms 9
Chapter 3 PROBLEM MODELING AND MATHEMATICAL TECHNIQUES FOR CORRELATIONS 11
3.1. Problem formulation 13
3.2. Mathematical techniques for correlations 14
3.3. Development of the SFN model associated with a resource assignment 18
3.3.1. Flow vector and capacity vector 18
3.3.2. Reliability evaluation of a stochastic-flow network 18
3.3.3. Generation of all d-MPs 19
3.4. Reliability evaluation algorithm 22
Chapter 4 DEVELOPMENT FOR HYBRID GA-TS ALGORITHM 24
4.1. HGTA development 25
4.1.1. Genetic algorithm 26
4.1.2. Tabu search 29
4.2. HGTA procedure 31
Chapter 5 NUMERICAL EXPERIMENTS 35
5.1. Comparing the soft computing algorithms’ computational efficiency 35
5.2. Assess the impact on network reliability within different values of correlation 51
Chapter 6 CONCLUSIONS AND FUTURE RESEARCH 54
REFERENCES 56
APPENDIX A. PROCEDURE FOR THE MATHMATICAL TECHNIQUES 60
A. Correlated identical physical lines 60
A.1. Series of physical lines 61
A.2. Two out of three physical lines 62
A.3. Parallel of physical lines 62
A.4. k-out-of-n of physical lines 62
Amiri, A. and Pirkul, H., “Routing and capacity assignment in backbone communication networks”, Computers and Operations Research, Vol. 24, pp. 275-287 (1997).
Bilgin, S. and Azizoǧlu, M., “Operation assignment and capacity allocation problem in automated manufacturing systems”, Computers and Industrial Engineering, Vol. 56, no. 2, pp. 662-676 (2009).
Blum, C., “Ant colony optimization: Introduction and recent trends”, Physics of Life Reviews, Vol. 2, no. 4, pp. 353-373 (2005).
Charles1, V. and Udhayakumar, A., “Genetic algorithm for reliability evaluation of a stochastic-flow network with node failure”, International Journal of Operational Research, Vol. 14, no. 4, pp. 417-432 (2012).
Fiondella, L. and Zeephongsekul, P., “Reliability of systems with identically distributed correlated components”, Proceedings of ISSAT International Conference on Reliability and Quality in Design, pp. 26-30 (2011).
Ford, L. R. and Fulkerson, D. R., Flows in networks, Princeton University, NJ (1962).
Glover F., “Future paths for integer programming and links to artificial intelligence”, Computers and Operations Research, Vol. 13, no. 5, pp. 533-549 (1986).
Glover F., “ Tabu Search: A tutorial”, Interfaces, Vol. 20, no. 4, pp. 74-94 (1990).
Glover, F., “Heuristic for integer programming using surrogate constraints”, Decisioni Scienices, Vol. 8, no. 1, pp.156-166 (1997).
Glover, F. and Laguna, M., Tabu search. Dordrecht: Kluwer Academic Publishers (1997).
Goldberg, D. E. and Holland J. H., “Genetic algorithms and machine learning”, Machine Learning, Vol. 3, no. 2-3, pp. 95-99 (1988).
Holland, J. H., Adaption in natural and artificial systems. Ann Arbor: University of Michigan Press (1975).
Hsieh, C.C. and Chen, Y.T., “Reliable and economic resource allocation in an unreliable flow network”, Computer and Operations Research, Vol. 32, no. 3, pp. 613-628 (2005a).
Hsieh, C.C. and Chen, Y.T., “Resource allocation decisions under various demands and cost requirements in an unreliable flow network”, Computer and Operations Research, Vol. 32, no. 3, pp. 2771-2784 (2005b).
Hsieh, C. C. and Lin, M. H., “Simple algorithms for updating multi-resource allocations in an unreliable flow network”, Computers and Industrial Engineering, Vol. 50, pp. 120-129 (2006).
Levitin, G. and Lisnianski, A., “A new approach to solving problems of multi-state system reliability optimization”, Quality Reliability Engineering International, Vol. 17, no. 2, pp. 93-104 (2001).
Li, Y. and Deng, Y., Hybrid algorithm based on improved PSO and Tabu. Central South University (2012).
Lin, J.S., Jane, C.C., and Yuan, J., “On reliability evaluation of a capacitated-flow network in terms of minimal pathsets”, Networks, Vol. 25, no. 3, pp. 131-138 (1995).
Lin, Y.K., “A simple algorithm for reliability evaluation of a stochastic-flow network with node failure”, Computer and Operations Research, Vol. 28, no. 13, pp. 1277-1285 (2001a).
Lin, Y. K., “Study on the multicommodity reliability of a capacitated-flow network”, Computers and Mathematics with Applications, Vol. 42, no.1-2, pp. 255-264 (2001b).
Lin, Y. K., “Reliability of a stochastic-flow network with unreliable branches and nodes under budget constraints”, IEEE Transactions on Reliability, Vol. 53, no.3, pp. 381-387 (2004).
Lin, Y. K., “Reliability evaluation for an information network with node failure under cost constraint”, IEEE Transactions on Systems, Man and Cybernetics – Part A: Systems and Humans, Vol. 37, no.2, pp. 180-188 (2007a).
Lin, Y. K., “On a multicommodity stochastic-flow network with unreliable nodes subject to budget constraint”, European Journal of Operational Research, Vol. 176, no.1, pp. 347-360 (2007b).
Lin, Y.K. and Yeh, C.T., “Maximal network reliability with optimal transmission line assignment for stochastic electric power networks via genetic algorithms”, Applied Soft Computing, vol. 11, no. 2, pp. 2714-2724 (2010a).
Lin, Y. K. and Yeh, C. T., “Optimal resource assignment to maximize multistate network reliability for a computer network”, Computers and Operations Research, Vol. 37, no. 12, pp. 2229-2238 (2010b).
Lin, Y. K. and Yeh, C. T., “Computer network reliability optimization under double-resource assignments subject to a transmission budget”, Information Sciences, Vol. 181, no. 3, pp. 582-599 (2011).
Lin, Y.K., Chang, P.C., and Fiondella L., “Quantifying the impact of correlated failures on stochastic flow network reliability”, IEEE Trans. Reliability, Vol. 61, no. 3, pp. 275-287 (2012).
Lin, Y. K., Yeh, C.T., and Huang, P.S., “A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem”, Applied Soft Computing Journal, Vol. 13, no. 8, pp. 3529-3543 (2013).
Lisnianski, A. and Levitin, G., Multi-state system reliability: assessment, optimization and application, Vol. 6, World Scientific, Singapore (2003).
Liu, Q., Zhang, H., Ma, X., and Zhao, Q., “Genetic algorithm-based study on flow allocation in a multi-commodity stochastic-flow network with unreliable nodes”, Proceedings of The 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Tsinan, pp. 576-581 (2007).
Liu, Q., Zhao, Q., and Zang, W., “Study on multi-objective optimization of flow allocationin a multi-commodity stochastic-flow network with unreliable nodes”, Journal of Applied Mathematics and Computing, Vol. 28, no. 1-2, pp. 185-198 (2008).
Neumayer, S., Zussman, G., Cohen, R., and Modiano, E., “Assessing the impact of geographically correlated network failures”, Proceedings of IEEE Military Communications Conference MILCOM, art. no. 4753111 (2008).
Neumayer, S., Zussman, G., Cohen, R., and Modiano, E., “Assessing the vulnerability of the fiber infrastructure to disasters”, Proceedings of IEEE INFOCOM , art. no. 5062074 , pp. 1566-1574 (2009).
Neumayer, S. and Modiano, E., “Network reliability with geographically correlated failures”, Proceedings of IEEE INFOCOM, art. no. 5461984 (2010).
Park, C.G., Park, T., and Shin, D.W., “A Simple Method for Generating Correlated Binary Variates”, American Statistician, Vol. 50, no. 4, pp. 306-301 (1996).
Rahnamay-Naeini, M., Pezoa, J.E., Azar, G., Ghani, N., and Hayat, M.M., “Modeling stochastic correlated Failures and their effects on network reliability”, Proceedings of International Conference on Computer Communications and Networks, ICCCN , art. no. 6005789 (2011).
Ramirez-Marquez, J. E. and Coit, D. W., “A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability”, Reliability Engineering & System Safety”, Vol. 87, no. 2, pp. 253-264 (2005).
Ramirez-Marquez, J. E. and Rocco S., C. M., “Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery”, Reliability Engineering and System Safety, Vol. 94, no. 5, pp. 913-921 (2009).
Ramirez-Marquez, J. E., Rocco S., C. M., and Levitin, G., “Optimal protection of general source-sink networks via evolutionary techniques”, Reliability Engineering and System Safety, Vol. 94, no. 10, pp. 1676-1684 (2009).
Xu, W., He, S., Song, R., and Li, J., “Reliability based assignment in stochastic-flow freight network”, Applied Mathematics and Computation, Vol. 211, no. 1, pp. 85-94 (2009).
Yang, Q., Zhang, C. and Wang, C., “An efficient discrete particle swarm algorithm for task assignment problems”, IEEE International Conference on Granular Computing, GRC 2009, art. no. 5255030, pp. 686-690 (2009).
Yim, K.K.W., Wong, S.C., Chen, A., Wong, C.K., and Lam, W.H.K., “A reliability-based land use and transportation optimization model”, Transportation Research Part C: Emerging Technologies, Vol. 19, no. 2, pp. 351-362 (2011).
Younes A. and Hassan M. R., “A genetic algorithm for reliability evaluation of a stochastic- flow network with node failure”, International Journal of Computer Science and Security, Vol. 4, no. 6, pp. 528-536 (2011).
Zhang, Y., Xu, Z.G., Wang, W.H., Lu, J.G., and Sun, Y.X., “Optimal transmission lines assignment with maximal reliabilities in multi-source multi-sink multi-state computer network”, Journal of Central South University, Vol. 20, no. 7, pp. 1868-1877 (2013).
Zuo, M. J., Tian, Z., and Huang, H. Z., “An efficient method for reliability evaluation of multistate networks given all minimal path vectors”, IIE Transactions, Vol. 39, no. 8, pp. 811-817 (2007).
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔