Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/5592
DC FieldValueLanguage
dc.contributor.advisor林明德zh_TW
dc.contributor.advisorLin Min Deren_US
dc.contributor.author林禹豪zh_TW
dc.contributor.authorHAO, Lin YUen_US
dc.date2003zh_TW
dc.date.accessioned2014-06-06T06:35:08Z-
dc.date.available2014-06-06T06:35:08Z-
dc.identifier.urihttp://hdl.handle.net/11455/5592-
dc.description.abstract環境中存在許多最佳化問題,如配水管網最佳化、地下水優選問題以及垃圾車最佳清運路線等,其中配水管網最佳化屬於離散變數且多維度複雜性問題,不易以傳統的優選演算法求解,因此本研究採取具跳脫區域解能力之禁忌搜尋法(Tabu Search, TS),並結合新興之平行運算技術,發展平行禁忌搜尋法(Parallel TS, PTS)將其應用於配水管網最佳化問題上,做為配水管網設計決策之參考。 本研究之PTS可分為鄰近解的平行化(Parallelize Neighborhood TS, PNTS)與多重禁忌搜尋法(Parallel multiple TS, PMTS)兩種平行方式,以達到加速求解與提昇TS的最佳化能力,進一步探討其平行效率。 研究結果顯示,TS由於移步方式與接受劣化解之機制,因此對於配水管網最佳化問題具有良好之求解能力。至於PTS方面, PNTS主要有加速求解的表現;而PMTS則不但可達到加速求解,更可提升TS求解能力。因此結合平行運算之TS於求解時間與最佳化能力上都有不錯之表現。zh_TW
dc.description.abstractOptimizations 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.en_US
dc.description.tableofcontents中文摘要 環境中存在許多最佳化問題,如配水管網最佳化、地下水優選問題以及垃圾車最佳清運路線等,其中配水管網最佳化屬於離散變數且多維度複雜性問題,不易以傳統的優選演算法求解,因此本研究採取具跳脫區域解能力之禁忌搜尋法(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-22zh_TW
dc.language.isoen_USzh_TW
dc.publisher環境工程學系zh_TW
dc.subjectoptimal Design of water network systemen_US
dc.subject配水管網最佳化zh_TW
dc.subjecttabu searchen_US
dc.subjectparallel computationen_US
dc.subjectparallel tabu searchen_US
dc.subject禁忌搜尋法zh_TW
dc.subject平行運算zh_TW
dc.subject平行禁忌搜尋法zh_TW
dc.title平行禁忌搜尋法於配水管網最佳化設計之應用zh_TW
dc.titleThe Application of Parallel Tabu Search on the Optimal Design of Water Network Systemen_US
dc.typeThesis and Dissertationzh_TW
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairetypeThesis and Dissertation-
item.cerifentitytypePublications-
item.fulltextno fulltext-
item.languageiso639-1en_US-
item.grantfulltextnone-
Appears in Collections:環境工程學系所
Show simple item record
 
TAIR Related Article

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.