Application of two ant colony optimisation algorithms to water distribution system optimisation

Abstract

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. © 2005 Elsevier Ltd. All rights reserved.