Description
A nontrivial multiobjective optimization problem, there does not exist a single solution that simultaneously optimizes each objective. In that case, the objective functions are said to be conflicting, and there exists a (possibly infinite number of) Pareto optimal solutions.
Single-objective vs. Multiobjective Optimisation for Integrated Decision Support
Dragan Savic Centre for Water Systems, Department of Engineering School of Engineering and Computer Science, sity of Exeter, United Kingdom, E-mail: [email protected] Univer-
Abstract: In many optimisation problems, analysts are often confronted with multiobjective decision problems. The most common purpose of an analysis is to choose the best trade-offs among all the defined and conflicting objectives. However, many optimisation studies are formulated as a problem whose goal is to find the “best” solution, which corresponds to the minimum or maximum value of a single objective function that lumps all different objectives into one. Water distribution system design is a multiobjective problem for which it is difficult to identify the true benefits and constraints due primarily to the uncertainty in future demands. This paper shows some shortcomings of the use of single-objective optimisation for water distribution system design and introduces a genetic algorithm multiobjective model that promises to ease the difficulties in applying optimisation and providing decision support for that important problem. The optimisation model used in this paper utilises simple and intuitive objectives and constraints that are not difficult to formulate in mathematical terms. Those objectives allow a decision-maker to visualise the trade-offs between different benefits and costs, and more importantly to consider uncertainty in future demands and performance levels. This type of optimisation could also take into account that the system needs to be implemented in stages. Keywords: optimisation, multiobjective, Pareto solutions, water distribution system, design 1. INTRODUCTION 1.1. Role of Optimisation As engineers and/or analysts, we are trying to find improved ways of coping with complexity, increasing the flexibility of the design and analysis processes, and empowering the modeller with advanced tools that integrate with other existing components of the analysis process, e.g. simulation models, standards, etc. All modellers like to think that they produce well-calibrated models or good safe designs that represent value for money. However, it is rare for a modeller to have the time or resources to consider more than a handful of solutions to a problem. In project planning there are often many alternatives for each individual component of a scheme. The number of different designs for a complete scheme can then be very large indeed, if not infinite. Even with detailed design, there are usually an enormous number of possibilities, far too many to be considered and evaluated individually. Clearly, if this is possible then optimisation is not needed! The main reason to rely on any model in a decision making process is to provide a quantitative assessment of the effects of management decisions on the system being considered. A model also provides a fairly objective assessment as opposed to subjective opinions of system behaviour. Thus, models should be used in support of decision making. Optimisation is just another type of modelling and the same applies to optimisation models. Optimisation tools should be used for supporting decisions rather than for making decisions, i.e. should not substitute decision-making process! 1.2. Single vs. Multiobjective Optimisation Many real-world decision making problems need to achieve several objectives: minimise risks, maximise reliability, minimise deviations from desired levels, minimise cost, etc. The main goal of single-
7
objective (SO) optimisation is to find the “best” solution, which corresponds to the minimum or maximum value of a single objective function that lumps all different objectives into one. This type of optimisation is useful as a tool which should provide decision makers with insights into the nature of the problem, but usually cannot provide a set of alternative solutions that trade different objectives against each other. On the contrary, in a multiobjective optimisation with conflicting objectives, there is no single optimal solution. The interaction among different objectives gives rise to a set of compromised solutions, largely known as the trade-off, nondominated, noninferior or Pareto-optimal solutions. The consideration of many objectives in the design or planning stages provides three major improvements to the procedure that directly supports the decision-making process [Cohon, 1978]: (1) A wider range of alternatives is usually identified when a multiobjective methodology is employed. (2) Consideration of multiple objectives promotes more appropriate roles for the participants in the planing and decision-making processes, i.e. “analyst” or “modeller”– who generates alternative solutions, and “decision maker” who uses the solutions generated by the analyst to make informed decisions. (3) Models of a problem will be more realistic if many objectives are considered. Single-objective optimisation identifies a single optimal alternative, however, it can be used within the multiobjective framework. This does not involve aggregating different objectives into a single objective function, but, for example, entails setting all except one of them as constraints in the optimisation process. Those objectives expressed as constraints are assigned different levels of attainment of their respective objective functions (e.g. minimum reliability levels) and several runs are performed to obtain solutions corresponding to different satisfaction of constraints. However, most design and planning problems are characterised by a large and often infinite number of alternatives. Thus, multiobjective methodologies are more likely to identify a wider range of these alternatives since they do not need to prespecify for which level of one objective a single optimal solution is obtained for another. A very simplified view of the decision-making process is that it involves two types of actors: analysts (modellers) and decision makers. This is a
crude simplification of the process since many stakeholders and actors may be involved, but simple enough to demonstrate shortcomings of assuming that in general one person can assume both (or many more) roles. Analysts are technically capable people who provide information about a problem to decision makers who decide which course of action to take. Modelling and optimisation techniques are tools which analysts may use to develop useful information for the decision makers. However, single-objective models require that all design objectives must be measurable in terms of a single fitness function. This in turn requires some a priori ordering of different objectives (i.e., a weighting scheme) to allow easy integration of them into a single function of same units. Thus, single-objective approaches place the burden of decision making squarely on the shoulders of the analyst. For example, it is the analyst who must decide the cost equivalent of a specific risk of failure. Even if the decision makers are technically capable and willing to provide some a priori preference information, the decision making role is taken away from them. By providing a trade-off curve between different objectives and alternative solutions corresponding to the points on this curve, multiobjective approaches allow for the responsibility of assigning relative values of the objectives to remain where it belongs: with the decision maker! 1.3. Water Distribution System Design Nowadays pipelines are the most common means for transporting water (potable and wastewater), gasses and oils necessary for everyday life in modern cities. The design, construction, operation and maintenance of millions of kilometres of these pipelines represent an immense challenge for engineers around the world. This paper concentrates on water networks as an element of urban settlement. The design of water distribution networks is often viewed as a single-objective, least-cost optimisation problem with pipe diameters acting as the primary decision variables. The optimisation problem of least-cost pipe sizing is a non-linear, discrete combinatorial optimisation problem. It is non-linear because the head-loss relationship and discrete because pipe diameters are produced in distinct diameters only. Optimal design problems of realistic size become intractable for enumeration techniques. This is because of the exponential growth of the problem size with the increase in number of discrete decisions (that is, the dimension of the problem), or
8
the so-called curse of dimensionality. This rather emotive term is used to describe difficulties in obtaining an optimal solution over many dimensions. The search for a solution in such a multidimensional space quickly becomes “lost” in the wealth of space when the dimensionality becomes too large. Water distribution system design optimisation is one of the most heavily researched areas in the hydraulics profession. Hundreds of papers and reports on approaches have been developed over the past few decades. Several reviews of the state-of-the-art in water distribution optimisation have been prepared over the years [Walski, 1985; Goulter, 1992; Lansey, 2000]. However, in spite of considerable development in the literature, the techniques have not been accepted in practice and Walski [2001] recently criticised most previous optimisation approaches for several practical reasons. The main ones being that (i) it is difficult for practitioners to define objective functions and constraints; (ii) there is not a single design flow for which the system should be designed, (iii) optimisation fails to account for the fact that a total distribution system is not built all at once, and (iv) optimisation tends to reduce costs by reducing the diameter of or completely eliminating pipes thus leaving the system with insufficient capacity to respond to pipe breaks or demands that exceed design values without failing to achieve required performance levels. This paper offers an alternative optimisation approach that tries to answer the questions raised by Walski [2001] by more appropriate use of optimisation within the multiobjective framework. 2. NEW YORK CITY TUNNELS PROBLEM
For 15 available diameters, i.e., 16 possible decisions including the ‘do nothing’ option, and 21 pipes to be considered for duplication, the total solution space is 1621 = 1.93×1025 possible network
Figure 1. New York Tunnel System designs. After this first study various researchers have optimised the NYCT problem using a singleobjective optimisation approach with the fixed pressure requirements, i.e., the objective function considered was:
f ( D1 ,..., Dn ) = ? c( Di , Li )
i =1 N
(1)
The New York City tunnels (NYCT) problem dates back to the late sixties when Schaake and Lai [1969] attempted to use linear programming optimisation to analyse the New York City water supply tunnels system. The City was looking to increase the capacity of its water supply system to meet future demands by adding one or more pipes to the existing network of 21 tunnels. The tunnel system layout is shown in Figure 1. Because of age and increased demands the then existing gravity flow tunnels have been found to be inadequate to meet the pressure requirements (nodes 16, 17, 18, 19 and 20 in Figure 1) for the projected consumption level. The proposed method of expansion was the same as in previous studies, i.e., to reinforce the system by constructing tunnels parallel to the existing ones.
where c(Di,Li) is the cost of the pipe i with the diameter Di and the length Li, and N is the total number of pipes in the system. The above function is minimised under the minimum pressure constraints:
H j ? H min j ; j = 1,..., M
(2)
where Hj is the head at node j, Hjmin is the minimum required head at the same node and M is the total number of nodes in the system. Savic and Walters [1997] give an overview of results obtained by different optimisation studies with costs in the range from $36.10M to $78.09M. However, the main objections raised by Walski [2001] apply to all of the solutions in that they were developed for a single objective (cost minimisation), where future demands are perfectly known and no
9
staging of decisions was assumed in any of the models. In addition, solutions that were close to feasibility, i.e. just below the required minimum pressure level were considered infeasible and did not allow any explicit trade-off analysis, e.g., between uncertainty and cost or capacity and cost. To examine trade-offs, the following additional objectives were identified: (i) minimise the number of nodes with pressure deficiencies, e.g., nodes where Hj < Hjmin; (ii) minimise the total head deficit across the network, e.g. sum of individual deficiencies; and (iii) maximise the capacity to deliver additional water. These objectives will be analysed in the section dealing with multiobjective solutions to the NYTC problem. 3. MULTIOBJECTIVE GA OPTIMISATION
The constraint method is an alternative framework for generating Pareto-optimal solutions. It operates by optimising one objective while all of the others are constrained to some value [Cohon, 1978]. The main disadvantage of both weighting and constraint methods is that not all of the points can be identified because the appropriate weights (or constraint levels) are not known in advance. These methods also suffer from high computational costs since the number of optimisation runs increases exponentially with the number of objectives. The need to identify as many solutions as possible within the Pareto-optimal range often represents a problem for standard generating techniques. By maintaining and continually improving a population of solutions, a genetic algorithm (GA) can search for many non-dominated solutions at the same time (in a single run), which makes it a very attractive tool for solving multiobjective optimisation problems GA is an adaptive search method that emulates nature’s evolution based on preferential survival, reproduction of the fittest members of the population, maintenance of a population with diverse members, inheritance of genetic material from parents, occasional mutation of genes, etc. [Goldberg, 1989]. Few multiobjective genetic algorithm (MOGA) approaches exist today [Veldhuizen and Lamont, 1998]. The first MOGA non-Pareto approach, Vector Evaluated Genetic Algorithm (VEGA), was proposed by Schaffer [1985]. Later, Goldberg [1989] introduced Pareto-ranking in his simple GA, in addition to standard selection, crossover and mutation operators. At each generation, members of the current population were ranked according to Pareto domination rules. By introducing Pareto domination ranking, the population was effectively divided into a number of subpopulations. However, Goldberg soon realised that Pareto ranking, on its own, does not guarantee that individuals will be uniformly distributed along the Pareto optimal front. In order to maintain population diversity, the fitness sharing method was proposed. This led to the formation of so called niches, i.e. to speciation of species. Goldberg also suggested the restriction of mating between individuals occupying different niches in order to avoid excessive competition between distant members of the population. Fonseca and Fleming [1993] proposed a slightly different Pareto-based scheme in which an individual’s rank corresponds to the number of individuals
In many optimisation problems, analysts are often confronted with multiobjective decision problems. The most common purpose of an analysis is to choose the best trade-offs among all the defined and conflicting objectives. In multiobjective optimisation, after the decision-maker has defined all the objectives, he/she has to determine the multiobjective optimal zone by using the concept of the domination criterion called the Pareto domination. Each solution of the Pareto optimal set is not dominated by any other solution, i.e. in going from one solution to another, it is not possible to improve on one objective (e.g. reduce the risk of not meeting demand for water) without making at least one of the other objectives worse (e.g. increase cost). It is clear, however, that there is a need to identify as many solutions as possible within the Paretooptimal range to ensure that an acceptable solution will be produced and selected by the decisionmaker. Many, if not all, of the single-objective optimisation techniques can be used to generate a subset of the Pareto-optimal range if more objectives are identified and these techniques are used appropriately. Weighting the objectives to obtain Pareto solutions can do this where solutions could be generated by using one of the single-optimisation methods. The objective functions need to be lumped together, but with different weights applied to each of them in respective runs. The procedure for weighting the objectives to obtain Pareto solution in this manner is called the weighting method [Cohon, 1978].
10
in the current population by which it is dominated. Non-dominated individuals are assigned the same rank, while dominated ones are penalised according to the local population density. Fonseca and Fleming also suggested the use of a stochastic universal selection sampling algorithm. In the current version of the MOGA software the Fonseca and Fleming [1993] model is used for solving the New York Tunnels problem. 4. MOGA SOLUTIONS
late and did not require complex mathematical tools to implement.
20.00 18.00 16.00 Total Deficit (m) 14.00 12.00 10.00 8.00 6.00 4.00 2.00 0.00 15.00 20.00 25.00 30.00 35.00 40.00 45.00 1 Node 2 Nodes 3 Nodes 4 Nodes 5 Nodes No Deficit
The first MOGA run was performed on the following three objectives: (1) minimisation of cost, (2) minimisation of the number of nodes with deficient pressure (i.e. the spread of deficits), and (3) minimisation of the total pressure deficit across the network. Since it is quite difficult to visualise the three objectives on a single 3D graph, the solutions are presented on a 2D graph where different symbols represent the different level of attainment of the second objective (Figure 2). The first observation from the graph is that MOGA detected a large number of solutions on the Paretooptimal front in a single run. Preferences for the minimum pressure requirement (or the total pressure deficit) do not need to be specified before the model run. For example, a large number of different solutions with the total pressure deficit of less than 2.0m have the total cost ranging from $25M to $39M. This is quite important since it is quite likely that uncertainty about the calculated pressure levels is actually of the order much greater than 2.0m. If a single-objective optimisation runs were performed with a fixed minimum pressure constraint, only the solution with or close to no constraint violation (e.g. $39M solution) would be found. With the MOGA solution the decision-maker has the opportunity to visualise trade-offs and may be inclined to accept a very small violation of the pressure requirement for a large cost saving. Where on the trade-off zone the ‘best’ solution is found would be totally up to the decision maker and not to the analyst. In other words the decision-maker’s preferences are expressed after a model run. This is an advantage when compared to the case where multiobjective problem is solved by normalising and combining objectives into a single one (in that case, weights, i.e. preferences must be specified before the model run). Another advantage of the MOGA approach is that the objective functions were simple to formu-
Cost ($ Million)
Figure 2. Trade-off between pressure deficit and cost Additionally, Pareto solutions with larger pressure deficits cost much less than the solutions that satisfy the ultimate performance levels. They usually identify a smaller number of pipes to be implemented, hence smaller capacity and larger pressure deficits. However, those designs could also be seen as possible candidates for staged implementation of the ‘final’ solution. The only additional requirement is that they are a subset of the ‘final’ solution, i.e. pipes identified for duplication in the staged designs are a subset of pipes in the ‘final’ solution.
20.00 18.00 Maximum Deficit (m) 16.00 14.00 12.00 10.00 8.00 6.00 4.00 2.00 0.00 20.00 30.00 40.00 50.00 60.00 70.00 DM=1.2 DM=1.1
Cost ($ Million)
Figure 3. Trade-off between pressure deficit, demand (capacity) and cost In order to provide the decision-maker with a better insight into the trade-off between the benefits of spare capacity in the system and the cost of the system, an additional MOGA run was performed. Figure 3 shows some of the 2000+ solutions from the Pareto front obtained in this run. This time a surrogate measure of additional capacity was introduced by considering an increase in demand (i.e. water delivered to customers). A global demand
11
multiplier (DM) was introduced as an objective that was maximised (e.g. DM larger than 1.0 represents percentage increase in demand assigned to each and every node in the network). Again, the decisionmaker may be able to trade off solutions with increased capacity (DM > 1.0) against the cost of the solution and/or against some pressure deficiency. Considering uncertainties associated with hydraulic modelling results, it is possible that substantial benefits can be achieved by considering the network design problem as a multiobjective one. 5. CONCLUSIONS
GR/R14712/01 and Advanced Research Fellowship AF/000964. 7. REFERENCES
Water distribution network design is usually a very complex task. Rather than using some trial-anderror approach, an optimisation procedure should be used to solve it. Still, due to a number of reasons it is not reasonable to expect that in general the problem will be solved using a completely automated procedure, i.e. optimisation should be viewed as a decision support tool, rather than a decision making tool. Single-objective optimisation can detect one optimal solution in a single run while MOGA can detect a whole set of (Pareto) optimal solutions, i.e. it can detect the whole trade-off surface. As a consequence, multiple SO runs are necessary to obtain the same level of information that can be obtained from a single MOGA run. When the SO model is used, the decision maker must express preferences before a model run, while in the MOGA approach one expresses preferences after a run. While the author acknowledges that it is difficult to identify the true benefits and constraints in water distribution design (due primarily to the uncertainty in future demands), the MOGA model used in this paper utilises simple and intuitive objectives and constraints that are not difficult to formulate in mathematical terms. Those objectives allow a decision-maker to visualise the trade-offs between different benefits and costs, and more importantly to consider uncertainty in future demands and performance levels. MOGA optimisation could also take into account that the system needs to be implemented in stages. 6. ACKNOWLEDGEMENTS
Cohon, J.L., Multiobjective Programming and Planning, Academic Press, New York, 1978. Fonseca, C.M., and P.J. Fleming, Genetic Algorithms for Multi-Objective Optimisation: Formulation, Discussion and Generalisation. In Proc. of the 5th International Conference on Genetic Algorithms, 416-423, 1993. Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, AddisonWesley, 1989. Goulter, I. C., Systems analysis in waterdistribution network design: From theory to practice, Journal of Water Resources Planning and Management, ASCE, 118(3), 238-248, 1992. Lansey, K.E. Optimal Design of Water Distribution Systems, in Water Distribution System Handbook, (ed. Mays, L.W.) McGraw-Hill, 2000. Savic, D.A. and G.A. Walters, Genetic Algorithms for the Least-cost Design of Water Distribution Networks, Journal of Water Resources Planning and Management, ASCE, 123 (2), 67-77, 1997. Schaake, J., and D. Lai, Linear Programming and Dynamic Programming Applications to Water Distribution Network Design, Report 116, Department of Civil Engineering, Massachusetts Inst. of Tech., Cambridge, Mass., 66p, 1969. Schaffer, J.D. Multiple Optimisation with Vector Evaluated Genetic Algorithms. In Proc. of the 1st International Conference on Genetic Algorithms, 93-100, 1985. Veldhuizen, D.A.V., and G.B. Lamont, Multiobjective Evolutionary Algorithm Research: A History and Analysis, Report No. TR-98-03, Department of Electrical and Computer Engineering, Air Force Institute of Technology, p. 88, 1998. Walski, T.M. State of the Art: Pipe Network Optimization, Computer Applications in Water Resources, ASCE, 1985. Walski, T.M. The Wrong Paradigm—Why water distribution optimization doesn’t work, Journal of Water Resources Planning and Management, ASCE, 127(4), 203-25, 2001.
This work was supported by the U.K. Engineering and Physical Sciences Research Council, grant
12
doc_149148229.pdf
A nontrivial multiobjective optimization problem, there does not exist a single solution that simultaneously optimizes each objective. In that case, the objective functions are said to be conflicting, and there exists a (possibly infinite number of) Pareto optimal solutions.
Single-objective vs. Multiobjective Optimisation for Integrated Decision Support
Dragan Savic Centre for Water Systems, Department of Engineering School of Engineering and Computer Science, sity of Exeter, United Kingdom, E-mail: [email protected] Univer-
Abstract: In many optimisation problems, analysts are often confronted with multiobjective decision problems. The most common purpose of an analysis is to choose the best trade-offs among all the defined and conflicting objectives. However, many optimisation studies are formulated as a problem whose goal is to find the “best” solution, which corresponds to the minimum or maximum value of a single objective function that lumps all different objectives into one. Water distribution system design is a multiobjective problem for which it is difficult to identify the true benefits and constraints due primarily to the uncertainty in future demands. This paper shows some shortcomings of the use of single-objective optimisation for water distribution system design and introduces a genetic algorithm multiobjective model that promises to ease the difficulties in applying optimisation and providing decision support for that important problem. The optimisation model used in this paper utilises simple and intuitive objectives and constraints that are not difficult to formulate in mathematical terms. Those objectives allow a decision-maker to visualise the trade-offs between different benefits and costs, and more importantly to consider uncertainty in future demands and performance levels. This type of optimisation could also take into account that the system needs to be implemented in stages. Keywords: optimisation, multiobjective, Pareto solutions, water distribution system, design 1. INTRODUCTION 1.1. Role of Optimisation As engineers and/or analysts, we are trying to find improved ways of coping with complexity, increasing the flexibility of the design and analysis processes, and empowering the modeller with advanced tools that integrate with other existing components of the analysis process, e.g. simulation models, standards, etc. All modellers like to think that they produce well-calibrated models or good safe designs that represent value for money. However, it is rare for a modeller to have the time or resources to consider more than a handful of solutions to a problem. In project planning there are often many alternatives for each individual component of a scheme. The number of different designs for a complete scheme can then be very large indeed, if not infinite. Even with detailed design, there are usually an enormous number of possibilities, far too many to be considered and evaluated individually. Clearly, if this is possible then optimisation is not needed! The main reason to rely on any model in a decision making process is to provide a quantitative assessment of the effects of management decisions on the system being considered. A model also provides a fairly objective assessment as opposed to subjective opinions of system behaviour. Thus, models should be used in support of decision making. Optimisation is just another type of modelling and the same applies to optimisation models. Optimisation tools should be used for supporting decisions rather than for making decisions, i.e. should not substitute decision-making process! 1.2. Single vs. Multiobjective Optimisation Many real-world decision making problems need to achieve several objectives: minimise risks, maximise reliability, minimise deviations from desired levels, minimise cost, etc. The main goal of single-
7
objective (SO) optimisation is to find the “best” solution, which corresponds to the minimum or maximum value of a single objective function that lumps all different objectives into one. This type of optimisation is useful as a tool which should provide decision makers with insights into the nature of the problem, but usually cannot provide a set of alternative solutions that trade different objectives against each other. On the contrary, in a multiobjective optimisation with conflicting objectives, there is no single optimal solution. The interaction among different objectives gives rise to a set of compromised solutions, largely known as the trade-off, nondominated, noninferior or Pareto-optimal solutions. The consideration of many objectives in the design or planning stages provides three major improvements to the procedure that directly supports the decision-making process [Cohon, 1978]: (1) A wider range of alternatives is usually identified when a multiobjective methodology is employed. (2) Consideration of multiple objectives promotes more appropriate roles for the participants in the planing and decision-making processes, i.e. “analyst” or “modeller”– who generates alternative solutions, and “decision maker” who uses the solutions generated by the analyst to make informed decisions. (3) Models of a problem will be more realistic if many objectives are considered. Single-objective optimisation identifies a single optimal alternative, however, it can be used within the multiobjective framework. This does not involve aggregating different objectives into a single objective function, but, for example, entails setting all except one of them as constraints in the optimisation process. Those objectives expressed as constraints are assigned different levels of attainment of their respective objective functions (e.g. minimum reliability levels) and several runs are performed to obtain solutions corresponding to different satisfaction of constraints. However, most design and planning problems are characterised by a large and often infinite number of alternatives. Thus, multiobjective methodologies are more likely to identify a wider range of these alternatives since they do not need to prespecify for which level of one objective a single optimal solution is obtained for another. A very simplified view of the decision-making process is that it involves two types of actors: analysts (modellers) and decision makers. This is a
crude simplification of the process since many stakeholders and actors may be involved, but simple enough to demonstrate shortcomings of assuming that in general one person can assume both (or many more) roles. Analysts are technically capable people who provide information about a problem to decision makers who decide which course of action to take. Modelling and optimisation techniques are tools which analysts may use to develop useful information for the decision makers. However, single-objective models require that all design objectives must be measurable in terms of a single fitness function. This in turn requires some a priori ordering of different objectives (i.e., a weighting scheme) to allow easy integration of them into a single function of same units. Thus, single-objective approaches place the burden of decision making squarely on the shoulders of the analyst. For example, it is the analyst who must decide the cost equivalent of a specific risk of failure. Even if the decision makers are technically capable and willing to provide some a priori preference information, the decision making role is taken away from them. By providing a trade-off curve between different objectives and alternative solutions corresponding to the points on this curve, multiobjective approaches allow for the responsibility of assigning relative values of the objectives to remain where it belongs: with the decision maker! 1.3. Water Distribution System Design Nowadays pipelines are the most common means for transporting water (potable and wastewater), gasses and oils necessary for everyday life in modern cities. The design, construction, operation and maintenance of millions of kilometres of these pipelines represent an immense challenge for engineers around the world. This paper concentrates on water networks as an element of urban settlement. The design of water distribution networks is often viewed as a single-objective, least-cost optimisation problem with pipe diameters acting as the primary decision variables. The optimisation problem of least-cost pipe sizing is a non-linear, discrete combinatorial optimisation problem. It is non-linear because the head-loss relationship and discrete because pipe diameters are produced in distinct diameters only. Optimal design problems of realistic size become intractable for enumeration techniques. This is because of the exponential growth of the problem size with the increase in number of discrete decisions (that is, the dimension of the problem), or
8
the so-called curse of dimensionality. This rather emotive term is used to describe difficulties in obtaining an optimal solution over many dimensions. The search for a solution in such a multidimensional space quickly becomes “lost” in the wealth of space when the dimensionality becomes too large. Water distribution system design optimisation is one of the most heavily researched areas in the hydraulics profession. Hundreds of papers and reports on approaches have been developed over the past few decades. Several reviews of the state-of-the-art in water distribution optimisation have been prepared over the years [Walski, 1985; Goulter, 1992; Lansey, 2000]. However, in spite of considerable development in the literature, the techniques have not been accepted in practice and Walski [2001] recently criticised most previous optimisation approaches for several practical reasons. The main ones being that (i) it is difficult for practitioners to define objective functions and constraints; (ii) there is not a single design flow for which the system should be designed, (iii) optimisation fails to account for the fact that a total distribution system is not built all at once, and (iv) optimisation tends to reduce costs by reducing the diameter of or completely eliminating pipes thus leaving the system with insufficient capacity to respond to pipe breaks or demands that exceed design values without failing to achieve required performance levels. This paper offers an alternative optimisation approach that tries to answer the questions raised by Walski [2001] by more appropriate use of optimisation within the multiobjective framework. 2. NEW YORK CITY TUNNELS PROBLEM
For 15 available diameters, i.e., 16 possible decisions including the ‘do nothing’ option, and 21 pipes to be considered for duplication, the total solution space is 1621 = 1.93×1025 possible network
Figure 1. New York Tunnel System designs. After this first study various researchers have optimised the NYCT problem using a singleobjective optimisation approach with the fixed pressure requirements, i.e., the objective function considered was:
f ( D1 ,..., Dn ) = ? c( Di , Li )
i =1 N
(1)
The New York City tunnels (NYCT) problem dates back to the late sixties when Schaake and Lai [1969] attempted to use linear programming optimisation to analyse the New York City water supply tunnels system. The City was looking to increase the capacity of its water supply system to meet future demands by adding one or more pipes to the existing network of 21 tunnels. The tunnel system layout is shown in Figure 1. Because of age and increased demands the then existing gravity flow tunnels have been found to be inadequate to meet the pressure requirements (nodes 16, 17, 18, 19 and 20 in Figure 1) for the projected consumption level. The proposed method of expansion was the same as in previous studies, i.e., to reinforce the system by constructing tunnels parallel to the existing ones.
where c(Di,Li) is the cost of the pipe i with the diameter Di and the length Li, and N is the total number of pipes in the system. The above function is minimised under the minimum pressure constraints:
H j ? H min j ; j = 1,..., M
(2)
where Hj is the head at node j, Hjmin is the minimum required head at the same node and M is the total number of nodes in the system. Savic and Walters [1997] give an overview of results obtained by different optimisation studies with costs in the range from $36.10M to $78.09M. However, the main objections raised by Walski [2001] apply to all of the solutions in that they were developed for a single objective (cost minimisation), where future demands are perfectly known and no
9
staging of decisions was assumed in any of the models. In addition, solutions that were close to feasibility, i.e. just below the required minimum pressure level were considered infeasible and did not allow any explicit trade-off analysis, e.g., between uncertainty and cost or capacity and cost. To examine trade-offs, the following additional objectives were identified: (i) minimise the number of nodes with pressure deficiencies, e.g., nodes where Hj < Hjmin; (ii) minimise the total head deficit across the network, e.g. sum of individual deficiencies; and (iii) maximise the capacity to deliver additional water. These objectives will be analysed in the section dealing with multiobjective solutions to the NYTC problem. 3. MULTIOBJECTIVE GA OPTIMISATION
The constraint method is an alternative framework for generating Pareto-optimal solutions. It operates by optimising one objective while all of the others are constrained to some value [Cohon, 1978]. The main disadvantage of both weighting and constraint methods is that not all of the points can be identified because the appropriate weights (or constraint levels) are not known in advance. These methods also suffer from high computational costs since the number of optimisation runs increases exponentially with the number of objectives. The need to identify as many solutions as possible within the Pareto-optimal range often represents a problem for standard generating techniques. By maintaining and continually improving a population of solutions, a genetic algorithm (GA) can search for many non-dominated solutions at the same time (in a single run), which makes it a very attractive tool for solving multiobjective optimisation problems GA is an adaptive search method that emulates nature’s evolution based on preferential survival, reproduction of the fittest members of the population, maintenance of a population with diverse members, inheritance of genetic material from parents, occasional mutation of genes, etc. [Goldberg, 1989]. Few multiobjective genetic algorithm (MOGA) approaches exist today [Veldhuizen and Lamont, 1998]. The first MOGA non-Pareto approach, Vector Evaluated Genetic Algorithm (VEGA), was proposed by Schaffer [1985]. Later, Goldberg [1989] introduced Pareto-ranking in his simple GA, in addition to standard selection, crossover and mutation operators. At each generation, members of the current population were ranked according to Pareto domination rules. By introducing Pareto domination ranking, the population was effectively divided into a number of subpopulations. However, Goldberg soon realised that Pareto ranking, on its own, does not guarantee that individuals will be uniformly distributed along the Pareto optimal front. In order to maintain population diversity, the fitness sharing method was proposed. This led to the formation of so called niches, i.e. to speciation of species. Goldberg also suggested the restriction of mating between individuals occupying different niches in order to avoid excessive competition between distant members of the population. Fonseca and Fleming [1993] proposed a slightly different Pareto-based scheme in which an individual’s rank corresponds to the number of individuals
In many optimisation problems, analysts are often confronted with multiobjective decision problems. The most common purpose of an analysis is to choose the best trade-offs among all the defined and conflicting objectives. In multiobjective optimisation, after the decision-maker has defined all the objectives, he/she has to determine the multiobjective optimal zone by using the concept of the domination criterion called the Pareto domination. Each solution of the Pareto optimal set is not dominated by any other solution, i.e. in going from one solution to another, it is not possible to improve on one objective (e.g. reduce the risk of not meeting demand for water) without making at least one of the other objectives worse (e.g. increase cost). It is clear, however, that there is a need to identify as many solutions as possible within the Paretooptimal range to ensure that an acceptable solution will be produced and selected by the decisionmaker. Many, if not all, of the single-objective optimisation techniques can be used to generate a subset of the Pareto-optimal range if more objectives are identified and these techniques are used appropriately. Weighting the objectives to obtain Pareto solutions can do this where solutions could be generated by using one of the single-optimisation methods. The objective functions need to be lumped together, but with different weights applied to each of them in respective runs. The procedure for weighting the objectives to obtain Pareto solution in this manner is called the weighting method [Cohon, 1978].
10
in the current population by which it is dominated. Non-dominated individuals are assigned the same rank, while dominated ones are penalised according to the local population density. Fonseca and Fleming also suggested the use of a stochastic universal selection sampling algorithm. In the current version of the MOGA software the Fonseca and Fleming [1993] model is used for solving the New York Tunnels problem. 4. MOGA SOLUTIONS
late and did not require complex mathematical tools to implement.
20.00 18.00 16.00 Total Deficit (m) 14.00 12.00 10.00 8.00 6.00 4.00 2.00 0.00 15.00 20.00 25.00 30.00 35.00 40.00 45.00 1 Node 2 Nodes 3 Nodes 4 Nodes 5 Nodes No Deficit
The first MOGA run was performed on the following three objectives: (1) minimisation of cost, (2) minimisation of the number of nodes with deficient pressure (i.e. the spread of deficits), and (3) minimisation of the total pressure deficit across the network. Since it is quite difficult to visualise the three objectives on a single 3D graph, the solutions are presented on a 2D graph where different symbols represent the different level of attainment of the second objective (Figure 2). The first observation from the graph is that MOGA detected a large number of solutions on the Paretooptimal front in a single run. Preferences for the minimum pressure requirement (or the total pressure deficit) do not need to be specified before the model run. For example, a large number of different solutions with the total pressure deficit of less than 2.0m have the total cost ranging from $25M to $39M. This is quite important since it is quite likely that uncertainty about the calculated pressure levels is actually of the order much greater than 2.0m. If a single-objective optimisation runs were performed with a fixed minimum pressure constraint, only the solution with or close to no constraint violation (e.g. $39M solution) would be found. With the MOGA solution the decision-maker has the opportunity to visualise trade-offs and may be inclined to accept a very small violation of the pressure requirement for a large cost saving. Where on the trade-off zone the ‘best’ solution is found would be totally up to the decision maker and not to the analyst. In other words the decision-maker’s preferences are expressed after a model run. This is an advantage when compared to the case where multiobjective problem is solved by normalising and combining objectives into a single one (in that case, weights, i.e. preferences must be specified before the model run). Another advantage of the MOGA approach is that the objective functions were simple to formu-
Cost ($ Million)
Figure 2. Trade-off between pressure deficit and cost Additionally, Pareto solutions with larger pressure deficits cost much less than the solutions that satisfy the ultimate performance levels. They usually identify a smaller number of pipes to be implemented, hence smaller capacity and larger pressure deficits. However, those designs could also be seen as possible candidates for staged implementation of the ‘final’ solution. The only additional requirement is that they are a subset of the ‘final’ solution, i.e. pipes identified for duplication in the staged designs are a subset of pipes in the ‘final’ solution.
20.00 18.00 Maximum Deficit (m) 16.00 14.00 12.00 10.00 8.00 6.00 4.00 2.00 0.00 20.00 30.00 40.00 50.00 60.00 70.00 DM=1.2 DM=1.1
Cost ($ Million)
Figure 3. Trade-off between pressure deficit, demand (capacity) and cost In order to provide the decision-maker with a better insight into the trade-off between the benefits of spare capacity in the system and the cost of the system, an additional MOGA run was performed. Figure 3 shows some of the 2000+ solutions from the Pareto front obtained in this run. This time a surrogate measure of additional capacity was introduced by considering an increase in demand (i.e. water delivered to customers). A global demand
11
multiplier (DM) was introduced as an objective that was maximised (e.g. DM larger than 1.0 represents percentage increase in demand assigned to each and every node in the network). Again, the decisionmaker may be able to trade off solutions with increased capacity (DM > 1.0) against the cost of the solution and/or against some pressure deficiency. Considering uncertainties associated with hydraulic modelling results, it is possible that substantial benefits can be achieved by considering the network design problem as a multiobjective one. 5. CONCLUSIONS
GR/R14712/01 and Advanced Research Fellowship AF/000964. 7. REFERENCES
Water distribution network design is usually a very complex task. Rather than using some trial-anderror approach, an optimisation procedure should be used to solve it. Still, due to a number of reasons it is not reasonable to expect that in general the problem will be solved using a completely automated procedure, i.e. optimisation should be viewed as a decision support tool, rather than a decision making tool. Single-objective optimisation can detect one optimal solution in a single run while MOGA can detect a whole set of (Pareto) optimal solutions, i.e. it can detect the whole trade-off surface. As a consequence, multiple SO runs are necessary to obtain the same level of information that can be obtained from a single MOGA run. When the SO model is used, the decision maker must express preferences before a model run, while in the MOGA approach one expresses preferences after a run. While the author acknowledges that it is difficult to identify the true benefits and constraints in water distribution design (due primarily to the uncertainty in future demands), the MOGA model used in this paper utilises simple and intuitive objectives and constraints that are not difficult to formulate in mathematical terms. Those objectives allow a decision-maker to visualise the trade-offs between different benefits and costs, and more importantly to consider uncertainty in future demands and performance levels. MOGA optimisation could also take into account that the system needs to be implemented in stages. 6. ACKNOWLEDGEMENTS
Cohon, J.L., Multiobjective Programming and Planning, Academic Press, New York, 1978. Fonseca, C.M., and P.J. Fleming, Genetic Algorithms for Multi-Objective Optimisation: Formulation, Discussion and Generalisation. In Proc. of the 5th International Conference on Genetic Algorithms, 416-423, 1993. Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, AddisonWesley, 1989. Goulter, I. C., Systems analysis in waterdistribution network design: From theory to practice, Journal of Water Resources Planning and Management, ASCE, 118(3), 238-248, 1992. Lansey, K.E. Optimal Design of Water Distribution Systems, in Water Distribution System Handbook, (ed. Mays, L.W.) McGraw-Hill, 2000. Savic, D.A. and G.A. Walters, Genetic Algorithms for the Least-cost Design of Water Distribution Networks, Journal of Water Resources Planning and Management, ASCE, 123 (2), 67-77, 1997. Schaake, J., and D. Lai, Linear Programming and Dynamic Programming Applications to Water Distribution Network Design, Report 116, Department of Civil Engineering, Massachusetts Inst. of Tech., Cambridge, Mass., 66p, 1969. Schaffer, J.D. Multiple Optimisation with Vector Evaluated Genetic Algorithms. In Proc. of the 1st International Conference on Genetic Algorithms, 93-100, 1985. Veldhuizen, D.A.V., and G.B. Lamont, Multiobjective Evolutionary Algorithm Research: A History and Analysis, Report No. TR-98-03, Department of Electrical and Computer Engineering, Air Force Institute of Technology, p. 88, 1998. Walski, T.M. State of the Art: Pipe Network Optimization, Computer Applications in Water Resources, ASCE, 1985. Walski, T.M. The Wrong Paradigm—Why water distribution optimization doesn’t work, Journal of Water Resources Planning and Management, ASCE, 127(4), 203-25, 2001.
This work was supported by the U.K. Engineering and Physical Sciences Research Council, grant
12
doc_149148229.pdf