臺灣博碩士論文加值系統

本研究提出ㄧ個新的啟發式演算法名為「仿水流優化演算法」(Water Flow-Like Algorithm，WFA)。WFA的求解機制是仿水流在地理空間中所表現的物理特性而成。地理空間中的水流存在的位置被視為優化問題求解空間的一個解。一股水流即代表一個解，水流即是解的代理人。水流會受地心吸力影響不斷地向低處流動。流動的過程中隨著地理空間的變化會有分流、匯流、…等現象，部分水流會蒸發至大氣中形成水氣，降水後繼續流動。自然界的水流泰半會流經地理空間中的最低點。WFA是藉由模仿水流的物理特性，提出的一代理人解數目會隨求解過程變化的演算法，朝解空間的最低點流動演化。
WFA在解搜尋過程中透過分流、匯流、蒸發、降水四個演化作業調整代理人數，避免搜尋上的過度或不足。本研究提出的WFA是以離散優化問題為求解對象設計演化作業細節。研究中將針對幾個物件分群優化問題中的裝箱問題(Bin Packing Problem, BPP)及物件排序優化問題中的旅行銷售員問題(Traveling Salesman Problem， TSP)進行求解。求解結果與遺傳演算法、仿電磁吸斥優化演算法、及粒子群演算法比較以驗證可行性。求解四個不同特性和複雜度的自訂範例和OR-Library內的標竿問題後顯示WFA在求解BPP問題上較其他的啟發式演算法優秀，而求解TSP問題上則有較大的改進空間。

This research presents a novice heuristic algorithm called “Water Flow-Like Algorithm” (WFA) for solving discrete optimization problems. WFA simulates solution agents searching in the solution space as water flows traversing a predefined terrain. Governed by the gravitation force, water flows change their composition and direction against the landforms by splitting and merging subflows. Usually at least one flow can travel to the lowest region of the terrain under consideration. Under the atmosphere, some water of the water flow will evaporate and return to the ground by precipitation. WFA is thus designed as an optimization algorithm that the number of solution agents changes dynamically to imitate the water flow splitting, merging, and dropping (precipitation). WFA is an evolution algorithm involving four water flow operations: split, merging, evaporation, and precipitation. These operations are rigorously explained and presented in this paper. In addition to the presentation of general operation procedures, adapted and modified procedures for Bin Packing Problems and Traveling Salesman Problems are presented. Solutions of WFA are compared with those computed from GA (Genetic Algorithm), EM (Electromagnetic-like Mechanism), and PSO (Particle Swarm Optimization). Four self-defined problems with different features and complexities and the benchmarks of the OR-LIB are tested and results show that WFA outperforms others in solving BPPs. However, the solutions qualities of WFA in solving TSPs need further improvement.

目錄
摘 要 I
ABSTRACT II
目錄 III
表目錄 V
圖目錄 VII
中英文名詞對照表 VIII
符號說明 XI
一、緒論 1
1.1 研究動機 1
1.2 研究方法及範疇 3
1.3 研究流程 4
1.4 章節概要 5
二、文獻探討 6
2.1 啟發式演算法 6
2.1.1 禁忌演算法 6
2.1.2 遺傳演算法 8
2.1.3 模擬退火演算法 13
2.1.4 仿電磁吸斥優化演算法 14
2.1.5 粒子群演算法 16
2.2 離散優化問題 18
2.2.1 裝箱問題(Bin Packing Problem) 18
2.2.2 旅行推銷員問題(Traveling Salesman Problem) 20
2.3 文獻探討結語 21
三、離散優化問題的仿水流優化演算法 23
3.1 水流特性 23
3.2 水流特性於優化問題求解上的應用 24
3.3 仿水流優化演算法的特色 25
3.4 仿水流優化演算法的搜尋機制及流程 27
3.5 求解物件分群優化問題的仿水流優化演算法 45
3.5.1 求解裝箱重量均等問題的主流程 46
3.5.2 求解有容量限制的裝箱重量均等問題的流程 47
3.6 求解物件排序優化問題的仿水流優化演算法 49
3.6.1 物件排序優化問題修正機制 50
3.7 小結 54
四、仿水流優化演算法求解系統及範例驗證 55
4.1 仿水流離散優化演算法求解礎架 55
4.1.1 WFBDOS介面及使用說明 55
4.1.2 物件分群優化問題求解介面 59
4.1.3 物件排序優化問題求解介面 62
4.2 物件分群優化問題範例演練 63
4.2.1 分群問題自定範例演練 63
4.2.2 ORLIB裝箱標竿問題試驗 82
4.3 旅行推銷員標竿問題演練 97
4.4 小結 101
五、結論與建議 102
5.1 結論 102
5.2 建議 104
參考文獻 106

