(3.235.108.188) 您好!臺灣時間:2021/02/27 03:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林師檀
研究生(外文):Shin-Tien Lin
論文名稱:禁忌搜尋法與遺傳演算法混合模式在地下水復育優選問題之應用
論文名稱(外文):The Applications of Tabu Search - Genetic Algorithms Hybrid Model on the Optimization of Groundwater Remediation Problems
指導教授:林明德林明德引用關係
學位類別:碩士
校院名稱:國立中興大學
系所名稱:環境工程學系
學門:工程學門
學類:環境工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:禁忌搜尋法遺傳演算法混合模式地下水復育優選問題
外文關鍵詞:tabu searchgenetic algorithmshybrid modelgroundwater optimization problem
相關次數:
  • 被引用被引用:29
  • 點閱點閱:1041
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:240
  • 收藏至我的研究室書目清單書目收藏:0
地下水復育優選問題為複雜、困難之最佳化問題,以往大多利用傳統之優選技術如非線性規劃法來求解,然此類問題之目標函數及限制式具有非線性及非凸之特性,傳統方法在求解過程中常因其特性,而造成搜尋陷入局部解中難以跳脫。
近十多年來發展出具有強健之尋優能力的啟發式優選技術如遺傳演算法、禁忌搜尋法、模擬退火法等,強調具有跳脫局部解及接受劣化解(inferior solution)之優點,本研究係以具有記憶功能之禁忌搜尋法來求解地下水復育優選問題;並再發展以遺傳演算法與禁忌搜尋法結合之混合模式(GA-TS法)來解決地下水復育系統之優選問題,混合模式擷取了兩個演算法之優點,先以遺傳演算法作前處理器,對問題之解空間作整體性之初步搜尋,再藉由後處理器--禁忌搜尋法之精煉的解題技巧來獲得更高品質的解。
本研究以一虛擬、拘限、均質之地下水復育案例為例,藉由禁忌搜尋法、混合模式針對不同的復育方案予以求解,以了解各優選技術之求解效率,進而提出最具效率之優選技術,供日後地下水之研究者選擇處理技術之參考。
研究結果發現,兼具遺傳演算法與禁忌搜尋法之優點的混合模式,無論是求解何種復育方案,在解的品質與運算時間上,其結果明顯地都較禁忌搜尋法較佳。
The optimization problems of groundwater remediation system have the feature that the objective function and constraints may be noncovex as well as nonlinear. Classical gradient-based algorithms including nonlinear programming (NLP) and descent methods have not been successful in solving such kind of problems. In general, these methods converge to a local optimum easily.
Heuristic algorithms have becmoe the most widely used tool for solving many optimization problems. These methods, e.g. genetic algorithms (GA), simulated annealing (SA) and tabu search (TS), emphasize powerful and robust optimization procedures. This research selects tabu search for solving groundwater remediation optimization problems. A new hybrid model which combines GA and TS is also developed. In the hybrid model, GA is served as a coarse-grained optimizer, then TS served as a fine-grained optimizer.
The results show that the performance of hybrid model is more efficient and robust than TS.
總目錄
第一章 前言 1-1
1-1 研究動機 1-1
1-2 研究目的 1-2
1-3 研究項目 1-3
1-4 本文架構 1-3
第二章 文獻回顧 2-1
2-1地下水問題之文獻回顧 2-1
2-2啟發式演算法 2-5
2-2-1遺傳演算法 2-6
2-2-2禁忌搜尋法 2-8
2-3文獻總結及研究方向 2-17
第三章 研究方法 3-1
3-1禁忌搜尋法 3-1
3-1-1 背景 3-1
3-1-2 基本概念及演算步驟 3-2
3-1-3禁忌搜尋法之構成要素 3-11
3-2遺傳演算法 3-18
3-2-1遺傳演算法之基本架構 3-19
3-3 GA - TS之混合模式 3-25
3-4地下水傳輸模式 3-28
3-5地下水復育優選問題 3-30
第四章 模式測試方式及問題描述 4-1
4-1各優選技術之測試方法 4-1
4-1-1禁忌搜尋法 4-1
4-1-2 GA-TS混合模式 4-2
4-2結果之比較方法 4-3
4-2-1名詞定義 4-3
4-2-2比較項目 4-3
4-3問題描述 4-5
4-3-1函數描述 4-6
4-3-2地下水污染場址復育案例描述 4-13
第五章 結果與討論 5-1
5-1函數測試 5-1
5-2地下水復育優選問題 5-10
5-3各優技術之求解效率分析 5-29
第六章 結論與建議 6-1
6-1結論 6-1
6-2建議 6-3
參考文獻 7-1
表目錄
表3-1 禁忌搜尋法之參數值 3-17
表3-2 遺傳演算法中之參數設定 3-26
表3-3 混合模式中禁忌搜尋之參數設定 3-27
表3-4 地下水復育優選問題中限制式之相關設定值 3-33
表3-5 最小復育成本問題中成本函數之係數值 3-33
表4-1 地下含水層的模擬參數值 4-14
表5-1 利用三種移步方式求解函數一之成功率 5-2
表5-2 利用三種移步方式求解函數二之成功率 5-3
表5-3 利用三種移步方式求解函數三之成功率 5-3
表5-4 利用三種移步方式求解函數四之成功率 5-3
表5-5 利用三種移步方式求解函數五之成功率 5-3
表5-6 利用三種移步方式求解函數六之成功率 5-4
表5-7 求解函數一比較增加多樣化及強化策略後對求解效率的影響
5-6
表5-8 比較單用強化及多樣化策略後對求得近全域最佳解之成功率(﹪)的影響 5-7
表5-9 比較單用強化及多樣化策略對運算時間(sec)的影響 5-8
表5-10 各優選模式求解六個函數100次後所得之最佳結果 5-8
表5-11 禁忌搜尋法、遺傳演算法與模擬退火法對於六個測試函數的尋優能力之比較 5-9
表5-12a以最小抽取量為目標函數,禁忌搜尋法求解之最佳結果…… 5-11
表5-12b以最小抽取量為目標函數,禁忌搜尋法求解之平均表現…… 5-11
表5-13 三種演算法求解最小抽取量問題之最佳結果.….. 5-13
表5-14a以最小抽取量為目標函數,比較各優選模式求解之最佳結果(遺傳演算法之世代數為10) 5-15
表5-14b以最小抽取量為目標函數,比較各優選方法求解之最佳結果(遺傳演算法之世代數為20)…… ……5-15
表5-14c以最小抽取量為目標函數,比較各優選方法求解之最佳結果(遺傳演算法之世代數為30) ……….5-16
表5-14d以最小抽取量為目標函數,比較GA-TS法與禁忌搜尋法求解之平均結果(遺傳演算法之世代數為10) ………….5-16
表5-14e以最小抽取量為目標函數,比較GA-TS法與禁忌搜尋法求解之平均結果(遺傳演算法之世代數為20) ..….….5-17
表5-14f以最小抽取量為目標函數,比較GA-TS法與禁忌搜尋法求解之平均結果(遺傳演算法之世代數為30)..….…… .5-17
表5-15a禁忌搜尋法求解最小總抽取量及總抽注量問題之平均表現…… .5-18
表5-15b三種演算法求解最小抽注量問題之最佳結果..….…… .5-19
表5-16a以最小復育成本為目標函數,禁忌搜尋法之求解結果(僅設抽取井) .….…….5-20
表5-16b以最小復育成本為目標函數,禁忌搜尋法求解之平均結果(僅設抽取井) ……….………5-20
表5-17 禁忌搜尋法、遺傳演算法求解最小復育成本問題所得之最佳結果(僅設抽取井) .……...…….5-22
表5-18a各優選模式求解最小復育成本問題之最佳結果(僅設抽取井;遺傳演算法之世代數為10) …….5-23
表5-18b各優選模式求解最小復育成本問題之最佳結果(僅設抽取井;遺傳演算法之世代數為20) ….5-23
表5-18c各優選模式求解最小復育成本問題之最佳結果(僅設抽取井;遺傳演算法之世代數為30) ….5-24
表5-18d GA-TS法與禁忌搜尋法求解最小復育成本問題之平均結果(僅設抽取井;遺傳演算法之世代數為10)…. .5-24
表5-18e GA-TS法與禁忌搜尋法求解最小復育成本問題之平均結果(僅設抽取井;遺傳演算法之世代數為20)…. …5-25
表5-18f GA-TS法與禁忌搜尋法求解最小復育成本問題之平均結果(僅設抽取井;遺傳演算法之世代數為30)…. …5-25
表5-19a不同之復育工作,禁忌搜尋法求解最小復育成本問題所求得之最佳結果…. …5-27
表5-19b不同之復育工作,禁忌搜尋法求解最小復育成本問題之平均表現. …5-27
表5-20 禁忌搜尋法與遺傳演算法求解最小復育成本問題之最佳結果(抽取井搭配注水井)…. …5-28
表5-21 GA-TS法與禁忌搜尋法求解最小抽取量問題,其目標函數值落入門檻值範圍內之成功率(﹪) 5-32
圖目錄
圖3-1 禁忌搜尋法之流程圖 3-10
圖3-2 遺傳演算法之簡易流程圖 3-24
圖3-3 二進位編碼方式之示意圖 3-20
圖3-4 交叉重組執行方式的示意圖 3-23
圖3-5 進行突變的程序之簡示圖 3-23
圖3-6 三種混合模式之執行方式 3-26
圖4-1 禁忌搜尋法不同參數設定組合之結果比較 4-5
圖4-2 函數一之目標函數示意圖 4-8
圖4-3 函數二之目標函數示意圖 4-8
圖4-4 函數三之目標函數示意圖 4-9
圖4-5 函數四之目標函數示意圖 4-10
圖4-6 函數五之目標函數示意圖 4-11
圖4-7 函數六之目標函數示意圖 4-12
圖4-8 測試案例之初始污染濃度分布及井位圖 4-14
圖5-1 求解函數一增加多樣化及強化策略對最佳解的影響 5-6
圖5-2 比較單用強化及多樣化策略後對求得近全域最佳解之成功率(﹪)的影響 5-7
圖5-3 禁忌搜尋法求得之最佳抽取量復育方案之污染濃度分佈圖………………… 5-12
圖5-4 禁忌搜尋法求得之最佳復育成本方案之污染濃度分佈(僅設抽取井) 5-21
圖5-5 禁忌搜尋法求得之最佳復育成本方案之污染濃度分佈圖(抽取井搭配注水井) 5-26
圖5-6a 不同世代數下GA-TS法求解最小抽取量問題之平均表現
5-31
圖5-6b 不同世代數下GA-TS法求解最小抽取量問題之平均運算時間 5-31
圖5-6c 在不同世代數下,GA-TS法求解最小抽取量問題時禁忌搜尋法對遺傳演算法之解答之改善百分比 5-32
圖5-7a 不同世代數下GA-TS法求解最小復育成本問題之平均表現.. 5-34
圖5-7b 不同世代數下GA-TS法求解最小復育成本問題之平均運算時間 5-34
圖5-7c GA-TS法在不同世代數下求解最小復育成本之問題較禁忌搜尋法之改善百分比 5-35
圖5-7d 在不同世代數下,GA-TS法求解最小復育成本問題時禁忌搜尋法對遺傳演算法之解答之改善百分比 5-35
參考文獻
1. Al-Sultan, K. S., and M. A. Al-Fawzan, “A Tabu Search Hooke and Jeeves Algorithm for Unconstrained Optimization,” European Journal of Operational Res., Vol. 103, pp. 198-208, 1997.
2. Bear, J. and Y. Sun, “Optimization of Pump-Treat-Inject (PTI) Design for the Remediation of A Contaminated Aquifer:Multi-Stage Design with Chance Constraints,” Journal of Contsminant Hydrology, Vol. 29, pp. 225-244, 1998.
3. Ben-Daya, M., and M. Al-Fawzan, “A Tabu Search Approach for the Flow Shop Scheduling Problem,” European Journal of Operational Res., Vol. 109, pp. 88-95, 1998.
4. Bland, J.A., “A Memory-Based Technique for Optimal Structural Design,” Engineering Application of Articial Intelligence, 11, pp.319-325, 1998.
5. Chen, Yu-Ming, “Management of Water Resources Using Improved Genetic Algorithms,” Computers and Electronics in Agriculture, Vol. 18, pp. 117-127, 1997.
6. Committee on the Decade of Operation Research (Condor), “Operation Research: The Next Decade”, Operation Research, Vol. 36, pp. 619-637, 1988.
7. DeJong, K. A., “Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph. D. Dissertation , Department of Computer and Communication Sciences,” University of Michigan, Ann Arbor, MI, 1975.
8. Gendreau, M., G. Laporte, and F. Semet, “A Tabu Search Heuristic for the Undirected Selective Traveling Salesman Problem,” European Journal of Operational Res., Vol. 106, pp. 539-545, 1998.
9. Glover, F., “Future Path for Integer Programming and Links to Articial Intelligence,” Comput. Oper. Res., Vol. 13, pp. 533-549, 1986.
10. Glover, F., “Tabu Search — Wellsprings and Challenges,” European Journal of Operational Res., Vol. 106, pp. 221-225, 1998.
11. Glover, F., and M. Laguna, Tabu Search, Kluwer Academic, Boston,1997.
12. Glover, F., P. K. James, and L. Manuel, “Genetic Algorithms and Tabu Search : Hybrids for Optimization,” Computer Ops. Res., Vol. 22, pp. 111-134, 1995.
13. Goldberg, D. E., “Optimal Initial Population Size for Binary-coded Genetic Algorithms. TCGA Report #850001, The Clearinghouse for Genetic Algorithms, Department of Engineering Mechanics,” University of Alabama, 1985.
14. Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA, 1989.
15. Guan, J., and M. M. Aral, “Optimal Remediation with Well Locations and Pumping Rates Selected as Continuous Decision Variable,” Journal of Hydrology, Vol. 221, pp. 20-42, 1999.
16. Holland, J. H., Adaptation in Nature and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.
17. Kolahan, F., and M. Liang, ”A Tabu Search Approach to Optimization of Drilling Operations,” Computers ind. Engng, Vol. 31, No. 1/2, pp. 371-374, 1996.
18. Kovacevic-Vujcic, V. V., M. M. Cangaliovic, M. D. Asic, L. Ivanovic, and M. Drazic, “Tabu Search Methodology in Global Optimization,” Computers and Mathematics with Application, Vol. 37, pp. 125-133, 1999.
19. Laguna, M., R. Marti, and V. Campos, “Intensification and diversification with elite tabu search solutions for the linear ordering problem,” Computer & Operations Res., Vol. 26, pp. 1217-1230, 1999.
20. Lin, M-D. , “Nonaqueous Phase Liquid Contaminated Aquifer Remediation: Using Nonlinear Programming and Genetic Algorithms to Optimize Surfactant Enhanced Pump-and-Treat Aquifer Remediation Systems,” Ph. D. Dissertation, Uinversity of Texas, Austin, 1995.
21. Machado, J. M., Y. Shiyou, S. L. Ho, and N. Peihong , “A common Tabu Search Algorithm for the Global Optimization of Engineering Problem,” Comput. Methodes Appl. Mech. Engrg., Vol. 190, pp. 3501-3510, 2001.
22. Mantawy, A. H., Y. L. Abdel-Magid, and S. Z. Selim, “A New Genetic-Based Tabu Search Algorithm for Unit Commitment Problem,” Electric Power Systems Res., Vol. 49, pp. 71-78, 1999.
23. McKinney, D. C. ,and Min-Der Lin, “Approximate Mixed-Integer Nonlinear Programming Methods for Optimal Aquifer Remediation Design,” Water Resources Research, Vol. 31, No. 3, pp. 731-740, 1995.
24. Michalewics, Z., Genetic Algorithm + Data Structures = Evolution Programs, Springer-Verlag, 1992.
25. Pinder, G. F., ”Galerkin Finite Element Models for Aquifer Simulation,” Report 78-WR-5, Dep. Of Civ. Eng., Princeton Univ., Princeton, N. J., 1978.
26. Psilovikos A. A., “Optimization Models in Groundwater Management, Based on Linear and Mixed Integer Programming. An Application to Greek Hydrogeological Basin,” Phys. Chem. Earth (B), Vol. 24, No. 1-2, pp. 139-144, 1999.
27. Talbi, E. G., Z. Hafidi, and J-M. Geib, “A Parallel Adaptive Tabu Search Approach,” Parallel Computeing, Vol. 24, pp. 2003-2019, 1998.,
28. Tsubakitani, S., and R. E. James, “Optimizing Tabu List Size for the Travelling Salesman Problem,” Computers Ops Res., Vol, 25, No. 2, pp. 91-97, 1998.
29. Wang, C., H. Quan, and X. Xu, ”Optimal Design of Multiproduct Batch Chemical Process Using Tabu Search,” Computers and Chemical Engineering, Vol. 23, pp. 427-437, 1999.
30. Wang, P. P., and C. Zheng, “A Efficient Approach of Successively Perturbed Groundwater Methods,” Advances in Water Res., Vol. 21, pp. 499-508, 1998.
31. Zheng, C., and P. Wang, “Parameter Structure Identification Using Tabu Search and Simulated Annealing,” Advances in Water Res., Vol. 19, No. 4, pp. 215-224, 1996.
32. 吳泰熙、張欽智,「以禁忌搜尋法則求解推銷員旅行問題」,大業學報,第六卷,第一期,pp. 87-99,1997。
33. 李宇欣、陳立文,「鄰近搜尋法於大型問題之求解績效:以TSP為例」,第五屆運輸網路研討會,pp. 1~9,2000。
34. 林妙貞,「遺傳演算法在地下水復育系統的不確定性分析之應用」,碩士論文,中興大學環境工程研究所,1997。
35. 林明德,「遺傳演算法」,環境系統分析研習會論文集,pp. 197-203,1997。
36. 徐君豪,「全域工程最佳化之模擬退火法」,碩士論文,淡江大學機械工程研究所,1998。
37. 曹以松、黃國倫,「地下水參數鑑定反向推求抽水量之研究與應用」,台灣水利,第三十二卷,第四期,pp. 102-122,1986。
38. 許益源,「受污染廠址整治技術介紹」,化工資訊,第十四卷,第12期,pp. 24-31,2000。
39. 許清荃,「地下水資源調配與管理-以濁水溪沖積扇為案例」,水資源管理季刊,第八卷,pp. 24-31,2000。
40. 許維群,「遺傳演算法與非線性規劃混合模式在地下水復育問題上之研究」,碩士論文,中興大學環境工程研究所。
41. 郭勝豐,「遺傳機制原理應用於灌溉系統規劃之理念」,農業工程學報,第41卷,第2期,pp. 36-40,1995。
42. 郭嘉真,「抽注率敏感方程法在地下水管理上之研究」,中國環境工程學刊,第三卷,第三期,pp. 199-207,1992。
43. 陳莉、張斐章,「遺傳演算法優選水庫運用規線之研究」,農業工程學報,第四十一卷,第四期,pp. 20-29,1995。
44. 童慶斌、周哲正,「禁忌搜尋法在地下水之參數分區之應用」,第二屆環境系統分析研討會論文專輯,pp. 211-217,1999。
45. 黃安德,「二階線性規劃問題之塔布搜尋法」,博士論文,清華大學工業工程研究所,1995。
46. 葉恩仲,「模擬退火法與遺傳演算法混合模式在地下水復育優選問題之應用」,碩士論文,中興大學環境工程研究所,2002。
47. 鄭瑞富,「公路平縱面線性最佳化設計模式」,博士論文,成功大學土木工程研究所,2000。
48. 謝欽旭、楊正宏,「混合式最佳化方法-遺傳演算法與梯度法」,高雄工商專學報,第二十三期,pp. 297-307,1994。
49. 嚴浩哲,「平行遺傳演算法以電腦叢集為工具應用於地下水優選問題」,碩士論文,中興大學環境工程研究所,2002。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