Abstract
The paper describes the development of a computer model GANET that involves the application of an area of evolutionary computing, better known as genetic algorithms, to the problem of least-cost design of water distribution networks. Genetic algorithms represent an efficient search method for nonlinear optimization problems; this method is gaining acceptance among water resources managers/planners. These algorithms share the favorable attributes of Monte Carlo techniques over local optimization methods in that they do not require linearizing assumptions nor the calculation of partial derivatives, and they avoid numerical instabilities associated with matrix inversion. In addition, their sampling is global, rather than local, thus reducing the tendency to become entrapped in local minima and avoiding dependency on a starting point. Genetic algorithms are introduced in their original form followed by different improvements that were found to be necessary for their effective implementation in the optimization of water distribution networks. An example taken from the literature illustrates the approach used for the formulation of the problem. To illustrate the capability of GANET to efficiently identify good designs, three previously published problems have been solved. This led to the discovery of inconsistencies in predictions of network performance caused by different interpretations of the widely adopted Hazen-Williams pipe flow equation in the past studies. As well as being very efficient for network optimization, GANET is also easy to use, having almost the same input requirements as hydraulic simulation models. The only additional data requirements are a few genetic algorithm parameters that take values recommended in the literature. Two network examples, one of a new network design and one of parallel network expansion, illustrate the potential of GANET as a tool for water distribution network planning and management.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Alperovits, E., and Shamir, U.(1977). “Design of optimal water distribution systems.”Water Resour. Res., 13(6), 885–900.
2.
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.
3.
Chiplunkar, A. V., Mehndiratta, S. L., and Khanna, P.(1985). “Looped water distribution system optimization for single loading.”J. Envir. Engrg., ASCE, 112(2), 264–279.
4.
de la Maza, M., and Tidor, B. (1993). “An analysis of selection procedures with particular attention paid to proportional and Boltzmann selection.”Proc., 5th Conf. of Genetic Algorithms, S. Forest, ed., Morgan Kaufmann Publishers, San Mateo, Calif., 124–131.
5.
Duan, N., Mays, L. W., and Lansey, K. E.(1990). “Optimal reliability-based design of pumping and distribution systems.”J. Hydr. Engrg., ASCE, 116(2), 249–268.
6.
Eiger, G., Shamir, U., and Ben-Tal, A.(1994). “Optimal design of water distribution networks.”Water Resour. Res., 30(9), 2637–2646.
7.
El-Bahrawy, A., and Smith, A. A.(1985). “Application of MINOS to water collection and distribution networks.”Civ. Engrg. Sys., 2(1), 38–49.
8.
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.
9.
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.
10.
Gessler, J. (1985). “Pipe network optimization by enumeration.”Proc., Spec. Conf. on Comp. Applications/Water Resour., ASCE, New York, N.Y., 572–581.
11.
Goldberg, D. E. (1983). “Computer-aided gas pipeline operation using genetic algorithms and rule learning,” PhD dissertation, Univ. of Michigan.
12.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Co., Reading, Mass.
13.
Goldberg, D. E., and Kuo, C. H.(1987). “Genetic algorithms in pipeline optimization,”J. Comp. in Civ. Engrg., 1(2), 128–141.
14.
Goulter, I. C.(1987). “Current and future use of systems analysis in water distribution network design.”Civ. Engrg. Sys., 4(4), 175–184.
15.
Goulter, I. C., and Morgan, D. R.(1985). “An integrated approach to the layout and design of water distribution networks.”Civ. Engrg. Sys., 2(2), 104–113.
16.
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.
17.
Grefenstette, J. J., and Baker, J. E. (1989). “How genetic algorithms work: a critical look at implicit parallelism,”Proc., 3rd Int. Conf. of Genetic Algorithms, J. D. Schaffer, ed., Morgan Kaufmann Publishers, San Mateo, Calif., 20–27.
18.
Hansen, C. T., Madsen, K., and Nielsen, H. B.(1991). “Optimization of pipe networks.”Math. Programming, 52(1), 45–58.
19.
Holland, J. H. (1975). Adaptation in natural and artificial systems. MIT Press, Cambridge, Mass.
20.
Jain, A. K., Mohan, D. M., and Khanna, P.(1978). “Modified Hazen-Williams formula.”J. Envir. Engrg. Div., ASCE, 104(1), 137–146.
21.
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.
22.
Kessler, A., and Shamir, U. (1991). “Decomposition technique for optimal design of water supply networks.”Engrg. Optimization, 17(1), 1–19.
23.
Michalewicz, Z. (1992). Genetic algorithms + data structures = evolutionary programs. Springer-Verlag, New York, Inc., New York, N.Y.
24.
Morgan, G. R., and Goulter, I. C.(1985). “Optimal urban water distribution design.”Water Resour. Res., 21(5), 642–652.
25.
Murphy, L. J., and Simpson, A. R. (1992). “Genetic algorithms in pipe network optimization.”Res. Rep. No. R93, Dept. of Civ. and Envir. Engrg., Univ. of Adelaide, Australia.
26.
Murphy, L. J., Simpson, A. R., and Dandy, G. C. (1993). “Pipe network optimization using an improved genetic algorithm.”Res. Rep. No. R109, Dept. of Civ. and Envir. Engrg., Univ. of Adelaide, Australia.
27.
Ormsbee, L. E., and Wood, D. J.(1986). “Hydraulic design algorithms for pipe networks.”J. Hydr. Engrg., ASCE, 112(12), 1195–1207.
28.
Quindry, G. E., Brill, E. D., and Liebman, J. C.(1981). “Optimization of looped water distribution systems.”J. Envir. Engrg., ASCE, 107(4), 665–679.
29.
Rossman, L. A. (1993). EPANET, users manual. U.S. Envir. Protection Agency, Cincinnati, Ohio.
30.
Savic, D. A., and Walters, G. A. (1994). “Genetic algorithms and evolution programs for decision support.” in Proc., 4th Int. Symp.: Advances in Logistics Sci. and Software, J. Knezevic, ed., Exeter, U.K., 72–80.
31.
Schaake, J., and Lai, D. (1969). “Linear programming and dynamic programming applications to water distribution network design.”Rep. 116, Dept. of Civ. Engrg., Massachusetts Inst. of Technol., Cambridge, Mass.
32.
Shamir, U., and Howard, C. D. D.(1968). “Water distribution systems analysis.”J. Hydr. Div., ASCE, 94(1), 219–234.
33.
Simpson, A. R., Dandy, G. C., and Murphy, L. J.(1994). “Genetic algorithms compared to other techniques for pipe optimization.”J. Water Resour. Plng. and Mgmt., ASCE, 120(4), 423–443.
34.
Sonak, V. V., and Bhave, P. R.(1993). “Global optimum tree solution for single-source looped water distribution networks subjected to a single loading pattern.”Water Resour. Res., 29(7), 2437–2443.
35.
Syswerda, G. (1989). “Uniform crossover in genetic algorithms.”Proc., 3rd Int. Conf. on Genetic Algorithms, J. D. Schaffer, ed., George Mason Univ., Arlington, Va., 2–9.
36.
Todini, E., and Pilati, S. (1987). “A gradient method for the analysis of pipe networks.”Proc., Int. Conf. on Comp. Applications for Water Supply and Distribution, Leicester Polytechnic, Leicester, U.K.
37.
Walski, T. M. (1984). Analysis of water distribution systems. Van Nostrand Reinhold Co., Inc., New York, N.Y.
38.
Walski, T. M. (1985). “State-of-the-art pipe network optimization.”Proc., Spec. Conf. on Comp. Applications/Water Resour., ASCE, New York, N.Y., 559–568.
39.
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 Publications, Southampton, 91–117.
40.
Walters, G. A., and Lohbeck, T.(1993). “Optimal layout of tree networks using genetic algorithms.”Engrg. Optimization, 22(1), 27–48.
41.
WATNET, analysis and simulation of water networks and a guide to the WATNET3 computer program. (1989). WRc Engineering, Swindon, U.K.
42.
Whitley, D. (1989). “The GENITOR algorithm and selection models and selection pressure: why rank-based allocation of reproductive trials is best.”Proc., 3rd Int. Conf. of Genetic Algorithms, J. D. Schaffer, ed., Morgan Kaufmann Publishers, San Mateo, Calif., 116–121.
43.
Wood, D. J. (1980). “Computer analysis of flow in pipe networks including extended period simulations.”Rep., Univ. of Kentucky, Lexington, Ky.
44.
Wood, D. J., and Funk, J. E. (1993). “Hydraulic analysis of water distribution systems,” in Water supply systems, state of the art and future trends, E. Cabrera and F. Martinez, eds., Computational Mechanics Publications, Southampton, 41–85.
45.
Yates, D. F., Templeman, A. B., and Boffey, T. B.(1984). “The computational complexity of the problem of determining least capital cost designs for water supply networks.”Engrg. Optimization, 7(2), 142–155.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 123 • Issue 2 • March 1997
Pages: 67 - 77
Copyright
Copyright © 1997 American Society of Civil Engineers.
History
Published online: Mar 1, 1997
Published in print: Mar 1997
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.