(34.204.201.220) 您好!臺灣時間:2021/04/19 16:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林禹豪
研究生(外文):Lin YU HAO
論文名稱:平行禁忌搜尋法於配水管網最佳化設計之應用
論文名稱(外文):The Application of Parallel Tabu Search on the Optimal Design of Water Network System
指導教授:林明德林明德引用關係
指導教授(外文):Lin Min Der
學位類別:碩士
校院名稱:國立中興大學
系所名稱:環境工程學系
學門:工程學門
學類:環境工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
中文關鍵詞:配水管網最佳化禁忌搜尋法平行運算平行禁忌搜尋法
外文關鍵詞:optimal Design of water network systemtabu searchparallel computationparallel tabu search
相關次數:
  • 被引用被引用:15
  • 點閱點閱:446
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:56
  • 收藏至我的研究室書目清單書目收藏:3
環境中存在許多最佳化問題,如配水管網最佳化、地下水優選問題以及垃圾車最佳清運路線等,其中配水管網最佳化屬於離散變數且多維度複雜性問題,不易以傳統的優選演算法求解,因此本研究採取具跳脫區域解能力之禁忌搜尋法(Tabu Search, TS),並結合新興之平行運算技術,發展平行禁忌搜尋法(Parallel TS, PTS)將其應用於配水管網最佳化問題上,做為配水管網設計決策之參考。
本研究之PTS可分為鄰近解的平行化(Parallelize Neighborhood TS, PNTS)與多重禁忌搜尋法(Parallel multiple TS, PMTS)兩種平行方式,以達到加速求解與提昇TS的最佳化能力,進一步探討其平行效率。
研究結果顯示,TS由於移步方式與接受劣化解之機制,因此對於配水管網最佳化問題具有良好之求解能力。至於PTS方面, PNTS主要有加速求解的表現;而PMTS則不但可達到加速求解,更可提升TS求解能力。因此結合平行運算之TS於求解時間與最佳化能力上都有不錯之表現。
Optimizations of water distribution systems often need to deal with enormous discrete variables and highly nonlinear computations. It has been shown that classical optimization algorithms are unable to solve these problems successfully. Therefore, this research utilizes tabu search (TS), which belongs to the heuristic algorithm category, to find the optimal design of water distribution systems and evaluates its optimization performance. Furthermore, this research also introduces the parallel techniques to develop parallel versions of tabu search (PTS) to solve the problems more efficiently and effectively. There are two kinds of PTS developed in this research, one is so called “parallel-neighborhood TS (PNTS)” and the other is “parallel multiple TS (PMTS)”. The performance of the PTSs are also evaluated and compared with sequential TS and other algorithms.
The results show that TS can successfully and very efficiently find the optimal designs of the water distribution systems. When incorporated with parallel techniques, PNTS can significantly reduce the computation time without degrading the optimization ability. On the other hand, PMTS not only speeds up the computations but also improves the optimization performance of TS. To sum up, TS incorporates parallel computing has excellent performance for solving optimal design problems of water distribution systems.
中文摘要
環境中存在許多最佳化問題,如配水管網最佳化、地下水優選問題以及垃圾車最佳清運路線等,其中配水管網最佳化屬於離散變數且多維度複雜性問題,不易以傳統的優選演算法求解,因此本研究採取具跳脫區域解能力之禁忌搜尋法(Tabu Search, TS),並結合新興之平行運算技術,發展平行禁忌搜尋法(Parallel TS, PTS)將其應用於配水管網最佳化問題上,做為配水管網設計決策之參考。
本研究之PTS可分為鄰近解的平行化(Parallelize Neighborhood TS, PNTS)與多重禁忌搜尋法(Parallel multiple TS, PMTS)兩種平行方式,以達到加速求解與提昇TS的最佳化能力,進一步探討其平行效率。
研究結果顯示,TS由於移步方式與接受劣化解之機制,因此對於配水管網最佳化問題具有良好之求解能力。至於PTS方面, PNTS主要有加速求解的表現;而PMTS則不但可達到加速求解,更可提升TS求解能力。因此結合平行運算之TS於求解時間與最佳化能力上都有不錯之表現。
關鍵字:配水管網最佳化、禁忌搜尋法、平行運算、平行禁忌搜尋法
Abstract
Optimizations of water distribution systems often need to deal with enormous discrete variables and highly nonlinear computations. It has been shown that classical optimization algorithms are unable to solve these problems successfully. Therefore, this research utilizes tabu search (TS), which belongs to the heuristic algorithm category, to find the optimal design of water distribution systems and evaluates its optimization performance. Furthermore, this research also introduces the parallel techniques to develop parallel versions of tabu search (PTS) to solve the problems more efficiently and effectively. There are two kinds of PTS developed in this research, one is so called “parallel-neighborhood TS (PNTS)” and the other is “parallel multiple TS (PMTS)”. The performance of the PTSs are also evaluated and compared with sequential TS and other algorithms.
The results show that TS can successfully and very efficiently find the optimal designs of the water distribution systems. When incorporated with parallel techniques, PNTS can significantly reduce the computation time without degrading the optimization ability. On the other hand, PMTS not only speeds up the computations but also improves the optimization performance of TS. To sum up, TS incorporates parallel computing has excellent performance for solving optimal design problems of water distribution systems.
key word:optimal design of water network system、tabu search、parallel computation、parallel tabu search
總目錄
中文摘要 i
英文摘要…………………………………………………………………ii
總目錄 iii
表目錄 v
圖目錄 vi
第一章 前言…………………………………………………………..1-1
1-1 研究動機………………………………………………………1-1
1-2 研究目的………………………………………………………1-1
1-3 研究項目………………………………………………………1-2
1-4 本文架構………………………………………………………1-3
第二章 文獻回顧……………………………………………………...2-1
2-1 配水管網最佳化………………………………………………2-1
2-2 最佳化方法.……………………………………………….…..2-4
2-2-1 傳統演算法………………………………………….…2-4
2-2-2 啟發式演算法……………………………………….…2-4
2-3 禁忌搜尋法及其平行化之發展………………………………2-7
2-3-1 禁忌搜尋法之文獻回顧……………………………...….2-7
2-3-2 平行禁忌搜尋法之文獻回顧………………….…….…2-12
2-4 文獻總結及研究方向………………….……………………2-20
第三章 研究方法………………….…………………………………3-1
3-1配水管網模式………………….………………………….……3-1
3-1-1水力分析模組………………….…………………………3-2
3-1-2配水管網研究案例………………….……………………3-5
3-1-2-1配水管網研究案例1……..…………….…….……3-5
3-1-2-2配水管網研究案例2………………….……...……3-8
3-1-2-3配水管網研究案例3……….…….…….………...3-10
3-2禁忌搜尋法………………….………………………...………3-15
3-2-1背景………………….…………………………………..3-15
3-2-2 TS之基本概念及演算步驟………………….…………3-16
3-2-3本研究 TS之構成要素………………….…………...…3-17
3-3平行禁忌搜尋法………………………………………………3-25
3-3-1平行禁忌搜尋法之PNTS………………….……………3-26
3-3-2 平行禁忌搜尋法之PMTS………………….………..…3-28
第四章 結果與討論 ……………………………………...……………4-1
4-1 實驗設計………………………………………………………4-1
4-1-1 移步方式之設計…………………………………………4-1
4-1-2 TS及PTS之參數測試…………………………………4-2
4-1-3 限制式相關說明…………………………………………4-4
4-1-4 TS最佳化能力之評估…………………………………4-5
4-1-5 平行效率之評估…………………………………………4-6
4-2 禁忌搜尋法之應用結果………………………………………4-9
4-2-1 TS於案例1之應用結果………………………………4-9
4-2-2 TS於案例2之應用結果………………………………4-12
4-2-3 TS於案例3之應用結果………………………………4-14
4-3 平行禁忌搜尋法之應用結果…………………………..…4-17
4-3-1 PTS於案例1之應用結果……………………………4-17
4-3-2 PTS於案例2之應用結果……………………………4-20
4-3-3 PTS於案例3之應用結果……………………………4-22
4-4 結果與討論……………………………..……………………4-24
第五章 結論與建議 ………………………………………………...…5-1
5-1 結論……………………………………………………………5-1
5-2 建議 ……………………………………………………………5-2
參考文獻….……………………………………………………………6-1
表目錄
表2-1 不同形式的平行禁忌搜尋法 2-18
表3-1 案例1各管線之相關資料 3-7
表3-2 案例1可用商用管徑之資料 3-7
表3-3 案例1各節點之相關資料 3-8
表3-4 案例2各管線之相關資料 3-9
表3-5 案例2各節點之相關資料 3-10
表3-6 案例2可用商用管徑之資料 3-10
表3-7 案例3可用商用管徑之資料 3-12
表3-8 案例3各管線之相關資料 3-13
表3-9 案例3各節點之相關資料 3-14
表3-10 TS之參數設定 3-23
表4-1 案例1之相關參數設定 4-3
表4-2 案例2之相關參數設定 4-3
表4-3 案例3之相關參數設定 4-4
表4-4 Cunha and Sousa(1999)最佳設計結果 4-5
表4-5 本研究電腦叢集之相關軟體 4-8
表4-6 本研究電腦叢集之相關硬體 4-8
表4-7 案例1考慮水頭限制下最佳化之各管線資料 4-9
表4-8 案例1考慮水頭限制下最佳化之各節點資料 4-9
表4-9 案例1 TS與相關文獻結果之比較 4-10
表4-10 案例1考慮水頭與流速限制下最佳設計之各管線資料 4-10
表4-11 案例1考慮水頭與流速限制下最佳設計之各節點資料 4-11
表4-12 案例2相關文獻最佳化之設計成本 4-12
表4-13 案例2考慮水頭與流速限制下最佳設計之各管線資料 4-12
表4-14 案例2考慮水頭與流速限制下最佳設計之各節點資料 4-13
表4-15 案例3考慮水頭與流速限制下最佳化之各管線資料 4-15
表4-16 案例3考慮水頭與流速限制下最佳化之各節點資料 4-16
表4-17 案例1 PMTS與TS求解能力之比較 4-19
表4-18 案例2 PMTS與TS求解能力之比較 4-21
表4-19 案例3 PMTS與TS求解能力之比較 4-23
圖目錄
圖2-1 SMP電腦系統之架構 2-14
圖2-2 MPP電腦系統之架構 2-15
圖2-3 PC Cluster電腦系統架構 2-15
圖3-1 Hardy Cross 流程圖……………………………………….....3-4
圖3-2 案例1管網系統配置圖………………………………………..3-6
圖3-3 案例2管網系統配置圖………………………………………..3-8
圖3-4 案例3管網系統配置圖………………...…………………….3-11
圖3-5 TS流程圖………………………………………………..…..3-24
圖3-6 PNTS流程圖………………………………………….……..3-27
圖3-7 PMTS流程圖………………………………………………..3-28
圖4-1 案例1 PNTS求解結果……………………………………….4-18
圖4-2 案例1 PNTS之加速與效率圖…………………………..…..4-18
圖4-3 案例2 PNTS求解結果…………………………………...…..4-20
圖4-4 案例2 PNTS之加速與效率圖…………………………...…..4-20
圖4-5 案例3 PNTS求解結果………………………………..……..4-22
圖4-6 案例3 PNTS之加速與效率圖……………………..………..4-22
參考文獻
1. Alperovits, E., and U. Shamir, “Design of optimal water distribution systems,” 1977, Water Resources Ressources, ASCE, Vol. 13, No. 6, pp. 885-900.
2. Bachelet, V., P. Preux, and E-G. Talbi, “Parallel Hybrid Meta-Heuristics: Application to the Quadratic Assignment Problem,” 1996, http://www.citeseer.nj.nce.com/.
3. Badeau, P., F. Guertin, M. Gendreau, J.Y. Potvin, and E. Taillard, “A parallel tabu search heuristic for the vehicle routing problem with time windows,” 1997, Transpn Res.-C, Vol 5, No. 2, pp. 109-122.
4. Blesa, M., Ll. Hernandez, and F. Xhafa, “Parallel Skeletons for Tabu Search Method Based on Search Strategies and Neighborhood Partition,” 2002, http://citeseer.nj.nec.com/501831.html.
5. Blesa, M.J., L. Hernandez, and F. Xhafa, “Parallel Skeletons for Tabu Search Method,” 2001, Proceedings of International Conference on Parallel and Distributed System, ICPADS’01, IEEE.
6. Bock, S., and O. Rosenberg, “A new parallel breadth tabu search technique for solving production planning problem,” 2000, Operation Research, Vol. 7, pp. 625-635.
7. Chelouah, R., and P. Siarry, “Tabu search applied to global optimization,” 2000, European Journal of Operational Research 123, 256-270.
8. Crainic, T.G., M. Toulouse, and M. Gendreau, “Toward a taxonomy of parallel tabu search heuristic,” 1997, INFORMS Journal on Computing, Vol. 9, No. 1, pp. 61-79.
9. Cunha, M.D.C., and J. Sousa, ”Water distribution network design optimization simulation annealing approach,” 1999, J. Water Resour. Plg. And Mgt., Vol. 125, No. 4, pp. 215-221.
10. Dermuren, A. D., and F. J. K. Ideriah, “Pipe Network Analysis by Partial Pivoting Method,” 1986, Journal of Hydraulic Division, ASCE, Vol. 112, No. 5, pp. 327-334.
11. Featherstone, R. E., and K. K. EI-Jumaily, “Optimal diameter selection for pipe network,” 1983, Journal of Hydraulics, ASCE, Vol. 109, No. 2.
12. Gendreau, M., L. Gilbert, and S. Frederic, “A dynamic model and parallel tabu search heuristic for real-time ambulance relocation,” 2001, Parallel Computer 24, 2009-2019.
13. Glover, F., and M. Laguna, Tabu Search, Kluwer Academic Publishers, 1999.
14. Glover, F., Frequently Asked Questionson Tabu search, http://www.tabusearch.net/tabu search/tabu fab.asp.
15. Glover, F., Tabu Search Glossary, http://www.tabusearch.net/tabu .
16. Gupta, I., A. Gupta, and P. Khanna, “Genetic algorithm for optimization of water distribution systems,” 1999, Environmental Modeling & Software, Vol. 14, pp. 437-446.
17. Higgins, A.J., “A dynmic tabu search for large-scale generalized assignment problems,” 2001, Computers & Operations Research Vol. 28, pp. 1039-1048.
18. Kolahan, F., and M. Liang, “A tabu search approach to optimization of drilling operations,” 1996, Computers ind. Engng Vol. 31, No.1/2, pp. 371-374.
19. Kovacevic-Vujcic, V.V., and M.M. Cangalovic, “TABU Search Methology in Global Optimization,” 1999, Computers and Mathematics with Applications 37, 125-133. http://www-di.inf.puc-rio.br/~celso/artigos/environments.pdf
20. Lee, I., “Aritificial intelligence search methods for multi-machine two-stage scheduling with due date penalty, inventory, and machining cost,” 2001, Computers & Operations Research Vol. 28, pp. 835-852.
21. Lin, Y.C. and H.D. Yeh, “The Application of Optimization Methods: Analyzing the Pipe Network System,” 2002, 第12屆環境規劃與管理研討會論文集。
22. Loganathan, G.V., J.J. Greene, and T.J. Ahn, “Design heuristic for globally minimum cost water-distribution systems,” 1995, Journal of water resources planning and management, ASCE, ASCE Vol. 121 No. 2, pp. 182-192.
23. Mamtawy, A.H., Y.L. Abdel-Magid, and S.Z. Selim, “A new genetic-based tabu search algorithm for unit commitment problem,” 1999, Electric Power System Research Vol 49, pp. 71-78.
24. Martins, S.D.L., C.C. Riberiro, and N. Rodriguez, “Parallel Computing Environments,” http://www-di.inf.puc-rio.br/~celso/artigos/environments.pdf .
25. Morgan, D.R., and I.C. Goulter, “Optimal Urban Water Distribution Design,” 1985, Water Resources Research, ASCE, Vol. 21, No. 5, pp. 642-652.
26. Niar, S., and A. Freville, “A Parallel Tabu Search Algorithm For The 0-1 Multidimensional Knapsack Problem,” 2000, http://ipdps.eece.unm.edu/1997/s14/218.pdf.
27. Porto, S.C.S., J.P.F.W. Kitajima, and C.C. Riberiro, “Performance evaluation of a parallel tabu search task scheduling algorithm,” 2000, Parallel Computer 26, 73-90.
28. Salhi, S., “Defining tabu list size and aspiration criterion within tabu search methods,” 2002, Computer Ops Res. Vol. 29, pp. 67-86.
29. Simpson, R.A., G.C. Dandy, and J.M. Laurence, “Genetic algorithms compared to other techniques for pipe optimization,” 1994, J. Water Resour. Plg. And Mgt., Vol. 120, No. 4, pp. 423-443.
30. Tablbi, E.G., Z. Hafidi, and J-M. Geib, “A parallel adaptive tabu search approach,” 1998, Parallel Computer 24,2003-2019.
31. Ting, C.K., C. Lee, and S.T. Li, “A Novel Hybrid Optimization Algorithm Based on Genetic Algorithm and Tabu Search,” ICS2000, December 6-8, 2000, Taiwan.
32. Tsubakitani, S., and R.E. James, “Optimizing tabu list size for the travel salesman problem,” 1997, Computer Ops Res. Vol. 25, No. 2, pp. 91-97.
33. 朱健行,「自來水管網水利分析與參數優選之探討」,自來水會刊第五十二期。
34. 吳泰熙、張欽智,「以禁忌搜尋法則求解推銷員旅行問題」,大葉學報,6,87-99 (1997)。
35. 吳泰熙、張欽智,「應用禁忌搜尋法則於多目標推銷員旅行問題之求解」,大葉學報,15,589-603 (1998)。
36. 吳瑞賢、林永敏,「自來水管網之最佳化設計及擴建分析」,1995,自來水會刊第五十五期。頁42-55
37. 李宇欣、陳立文,「鄰近搜尋法於大型問題之求解績效:以TSP為例」,中華民國第五屆運輸網路研討會, 2000。
38. 林師檀,「禁忌搜尋法與遺傳演算法混合模式在地下水復育問題之應用」,國立中興大學環境工程學系,碩士論文,2002。
39. 林偉田,「配水管網之佳化設計」,國立成功大學環境工程學系,碩士論文,1984。
40. 林睿暘,「改進之平行禁忌搜尋法」,國立清華大學工業工程學系,碩士論文,2001。
41. 林碧亮,「自來水管網系統設計最佳化之發展與探討」,國立中央大學環境工程學系,博士論文,1999。
42. 洪志銘,「管網系統之最佳化設計」,國立中興大學土木工程學系,碩士論文,2000。
43. 國家高速電腦中心編,「MPI平行計算程式設計」,2001。
44. 國家高速電腦中心編,「PC Cluster 整體性課程研習營」,2001。
45. 陳俊麟,「高速計算環境」,國家高速電腦中心,2001。
46. 陳榮藏,「配水管網分析方法之探討及應用」,自來水會刊第十六期,1997。
47. 曾耀寰,「以Linux進行電腦叢集計算」,台北市:碩科技文化,2001。
48. 童慶斌,「啟發式演算法與水資源管理」,上課講義,2001。(http://sdl.ae.ntu.edu.tw/oldindex.htm)
49. 童慶斌、周俊安,「禁忌搜尋法應用於決定最佳地下水參數分區」,2000,農業工程研討會論文集。
50. 童慶斌、周哲正,「禁忌搜尋法在地下水參數分區之應用」,第二屆環境系統分析研討會論文集,pp. 211-217,1999。
51. 楊朝棟,「電腦之平行處理技術發展探討」,電腦科技56期,2001。
52. 鄭守成,「漫談平行電腦與平行計算」,國家高速電腦中心,2001a。
53. 鄭守成,「漫談程式的向量化與平行化」,國家高速電腦中心,2001b。
54. 嚴浩哲,「平行遺傳演算法以電腦叢集為工具應用於地下水優選問題之探討」,國立中興大學環境工程學系,碩士論文,2002。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