仿水流離散優化演算法

Water Flow-like Algorithm for Discrete Optimization Problems

王元鵬(Yuan-Peng Wang)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.02959

摘要

本研究提出ㄧ個新的啟發式演算法名為「仿水流優化演算法」(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.

並列關鍵字

heuristic algorithm ； genetic algorithm ； water flow-like algorithm

參考文獻

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

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.