Optimal Design of Water Distribution Systems using Agent Swarm Optimisation

Extended summary

Introduction

The need to make large investments for the construction and maintenance of economically efficient water supply networks means special attention must be paid to the design of such networks. The optimisation of design solutions that ensure proper operation of water distribution systems (WDS), taking into account the reliability of the network and the need to continue operations despite failures, is a major challenge for researchers and specialists working in the area. The aim is to obtain the greatest benefit for the least cost. 
Work objectives 

  Main objective:

•	Propose and implement an algorithm for the economically optimised design of a WDS that supports a multi-objective approach, is flexible (in terms of working with other algorithms), can be used to solve real problems, and is extendable to assimilate future challenges.
  Other objectives:
•	Study the formulation of economically optimal WDS design problems, examining elements related to the reliability of such systems.
•	Propose a formulation to assess economically feasible WDS designs, taking into account the reliability of such systems.
•	Study and modify as necessary the technique of evolutionary optimisation known as particle swarm optimisation (PSO) so that it can be applied to the design of WDS.  
•	Develop an algorithm with a multi-objective focus that can be extended to solve possible future challenges in the optimal design of WDS. 
•	Implement through a computer program the algorithm resulting from the combination of: a) the proposed multi-objective algorithm; b) the proposed formulation for the economic evaluation of WDS designs; and c) a simulator that shows the hydraulic performance of the solutions under various load and operating conditions.
•	Evaluate the goodness of the proposed algorithm through its application in cases from the literature and real WDS designs.

Observations

The WDS optimisation problem can be defined as the combination of minimising cost in the layout and design of new components, rehabilitation, or replacement of existing components, and operating the entire system with a view to satisfying water demands and design constraints, even under certain fault conditions. In practice, this optimisation can take many forms because several types of components can be found in distribution systems and the performance criteria and designs for such systems vary. Moreover, unlike other optimisation problems, the feasibility of the solutions can be estimated only after the solution has been totally built, requiring the use of simulators to analyse the system under different states of load and operating conditions. The optimisation method employed should be able to deal satisfactorily with this unique feature.
The objective function used differs depending on the problem to be tackled (expansion, rehabilitation, new design, operation). There is no single objective function or functions that are definitely the most useful – even when the same problem is being addressed. This makes the use of optimisation techniques essential because they can be adapted directly to any objective function, and even consider several objectives simultaneously. 
One of the most difficult tasks facing researchers is to explicitly consider the reliability of the WDS within the solution process. Regardless of the optimisation technique used, the existence of nodes in the distribution network provides an increased difficulty for design methods that try to find the cheapest variant for initial investment (Templeman, 1982). These methods, by their very nature, seek to eliminate redundancy or ‘unnecessary’ nodes when searching for the most economically advantageous option and only consider the cost of items to be placed. This undoubtedly limits the operational reliability of the solutions. The explicit consideration of reliability within the optimisation methods that can be used to design WDS is one of the most difficult tasks facing researchers working in the area. Increased reliability of distribution networks can normally be obtained in a deterministic sense by providing redundancy in the nodes of a distribution network. In some cases, attempts have been made to solve the problem by introducing minimum allowable diameter pipes, in other words by introducing connective redundancy. However, this approach effectively guarantees that no pipe is removed, the capacitive redundancy in terms of having an adequate and independent flow to each node is not guaranteed, and the resulting network could operate as implicitly branched, (Martínez, 2010). These solutions remain controversial because there is no completely accurate method accepted by all specialists in the field. Several attempts have been made based on similar principles but with differing scopes and objectives. This work has taken a recently published formulation as a reference (Martínez, 2007) that better economically values the fact that nodes in a network offer greater reliability in operation.
Work has continued on the design of distribution networks using methodologies that enable economically acceptable solutions to be searched for after testing various variants that meet the design requirements and could logically be considered. In this sense, (Strafaci, 2001) proposes the modelling of distribution networks for making extensions to WDS where needed. Such extensions would be optimally designed from the modelling of various possible scenarios and the selection of the most suitable. When using an established modelling software, for example, EPANET (Rossman, 2000), users largely depend on their own experience in the task of finding satisfactory solutions within the scenarios being evaluated.   
Optimisation techniques have conditioned the way in which the problem of optimal design of WDS has been tackled over the years. Linear programming, for example, has led to the linearization of the objective function, while techniques based on gradient have meant that differentiability of the function has had to be guaranteed, or the problem has been divided into parts and applied only to differentiable terms. For many years, the problem was adapted to the optimisation technique used – consciously or unconsciously. During the last decade, many researchers have started using modern evolutionary optimisation techniques, leaving aside more traditional methods based on linear and nonlinear programming. In the field of water systems, genetic algorithms have been the most used (Savic y Walters, 1997; Wu y Simpson, 2001; Matías, 2003; Wu y Walski, 2005), although other techniques based on ant colonies (ant colony optimisation or ACO) (Zecchin et al., 2006; Montalvo et al., 2007a) have been used; as well as simulated annealing (Cunha y Sousa, 1999); shuffled complex evolution (Liong y Atiquzzama, 2004); harmony search (Geem, 2006); and particle swarm optimisation (PSO) based on the collective intelligence of systems of particles (Montalvo et al., 2008d; Montalvo et al., 2008e). The advantages of the growing use of evolutionary algorithms in the optimal design of WDS include:

