Please use this identifier to cite or link to this item:
標題: 平行禁忌搜尋法於配水管網最佳化設計之應用
The Application of Parallel Tabu Search on the Optimal Design of Water Network System
作者: 林禹豪
關鍵字: optimal Design of water network system;配水管網最佳化;tabu search;parallel computation;parallel tabu search;禁忌搜尋法;平行運算;平行禁忌搜尋法
出版社: 環境工程學系
環境中存在許多最佳化問題,如配水管網最佳化、地下水優選問題以及垃圾車最佳清運路線等,其中配水管網最佳化屬於離散變數且多維度複雜性問題,不易以傳統的優選演算法求解,因此本研究採取具跳脫區域解能力之禁忌搜尋法(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.
Appears in Collections:環境工程學系所

Show full item record
TAIR Related Article

Google ScholarTM


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