Water Flow-like Algorithm for Discrete Optimization Problems
Date Issued
2006
Date
2006
Author(s)
Wang, Yuan-Peng
DOI
zh-TW
Abstract
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.
Subjects
啟發式演算法
遺傳演算法
仿水流優化演算法
heuristic algorithm
genetic algorithm
water flow-like algorithm
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93546032-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):0693bbae2c853cf009955bf815168f00