表目錄
表2-1 BPP問題延伸的相關問題表 19
表2-2 常見求解BPP問題的啟發式演算法表 20
表2-3 TSP問題延伸的相關問題表 21
表2-4 常見求解TSP問題的啟發式演算法表 21
表4-1 自訂範例一的物件重量表 65
表4-2 自訂範例一的搜尋資訊表 65
表4-3 WFA求解自訂範例一的初始參數設定 66
表4-4 求解自訂範例一各演算法求得的群間重量標準差 67
表4-5 自訂範例二的物件最佳分群狀況設計 70
表4-6 自訂範例二的搜尋資訊表 70
表4-7 WFA求解自訂範例二的初始參數設定 71
表4-8 自訂範例二WFA與GA求得的群間重量標準差及違反容量限制狀況 72
表4-9 比較WFA有無執行蒸發及降水作業下搜尋到的群間重量標準差 73
表4-10 自訂範例三的物件最佳分群狀況設計 75
表4-11 自訂範例三的搜尋資訊表 75
表4-12 WFA求解自訂範例三的初始參數設定 76
表4-13 自訂範例三WFA與GA求得的群間重量標準差及違反容量限制狀況 77
表4-14 自訂範例四的物件最佳分群狀況設計 79
表4-15 自訂範例四的搜尋資訊表 79
表4-16 WFA求解自訂範例四的初始參數設定 79
表4-17 自訂範例四WFA與GA求得的群間重量標準差及違反容量限制狀況 81
表4-18 BBP標竿問題物件重量表 83
表4-19 無容量限制的裝箱重量均等問題搜尋條件表 85
表4-20 無容量限制的裝箱重量均等問題WFA初始參數設定 85
表4-21 各演算法求解無容量限制裝箱重量均等問題得到的箱間總重量標準差 85
表4-22 有容量限制的裝箱重量均等問題(48箱) 搜尋資訊表 87
表4-23 WFA求解有容量限制的裝箱重量均等問題(48箱)的初始參數設定 87
表4-24 GA與WFA求解有容量限制的裝箱重量均等問題(48箱)得到的箱間總重量標準差及違反容量限制情形 88
表4-25 有容量限制之裝箱重量均等問題(48箱)物件及重量分佈最佳解 89
表4-26 有容量限制之裝箱重量均等問題(48箱)物件最佳分群狀況 89
表4-27 有容量限制之裝箱重量均等問題(49箱)搜尋條件表 90
表4-28 有容量限制之裝箱重量均等問題(49箱)初始參數設定 90
表4-29 GA與WFA求解有容量限制的裝箱重量均等問題(49箱)得到的箱間總重量標準差及違反容量限制情形 91
表4-30 有容量限制之裝箱重量均等問題(49箱)各群最佳重量分配 92
表4-31 有容量限制之裝箱重量均等問題(49箱)物件及重量分佈最佳解 93
表4-32 有容量限制之裝箱重量均等問題(50箱)搜尋條件表 94
表4-33 有容量限制之裝箱重量均等問題(50箱)WFA初始參數設定 94
表4-34 GA與WFA求解有容量限制的裝箱重量均等問題(50箱)得到的箱間總重量標準差及違反容量限制情形 95
表4-35 有容量限制之裝箱重量均等問題(50箱)各群最佳重量分配 96
表4-36 有容量限制之裝箱重量均等問題(50箱)物件及重量分佈最佳解 97
表4-37 TSP(14)問題各城市的座標點 99
表4-38 TSP(14)相關資訊 99
表4-39 TSP(14)問題初始參數設定 99
表4-40 各演算法求解TSP(14)問題得到的最短路徑 100
表4-41 WFA以三種降水的方法求解TSP得到的最短路徑 100

