A parameter free continuous ant colony optimization algorithm for the optimal design of storm sewer networks: constrained and unconstrained approach. (English) Zbl 1182.65087
Summary: This paper describes the application of the newly introduced continuous ant colony optimization algorithm (CACOA) to optimal design of sewer networks. Two alternative approaches to implement the algorithm is presented and applied to a storm sewer network in which the nodal elevations of the network are considered as the decision variables of the optimization problem.
In the first and unconstrained approach, a Gaussian probability density function is used to represent the pheromone concentration over the allowable range of each decision variable. The pheromone concentration function is used by each ant to randomly sample the nodal elevations of the trial networks. This method, however, will lead to solutions which may be infeasible regarding some or all of the constraints of the problem and in particular the minimum slope constraint.
In the second and constrained approach, known value of the elevation at downstream node of a pipe is used to define new bounds on the elevation of the upstream node satisfying the explicit constraints on the pipe slopes. Two alternative formulations of the constrained algorithm are used to solve a test example and the results are presented and compared with those of unconstrained approach. The methods are shown to be very effective in locating the optimal solution and efficient in terms of the convergence characteristics of the resulting algorithms. The proposed algorithms are also found to be relatively insensitive to the initial colony and size of the colony used compared to the original algorithm.
In the first and unconstrained approach, a Gaussian probability density function is used to represent the pheromone concentration over the allowable range of each decision variable. The pheromone concentration function is used by each ant to randomly sample the nodal elevations of the trial networks. This method, however, will lead to solutions which may be infeasible regarding some or all of the constraints of the problem and in particular the minimum slope constraint.
In the second and constrained approach, known value of the elevation at downstream node of a pipe is used to define new bounds on the elevation of the upstream node satisfying the explicit constraints on the pipe slopes. Two alternative formulations of the constrained algorithm are used to solve a test example and the results are presented and compared with those of unconstrained approach. The methods are shown to be very effective in locating the optimal solution and efficient in terms of the convergence characteristics of the resulting algorithms. The proposed algorithms are also found to be relatively insensitive to the initial colony and size of the colony used compared to the original algorithm.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C15 | Stochastic programming |
| 90C90 | Applications of mathematical programming |
Keywords:
constrained continuous ant colony optimization algorithm; explicit constraints; optimal design; storm water network; numerical examples; algorithm; convergenceSoftware:
avidaReferences:
| [1] | Abbaspour, K. C.; Schlin, R.; Van Genuchten, M. T.: Estimating unsaturated soil hydraulic parameters using ant colony optimization, Adv water resour 24, No. 8, 827-933 (2001) |
| [2] | Adami C. Introduction to artificial life. Santa Clara (CA): TELOS, The Electronic Library of Science; 1998. p. 1 – 15. |
| [3] | Afshar, M. H.: A new transition rule for ant colony optimisation algorithms: application to pipe network optimisation problems, Eng optim 37, No. 5, 525-540 (2005) |
| [4] | Afshar, M. H.: Improving the efficiency of ant algorithms using adaptive refinement: application to storm water network design, Adv water resour 29, 1371-1382 (2006) |
| [5] | Afshar, M. H.: Partially constrained ant colony optimization algorithm for the solution of constrained optimization problems: application to storm water network design, Adv water resour 30, 954-965 (2007) |
| [6] | Afshar, M. H.; Marino, M. A.: Application of an ant algorithm for layout optimization of tree networks, Eng optim 38, No. 3, 353-369 (2006) |
| [7] | Afshar, M. H.; Afshar, A.; Mariño, M. A.; Darbandi, A. A. S.: Hydrograph-based storm sewer design optimization by genetic algorithm, Can J civ eng 33, 319-325 (2006) |
| [8] | Bilchev, G.; Parmee, I. C.: The ant colony metaphor for searching continuous design spaces, Proceedings of the AISB workshop on evolutionary computation, LNCS 993, 25-39 (1995) |
| [9] | Burian, S. J.; Nix, S. J.; Durrans, S. R.; Pitt, R. E.; Fan, C. Y.; Field, R.: Historical development of wet-weather flow management, J water resour plan manage 125, No. 1, 3-13 (1999) |
| [10] | Dreo, J.; Siarry, P.: A new ant colony algorithm using the heterarchical concept aimed at optimization of multiminima continuous functions, , 216-221 (2002) |
| [11] | Dorigo, M.; Di Caro, G.: The ant colony optimization meta heuristic, New ideas in optimization, 11-32 (1999) |
| [12] | Dorigo, M.; Manielzo, V.; Colomi, A.: The ant system: optimization by a colony of cooperating ants, IEEE trans syst man cybem 26, 29-42 (1996) |
| [13] | Elimam, A. A.; Charalambous, C.; Ghobrial, F. H.: Optimum design of large sewer networks, J environ eng, ASCE 115, No. 6, 1171-1189 (1989) |
| [14] | Jun, L. Y.; Jun, W. T.: An adaptive ant colony system algorithm for continuous-space optimization problems, J zhejiang univ sci 4, No. 1, 40-46 (2003) |
| [15] | Guo, Y.; Walters, G. A.; Khu, S. T.; Keedwell, E.: A novel cellular automata based approach to storm sewer design, Eng optim 39, No. 3, 345-364 (2007) |
| [16] | Heaney JP, Wright LT, Sample D, Field R, Fan C-Y. Innovative methods for the optimization of gravity storm sewer design. In: Proceedings of the 8th international conference on urban storm drainage, Sydney, Australia; 1999. p. 1896 – 903. |
| [17] | Kulkarni, V. S.; Khanna, P.: Pumped wastewater collection systems optimization, J environ eng, ASCE 111, No. 5, 589-601 (1985) |
| [18] | Li, G.; Matthew, R. G. S.: New approach for optimization of urban drainage systems, J environ eng, ASCE 116, No. 5, 927-944 (1990) |
| [19] | Ling, C.; Jie, S.; Ling, O.; Hongjian, C.: A method for solving optimization problems in continuous space using ant colony algorithm, Lect notes comput sci 2463, 288-289 (2002) |
| [20] | Maier, H. R.; Simpson, A. R.; Zecchin, A. C.; Foong, W. K.; Phang, K. Y.; Seah, H. Y.: Ant colony optimization for design of water distribution systems, J water resour plan manage, ASCE 129, No. 3, 200-209 (2003) |
| [21] | Mays, L. W.; Wenzel, H. G.: Optimal design of multi-level branching sewer systems, Water resour res 12, No. 5, 913-917 (1976) |
| [22] | Miles, S. W.; Heaney, J. P.: Better than optimal method for designing drainage systems, J water resour plan manage, ASCE 114, No. 5, 477-499 (1988) |
| [23] | Monmarche, N.; Venturini, G.; Slimane, M.: On how pachycondyla apicalis ants suggest a new search algorithm, Future gener comput syst 16, 937-946 (2000) |
| [24] | Pitt R, Lilburn M, Durrans SR, Burian S, Nix S, Voorhees J, et al. Guidance manual for integrated wet weather flow (WWF) collection and treatment systems for newly urbanized areas (new WWF systems). Project report, EPA/600/X-99/XXX. Cincinnati (United States): US Environmental Protection Agency; 1999. |
| [25] | Pourtakdoust SH, Nobahari H. An extension of ant colony system to continuous optimization problems. In: ANTS Workshop; 2004. p. 294 – 301. |
| [26] | Robinson DK, Labadie JW. Optimal design of urban storm water drainage system. In: International symposium on urban hydrology, hydraulics, and sediment control. Lexington (KY): University of Kentucky; 1981. p. 145 – 56. |
| [27] | Simpson AR, Maier HR, Foong WK, Phang KY, Seah HY, Tan CL. Selection of parameters for Ant Colony Optimization applied to the optimal design of water distribution systems. In: Proceedings of the international congress on modelling and simulation, Canberra, Australia; 2001. p. 1931 – 6. |
| [28] | Stutzle, T.; Hoos, H. H.: MAX-MIN ant system, Future gener comput syst 16, 889-914 (2001) |
| [29] | Wodrich, M.; Bilchev, G.: Cooperative distributed search: the ant’s way, Control cybern, No. 3, 413-446 (1997) · Zbl 0890.90159 |
| [30] | Yuan B, Gallagher, M. Playing in continuous spaces: some analysis and extension of population-based incremental learning. In: Sarker R, et al., editors. Proceedings of congress of evolutionary computation (CEC); 2003. p. 443 – 50. |
| [31] | Zecchin AC, Maier HR, Simpson AR, Roberts A, Berrisford MJ, Leonard M. Max – Min ant system applied to water distribution system optimization. In: Modsim 2003 – international congress on modeling and simulation, vol. 2. Townsville, Australia: Modeling and Simulation Society of Australia and New Zealand Inc.; 2003. p. 795 – 800. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
