摘 要

污水下水道管網系統是一套收集生活污水的密閉管路系統，具備獨立排除污水、改善居住環境品質、防止污染公共水域水質以及進行水處理再循環利用的多重功_能。重視環境衛生的世界先進國家都非常重視下水道建設，視之為都市發展重要的基礎建設。
龐大的建設經費是導致臺灣地區污水下水道普及率增加緩慢的主因之一，為求以更經濟之成本加速提昇普及率，本研究將重心聚焦在影響系統建造成本最大的管徑組合部分，希望呈現合乎水理模式限制之最低成本管徑組合的管網系統。利用MATLAB® 程式語言建立模擬管渠水力學之數學模式，計算各分管段在不同管徑組合下的水理資料，透過基因演算法的既定程序，一代接著一代運算，最後尋得令人信任的最低建設成本，具體可行的管徑組合方案。
本研究之基因演算法與傳統基因演算法的差異是把編碼方式改為格雷碼，增加菁英保留策略，而且採用競爭挑選法、均等交配與倒置突變運算元，以改良傳統基因演算法搜尋時間過於冗長的缺點。與研究案例設計規劃之成本相較，本研究尋得之建造成本約節省5.2 %，效果顯著。本研究所建立之污水下水道管網系統最低成本之管徑組合最佳化模式，亦可提供日後從事相關規劃的工作人員參考，兼具實務考量，有效地節省設計時間和人力。

ABSTRACT

The sewer network system is one closed pipeline system which collects daily sewage. The system is built for the multi-purposes of: independent drainage of sewer, quality improvement of residential environment, prevention of public water pollution, and recycling and reuse of sewer. In most advanced countries, sewer network system is regarded as crucial and as the backbone construction of city development.
Mess amount of dollars is the main cause that leads to slow increase in prevalence of sewer drainage in Taiwan area. To step up the prevalence of sewer drainage with a more cost economic way, the research focuses on the combinations of pipeline diameters which predominately affect the cost of system construction. In this way, it is expected to present the pipeline network system with pipeline combinations that meets the qualification of hydraulic modules and that has the least cost. Firstly, a mathematical model for modeling pipeline hydraulics is written using MATLAB. Secondly, the hydraulic data for subsection of pipelines under different combinations are calculated using genetic algorism, one generation after another,. Finally, a reliable scheme that has the least construction cost and is practically feasible is derived.
Different from the traditional genetic algorism, the research use genetic algorism with gray code and elitism reserve maneuver, In addition, for factors, tournament selection, uniform crossover, and inverse mutation operators, are utilized in order to reduce the lengthy search time which often occurs using in the traditional genetic algorism. When compared with the design plan of the reference report, the estimated construction cost is 5.2% lower. The optimization of the research provides an practical aid for designers of sewer network planning, saving effectively both time and manpower.

目 錄

中文摘要................................................................i
ABSTRACT............................................................. ii
誌謝辭................................................................. iii
目錄................................................................... iv
表目錄.................................................................vii
圖目錄................................................................. ix

