Abstract
Designing optimal water supply systems is an important purpose of any urban system that involves relevant installation, operation and maintenance costs. However, achieving the optimal design is known to be a complex task, indeed the corresponding mathematical model for this problem leads to a non-linear and non-convex problem classified as NP-hard. In this paper, we propose using the cuckoo search algorithm which a modern bio-inspired metaheuristic based on the obligate brood parasitic behavior of cuckoo birds. This behavior is combined with the interesting Lévy flight, which mimic the exploration of some birds and flies, that move by combining straight flights and ninety degrees turns. The proposed approach results in a fast convergence algorithm able to noticeably reduce the number of objective function evaluations needed to solve this problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Reynolds, A.M., Frye, M.A.: Free-flight odor tracking in drosophila is consistent with an optimal intermittent scale-free search. PLoS ONE 2(4), e354 (2007)
Baños, R., Gil, C., Reca, J., Montoya, F.G.: A memetic algorithm applied to the design of water distribution networks. Appl. Soft Comput. 10(1), 261–266 (2010)
Crawford, B., Soto, R., Monfroy, E., Palma, W., Castro, C., Paredes, F.: Parameter tuning of a choice-function based hyperheuristic using particle swarm optimization. Expert Syst. Appl. 40(5), 1690–1695 (2013)
Cunha, M., Sousa, J.: Water distribution network design optimization: simulated annealing approach. J. Water Resour. Plann. Manage. 125(4), 215–221 (1999)
Dandy, G., Simpson, A., Murphy, L.: An improved genetic algorithm for pipe network optimization. Water Resour. Res. 32(2), 449–458 (1996)
Eusuff, M., Lansey, K.: Optimization of water distribution network design using the shuffled frog leaping algorithm. J. Water Resour. Plan. Manage. ASCE 129(3), 210–225 (2003)
Geem, Z.W.: Optimal cost design of water distribution networks using harmony search. Eng. Optim. 38(3), 259–277 (2006)
Gupta, I., Gupta, A., Khanna, P.: Genetic algorithm for optimization of water distribution systems. Environ. Modell. Softw. 14(5), 437–446 (1999)
Halhal, D., Walters, G., Ouazar, D., Savic, D.: Water network rehabilitation with structured messy genetic algorithms. J. Water Resour. Plan. Manage. 123(3), 137–146 (1997)
Jacoby, S.L.S.: Design of optimal hydraulic networks. J. Hydraul. Div. 94(3), 641–661 (1968)
Keedwell, E., Khu, S.-T.: A hybrid genetic algorithm for the design of water distribution networks. Eng. Appl. AI 18(4), 461–472 (2005)
Lin, M., Liu, Y., Liu, G., Chu, C.: Scatter search heuristic for least-cost design of water distribution networks. Eng. Optim. 39(7), 857–876 (2007)
Maier, H., Simpsom, A., Zecchin, A., Foong, W., Phang, K., Seah, H., Tan, C.: Ant colony optimization for the design of water distribution systems. J. Water Resour. Plan. Manage. ASCE 129(3), 200–209 (2003)
Monfroy, E., Castro, C., Crawford, B., Soto, R., Paredes, F., Figueroa, C.: A reactive and hybrid constraint solver. J. Exp. Theoret. Artif. Intell. 25(1), 1–22 (2013)
Montalvo, I., Izquierdo, J., Pérez, R., Tung, M.M.: Particle swarm optimization applied to the design of water supply systems. Comput. Math. Appl. 56(3), 769–776 (2008)
Montalvo, I., Izquierdo, J., Pérez-García, R., Herrera, M.: Improved performance of PSO with self-adaptive parameters for computing the optimal design of water supply systems. Eng. Appl. AI 23(5), 727–735 (2010)
Ostfeld, A., Tubaltzev, A.: Ant colony optimization for least cost design and operation of pumping and operation of pumping water distribution systems. J. Water Resour. Plann. Manage. 134(2), 107–118 (2008)
Pavlyukevich, I.: Lévy flights, non-local search and simulated annealing. J. Comput. Phys. 226, 1830–1844 (2007)
Pitchai, R.: A model for designing water distribution pipe networks. Ph.D. thesis, Harvard University (1966)
Prasad, D., Park, N.: Multiobjective genetic algorithms for design of water distribution networks. J. Water Resour. Plan. Manage. 130(1), 73–82 (2004)
Quindry, G., Brill, E., Lienman, J.: Water distribution system design criteria. Technical report, Department of Civil Engineering, University of Illinois at Urbana-Champaign, Urbana, IL (1979)
Savic, D., Walters, G.: Genetic algorithms for least-cost design of water distribution networks. J. Water Resour. Plan. Manage. ASCE 123(2), 67–77 (1997)
Schaake, J., Lai, D.: Linear programming and dynamic programming applications to water distribution network design. Technical report 116, Hydrodynamics Laboratory, MIT, Cambridge, MA (1969)
Sedki, A., Ouazar, D.: Hybrid particle swarm optimization and differential evolution for optimal design of water distribution systems. Adv. Eng. Inf. 26(3), 582–591 (2012)
Shamir, U., Alperovits, E.: Design of optimal water distribution systems. Water Resour. Res. 13(6), 885–900 (1977)
Shlesinger, M.F.: Search research. Nature 443, 281–282 (2006)
Shlesinger, M.F., Zaslavsky, G.M., Frisch, U. (eds.): Lévy Flights and Related Topics in Phyics. Springer, Heidelberg (2007)
Simpson, A., Murphy, L., Dandy, G.: Genetic algorithms compared to other techniques for pipe optimisation. J. Water Resour. Plan. Manage. ASCE 120(4), 423–443 (1994)
Soto, R., Crawford, B., Galleguillos, C., Monfroy, E., Paredes, F.: A pre-filtered cuckoo search algorithm with geometric operators for solving sudoku problems. Sci. World J. 2014, 12 (2014). Article ID 465359
Suribabu, C.R.: Differential evolution algorithm for optimal design of water distribution networks. J. Hydroinf. 12(1), 66–82 (2010)
Suribabu, C.R., Neelakantan, T.R.: Design of water distribution networks using particle swarm optimization. J. Urban Water 3(2), 111–120 (2006)
Vairavamoorthy, K., Ali, M.: Water network rehabilitation with structured messy genetic algorithms. Comput. Aided Civil Infrastruct. Eng. 15(5), 374–382 (2000)
Yang, X.-S., Deb, S.: Cuckoo search via lévy flights. In: World Congress on Nature & Biologically Inspired Computing (NaBIC), pp. 210–214. IEEE (2009)
Yates, D.F., Templeman, A.B., Boffey, T.B.: The computational complexity of the problem of determining least capital cost designs for water supply networks. Eng. Optim. 7(2), 143–155 (1984)
Zecchin, A.C., Simpson, A.R., Maier, H.R., Leonard, M., Roberts, A.J., Berrisford, M.J.: Application of two ant colony optimisation algorithms to water distribution system optimisation. Math. Comput. Modell. 44(5–6), 451–468 (2006)
Acknowledgment
Ricardo Soto is supported by Grant CONICYT/FONDECYT/REGULAR/1160455. Broderick Crawford is supported by Grant CONICYT/FONDECYT/REGULAR/1171243. Rodrigo Olivares is supported by CONICYT/FONDEF/IDeA/ID16I10449, FONDECYT/STIC-AMSU/17STIC-03, FONDECYT/MEC/MEC80170097, and Postgraduate Grant Pontificia Universidad Católica de Valparaíso (INF - PUCV 2015–2018).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Soto, R., Crawford, B., Olivares, R., Castro, C., Escárate, P., Calderón, S. (2018). Cuckoo Search via Lévy Flight Applied to Optimal Water Supply System Design. In: Mouhoub, M., Sadaoui, S., Ait Mohamed, O., Ali, M. (eds) Recent Trends and Future Technology in Applied Intelligence. IEA/AIE 2018. Lecture Notes in Computer Science(), vol 10868. Springer, Cham. https://doi.org/10.1007/978-3-319-92058-0_37
Download citation
DOI: https://doi.org/10.1007/978-3-319-92058-0_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92057-3
Online ISBN: 978-3-319-92058-0
eBook Packages: Computer ScienceComputer Science (R0)