臺灣博碩士論文加值系統

本研究主要是應用平行計算（Parallel Computing）及遺傳演算法（Genetic Algorithms，GA）於水庫即時操作之優選模式。
由於平行處理技術進步與電腦功能提昇，使得個人電腦叢集成為新興的高效能平行計算平台。而遺傳演算法為全域搜尋，自動優選之一種系統佳化工具，其優點為適用性廣，可處理大型複雜系統最佳化問題，同時本質上具有可平行性。因此，本研究目的即在於建立一個以平行演算之電腦技巧，應用於以遺傳演算法為搜尋技能之水庫即時操作優選模式。在平行演算技術上，本研究使用個人電腦叢集（PC Cluster），進行以訊息傳輸介面（MPI，Message Passing Interface）為工具之平行計算，探討平行演算法可行性同時評估其效能。
此模式應用於德基水庫之操作，其演算結果顯示，平行演算之計算結果與未平行演算之單機執行結果完全相同。在演算效率上，改變初始族群數的大小，計算速度提升值亦會隨之增減，但改變染色體長度則並無造成明顯的影響。即當計算矩陣愈大時，進行平行計算的效率提升愈具成效。

This study is mainly applying parallel computing and Genetic Algorithms to the real-time reservoir operation mode.
The purpose of this study is setting up the Parallel Algorithms optimization mode. Choose De-Ji reservoir as example, using the ability of global searching and the property of parallel process of Genetic Algorithms, processing parallel computing with Message Passing Interface (MPI) by using PC cluster. And discussing the feasibility and evaluating the efficiency of Parallel Algorithms
The results show that the computing results of Parallel Algorithms by using PC cluster is the same as the computing results of Genetic Algorithms by using single computer completely. In the part of speedup, change the initial population size, the speedup value will increase with it. Changing the chromosome length, the speedup value won’t affect the speedup value obviously. The speedup value is more effective while the parallel computing matrix size is larger.

目錄
中文摘要 I
ABSTRACT II
目錄 III
表目錄 VI
圖目錄 VII
第一章 前言 1
1-1 研究動機 1
1-2 研究方法與目的 2
第二章 文獻回顧 4
2-1 即時操作相關研究 4
2-2 遺傳演算法之相關研究 5
2-3 平行演算法之相關研究 6
2-3-1 叢集式平行電腦系統的興起 7
2-3-2 平行計算之相關研究 8
2-3-3 平行演算法結合遺傳演算法之相關研究 10
第三章 理論基礎及研究設備 12
3-1 即時操作理論 12
3-1-1 引言 12
3-1-2 原理與模式架構 12
3-2 流量預測模式 13
3-3 遺傳演算法理論 14
3-3-1 概述與簡介 14
3-3-2 遺傳演算法的架構 16
3-3-4 基本的遺傳演算法運算元 18
3-4 平行演算法理論 19
3-4-1平行計算之原理 19
3-4-2 平行演算法之優點 20
3-4-3 平行電腦 20
3-5 研究設備 22
第四章 相關數據及假設 26
4-1 大甲溪流域之相關水力設施概述 26
4-2 相關引用資料 28
4-3 基本假設 28
第五章 模式之應用 30
5-1 即時操作流程 30
5-2 德基水庫旬入流量預測模式之建立 30
5-3 本文目標函數說明 31
5-4 遺傳演算法於模式中之應用 32
5-4-1 連續方程式 32
5-4-2 建立遺傳演算法之優選模式 32
5-4-3 遺傳演算法參數設定 34
5-5 平行演算法於模式中之應用 35
5-5-1 建立平行演算之模式 35
5-5-2 初始族群數之分割與分配 36
5-6 水庫操作限制方程式 36
5-6-1 水庫放水限制 36
5-6-2 水庫水位限制 36
5-6-3 發電量限制條件 37
5-6-4 即時操作旬初水庫蓄水量之修正 37
第六章 演算結果討論與分析 39
6-1 平行效能之評估指標 39
6-2 資料傳輸時間之分析 40
6-3 與前人研究結果之比較 41
6-3-1 速度提升與效率之探討 41
6-3-2 模式應用結果之探討 43
第七章 結論與建議 44
7-1 結論 44
7-2 建議 45
附錄 71
表目錄
表4-1 德基水庫水位標高-電水比關係表 51
表4-2 德基水庫水位標高-容積關係表 52
表4-3 民國九十年石岡壩下游公共給水及灌溉需水量表 53
表5-1 THOMAS & FIERING模式之相關數據表（30年） 54
表6-1 不同染色體長度與初始族群數之速度提升SN值（豐水年） 55
表6-2 不同染色體長度與初始族群數之速度提升SN值（枯水年） 55
表6-3 不同染色體長度與初始族群數之速度提升SN值（平水年） 55
表6-4 不同染色體長度與初始族群數之效率EN值（豐水年） 56
表6-5 不同染色體長度與初始族群數之效率EN值（枯水年） 56
表6-6 不同染色體長度與初始族群數之效率EN值（平水年） 56
表6-7 豐水年之操作結果 57
表6-8 枯水年之操作結果 58
表6-9 平水年之操作結果 59
附表1 MPI 內定的資料類別 75
圖目錄
圖3-1 遺傳演算法流程圖 60
圖3-2 硬體設備配置圖 61
圖4-1 大甲溪流域水力分佈圖 62
圖4-2 豐水年、枯水年、平水年之流量歷線圖 63
圖5-1 模式操作流程圖 64
圖5-2 平行遺傳演算法之概念流程圖 65
圖6-1（A） 不同染色體長度的SN值對初始族群數之關係 66
圖6-1（B） 不同初始族群數的SN值對染色體長度之關係 66
圖6-2（A） 不同染色體長度的EN值對初始族群數之關係 67
圖6-2（B） 不同初始族群數的EN值對染色體長度之關係 67
圖6-3（A） 不同染色體長度的SN三水文年平均值對初始族群數之關係 68
圖6-3（B） 不同初始族群數的SN三水文年平均值對染色體長度之關係 68
圖6-4（A） 不同染色體長度的EN三水文年平均值對初始族群數之關係 69
圖6-4（B） 不同初始族群數的EN三水文年平均值對染色體長度之關係 69
圖6-5 透過內部網路傳送封包之時間結果 70
圖6-6 透過外部網路傳送封包之時間結果 70

