遺傳演算法求解 Linear Consecutive-k-out-of-n 和 Linear Consecutive-(r, s)-out-of-(m, n): F 系統最佳化問題

Solving Optimization Problem with Linear Consecutive-k-out-of-n and Linear Consecutive-(r, s)-out-of-(m, n): F system by Using Genetic Algorithms

林政文(Cheng-Wen Lin)

指導教授 ： 陳茂生

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

摘要

對於 linear consecutive-k-out-of-n 和 linear consecutive-(r, s)-out-of-(m, n): F 系統最佳化的問題，目前已經有一些趨近的方法，這些方法都是以 reliability importance 為基礎；我們將使用遺傳演算法來求解 linear consecutive-k-out-of-n 和 linear consecutive-(r, s)-out-of-(m, n): F 系統最佳化的問題。
傳統的遺傳演算法在長時間之後，母體會有收斂到區域最佳解的情況，使得交配和突變的機制弱化。因此，我們在母體出現有可能收斂到區域最佳解時，對母體進行擾動，增加交配和突變的搜尋能力。

關鍵字

遺傳演算法

並列摘要

The linear consecutive-k-out-of-n and the linear consecutive-(r, s)-out-of-(m, n): F system both are enumerated minimum cuts easily. The optimization problem with linear consecutive-k-out-of-n: F system is discussed by many people. They proposed some heuristic methods for solving problem that are based on reliability importance. We propose the genetic algorithm for solving the optimization problem with linear consecutive-k-out-of-n: F system by introducing with reliability importance.
The population in a genetic algorithm may converge on a local optimal solution and the mechanisms of crossover and mutation are not very effective to search other solution when the algorithm runs long time. We propose a perturbation mechanism to let the population get diverge and solution search scope gets larger to escape the population converges on a local optimal solution.

並列關鍵字

Linear consecutive-k-out-of-n: F system ； Linear consecutive-(r,s)-out-of-(m,n): F system ； Genetic Algorithms ； Birnbum importance ； Reliability importance ； LK heuristic

參考文獻

[Chian 1981] Chiang, D. T. and N., S. (1981). " Reliability of consecutive-k-out-of-n: F system." IEEE Transactions on Reliability 30: 87-89.

[Dengi 1997] Dengiz, B., Altiparmak, Fulya and Smith, Alice E. (1997). "Efficient optimization of all-terminal reliable networks using an evolutionary approach." IEEE Transactions on Reliability 46: 18-26.

[Derma 1982] Derman, C., Lieberman, G. J. and Ross, S. (1982). "On the consecutive-k-out-of-n: F system." IEEE Transactions on Reliability 31: 57-63.

[Fogel 1994] Fogel, D. (1994). "An Introduction to simulated evolutionary optimization." IEEE Transactions on Neural Networks 5: 3-14.

[Fu 1981] Fu, J. C. (1986). "Reliability of consecutive-k-out-of-n: F system with (k-1) step Markov dependence." IEEE Transactions on Reliability 35: 602-606.