1.	Evolutionary algorithms can deal with problems in a discrete manner, which unlike other optimisation methods, enables the use of commercial diameters in the design.
2.	Evolutionary algorithms only work with the information of the objective function and this prevents complications associated with the determination of the derivatives and other auxiliary information. 
3.	Evolutionary algorithms are generic optimisation procedures and can directly adapt to any objective function. 
4.	Because evolutionary algorithms work with a population of solutions various optimal solutions can be obtained, or many solutions can be obtained with a value near to the optimal objective function and this can be of great value from an engineering point of view.
5.	An analysis of systems with different loading conditions can be made within the optimal design process.

In this work we have used an evolutionary algorithm that has proven useful for solving the problem of optimal design of WDS; the algorithm is known as particle swarm optimisation (PSO) and was developed by Kennedy and Eberhart in 1995. It was inspired by the social behaviour of a group of migratory birds trying to reach an unknown destination. The algorithm simulates a flock of birds who communicate in flight. Each bird has personal intelligence, but can also communicate with the leading bird for reference information. In the simulation the birds evolve co-ordinately. The evolution of each bird is calculated from recent history, their personal perceptions, and the influence exerted on each bird by the leader. The process of exploring the search space is repeated from each new position that is reached until the termination condition of the algorithm is met. The movement is made in a multidimensional space with as many dimensions as decision variables in the problem. The position vector of a bird in that space represents a potential solution.
The PSO algorithm used has been modified for application to the optimal design of a WDS. The PSO variant shown in this document overcomes two of the classic problems of the algorithm: 1) the consideration of discrete variables, because of the different diameters involved in the design (Montalvo et al., 2008e); 2) the need to be able to add diversity in the population, enabling optimal or quasi-optimal solutions to be found more efficiently (Montalvo et al., 2008d). A smaller number of generations is essential for calculating real systems, especially when reliability is included, because a disproportionately large number of executions of the algorithm and hydraulic assessments would make a solution impossible. The result reflects the algorithm’s ability to convergence and its ability to provide better designs for water distribution systems.
In the same way as other evolutionary techniques, the PSO has a set of parameters, whose correct choice has a strong influence on the efficiency and convergence of the algorithm. Parameter setting represents an initial investment of resources, which sometimes results in tedious trial and error sessions, especially when there are no guidelines as to which values to use to solve a particular problem. This document presents a proposal in which the PSO algorithm self manages all of its parameters with the exception of population size, thus enabling the designer to ignore these tasks and concentrate on the design (Montalvo et al., 2010a).
In the optimal design of WDS, as in many other optimisation problems, objectives needing optimisation are often conflicting. Therefore, rather than finding a single solution it is more worthwhile finding a set of solutions that represent the best possible compromise between all the objectives involved. This technique develops proposals for evolutionary algorithms that can be used to solve a multi-objective approaches for the optimal design of WDS (Vamvakeridou-Lyroudia et al., 2005; Dandy y Engelhardt, 2006; Montalvo et al., 2010b). In this work we have made a generalisation of the PSO algorithm that enables, among other advances, the solution of optimisation problems with a multi-objective approach. This generalisation is orientated towards distributed artificial intelligence and based on multi-agent systems – and has been termed agent swarm optimisation (ASO). ASO takes advantage of the benefits of parallel and distributed computing to interact with various populations of agents that may have different behaviours. The algorithm offers a common platform of understanding for the plurality of current evolutionary algorithms. Its versatility gives rise to its greatest strength: the ability to introduce agents with specific behavioural rules for the best solution to a problem, and which work in conjunction with general evolutionary algorithms such as PSO, genetic algorithms, ant colony optimisation, etc. The concept of being able to introduce new agents in the solution process means that, in the case of designing water distribution systems, project managers form an active role as agents in searching for solutions (Montalvo et al., 2010c). This development means an end to the period in which project managers waited patiently for the computer results so that they could be subsequently analysed by human experts. Using ASO, human experts are also agents who can propose solutions and interact with other agents (human or otherwise) to find the best results for the proposed objectives. In this point, ASO differs from the multi-agent systems that can be found in the literature.
Major contributions