1. 李天佑、游輝宏，「非線性系統之平行計算－區域分割方法在流體力學計算上的應用」，高速計算世界，VOL.7 NO.4，1999年12月。
2. 沈澄宇，「從計算流體力學論平行電腦之可擴充性」，高速計算世界，VOL.2 NO.2，1994年6月。
3. 沈澄宇、姜巍棠，「計算流體力學系列講座(II)：『平行計算流體力學』簡介」，高速計算世界，VOL.5 NO.3，1997年12月。
4. 吳膺義，「平行計算在結構大變形分析之應用」，國立成功大學土木工程學系研究所碩士論文，民國89年。
5. 易任、胡文章、朱健行，「應用數理規劃建立水庫運用基準線配合合理農業用水之研究」，農委會水利工程組 / 國立台灣大學農業工程研究所，民國71年6月。
6. 周育興，「計算網格產生之平行運算與效益」，國立成功大學水利及海洋工程學系研究所碩士論文，民國89年。
7. 邱仕宏，「遺傳演算法於水庫即時操作之應用」，國立中興大學土木工程學系研究所碩士論文，民國90年6月。
8. 邱永裕，「以基因演算法與平行運算進行翼型優化」，國立成功大學航空太空工程學系研究所碩士論文，民國89年。
9. 林勝儀，「配水管網及配水池之佳化設計」，國立中興大學土木工程學系研究所碩士論文，民國90年6月。
10. 高力山，「水庫操作規線對供水及排砂影響之研究」，國立台灣大學農業工程研究所碩士論文，民國86年。
11. 陳仁暐，「即時水庫操作優選模式之研究」，國立中興大學土木工程學系研究所碩士論文，民國86年6月。
12. 許至璁、葉克家，「分散式平行計算在渠道變量流模擬之應用」，高速計算世界，VOL.3 NO.3，1995年。
13. 張良正、石明輝，「基因演算法於多目標水庫系統操作之運用」，國立交通大學土木所碩士論文，民國87年6月。
14. 連和政、葉克家，「分散式平行計算在土石流堆積模擬之應用」，高速計算世界， VOL.3 NO.3，1995年。
15. 梁俊偉，「平行混成多層遺傳演算法應用於幾何非線性結構最佳化設計之研究」，國立中山大學機械工程學系研究所碩士論文，民國89年。
16. 郭振泰等，「淡水河流域水庫系統即時優選操作模式之發展與應用」，國立台灣大學土木工程學研究所水利工程組研究報告7711號，民國77年。
17. 郭振泰、徐年盛、陳昶憲等，「德基水庫旬即時操作之研究與應用」，經濟部水資會委託，台大土木工程研究所執行，民國81年。
18. 陳莉，「動態規劃模式有效應用於多水庫系統操作之研究」，國立台灣大學農業工程研究所碩士論文，民國78年。
19. 陳莉，「以物件導向之遺傳演算法優選水庫運用規線之研究」，國立台灣大學農業工程研究所博士論文，民國83年。
20. 陳飛文，「平行遺傳演算法於營建排程運用之探討」，國立台灣科技大學營建工程系研究所碩士論文，民國90年。
21. 張斐章、王文清，「模糊線性規劃於水資源規劃之應用」，台灣水利，第43卷 第一期，民國84年。
22. 張斐章、陳莉，「目標函數對水庫即時操作之影響」，台灣水利，第39卷 第二期，民國80年3月。
23. 張斐章、賴進松、高力山，「應用遺傳演算法優選大埔水庫排砂操作規線」，台灣水利，第46卷 第三期，民國87年9月。
24. 陳頌平，「灰色模糊動態規劃於水庫即時操作之應用」，國立中興大學土木工程學系研究所碩士論文，民國89年6月。
25. 郭錦文，「德基水庫操作優選模式之研究」，國立中興大學土木工程學系研究所碩士論文，民國85年6月。
26. 曾明性，「分散式計算於方柱周圍紊流流場模擬之應用」，高速計算世界，VOL.3 NO.2，1995年6月。
27. 楊元森、謝尚賢，「利用個人電腦叢集進行平行有限元素結構分析」，中國土木水利工程學刊，第12卷 第4期，民國89年。
28. 經濟部水資源局，「水資源政策白皮書」，民國86年。
29. 經濟部水利司，「台灣地區重要水庫運用規線之探討」，民國84年。
30. 萬象，「水庫即時優選操作與風險分析之研究」，國立臺灣大學土木工程研究所博士論文，民國79年。
31. 鄭守成 編著，「Fortran 語言MPI 平行計算程式設計」，民國90年3月。
32. 鄭守成，「漫談程式的向量化與平行化」，高速計算世界，VOL.1 NO.2，1993年12月。
33. 鄭守成，「漫談平行電腦與平行計算」，高速計算世界，VOL.4 NO.4，1996年12月。
34. 鄭守成，「MPI平行計算程式設計 -1- 」，高速計算世界，VOL.6 NO.3 ，1998年12月。
35. 鄭守成，「MPI平行計算程式設計 -2- 」，高速計算世界，VOL.7 NO.1，1999年3月。
36. 鄭守成，「MPI平行計算程式設計 -3- 」，高速計算世界，VOL.7 NO.2，1999年6月。
37. 鄭守成，「MPI平行計算程式設計 -4- 」，高速計算世界，VOL.7 NO.3，1999年9月。
38. 鄭守成，「MPI平行計算程式設計 -5- 」，高速計算世界，VOL.7 NO.4，1999年12月。
39. 盧延年，「平行計算環境的建製與區域分解算法求解純對流方程式的數值計算」，淡江大學航空太空工程學系研究所碩士論文，民國89年。
40. 謝季壽、趙芳成，「大甲溪流域水力開發中之新天輪與馬鞍水力兩發電計畫」，第四屆海峽兩岸水利科技交流研討會論文集，民國87年。
41. 蔡佳璋、張西亞、黃國展、李先知、周朝宜、鄭守成、陳敏、沈澄宇，「科學計算應用之新寵：個人電腦叢集」，高速計算世界，VOL.7 NO.4，1999年12月。
42. 蔡惠峰，「水資源及環工與高速計算」，高速計算世界，VOL.2 NO.2，1994年6月。
43. 魏嘉平，「灰色規劃操作模式之研究」，國立中興大學土木工程研究所碩士論文，民國87年6月。
44. 蘇俊豪，「淺談高速計算環境」，高速計算世界，VOL.2 NO.3，1994年9月。
45. 蘇明道、徐忠寶、陳維英，「石門水操作規則之推導及評估」，台灣水利，第45卷第一期，民國86年3月。
46. Anibal Armijos ,Student Member, ASCE, Jeff R. Wright, and Mark H. Houck, Members, ASCE, “Bayesian Inferencing Applied To Real-Time Reservoir Operation”, Vol.116.No.3, pp.38-50, 1990.
47. Bithin Datta, Mark H. Houck, “A Stochastic Operation Model for Real-Time Reservoir Operation Using Uncertain Forecasts”, Water Resources Research, Vol. 20, No. 8, PP.1039-1047, 1984.
48. Can, E .K., and M. H. Houck, ”Real-time reservoir operations by goal programming”, J. of Water Resource Planning and Management, 110, pp.297-309, 1984.
49. East, V, and M. J. Hall, ”Water resource system optimization using genetic algorithms ”Hydroinformatics 94, Proc., 1st Int. Conf. on Hydroinformatics, Balkema,Rotterdam, The Netherlands, pp.225-231, 1994.
50. Emre K. Can, A. M. ASCE and Mark H. Houck, M. ASCE, “Problems With Modeling Real-Time Reservoir Operations”, Water Resource Research, October, 1985.
51. Fahmy, H.S. , J.P. King, M.W. Wentzel, and J. A. Seton, ”Economic optimization of river management using genetic algorithms ”, Paper No.943034, ASCE 1994, Int. Summer Meeting, Am. Soc. of Agricultural Engra, St. Joseph, Mich.
52. Goldberg, David E., ”Genetic Algorithms in Search, Optimization, and Machine Learning”, Addison-Wesley Publishing Company Inc., 1989.
53. J.J. Grefenstette, “Parallel Adaptive Algorithms for Function Optimization”, Technical report on CS-81-19 Nashville Vanderbilt University, Computer Science Department , 1981.
54. J.P. Cohoon, S.U.Heged, W.N. Martin and D.S. Richard, “Punctuated Equilibrate: a Parallel Genetic Algorithm”, in Proceeding of the second international conference on Genetic Algorithm. pp.148-154,1987.
55. Leonard Becker and William W-G.YEH, “Optimization of Real Time Operation of a Multiple-Reservoir System”, Water Resource Research, Vol.10, No.6, pp.1107-1112, 1974.
56. Mohamm, K. and Haralambos , V. V. , “Bayesian Stochastic Operation of Reservoir Operation Using Uncertain Forecasts”, Water Resources Research, Vol. 28, No. 5, pp.1221-1232, 1992.
57. Mark H.Houck, “Real-Time Daily Reservoir Operation by Mathematical Programing”, Water Source Research.Vol.18, No5, pp.1345-1351, October, 1982.
58. R. Gaioni, R. Davoli, “Communication Topologies for Parallel Genetic Algorithms : A Comparative Study on Cray T3D”, Department of Computer Science University of Bologna.
59. Robin Wardlaw and Mohd Sharif, ”Evaluation of genetic algorithms for optimal reservoir system operation ”, journal of water resources planning and management, ,pp.25-33, 1999.1.
60. Stedinger, J. R., B. F. Sule, and D. P. Loucks, “Stochastic Dynamic Programming Model for Reservoir Operation Optimization”, Water Resources Research, Vol. 20. No. 11, pp.1499-1505, 1984.
61. Trezos, T. and W. W-G. Yeh, "Use of Stochastic Dynamic Programming for Reservoir management", Water Resources Research, Vol. 1.23, No.6, pp.983-996, 1984.
62. William W-G. Yeh, A. M.ASCE, Leonard Becker, and Wen-Sen Chu “Real-Time Hourly Reservoir Operation”, journal of The Water Resource Planning And Management Division ,pp.187-199, September 1979.
63. Wunderlich, W.O., “Planned enhacement of water management method for the TVA reservoir system” , Proceedings of the National Workshop on Reservoir Systems Operation, University of Colorado, Boulder, Colorado,pp.336-360, August 13-17, 1979.
參考網站
http://www.mpi.nd.edu/lam
http://www.lam-mpi.org/
http://pccluster.nchc.gov.tw/
http://www.erc.msstate.edu/misc/mpi/