Parametric Study for an Ant Algorithm Applied to Water Distribution System Optimization
- 4 April 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 9 (2), 175-191
- https://doi.org/10.1109/tevc.2005.844168
Abstract
Much research has been carried out on the optimization of water distribution systems (WDSs). Within the last decade, the focus has shifted from the use of traditional optimization methods, such as linear and nonlinear programming, to the use of heuristics derived from nature (HDNs), namely, genetic algorithms, simulated annealing and more recently, ant colony optimization (ACO), an optimization algorithm based on the foraging behavior of ants. HDNs have been seen to perform better than more traditional optimization methods and amongst the HDNs applied to WDS optimization, a recent study found ACO to outperform other HDNs for two well-known case studies. One of the major problems that exists with the use of HDNs, particularly ACO, is that their searching behavior and, hence, performance, is governed by a set of user-selected parameters. Consequently, a large calibration phase is required for successful application to new problems. The aim of this paper is to provide a deeper understanding of ACO parameters and to develop parametric guidelines for the application of ACO to WDS optimization. For the adopted ACO algorithm, called AS/sub i-best/ (as it uses an iteration-best pheromone updating scheme), seven parameters are used: two decision policy control parameters /spl alpha/ and /spl beta/, initial pheromone value /spl tau//sub 0/, pheromone persistence factor /spl rho/, number of ants m, pheromone addition factor Q, and the penalty factor (PEN). Deterministic and semi-deterministic expressions for Q and PEN are developed. For the remaining parameters, a parametric study is performed, from which guidelines for appropriate parameter settings are developed. Based on the use of these heuristics, the performance of AS/sub i-best/ was assessed for two case studies from the literature (the New York Tunnels Problem, and the Hanoi Problem) and an additional larger case study (the Doubled New York Tunnels Problem). The results show that AS/sub i-best/ achieves the best performance presented in the literature, in terms of efficiency and solution quality, for the New York Tunnels Problem. Although AS/sub i-best/ does not perform as well as other algorithms from the literature for the Hanoi Problem (a notably difficult problem), it successfully finds the known least cost solution for the larger Doubled New York Tunnels Problem.Keywords
This publication has 27 references indexed in Scilit:
- 10.1029/89WR02879Water Resources Research, 2010
- Parametric Study for an Ant Algorithm Applied to Water Distribution System OptimizationIEEE Transactions on Evolutionary Computation, 2005
- Evolutionary Programming Using Mutations Based on the LÉvy Probability DistributionIEEE Transactions on Evolutionary Computation, 2004
- Society and civilization: an optimization algorithm based on the simulation of social behaviorIEEE Transactions on Evolutionary Computation, 2003
- Elitism-based compact genetic algorithmsIEEE Transactions on Evolutionary Computation, 2003
- Ant colony system: a cooperative learning approach to the traveling salesman problemIEEE Transactions on Evolutionary Computation, 1997
- An Improved Genetic Algorithm for Pipe Network OptimizationWater Resources Research, 1996
- Ant system: optimization by a colony of cooperating agentsIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996
- Heuristics from Nature for Hard Combinatorial Optimization ProblemsInternational Transactions in Operational Research, 1996
- Global optimum tree solution for single‐source looped water distribution networks subjected to a single loading patternWater Resources Research, 1993