Abstract
The optimization of a water distribution network (WDN) is a highly nonlinear, multi-modal, and constrained combinatorial problem. Particle swarm optimization (PSO) has been shown to be a fast converging algorithm for WDN optimization. An improved estimation of distribution algorithm (EDA) using historic best positions to construct a sample space is hybridized with PSO both in sequential and in parallel to improve population diversity control and avoid premature convergence. Two water distribution network benchmark examples from the literature are adopted to evaluate the performance of the proposed hybrid algorithms. The experimental results indicate that the proposed algorithms achieved the literature record minimum (6.081 M$) for the small size Hanoi network. For the large size Balerma network, the parallel hybrid achieved a slightly lower minimum (1.921M€) than the current literature reported best minimum (1.923M€). The average number of evaluations needed to achieve the minimum is one order smaller than most existing algorithms. With a fixed, small number of evaluations, the sequential hybrid outperforms the parallel hybrid showing its capability for fast convergence. The fitness and diversity of the populations were tracked for the proposed algorithms. The track record suggests that constructing an EDA sample space with historic best positions can improve diversity control significantly. Parallel hybridization also helps to improve diversity control yet its effect is relatively less significant.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Walski T M. State-of-the-art: pipe network optimization. In: Toeno H C, ed. Computer Applications in Water Resources, ASCE, New York, 1985, 559–568
Fujiwara O, Jenchaimahakoon B, Edirishinghe N C P. A modified linear programming gradient method for optimal design of looped water distribution networks. Water Resources Research, 1987, 23(6): 977–982
Kessler A, Shamir U. Analysis of the linear programming gradient method for optimal design of water supply networks. Water Resources Research, 1989, 25(7): 1469–1480
Walters G A, Cembrowicz R G. Optimal design of water distribution networks. In: Cabrera E and Martinez F, eds.Water Supply Systems, State-of-the-Art And Future Trends. Computational Mechanics Inc., 1993, 91–117
Simpson A R, Dandy G C, Murphy L J. Genetic algorithms compared to other techniques for pipe optimization. Journal of Water Resources Planning and Management, 1994, 120(4): 423–443
Vairavamoorthy K, Ali M. Optimal design of water distribution systems using genetic algorithms. Computer-Aided Civil and Infrastructure Engineering, 2000, 15(5): 374–382
Kadu M S, Gupta R, Bhave P R. Optimal design of water networks using a modified genetic algorithm with reduction in search space. Journal of Water Resources Planning and Management, 2008, 134(2): 147–160
Montalvo I, Izquierdo J, Pérez R, Tung M M. Particle swarm optimization applied to the design of water supply systems. Computers & Mathematics with Applications (Oxford, England), 2008, 56(3): 769–776
Qi X. Water Distribution Network Optimization: A Hybrid Approach. Dissertation for the Master Degree. Athens, Georgia: University of Georgia, 2013
Eberhart R C, Shi Y. Comparison Between Genetic Algorithms and Particle Swarm Optimization, Evolutionary Programming VII, Lecture Notes in Computer Science: Springer, 1998, 611–616
Chen M R, Li X, Zhang X, Lu Y Z. A novel particle swarm optimizer hybridized with extremal optimization. Applied Soft Computing, 2010, 10(2): 367–373
Qi X, Rasheed K, Li K, Potter D. A Fast Parameter Setting Strategy for Particle Swarm Optimization and Its Application in Urban Water Distribution Network Optimal Design, The 2013 International Conference on Genetic and Evolutionary Methods (GEM), 2013
Kennedy J, Mendes R. Population structure and particle swarm performance. IEEE Congress on Evolutionary Computation, 2002, 1671–1676
Li X. Niching without niching parameters: particle swarm optimization using a ring topology. IEEE Transactions on Evolutionary Computation, 2010, 14(1): 150–169
Kennedy J. Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance. Proceedings of the 1999 Conference on Evolutionary Computation, 1999, 1931–1938
Krink T, Vesterstrom J, Riget J. Particle swarm optimization with spatial particle extension. Proceedings of the Congress on Evolutionary Computation, 2002
Monson C K, Seppi K D. Adaptive diversity in PSO. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO’06), ACM, New York, NY, USA, 2006, 59–66
Angeline P. Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In: Proceedings of the Conference on Evolutionary Computation 1998, 1998, 601–610
Zhou Y, Jin J. EDA-PSO-A new hybrid intelligent optimization algorithm. In: Proceedings of the Michigan University Graduate Student Symposium, 2006
Iqbal M, Montes de Oca M A. An estimation of distribution particle swarm optimization algorithm. In: Proceedings of the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, 2006
Kulkarni RV, Venayagamoorthy G K. An estimation of distribution improved particle swarm optimization algorithm. In: 3rd International Conference on Intelligent Sensors, Sensor Networks and Information, 2007, 539–544
El-Abd M, Kamel MS. Particle swarm optimization with varying bounds. In: Proceedings of IEEE congress on Evolutionary Computation. 2007, 4757–4761
El-Abd M. Preventing premature convergence in a PSO and EDA hybrid. In: Proceedings IEEE congress on Evolutionary Computation. 2009, 3060–3066
Ahn C W, An J, Yoo J C. Estimation of particle swarm distribution algorithms: combining the benefits of PSO and EDAs. Information Sciences, 2012, 192: 109–119
EPANET 2.0, 2002. http://www.epa.gov/nrmrl/wswrd/epanet.html
Fujiwara O, Khang D B. A two-phase decomposition method for optimal design of looped water distribution networks. Water Resources Research, 1991, 27(5): 985–986
Reca J, Martinez J, Gil C, Baños R. Application of several metaheuristic techniques to the optimization of real looped water distribution networks. Water Resources Management, 2008, 22(10): 1367–1379
Reca J, Martínez J. Genetic algorithms for the design of looped irrigation water distribution networks. Water Resources Research, 2006, 42(5): W05416
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. Mathematical and Computer Modelling, 2006, 44(5–6): 451–468
Geem Z W. Optimal cost design of water distribution networks using harmony search. Engineering Optimization, 2006, 38(3): 259–280
Geem Z W. Particle-swarm harmony search for water networks design. Engineering Optimization, 2009, 41(4): 297–311
Bolognesi A, Bragalli C, Marchi A, Artina S. Genetic Heritage Evolution by Stochastic Transmission in the optimal design of water distribution networks. Advances in Engineering Software, 2010, 41(5): 792–801
Tolson B A, Asadzadeh M, Maier H R, Zecchin A C. Hybrid discrete dynamically dimensioned search (HD-DDS) algorithm for water distribution system design optimization. Water Resources Research, 2009, 45(12): W12416
Zheng F F, Simpson A R, Zecchin A C. A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems.Water Resources Research, 2011, 47(8): W08531
Baños R, Gil C, Reca J, Montoya G G. A memetic algorithm applied to the design of water distribution networks. Applied Soft Computing, 2010, 10(1): 261–266
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Rights and permissions
About this article
Cite this article
Qi, X., Li, K. & Potter, W.D. Estimation of distribution algorithm enhanced particle swarm optimization for water distribution network optimization. Front. Environ. Sci. Eng. 10, 341–351 (2016). https://doi.org/10.1007/s11783-015-0776-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11783-015-0776-z