Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems

Xuepeng Liu; Qing Wang; An-Da Li

doi:doi:10.11648/j.ajmie.20220703.12

| Peer-Reviewed

Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems

Xuepeng Liu, Qing Wang, An-Da Li

Published in American Journal of Mechanical and Industrial Engineering (Volume 7, Issue 3)

Received: 11 July 2022 Accepted: 16 August 2022 Published: 24 August 2022

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

Being greatly inspired by the natural flowing regulation of water, we propose a new meta-heuristic algorithm — Flowing Water Algorithm (FWA) for the solution of combinatorial optimization problems (COPs). Since the solution space of COPs is multidimensional, complex and has many local extreme values, according to our proposed method, it appears to be similar to an endless hilly area with mountains, valleys and plateaus. The downward-flowing water in such area finds its way to the lowest point in the hill. Water always flows downward and eventually converges at the lowest place without any outside intervention except for gravity. Such a flowing course can be deemed as a process for the water to seek for the lowest point. The proposed algorithm is derived from such a water flow process. This algorithm combines a local search strategy with a population-based search strategy to improve both local and global search abilities. Four operators, including the local search, water overflow, drilling water tunnel and evaporation-rain are included in FWA, making this algorithm successfully perform tabu search, positive feedback, “survival of the fittest”, and local optimum escape. Two examples of its application in the traveling salesman problem (TSP) show that FWA outperforms the benchmark methods for both solution quality and convergence speed.

Published in	American Journal of Mechanical and Industrial Engineering (Volume 7, Issue 3)
DOI	10.11648/j.ajmie.20220703.12
Page(s)	45-52
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2022. Published by Science Publishing Group

Keywords

Combinatorial Optimization Problems, Heuristics, Flowing Water Algorithm, Artificial Water

References

[1]	M. Randall, D. Abramson, A general meta-Heuristic based solver for combinatorial optimisation problems, Computational Optimization & Applications, 20 (2) (2001) 185-210.
[2]	G. A. Kochenberger, F. Glover, B. Alidaee, C. Rego, A unified modeling and solution framework for combinatorial optimization problems, Or Spectrum, 26 (2) (2004) 237-250.
[3]	Z. Michalewicz, D. B. Fogel, How to solve it: Modern heuristics, Springer Science & Business Media, 2013.
[4]	J. H. Holland, Adaptation in natural and artificial systems, MIT Press, 1992.
[5]	S. Kirkpatrick, Optimization by simulated annealing: Quantitative studies, Journal of Statistical Physics, 34 (5-6) (1984) 975-986.
[6]	F. Glover, Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13 (5) (1986) 533-549.
[7]	M. Dorigo, V. Maniezzo, A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society, 26 (1) (1996) 29.
[8]	R. Eberhart, J. Kennedy, A new optimizer using particle swarm theory. In Micro Machine and Human Science,. MHS'95., Proceedings of the Sixth International Symposium on IEEE (1995) 39-43.
[9]	P. Tian, J. Ma, D. M. Zhang, Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism, European Journal of Operational Research, 118 (1) (1999) 81-94.
[10]	M. Obaidullah, G. N. Khan, Application mapping to mesh NoCs using a Tabu-search based swarm optimization, Microprocessors & Microsystems, 55 (2017) 13-25.
[11]	L. Fanjul-Peyro, R. Ruiz, Iterated greedy local search methods for unrelated parallel machine scheduling, European Journal of Operational Research, 207 (1) (2010) 55-69.
[12]	S. Sasikala, S. A. alias Balamurugan, S. Geetha, A novel adaptive feature selector for supervised classification, Information Processing Letters, 117 (2017) 25-34.
[13]	R. Saini, N. Anand, A multi-objective ant colony system algorithm for virtual machine placement, International Journal of Engineering Research & Applications, 7 (1) (2017) 95-97.
[14]	C. Jing, X. Wang, Identification of Hammerstein systems with continuous nonlinearity, Information Processing Letters, 115 (11) (2015) 822-827.
[15]	A. Hertz, M. Widmer, Guidelines for the use of meta-heuristics in combinatorial optimization, European Journal of Operational Research, 151 (2) (2003) 247-252.
[16]	A. H. Halim, I. Ismail, Combinatorial optimization: Comparison of heuristic algorithms in travelling salesman problem, Archives of Computational Methods in Engineering, (2017) 1-14. https://doi.org/10.1007/s11831-017-9247-y.
[17]	J. Shen, K. Wang, The light ray particle swarm optimization for solving the traveling salesman problem, CAAI Transactions on Intelligent Systems, 7 (2012) 174-182.(In Chinese).