圖目錄
圖2-1 禁忌演算法流程圖 8
圖2-2 遺傳演算法交配機制示意圖 11
圖2-3 遺傳演算法流程圖 13
圖2-4 粒子群優化法演算原理示意圖 18
圖4-1 WFA初始設定介面 56
圖4-2 WFA搜尋結果人機介面展示 57
圖4-3 WFA歷史搜尋資料展示 57
圖4-4 WFA最佳解搜尋結果展示 58
圖4-5 WFA 求解使用者自訂問題介面展示 59
圖4-6 WFA 求解BPP問題介面展示 60
圖4-6 WFA求解BPP問題介面展示(續) 61
圖4-6 WFA 求解BPP問題界面展示(續) 62
圖4-7 WFA 求解TSP問題界面展示 63
圖4-8 目標函數值收斂狀況展示圖 64
圖4-9 WFA求解自定範例一結果的人機介面展示 66
圖4-10 WFA求解自訂範例一的最佳分群結果 67
圖4-11 WFA求解自訂範例二目標函數值收斂狀況展示圖 71
圖4-12 GA求解自訂範例二目標函數值收斂狀況展示圖 71
圖4-13 WFA求解自訂範例二的群間總重量分布示意圖 73
圖4-14 WFA求解自訂範例二的最佳分群結果 74
圖4-15 WFA求解自訂範例三目標函數值收斂狀況展示圖 76
圖4-16 GA求解自訂範例三目標函數值收斂狀況展示圖 76
圖4-17 WFA求解自訂範例三群間總重量分布示意圖 77
圖4-18 WFA求解自訂範例三的最佳分群結果 78
圖4-19 WFA求解自訂範例四目標函數值收斂狀況展示圖 80
圖4-20 GA求解自訂範例四目標函數值收斂狀況展示圖 80
圖4-21 WFA求解自訂範例四的群間總重量分布示意圖 81
圖4-22 WFA求解自訂範例四的最佳分群結果 82
圖4-23 WFA求解TSP問題(14個城市)得到的最短路線示意圖 101

1. A., D. K., and Societies, A. o. E. O. R. (1993). "Some Experiments with Simulated Annealing Techniques for Packing Problems." European journal of operational research (Eur. j. oper. res.) 68, 389-399.

2. Birbil, S. I., and Feyzioglu, O. (2003). A Global Optimization Method for Solving Fuzzy Relation Equations.

3. Birbil, S. I., and Fang, S.-C., and Sheu, R.-L. (2004). "On the Convergence of a Population-Based Global Optimization Algorithm." Journal of Global Optimization, 30(2), 301-318.

4. Carlson, S. E., and Shonkwiler, R. "Annealing a Genetic Algorithm Over Constraints." 3931-3936 vol.4.

5. Chen, C.-Y., and Ye, F. "K-means Algorithm Based on Particle Swarm Optimization." 2003 International Conference on Informatics, Cybernetics, and Systems, I-Shou University, Taiwan, ROC Dec, pp.1470-1475.

6. D.E.Goldberg. (1989). "Computer-Aided Gas Pipeline Operation using Genetic Algorithm and Rule Learning," University of Michigan, Michigan,US.

7. Debels, D., Reyck, B. D., Leus, R., and Vanhoucke, M. (2004). "A Hybrid Scatter Search / Electromagnetism Meta-Heuristic for Project Scheduling." Ghent University, Faculty of Economics and Business Administration.

8. Dorigo, M., and Gambardella, L. M. (1997). "Ant Colonies for the Travelling Salesman Problem." Biosystems, 43(2), 73-81.

9. Dueck, G., and Scheuer, T. (1990 ). "Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing." Journal of Computational Physics 90 (1), 161 – 175.

10. E., D. D., A., M. R., and Union, A. G. (1991). "Optimal Groundwater Management. I: Simulated Anneling " Water Resources Research (Water resour. res.), 27, 2493-2508.

11. Falkenauer, E. (1996). "A Hybrid Grouping Genetic Algorithm for Bin Packing." Journal of Heuristics, 2(1), 5-30.

12. Fourie, P. C., and Groenwold, A. A. (2002). "The Particle Swarm Optimization Algorithm in Size and Shape Optimization." Structural and Multidisciplinary Optimization, 23(4), 259-267.
13. Fox, M. S. (1986). "Observations on the Role of Constraints in Problem Solving." Proceedings of the Annual Conference of the Canadian Society for Computational Studies of Intelligence.

14. Garey, M. R., Graham, R. L., Johnson, D. S., and Yao, A. C.-C. (1976). "Resource Constrained Scheduling as Generalized Bin Packing." J. Comb. Theory, Ser. A 21.

15. Gen, M., and Cheng, R. (1997). Genetic Algorithms and Engineering Design, Wiley-IEEE.

16. Glover, F., and Laguna, M. (1998). Tabu Search, Springer.

17. Glover, F., Taillard, E., and Taillard, E. (1993). "A User''s Guide to Tabu Search." Annals of Operations Research, 41(1), 1-28.

