應用混合螞蟻演算法於可靠度串並聯系統元件配置問題之研究

Optimization of the Series-Parallel System with the redundancy allocationproblem using a hybrid ant colony algorithm

黃宇辰(Yu-Chen Huang)

指導教授 ： 蔡啟揚

元智大學/工程學院/工業工程與管理學系/碩士(2003年)

摘要

隨著生產型態的改變下，使得生產系統效能之提昇逐漸受到系統設計者的重視，因此本研究首度提出一混合螞蟻演算法來分析串並聯系統元件配置的問題，在螞蟻演算法中之區域搜尋裡加入塔布串列的機制，以提昇搜尋解之品質，並應用此方法在多個可選用的元件中選擇來配置於子系統裡，以決定最佳的系統設計結構。進一步來說，此問題即是以系統配置成本最小化為目標，並在系統可靠度及體積作為限制下，來選擇元件與其複置水準最佳化的系統配置狀態，經由實驗設計與結果分析顯示，混合螞蟻演算法能尋求到最佳或是近似最佳解的元件配置組合，其所獲得的結果也具有相當之求解效益。
除上述成果外，本研究尚探討了混合螞蟻演算法參數的設計，對於保留費洛蒙的機率、機率函數的選擇基準、費洛蒙氣味的相對強度、區域探索的相對強度與塔布串列的長度等容易影響搜尋結果之參數作一分析討論，最後並提出參數因子之水準設定區間的建議。

關鍵字

串並聯系統 ； 元件配置問題 ； 螞蟻演算法

並列摘要

The efficiency of production system has drawn more and more attention of system designers, as competitive pressures increase. Therefore, in this research, we propose a new hybrid ant colony algorithm to analyze redundancy allocation problem in series-parallel systems. The mechanism of Tabu lists is applied for local search in ant colony algorithm to increase quality of search results. We study the problem of selecting component and redundancy levels to optimize allocation cost, given system-level constraints on reliability and weight. Through experimental design and result analysis, it is shown that hybrid ant colony algorithm can search for optimal or near-optimal solutions in redundancy allocation problems with impressive efficiency.
Besides the above-mentioned achievements, this research also investigates the best selection of parameter values in the mixed ant colony algorithm. The parameters we analyzed include trail persistence, the relative importance of exploitation versus exploration, the relative importance of pheromone trail, relative importance of local heuristic and length of tabu list. Finally, we provide suggestions for setting the levels of parameters.

並列關鍵字

series-parallel system ； redundancy allocation problem ； ant colony algorithm

參考文獻

1.Armentano V. A. and Ronconi D. P., “Tabu search total tardiness minimization in flowshop scheduling problem”, Computers and Operations Research, vol. 26, 1999, pp219-235.

2.Armentano V. A. and S. C. Rigao, “Tabu search total tardiness minimization in a job shop”, Internatiiional Journal of Production Economics, vol. 63, 2000, pp 131-140.

4.Barnes J. W., Laguna M., “A tabu search experience in production scheduling”, Annals of Operations Research, vol. 41, 1993.

5.Blazewics J., Hawryluk P., Walkowiak R., “Using tabu search approach for solving the two-dimensional irregular cutting problem”, Annals of Operations Research, vol. 41, 1993, pp 31-327.

7.Bellman R. E., Dreyfus E., “Dynamic programming and reliability of multi-component devices”, Operations Research, vol. 6, 1958 Mar-Apr, pp 200-206.