Cite This Article

Plain Text BibTeX RIS

APA Style

Xuepeng Liu, Qing Wang, An-Da Li. (2022). Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems. American Journal of Mechanical and Industrial Engineering, 7(3), 45-52. https://doi.org/10.11648/j.ajmie.20220703.12

Copy | Download

ACS Style

Xuepeng Liu; Qing Wang; An-Da Li. Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems. Am. J. Mech. Ind. Eng. 2022, 7(3), 45-52. doi: 10.11648/j.ajmie.20220703.12

Copy | Download

AMA Style

Xuepeng Liu, Qing Wang, An-Da Li. Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems. Am J Mech Ind Eng. 2022;7(3):45-52. doi: 10.11648/j.ajmie.20220703.12

Copy | Download

@article{10.11648/j.ajmie.20220703.12,
  author = {Xuepeng Liu and Qing Wang and An-Da Li},
  title = {Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems},
  journal = {American Journal of Mechanical and Industrial Engineering},
  volume = {7},
  number = {3},
  pages = {45-52},
  doi = {10.11648/j.ajmie.20220703.12},
  url = {https://doi.org/10.11648/j.ajmie.20220703.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmie.20220703.12},
  abstract = {Being greatly inspired by the natural flowing regulation of water, we propose a new meta-heuristic algorithm — Flowing Water Algorithm (FWA) for the solution of combinatorial optimization problems (COPs). Since the solution space of COPs is multidimensional, complex and has many local extreme values, according to our proposed method, it appears to be similar to an endless hilly area with mountains, valleys and plateaus. The downward-flowing water in such area finds its way to the lowest point in the hill. Water always flows downward and eventually converges at the lowest place without any outside intervention except for gravity. Such a flowing course can be deemed as a process for the water to seek for the lowest point. The proposed algorithm is derived from such a water flow process. This algorithm combines a local search strategy with a population-based search strategy to improve both local and global search abilities. Four operators, including the local search, water overflow, drilling water tunnel and evaporation-rain are included in FWA, making this algorithm successfully perform tabu search, positive feedback, “survival of the fittest”, and local optimum escape. Two examples of its application in the traveling salesman problem (TSP) show that FWA outperforms the benchmark methods for both solution quality and convergence speed.},
 year = {2022}
}

Copy | Download

TY  - JOUR
T1  - Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems
AU  - Xuepeng Liu
AU  - Qing Wang
AU  - An-Da Li
Y1  - 2022/08/24
PY  - 2022
N1  - https://doi.org/10.11648/j.ajmie.20220703.12
DO  - 10.11648/j.ajmie.20220703.12
T2  - American Journal of Mechanical and Industrial Engineering
JF  - American Journal of Mechanical and Industrial Engineering
JO  - American Journal of Mechanical and Industrial Engineering
SP  - 45
EP  - 52
PB  - Science Publishing Group
SN  - 2575-6060
UR  - https://doi.org/10.11648/j.ajmie.20220703.12
AB  - Being greatly inspired by the natural flowing regulation of water, we propose a new meta-heuristic algorithm — Flowing Water Algorithm (FWA) for the solution of combinatorial optimization problems (COPs). Since the solution space of COPs is multidimensional, complex and has many local extreme values, according to our proposed method, it appears to be similar to an endless hilly area with mountains, valleys and plateaus. The downward-flowing water in such area finds its way to the lowest point in the hill. Water always flows downward and eventually converges at the lowest place without any outside intervention except for gravity. Such a flowing course can be deemed as a process for the water to seek for the lowest point. The proposed algorithm is derived from such a water flow process. This algorithm combines a local search strategy with a population-based search strategy to improve both local and global search abilities. Four operators, including the local search, water overflow, drilling water tunnel and evaporation-rain are included in FWA, making this algorithm successfully perform tabu search, positive feedback, “survival of the fittest”, and local optimum escape. Two examples of its application in the traveling salesman problem (TSP) show that FWA outperforms the benchmark methods for both solution quality and convergence speed.
VL  - 7
IS  - 3
ER  -

Copy | Download

Author Information

Xuepeng Liu

School of Management, Tianjin University of Commerce, Tianjin, China
Qing Wang

School of Management, Tianjin University of Commerce, Tianjin, China
An-Da Li

School of Management, Tianjin University of Commerce, Tianjin, China

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Xuepeng Liu, Qing Wang, An-Da Li. (2022). Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems. American Journal of Mechanical and Industrial Engineering, 7(3), 45-52. https://doi.org/10.11648/j.ajmie.20220703.12

Copy | Download

ACS Style

Xuepeng Liu; Qing Wang; An-Da Li. Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems. Am. J. Mech. Ind. Eng. 2022, 7(3), 45-52. doi: 10.11648/j.ajmie.20220703.12

Copy | Download

AMA Style

Xuepeng Liu, Qing Wang, An-Da Li. Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems. Am J Mech Ind Eng. 2022;7(3):45-52. doi: 10.11648/j.ajmie.20220703.12

Copy | Download

@article{10.11648/j.ajmie.20220703.12,
  author = {Xuepeng Liu and Qing Wang and An-Da Li},
  title = {Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems},
  journal = {American Journal of Mechanical and Industrial Engineering},
  volume = {7},
  number = {3},
  pages = {45-52},
  doi = {10.11648/j.ajmie.20220703.12},
  url = {https://doi.org/10.11648/j.ajmie.20220703.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmie.20220703.12},
  abstract = {Being greatly inspired by the natural flowing regulation of water, we propose a new meta-heuristic algorithm — Flowing Water Algorithm (FWA) for the solution of combinatorial optimization problems (COPs). Since the solution space of COPs is multidimensional, complex and has many local extreme values, according to our proposed method, it appears to be similar to an endless hilly area with mountains, valleys and plateaus. The downward-flowing water in such area finds its way to the lowest point in the hill. Water always flows downward and eventually converges at the lowest place without any outside intervention except for gravity. Such a flowing course can be deemed as a process for the water to seek for the lowest point. The proposed algorithm is derived from such a water flow process. This algorithm combines a local search strategy with a population-based search strategy to improve both local and global search abilities. Four operators, including the local search, water overflow, drilling water tunnel and evaporation-rain are included in FWA, making this algorithm successfully perform tabu search, positive feedback, “survival of the fittest”, and local optimum escape. Two examples of its application in the traveling salesman problem (TSP) show that FWA outperforms the benchmark methods for both solution quality and convergence speed.},
 year = {2022}
}

Copy | Download

TY  - JOUR
T1  - Flowing Water Algorithm: A New Approach for Combinatorial Optimization Problems
AU  - Xuepeng Liu
AU  - Qing Wang
AU  - An-Da Li
Y1  - 2022/08/24
PY  - 2022
N1  - https://doi.org/10.11648/j.ajmie.20220703.12
DO  - 10.11648/j.ajmie.20220703.12
T2  - American Journal of Mechanical and Industrial Engineering
JF  - American Journal of Mechanical and Industrial Engineering
JO  - American Journal of Mechanical and Industrial Engineering
SP  - 45
EP  - 52
PB  - Science Publishing Group
SN  - 2575-6060
UR  - https://doi.org/10.11648/j.ajmie.20220703.12
AB  - Being greatly inspired by the natural flowing regulation of water, we propose a new meta-heuristic algorithm — Flowing Water Algorithm (FWA) for the solution of combinatorial optimization problems (COPs). Since the solution space of COPs is multidimensional, complex and has many local extreme values, according to our proposed method, it appears to be similar to an endless hilly area with mountains, valleys and plateaus. The downward-flowing water in such area finds its way to the lowest point in the hill. Water always flows downward and eventually converges at the lowest place without any outside intervention except for gravity. Such a flowing course can be deemed as a process for the water to seek for the lowest point. The proposed algorithm is derived from such a water flow process. This algorithm combines a local search strategy with a population-based search strategy to improve both local and global search abilities. Four operators, including the local search, water overflow, drilling water tunnel and evaporation-rain are included in FWA, making this algorithm successfully perform tabu search, positive feedback, “survival of the fittest”, and local optimum escape. Two examples of its application in the traveling salesman problem (TSP) show that FWA outperforms the benchmark methods for both solution quality and convergence speed.
VL  - 7
IS  - 3
ER  -

Copy | Download