×

zbMATH — the first resource for mathematics

Application of two ant colony optimisation algorithms to water distribution system optimisation. (English) Zbl 1171.90578
Summary: Water distribution systems (WDSs) are costly infrastructure in terms of materials, construction, maintenance, and energy requirements. Much attention has been given to the application of optimisation methods to minimise the costs associated with such infrastructure. Historically, traditional optimisation techniques have been used, such as linear and non-linear programming, but within the past decade the focus has shifted to the use of heuristics derived from nature (HDNs), for example Genetic Algorithms, Simulated Annealing and more recently Ant Colony Optimisation (ACO). ACO, as an optimisation process, is based on the analogy of the foraging behaviour of a colony of searching ants, and their ability to determine the shortest route between their nest and a food source. Many different formulations of ACO algorithms exist that are aimed at providing advancements on the original and most basic formulation, Ant System (AS). These advancements differ in their utilisation of information learned about a search-space to manage two conflicting aspects of an algorithm’s searching behaviour. These aspects are termed ‘exploration’ and ‘exploitation’. Exploration is an algorithm’s ability to search broadly through the problem’s search space and exploitation is an algorithm’s ability to search locally around good solutions that have been found previously. One such advanced ACO algorithm, which is implemented within this paper, is the Max-Min Ant System (MMAS). This algorithm encourages local searching around the best solution found in each iteration, while implementing methods that slow convergence and facilitate exploration. In this paper, the performance of MMAS is compared to that of AS for two commonly used WDS case studies, the New York Tunnels Problem and the Hanoi Problem. The sophistication of MMAS is shown to be effective as it outperforms AS and performs better than any other HDN in the literature for both case studies considered.

MSC:
90C90 Applications of mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
62P12 Applications of statistics to environmental and related topics
62P30 Applications of statistics in engineering and industry; control charts
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Schaake, D. Lai, Linear programming and dynamic programming applications to water distribution network design, Research Report No. 116, Department of Civil Engineering, Massachusetts Institute of Technology, 1969
[2] Bhave, P.R.; Sonak, V.V., A critical study of the linear programming gradient method for optimal design of water supply networks, Water resources research, 28, 6, 1577-1584, (1992)
[3] Varma, K.V.K.; Narasimhan, S.; Bhallamudi, S.M., Optimal design of water distribution systems using an NLP method, Journal of environmental engineering, ASCE, 123, 4, 381-388, (1997)
[4] Colorni, A.; Dorigo, M.; Maffioli, F.; Maniezzo, V.; Righini, G.; Trubian, M., Heuristics from nature for hard combinatorial optimization problems, International transactions in operational research, 3, 1, 1-21, (1996) · Zbl 0863.90120
[5] Simpson, A.R.; Murphy, L.J.; Dandy, G.C., Genetic algorithms compared to other techniques for pipe optimisation, Journal of water resources planning and management ASCE, 120, 4, 423-443, (1994)
[6] Dandy, G.C.; Simpson, A.R.; Murphy, L.J., An improved genetic algorithm for pipe network optimization, Water resources research, 32, 2, 449-458, (1996)
[7] Savic, D.A.; Walters, G.A., Genetic algorithms for least-cost design of water distribution networks, Journal of water resources planning and management, ASCE, 123, 2, 67-77, (1997)
[8] Lippai, I.; Heany, P.P; Laguna, M., Robust water system design with commercial intelligent search optimizers, Journal of computing in civil engineering, ASCE, 13, 3, 135-143, (1999)
[9] Wu, Z.Y.; Boulos, P.F.; Orr, C.H.; Ro, J.J., Using genetic algorithms to rehabilitate distribution system, Journal for American water works association, 74-85, (2001)
[10] Cunha, M.; Sousa, J., Water distribution network design optimization: simulated annealing approach, Journal of water resources planning and management, ASCE, 125, 4, 215-221, (1999)
[11] Eusuff, M.M.; Lansey, K.E., Optimisation of water distribution network design using the shuffled frog leaping algorithm, Journal of water resources planning and management, 129, 3, 210-225, (2003)
[12] Maier, H.R.; Simpson, A.R.; Zecchin, A.C.; Foong, W.K.; Phang, K.Y.; Seah, H.Y.; Tan, C.L., Ant colony optimization for the design of water distribution systems, Journal of water resources planning and management, ASCE, 129, 3, 200-209, (2003)
[13] Zecchin, A.C.; Simpson, A.R.; Maier, H.R.; Nixon, J.B., Parametric study for an ant algorithm applied to water distribution system optimisation, IEEE transactions on evolutionary computation, 9, 2, 175-191, (2005)
[14] Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: optimisation by a colony of cooperating agents, IEEE transactions on systems, man, and cybernetics. part B, cybernetics, 26, 1, 29-41, (1996)
[15] Dorigo, M.; Di Caro, G.; Gambardella, L.M., Ant algorithms for discrete optimization, Artificial life, 5, 2, 137-172, (1999)
[16] Stützle, T.; Hoos, H.H., MAX-MIN ant system, Future generation computer systems, 16, 889-914, (2000)
[17] Dorigo, M.; Bonabeau, E.; Therulaz, G., Ant algorithms and stigmergy, Future generation computer systems, 16, 851-871, (2000)
[18] Coello Coello, C.A., Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art, Computer methods in applied mechanics and engineering, 191, 1245-1287, (2002) · Zbl 1026.74056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.