A hybrid genetic algorithm for large-scaled reliability redundancy allocation problem with variable reduction strategies

複合式遺傳演算法暨變數縮減法求解大型可靠度冗件配置問題

郭奕群(Yih-Chun Kuo)

指導教授 ： 陳茂生

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

摘要

In this thesis, we propose a modified genetic algorithm (referred to as GA) for large-scaled reliability redundancy allocation problems (referred to as RRA) with series-parallel systems which were proven NP-hard. Traditional GAs do not perform well in large-scaled RRA without applying any frontier search technique. To obtain high quality solutions, it is critical to search the region near the boundary of the feasible region, but when considering large-scaled problems, it is difficult to achieve with such traditional GAs.
In the proposed algorithm, a large-scaled RRA problem is first narrowed down to an approximate core problem by applying some particular variable reduction strategies, and then the corresponding approximate core problem is solved by a modified hybrid genetic algorithm (referred to as HGA) first proposed by Huang. The proposed algorithm can obtain high quality solutions for large-scaled problems in a reasonable time and can be adopted into various problems by altering some mechanisms.

關鍵字

reliability redundancy allocation problem ； series-parallel system ； genetic algorithm ； core problem

參考文獻

[1] K. K. Aggarwal, J. S. Gupta, K. B. Misra, “A new heuristic criterion for solving a redundancy optimization problem”, IEEE Transactions on Reliability, vol. R-24, pp 86-87 (1975).

[2] K. K. Aggarwal, “Redundancy optimization in general systems”, IEEE Transactions on Reliability, vol. R-25, pp 330-332 (1976).

[3] E. Balas, “A note on the branch-and-bound principle”, Operations Research, vol. 16, pp 442-445 (1968).

[4] E. Balas, E. Zemel, “An algorithm for large zero-one knapsack problems”, Operations Research, vol. 28, pp 1130-1154 (1980).

[5] R. E. Bellman, S. E. Dreyfus, “Dynamic programming and the reliability of multicomponent devices”, Operations Research, vol. 6, pp 200-206 (1958).