•	A generalisation of the PSO algorithm, called agent swarm optimisation (ASO), has been made that can be used in the optimal design of water distribution systems using a multi-objective approach.
•	Implementation of a software application based on the proposed optimisation algorithm that facilitates the design of water distribution systems. The application also enables the steady state analysis of previously designed systems.
•	The proposed algorithm has been successfully implemented on various current benchmarking examples and in real cases of WDS design. Several problems are raised and resolved in a multi-objective approach.
•	Graphs are presented that show the probability that good solutions are obtained with the proposed algorithm in several of the studied cases.
•	A formulation of the problem of optimal design of WDS is proposed that examines the economic reliability of such systems and works successfully with the optimisation algorithm presented.
•	Comparisons are made showing the advantages of considering reliability elements within the objective function.
Scientific contribution 
•	The developed ASO algorithm enables the integration of various algorithms and agents with rules for behaviour specifically designed to solve the optimisation problem in hand. 
•	Integration of various populations of agents with asynchronous behaviour for the construction of a Pareto frontier for multi-objective optimisation problems.
•	Introduction of specific rules for sizing pipes in WDS within the optimisation process.
•	Consideration of users as active agents involved in the process of ASO algorithm solutions. Project managers can propose in real-time potential solutions to the problem being solved. The algorithm’s artificial agents can take advantage of the creativity and ideas of human experts to improve their own solutions, while human experts can take advantage of the speed and ability of artificial agents to explore larger solution spaces.
Main conclusions
•	The optimal design approach to WDS has been conditioned over the years by the optimisation techniques employed.
•	The algorithm presented can be used in the optimal design of real water distribution systems that include one or more goals. There is complete freedom to use any objective function that may be expressed mathematically.
•	The successful use of a design problem formulation in combination with the use of evolutionary algorithms and agents with specific behavioural rules enables designs to be produced with a significant reliability and within a reasonable period of time.
•	A high level of diversity in the evolutionary algorithms used for solving optimisation problems substantially improves the probability of obtaining good solutions.
•	Self-management of parameters is very useful for the optimisation process, especially when there are no guidelines as to appropriate parameter values. This approach also avoids unnecessary and lengthy processes of sensitivity analysis, often carried out by absurd brute force processes.
•	Real-time interaction with users during the process of making design decisions and the display of approximate Pareto frontier marks a significant difference between the algorithm proposed in this research and other existing algorithms.

Recommendations for future work 

Future work should be aimed at introducing new agents with possibly more efficient rules of behaviour during solution searches. Additional examples of study designs should also be considered, making use of various ways to approach the objective function. As for the solutions obtained, it would be interesting to compare the reliability considered with the actual behaviour of the network. The way in which the objective function is considered is in itself an evolutionary process that must not stop and must be adapted to the requirements of time and place. The study of the current conditions and needs of WDS design must continue, and there must be a broad exchange with specialists to add improvements to the algorithm used, and the resulting software application. The implementation of the proposed algorithm must be updated using emerging technologies in parallel and distributed computing.