Water Flow-Like Algorithm for Object Grouping Problems

物件分群之仿水流優化演算法

10.29977/JCIIE.200711.0005

楊烽正(Feng-Cheng Yang)；王元鵬(Yuan-Peng Wang)

啓發式演算法 ； 仿水流優化演算法 ； 匯流 ； 分流 ； 降水 ； heuristic algorithm ； discrete optimization ； water flow-like algorithm ； flow merging ； flow splitting

工業工程學刊

24卷6期（2007 / 11 / 01）

475 - 488

英文

本文提出一個新的啟發式演算法名爲「仿水流優化演算法」(Water Flow-Like Algorithm, WFA)以求解物件分群問題。WFA的求解機制是模仿水流在地理空間流動的物理特性。地理空間中的水流停駐的位置被應對爲優化問題求解空間的一個解。一股水流即代表一個解，水流即是解的代理人。水流會受地心引力影響不斷地向低處流動。流動的過程中隨著地理空間的變化會有分流、匯流等現象。部分水流會蒸發至大氣中形成水氣，降水後繼續流動。自然界的水流泰半會流經地理空間中的最低點。WFA在解搜尋過程中透過分流、匯流、蒸發、降水四個演化作業調整水流代理人的數量，兼顧節空間的探索(Exploration)和探究(Exploitation)，避免搜尋過度或搜尋不足。本文展示的WFA係以離散優化問題爲求解對象設計演化作業細節。此外也將針對物件分群優化問題中的裝箱問題(Bin Packing Problem, BPP)進行求解驗證。求解結果與遺傳演算法、仿電磁吸斥優化演算法、及粒子群演算法比較以驗證求解效能。範例測試則針對複雜度高的自訂範例和OR-Library內的標竿問題求解，並與其他方法比較。結果顯示，WFA在求解BPP問題上有優於其他啟發式演算法的趨勢。

This paper presents a novice heuristic algorithm, Water Flow-like Algorithm (WFA), for solving discrete optimization problems, particularly the bin packing problems. WFA simulates solution agents as water flows traversing the terrain mapped from the objective function. Governed by the gravitation force, water flows from higher attitudes to lower ones. Driven by the fluid momentum, water flows adjust their compositions and directions against the landforms by splitting into and merging from other flows. Water flows are allowed to move upward to higher attitudes once they possess enough momentum to overcome the potential barrier. Mostly, at least one flow can travel to the lowest region of the terrain under the consideration. In the atmosphere, some water of a flow will evaporate and return to the ground by precipitation. Inspired by the water flowing of the nature, WFA is designed as an optimization algorithm performing the water flow splitting, merging, and dropping (precipitation) operations to traverse the solution space. The number of solution agents deployed is dynamically changing. WFA is an evolutionary algorithm involving four water flow operations: splitting and moving, merging, evaporation, and precipitation. The computational flow and the four operations are extensively discussed. In addition to general operations of WFA, specific operations for bin packing problems are presented. A designed problem and a benchmark problem from OR-Lib are used to test WFA and to compare results with other methods, such as GA, POS, and EM. Numerical results show that WFA outperforms others in solving these BPPs.

1. Birbil, S. I.,S. C. Fang(2003).An electromagnetism-like mechanism for global optimization.Journal of Global Optimization,25,263-282.
2. Dougherty, D. E.,R. A. Marryott(1991).Optimal Groundwater Management.Water Resources Research,27,2493-2508.
3. Falkenauer, E.(1996).A hybrid grouping genetic algorithm for bin packing.Journal of Heuristics,2,5-30.
4. Gen, M.,R. Cheng(1997).Genetic Algorithms and Engineering Design.New York:Wiley.
5. Glover, F.,E. Taillard,E. Taillard(1993).A user's guide to tabu search.Annals of Operations Research,41,11-28.
6. Glover, F.,M. Laguna(1998).Tabu Search.Springer.
7. Hansen, P.,N. Mladenovic,V. Stefan,M. Silvano,S. Voss,S. Martello,I. H. Osman,C. Roucairol (eds.)(1999).Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization.Boston:Kluwer Acadenics.
8. Holland, J. H.(1975).Adaptation in Natural and Artificial System.Thesis, University of Michigan.
9. Kennedy, J.(2000).Stereotyping: improving particle swarm performance with cluster analysis.Proceedings of IEEE International Conference on Evolutionary Computing,California, USA:
10. Kennedy, J.,R. Eberhart(1995).Particle swarm optimization.Proceedings of IEEE International Conference on Neural Networks,Perth, Aust:
11. Moore, J.,R. Chapman(1999).Report of Department of Computer Science and Software Engineering.Auburn University.
12. Benchmark Library
13. Shi, Y.,R. C. Eberhart(2001).Fuzzy adaptive particle swarm optimization.Proceedings of the 2001 Congress on Evolutionary Computation,Seoul, Korea:
14. Yang, F. C.,C. L. Wei(2006).Electromagnetic-like mechanism based discrete optimization algorithm for object sequencing problems and object grouping problems.Proceedings of the 7th Asia Pacific Industrial Engineering and Management Systems Conference,Bangkok, Thailand:
15. Yang, F. C.,C. Y. Kang,Y. H. Hung(2006).Electromagnetic attraction and repulsion simulated techniques-based optimization framework and software Systems.Proceedings of the 11th Annual International Conference on Industrial Engineering,Nagoya, Japan:
16. Zheng, C.,P. P. Wang(1996).Parameter structure identification using tabu search and simulated annealing.Advances in Water Resources,19,215-224.