第一章 緒論............................................................1
1.1 前言....................................................1
1.2 研究動機....................................................................1
1.3 研究方法與目的..............................................................3
第二章 文獻探討.........................................................4
2.1 基因演算法簡介..............................................................4
2.1.1 基因演算法之發展...............................................4
2.1.2 基本理論.......................................................6
2.1.3 運算步驟.......................................................8
I. 產生初始族群....................................................8
II. 解碼.................................................................... 10
III. 計算適應度............................................................ 11
IV. 複製......................................................... 12
1. 挑選........................................................ 13
（1）輪盤法................................................... 14
（2）競爭法................................................... 16
（3）序位法................................................... 17
（4）世代隔閡................................................. 18
2. 交配........................................................ 18
（1）單點交配法............................................... 20
（2）雙點交配法............................................... 21
（3）倒置交配法............................................... 21
3. 突變........................................................ 23
V. 設定停止運算條件..............................................26
2.2 尋優模式.................................................................. 28
2.3 演算法特性....................................................... 30
2.4 近來發展概況..................................................... 32
第三章 污水下水道管網系統管徑組合最佳化模式之建立......................34
3.1 污水下水道管徑組合最佳化模式..................................... 34
3.1.1 污水下水道系統簡介............................................35
3.1.2 模式之基本假設................................................36
3.1.3 最佳化模式之推導..............................................37
I. 取得下水道配置資料.............................................38
II. 重新配置下水道管網與編號..............................................39
III. 水理模式計算.......................................................... 41
1. 水理設計準則................................................ 41
2. 水理分析.................................................... 43
IV. 短管推進施工法簡介........................................... 48
V. 成本函數......................................................49
3.1.4 程式撰寫與演算軟體............................................54
3.2 基因演算法之改良................................................. 55
3.2.1 格雷碼編碼....................................................55
3.2.2 解碼計算適應度................................................59
3.2.3 菁英策略......................................................59
3.2.4 競爭式挑選法..................................................61
3.2.5 均等交配......................................................63
3.2.6 倒置突變......................................................64
3.2.7 停止運算條件..................................................65
第四章 結果與討論......................................................66
4.1 基因演算法參數之選定..................................................... 66
4.1.1 世代數G之選定................................................66
4.1.2 族群大小N之選定..............................................68
4.1.3 交配率Pc之選定............................................... 71
4.1.4 突變率Pm之選定...............................................73
4.1.5 最佳參數組合之選定............................................75
4.1.6 運算元組合之搜尋效率比較......................................76
4.1.7 菁英策略之探討................................................81
4.2 案例研究......................................................... 83
4.2.1 主幹管Bjb之配置.............................................. 83
4.2.2 Bj分管段之配置................................................91
4.2.3 Bja分管段之配置...............................................94
4.2.4 Bjaa分管段之配置..............................................98
4.2.5 Bjba分管段之配置.............................................101
4.2.6 Bjbb分管段之配置.............................................104
4.2.7 Bjc分管段之配置..............................................107
4.2.8 Bjd分管段之配置..............................................110
4.2.9 Bjda分管段之配置.............................................113
4.2.10 Bje分管段之配置.............................................116
4.2.11 Bjf分管段之配置.............................................119
4.3 管網系統最佳化設計.............................................. 121
4.4 結果比較........................................................ 126
第五章 結論與建議.....................................................127
參考文獻..............................................................129
簡歷..................................................................134

參考文獻

1. Chakraborty, U. K.(1995). A branching process model for genetic algorithms. Information Processing Letters, 56(1):281-292.

2. Dandy, G. C., Simpson, A. R., and Murphy, L. J.(1996). An improved genetic algorithm for pipe network optimization. Water Resources Research, 32(2):449-458.

