Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm
Publication: Journal of Water Resources Planning and Management
Volume 129, Issue 3
Abstract
Shuffled Frog Leaping Algorithm (SFLA) is a meta-heuristic for solving discrete optimization problems. Here it is applied to determine optimal discrete pipe sizes for new pipe networks and for network expansions. SFLA is a population based, cooperative search metaphor inspired by natural memetics. The algorithm uses memetic evolution in the form of infection of ideas from one individual to another in a local search. The local search is similar in concept to particle swarm optimization. A shuffling strategy allows for the exchange of information between local searches to move toward a global optimum. This paper summarizes the development of SFLANET, a computer model that links SFLA and the hydraulic simulation software EPANET and its library functions. Application of SFLANET to literature network design problems is then described. Although the algorithm is in its initial stages of development, promising results were obtained.
Get full access to this article
View all available purchase options and get full access to this article.
References
Alperovits, E., and Shamir, U.(1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
Bhave, P.(1985). “Optimal expansion of water distribution systems.” J. Environ. Eng., 111(2), 177–197.
Bhave, P. R., and Sonak, V. V.(1992). “A critical study of the linear programming gradient method of optimal design of water supply networks.” Water Resour. Res., 28(6), 1577–1584.
Chiplunkar, A. V., Mehndiratta, S. L., and Khanna, P.(1986). “Looped water distribution system optimization for a single loading.” J. Environ. Eng., 112(2), 264–279.
Cunha, M., and Sousa, J.(1999). “Water distribution network design optimization: Simulated annealing approach.” J. Water Resour. Plann. Manage. Div., Am. Soc. Civ. Eng., 125(4), 215–221.
Dandy, G. C., Simpson, A. R., and Murphy, L. J.(1996). “An improved genetic algorithm for pipe network optimization.” Water Resour. Res., 32(2), 449–458.
Dawkins, R. (1976). The selfish gene, Oxford University Press, New York.
Duan, Q., Sorooshian, S., and Gupta, V.(1992). “Effective and efficient global optimization for conceptual rainfall-runoff models.” Water Resour. Res., 28(4), 1015–1031.
Eberhart, R. C., and Kennedy, J. (1995). “A new optimizer using particlesswarm theory.” Proc., 6th Int. Symposium on Micro Machine and Human Science (Nagoya, Japan), IEEE Service Center, Piscataway, N.J., 39–43.
Eiger, G., Shamir, U., and Ben-Tal, A.(1994). “Optimal design of water distribution networks.” Water Resour. Res., 30(9), 2637–2646.
El-Bahrawy, A., and Smith, A. A.(1985). “Application of MINOS to water collection and distribution networks.” Civ. Eng. Sys., 2(1), 38–49.
El-Bahrawy, A., and Smith, A. A.(1987). “A methodology for optimal design of pipe distribution networks.” Can. J. Civ. Eng., 14, 207–215.
Eusuff, M. M., and Lansey, K. E. (2000). “Shuffled frog leaping algorithm: a memetic meta-heuristic for combinatorial optimization.” J. Heuristics, in press.
Featherstone, R., and El-Jumaily, K.(1983). “Optimal diameter selection for pipe networks.” J. Hydraul. Eng., 109(2), 221–234.
Fujiwara, O., Jenchaimahakoon, B., and Edirisinghe, N. C. P.(1987). “A modified linear programming gradient method for optimal design of looped water distribution networks.” Water Resour. Res., 23(6), 977–982.
Fujiwara, O., and Khang, D. B.(1990). “A two-phase decomposition method for optimal design of looped water distribution networks.” Water Resour. Res., 26(4), 539–549.
Gessler, J. (1985). “Pipe network optimization by enumeration.” Proc., Special Conf. on Computer Applications/Water Resources, ASCE, New York, 572–581.
Goulter, I. C., Lussier, B. M., and Morgan, D. R.(1986). “Implications of head loss path choice in the optimization of water distribution networks.” Water Resour. Res., 22(5), 819–822.
Gupta, I., Gupta, A., and Khanna, P.(1999). “Genetic algorithm for optimization of water distribution systems.” J. Environ. Model. Software, 437–446.
Hadji, G., and Murphy, L. J. (1990). “Genetic algorithms in for pipe network optimization.” 4th Year Student Civil Engineering Research Rep., Univ. of Adelaide, Adelaide, Australia.
Kessler, A., and Shamir, U.(1989). “Analysis of the linear programming gradient method for optimal design of water supply networks.” Water Resour. Res., 25(7), 1469–1480.
Kessler, A., and Shamir, U.(1991). “Decomposition technique for optimal design of water supply networks.” Eng. Optimiz., 17(1), 1–19.
Lansey, K. E., and Mays, L. W. (1989). “Optimization model for design of water distribution systems.” Reliability analysis of water distribution systems, L. R. Mays, ed., ASCE, Reston, Va.
Lippai, I., Heaney, J. P., and Laguna, M.(1999). “Robust water system design with commercial intelligent search optimizers.” J. Comput. Civ. Eng., 13(3), 135–143.
Loganathan, G. V., Greene, J. J., and Ahn, T. J.(1995). “Design heuristic for globally minimum cost water-distribution systems.” J. Water Resour. Plann. Manage. Div., Am. Soc. Civ. Eng., 121(2), 182–192.
Monbaliu, J., Jo, J. H., Fraisse, C. W., and Vadas, R. G. (1990). “Computer aided design of pipe networks.” Water resources systems application, S. P. Simonovic, I. C. Goulter, and B. J. Lence, eds., Friesen Printers, Winnipeg, Canada.
Morgan, G. R., and Goulter, I. C.(1985). “Optimal urban water distribution design.” Water Resour. Res., 21(5), 642–652.
Murphy, L. J., and Simpson, A. R. (1992). “Genetic algorithms in pipe network optimization.” Research Rep. No. R93, Dept. of Civil and Environmental Engineering, Univ. of Adelaide, Australia.
Murphy, L. J., Simpson, A. R., and Dandy, G. C. (1993). “Pipe network optimization using an improved genetic algorithm.” Research Rep. No. R109, Dept. of Civil and Environmental Engineering, Univ. of Adelaide, Australia.
Quindry, G. E., Brill, E. D., and Liebman, J. C.(1981). “Optimization of looped water distribution systems.” J. Environ. Eng. Div., Am. Soc. Civ. Eng., 107(4), 665–679.
Rossman, L. A. (2000). EPANET, User’s Manual. U.S. Environmental Protection Agency, Cincinnati.
Savic, D. A., and Walters, G. A.(1997). “Genetic algorithms for least-cost design of water distribution networks.” J. Water Resour. Plann. Manage. Div., Am. Soc. Civ. Eng., 123(2), 67–77.
Schaake, J. C., and Lai, D. (1969). “Linear programming and dynamic programming application to water distribution network design.” Rep. 116, Dept. of Civil Engineering, Massachusetts Institute of Technology, Cambridge, Mass.
Shamir, U.(1974). “Optimal design and operation of water distribution systems.” Water Resour. Res., 10(1), 27–35.
Simpson, A. R., Dandy, G. C., and Murphy, L. J.(1994). “Genetic algorithms compared to other techniques for pipe optimization.” J. Water Resour. Plann. Manage. Div., Am. Soc. Civ. Eng., 120(4), 423–443.
Su, Y. L., Mays, L. W., Duan, N., and Lansey, K. E.(1987). “Reliability-based optimization model for water distribution systems.” J. Hydraul. Eng., 113(12), 1539–1556.
Walters, G. A., and Cembrowicz, R. G. (1993). “Optimal design of water distribution networks.” Water supply systems, state-of-the-art and future trends, E. Cabrera and F. Martinez, eds., Computational Mechanics Inc., Southampton, England, 91–117.
Information & Authors
Information
Published In
Copyright
Copyright © 2003 American Society of Civil Engineers.
History
Received: Mar 6, 2001
Accepted: Feb 27, 2002
Published online: Apr 15, 2003
Published in print: May 2003
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.