Estimation of distribution algorithm enhanced particle swarm optimization for water distribution network optimization

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.

Graphical abstract

Keywords

particle swarm optimization (PSO) / diversity control / estimation of distribution algorithm (EDA) / water distribution network (WDN) / premature convergence / hybrid strategy

References

[1] 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

[2] 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

[3] 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

[4] 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

[5] 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

[6] Vairavamoorthy K, Ali M. Optimal design of water distribution systems using genetic algorithms. Computer-Aided Civil and Infrastructure Engineering, 2000, 15(5): 374–382

[7] 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

[8] 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

[9] Qi X. Water Distribution Network Optimization: A Hybrid Approach. Dissertation for the Master Degree. Athens, Georgia: University of Georgia, 2013

[10] 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

[11] 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

[12] 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

[13] Kennedy J, Mendes R. Population structure and particle swarm performance. IEEE Congress on Evolutionary Computation, 2002, 1671–1676

[14] Li X. Niching without niching parameters: particle swarm optimization using a ring topology. IEEE Transactions on Evolutionary Computation, 2010, 14(1): 150–169

[15] 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

[16] Krink T, Vesterstrom J, Riget J. Particle swarm optimization with spatial particle extension. Proceedings of the Congress on Evolutionary Computation, 2002

[17] 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

[18] Angeline P. Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In: Proceedings of the Conference on Evolutionary Computation 1998, 1998, 601–610

[19] Zhou Y, Jin J. EDA-PSO—A new hybrid intelligent optimization algorithm. In: Proceedings of the Michigan University Graduate Student Symposium, 2006

[20] 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

[21] Kulkarni R V, 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

[22] El-Abd M, Kamel MS. Particle swarm optimization with varying bounds. In: Proceedings of IEEE congress on Evolutionary Computation. 2007, 4757–4761

[23] El-Abd M. Preventing premature convergence in a PSO and EDA hybrid. In: Proceedings IEEE congress on Evolutionary Computation. 2009, 3060–3066

[24] 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

[25] EPANET 2.0, 2002.

[26] 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

[27] Reca J, Martinez J, Gil C, Baños R. Application of several meta-heuristic techniques to the optimization of real looped water distribution networks. Water Resources Management, 2008, 22(10): 1367–1379

[28] Reca J, Martínez J. Genetic algorithms for the design of looped irrigation water distribution networks. Water Resources Research, 2006, 42(5): W05416

[29] 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

[30] Geem Z W. Optimal cost design of water distribution networks using harmony search. Engineering Optimization, 2006, 38(3): 259–280

[31] Geem Z W. Particle-swarm harmony search for water networks design. Engineering Optimization, 2009, 41(4): 297–311

[32] 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

[33] 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

[34] 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

[35] 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

Acknowledgments

This work was supported by the National Science Foundation Award 0836046. The opinions expressed in this paper are solely those of the authors, and do not necessarily reflect the views of the funding agency.

Supplementary materialis available in the online version of this article at http://dx.doi.org/ 10.1007/s11783-015-0776-z and is accessible for authorized users.

RIGHTS & PERMISSIONS

2015 Higher Education Press and Springer-Verlag Berlin Heidelberg