3. Deb, K.(2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering. 186(2-4):311-338.

4. Elazouni, A. M. and Metwally, F. G.(2005). Finance-based scheduling: tool to maximize project profit using improved genetic algorithms. Journal of Construction Engineering and Management. 131(4):400-412.

5. Espinoza, F. P., Minsker, B. S., and Goldberg, D. E.(2005). Adaptive hybrid genetic algorithm for groundwater remediation design. Journal of Water Resources Planning and Management, 131(1):14-24.

6. Hasancebi, O. and Erbatur, F.(2000). Evaluation of crossover techniques in genetic algorithm based optimum structural design. Computers and Structures. 78(1-3):435-448.

7. Hayes, B.(2001). How to count. American Scientist. 89(2):110-114.

8. Jalal, M. M., Rodin, S. I., Mariño, M. A., and Hon, M.(2004). Use of genetic algorithm in optimization of irrigation pumping stations. Journal of Irrigation and Drainage Engineering, 130(5):357-365.

9. Lee, K. Y., Han, S. N., and Roh, M. I.(2003). An improved genetic algorithm for facility layout problems having inner structure walls and passages. Computer & Operation Research, 30(1):117-138.

10. Lee, K. Y., Roh, M. I., and Jeong, H. S.(2005). An improved genetic algorithm for multi-floor facility layout problems having inner structure walls and passages. Computer & Operation Research, 32(4):879-899.

11. Liang, L. Y., Thompson, R. G., and Young, D. M.(2004). Optimising the design of sewer networks using genetic algorithms and tabu search. Engineering, Construction and Architectural Management, ABI/INFORM Global, 11(2):101-112.

12. Lobo, F. G. and Goldberg, D. E.(2004), “The parameter-less genetic algorithm in practice.” Information Sciences. 167(1-4):217-232.

13. McCall, J.(2005). Genetic algorithms for modelling and optimisation. Journal of Computation and Applied Mathematics, 184(1):205-222.

14. Mitchell, M.(1998). Book review L. D. Davis, Handbook of Genetic algorithms. Artificial Intelligence, 100:325-330.

15. Mitra, K. and Gopinath, R.(2004). Multiobjective optimization of an industrial grinding operation using elitist nondominated sorting genetic algorithm. Chemical Engineering Science, 59(2):358-396.

16. Ng, A. W. M. and Perera, B. J. C.(2003). Selection of genetic algorithm operators for river water quality model calibration. Engineering Applications of Artificial Intelligence. 16(5-6):529-541.

17. Park, J. H., Hwang, J. H., Lee, C. S., and Hwang, W.(2001). Stacking sequence design of composite laminates for maximum strength using genetic algorithms. Composite Structures. 52(2):217-231.

18. Rao, M. A., Srinivas, J., and Murthy, B. S. N.(2004). Damage detection in vibrating bodies using genetic algorithms. Computers & Structures, 82(11-12):963-968.

19. Rauch, W. and Harremoës, P.(1999). Genetic algorithms in real time control applied to minimize transient pollution from urban wastewater systems. Wat. Res.. 33(5):1265-1277.

20. Schmitt, L. M.(2001). Fundamental Study Theory of genetic algorithms. Theoretical Computer Science. 259(1-2):1-61.

21. Silva, C. M. and Biscaia, J. E. C.(2003). Genetic algorithm development for multi-objective optimization of batch free-radical polymerization reactors. Computers and Chemical Engineering. 27(8-9):1329-1344.

22. Savic, D. A. and Walters, G. A.(1997). Genetic Algorithms for least-cost design of water distribution networks. Journal of Water Resources Planning and Management. 123(2):67-77.

23. Simpson, A. R., Dandy, G. C., and Murphy, L. J.(1994). Genetic algorithms compared to other techniques for pipe optimization. Journal of Water Resource Planning and Management, ASCE, 120(4):423-443.

24. Wardlaw, R. and Sharif, M.(1999). Evaluation of genetic algorithms for optimal reservoir system operation. Journal of Water Resources Planning and Management. 125(1):25-33.

25. Whitley, D.(2001). An overview of evolutionary algorithms: practical issues and common pitfalls. Information and Software Technology. 43(14):817-831.

26. Yagi, S. and Shiba, S.(1999). Application of genetic algorithms and fuzzy control to a combined sewer pumping station. Wat. Sci. Tech. 39(9):217-224.

27. Yang, X. H., Yang, Z. F., and Shen, Z. Y.(2004). A hybrid accelerated genetic algorithm for system optimization. Environmental Informatics Archives. 2:275-288.

28. Zhang, H. and Ishikawa, M.(2004). A solution to combinatorial optimization with time-varying parameters by a hybrid genetic algorithm. International Congress Series 1269, Complete:149-152.

29、Liang, S. J.T.（1998）. A review of genetic algorithms. 國立虎尾技術學院學報第1期，pp.107-140。

30、下水道法，中華民國七十三年十二月二十一日總統令公布。中華民國八十九年十二月二十日華總一義字第八九○○三○一○八○號令公布修正。

31、下水道管渠工程設計指南，中國土木水利工程學會環境工程委員會，1984。

32、方曉嵐（1998），人工智慧技術—遺傳演算法，技術與訓練第23卷2期，pp.149-155。

33、王日昌，基因演算法在多目標組合最佳化問題之研究—以旅行推銷員問題為例，國立交通大學運輸研究所博士論文，1997。

34、內政部營建署，污水下水道規劃講習班，2001。

35、內政部營建署，污水下水道規劃講習班第一、二冊，2001。

36、何佳祥，應用基因演算法優化類神經網路於污水廠興建成本預估之研究，國立雲林科技大學環境與安全衛生工程系研究所碩士論文，2003。

37、何智超，遺傳演算法應用於雨水下水道最佳化設計，中華大學土木工程學系碩士論文，2001。

38、何承嶧，台灣地區公共下水道污水處理廠成本函數之分析研究，國立中興大學環境工程研究所碩士論文，2001。

39、林常平（1995），基因演算法，自動化工程133期，pp.170-175。

40、林基興（1997），遺傳演算法，科學月刊第28卷4期，pp.323-326。

41、林柏齊，運用基因演算法於週期性廢棄物收集路線之規劃，國立成奶j學資源工程研究所碩士論文，1997。

42、林碧亮，污水下水道最佳系統配置與最佳水力設計模式之建立，淡江大學水資源及環境工程研究所碩士論文，1990。

43、周鵬程，遺傳演算法原理與應用—活用Matlab，2002，二版，臺北市，全華科技圖書股份有限公司。

44、范純一，下水道工程，1989，初版，臺北市，中國土木水利工程學會。

45、胡振中，都市污水下水道採短管推進工法影響成本因素之研究，國立中央大學土木工程學系碩士論文，2001。

46、徐俊能，以遺傳基因演算法則解決多目標考量的推銷員旅行問題之研究，大葉大學事業經營研究所碩士論文，1993。

47、張乃斌，環境系統分析原理（上冊），2002，初版，臺北市，茂昌圖書有限公司。

48、張益誠等，電腦在環境工程與管理上之應用，2002，初版，臺北市，文魁資訊股份有限公司。

49、張智星，MATLAB程式設計入門篇，2004，初版，新竹市，清蔚科技股份有限公司。

50、張弘岳，污水下水道管網系統最佳化水理設計之研究，國立中興大學環境工程學系碩士論文，2002。

51、陳禹成，污水下水道分支管工程興建模式及其評估模式之研究，國立中央大學土木工程學系碩士論文，2001。

52、郭信川、王鴻鈞（1998），遺傳演算法在最佳化設計問題之應用，中國造船暨輪機工程學刊第17卷第1期，pp.39-48。

53、黃水德，台灣地區污水下水道短管推進施工（含材料）技術轉移之研究，國立高雄第一科技大學營建工程系碩士論文，2001。

54、黃天生、宋顯榮、王博文（2003），污水下水道工程施工與管理，中興工程第81期，pp.107-123。

55、廖述良、翁煥廷、林碧亮、宋淳伍（2001），都市污水下水道管網系統規劃設計模式之建構，國立中央大學環境工程學刊第七期，pp.39-49。

56、劉興榕（2002），臺北市污水下水道建設之執行與其對策，環保月刊第2卷12期，pp.96-113。

57、歐陽嶠暉，下水道工程學，2001，三版，臺北市，長松文化公司。

58、鍾志成（2003），基因演算法之應用，中興工程第80期，pp.87-106。

59、蘇木春、張孝德，機器學習：類神經網路、模糊系統以及基因演算法則，1999，二版，臺北市，全華科技圖書股份有限公司。

60、薛富南，基因演算法應用於污水下水道管網系統設計最佳化之研究，立德管理學院資源與環境研究所碩士論文，2004。

61、薛富南、翁建華、吳春生（2004），基因演算法應用於污水下水道管網系統設計最佳化之研究，第三屆資源與環境管理學術研討會，pp.55-69。

62、臺灣營建研究院，道路及下水道施工技術，1999。