18. Goldberg, D. E., and Lingle, J. R. (1985). "Alleles, Loci and the Traveling SalesmanProblem." en Proceedings of the First International Conference on Genetic Algorithms and Their Applications.

19. Holland, J. H. (1975). Adaptation in Natural and Artificial System, The University of Michigan Press.

20. J., L., and F., D. (2003). " Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems." Journal of the Operational Research Society, 55, 705-716.

21. Julia, A. B., and Kathryn, A. D. (1999). "A Tabu Thresholding Implementation for the Irregular Stock Cutting Problem." International Journal of Production Research, 37(18), 4259-4275.

22. Kang-Ping, W., Lan, H., Chun-Guang, Z., and Wei, P. "Particle Swarm Optimization for Traveling Salesman Problem." 1583-1585 Vol.3.

23. Kennedy, J. "Stereotyping: Improving Particle Swarm Performance with Cluster Analysis." 1507-1512 vol.2.

24. Kennedy, J., and Eberhart, R. "Particle Swarm Optimization." 1942-1948 vol.4.

25. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). "Optimization by Simulated Annealing." Science, 220, 671-680.

26. Li-Chiu Chang, F.-J. C. (2001). "Intelligent Control for Modelling of Real-time Reservoir Operation." Hydrological Processes, 15(9), 1621-1634.
27. Malek, M., Guruswamy, M., Pandya, M., and Owens, H. (1989). "Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem." Annals of Operations Research, 21(1), 59-84.

28. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller.E. (1953). "Equations of Calculation by Fast Computing Machines." Journal of Chemical Physics, 21(6), 1087-1092.

29. Moore, J., and Chapman, R. (1999). "Application of Particle Swarm to Multiobjective Optimization ", Department of Computer Science and Software Engineering, Auburn University.

30. P., H., N., M., Stefan, V., and Silvano, M. (1999). "An introduction to variable neighborhood search." Meta-heuristics : Advances and Trends in Local Search Paradigms for Optimization ("Sophia Antipolis", 21-24 July 1997) 433-458.

31. Parsopoulos, K. E., and Vrahatis, M. N. (2002a). "Initializing the Particle Swarm Optimizer Using the Nonlinear Simplex Method." Advances in Intelligent Systems, Fuzzy Systems, Evolutionary Computation,pp. 216--221, WSEAS Press.

32. Parsopoulos, K. E., and Vrahatis, M. N. (2002b). "Particle Swarm Optimization Method for Constrained Optimization Problems ", University of Patras Artificial Intelligence Research Center.

33. Robinson, J., Sinton, S., and Rahmat-Samii, Y. "Particle swarm, Genetic Algorithm, and Their Hybrids: Optimization of a Profiled Corrugated Horn Antenna." 314-317 vol.1.

34. S, I. B. (2002). "Stochastic Global Optimization Techniques," A Dissertation Submitted to the Graduate Faculty of North Carolina State University.

35. Toern, A., Ali, M. M., and Viitanen, S. (1999). "Stochastic Global Optimization: Problem Classes and Solution Techniques." Journal of Global Optimization, 14(4), 437-447.

36. Wang, T. (1991). "Global Optimization for Constrained Nonlinear Programming," Zhejiang University.
37. Xiao-Feng, X., Wen-Jun, Z., and Zhi-Lian, Y. "Adaptive Particle Swarm Optimization on Individual Level." 1215-1218 vol.2.

38. Yang, W.-H. (2002a). " A Study on the Intelligent Neural Network Training Using the Electromagnetism Algorithm," Yuan-Ze University.

39. Yang, W.-H. (2002b). "Textile Retail Operation using Electromagnetism Algorithm Based Neural network," Yuan-Ze University.

40. Yuhui, S., and Eberhart, R. C. "Fuzzy Adaptive Particle Swarm Optimization." 101-106 vol. 1.

41. Zheng, C., and Wang, P. P. (1996). "Parameter Structure Identification Using Tabu Search and Simulated Annealing " Advances in Water Resources Vol. 19, no. 4, pp. 215-224.

42. 吳泰熙，張欽智 (1997) ，「以禁忌搜尋法則求解推銷員旅行問題」，大葉學報6(1)，87-99頁。

43. 葉思緯 (2004) ，「應用粒子群最佳化演算法於多目標存貨分類之研究」，元智大學工業工程與管理研究所碩士論文。

44. 劉建宏 (2005) ，「應用粒子群優法作解制環境下新型態之經濟運轉」，雲林科技大學電機所碩士論文。