Max-min ant system applied 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 Evolutionary Algorithms, for example Genetic Algorithms, Simulated Annealing and more recently Ant Colony Optimisation (ACO). Advancements on the basic formulation of ACO have been developed, these advancements differ from one another in their utilisation of information learned about the search-space to manage the trade-off between exploitation and exploration in the algorithms searching behaviour. Exploration is the algorithms ability to search broadly through the problems search space and exploitation is the algorithms ability to search locally around good solutions that have been previously found. One such advanced ACO algorithm, which is presented 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 to slow convergence and facilitate exploration. The performance of MMAS is compared to that of the most basic ACO formulation Ant System (AS) for two commonly used WDS case studies. The sophistication of MMAS is shown to be effective as it outperforms AS for both case studies and performs competitively in comparison to other algorithms in the literature.