Towards the best-Known approximation to the true Pareto front

Note: SP-Small Problems; MP-Medium Problems; IP-Intermediate Problems; LP-Larger Problems; LC-number of loading conditions; WS-number of water sources; DV-number of decision variables; PD-number of pipe diameter options.

^*For TRN problem, three existing pipes have 8 diameter options for duplication and 2 extra options, i.e. cleaning and leaving alone.

Two objectives are considered, minimisation of the total capital cost associated with pipe components and maximisation of the network resilience. The mathematical expression of each objective is given in Eq. 1 and Eq. 2, respectively.

(1)

Where C=total cost (monetary units problem dependant); np=number of pipes; U_c=unit pipe cost depending on the diameter selected in a specific problem; D_i=diameter of pipe i; L_i=length of pipe i.

(2)

Where I_n=network resilience; nn=number of demand nodes; C_j, Q_j, H_j and H_j^req=uniformity, demand, actual head and minimum head of node j; nr=number of reservoirs; Q_k and H_k=discharge and actual head of reservoir k; npu=number of pumps; P_i=power of pump i if any; γ=specific weight of water; npj=number of pipes connected to node j; Di=diameter of pipe i connected to demand node j.

NSGA-II features a fast non-dominated sorting approach, implicit elitist selection method based on Pareto-dominance rank and a secondary selection method based on crowding distance, which significantly improve its performance on difficult multi-objective problems. Moreover, it provides a constraint-handling technique to deal with constrained problems efficiently and supports both binary and real coding representations. More details about NSGA-II readers are referred to the following paper:

• Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE T. Evolut. Comput. 6(2), 182-197.

The source code of NSGA-II was written in C and can be downloaded from the KanGAL website.

AMALGAM is a hybrid optimisation framework which employs four sub-algorithms simultaneously within its structure, including NSGA-II, adaptive metropolis search, particle swarm optimisation and differential evolution. It is designed to overcome the drawbacks of using an individual algorithm. The strategies of global information sharing and genetically adaptive offspring creation are implemented in the process of population evolution. Each sub-algorithm is allowed to produce a specific number of offspring based on the survival history of its solutions in the previous generation. The pool of current best solutions is shared among sub-algorithms for reproduction.

More details about AMALGAM readers are referred to the following paper:

• Vrugt, J. A., Robinson, B. A., 2007. Improved Evolutionary Optimization from Genetically Adaptive Multimethod Search. Proc. Natl. Acad. Sci. U.S.A. 104(3), 708-711.

The source code of AMALGAM was written in Matlab and can be obtained by request on their website.

Unlike the NSGA-II, ε-MOEA is a steady-state MOEA in which only one solution is generated per iteration. It incorporates the concept of ε-dominance, being able to preserve a good representation of Pareto front in terms of convergence and diversity. At the beginning, a population is initialised randomly and the non-dominated solutions are retained in an archive. Next, a solution is created via crossover and mutation using two parents each of which selected from the population and the archive. Then, this solution is checked for acceptance or rejection by the population and the archive, using Pareto dominance and ε-dominance, respectively. The abovementioned procedure is repeated until a stopping criterion is met.

More details about ε-MOEA readers are referred to the following paper:

• Deb, K., Mohan, M., Mishra, S., 2005. Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolut. Comput. 13(4), 501-525.

The source code of ε-MOEA was written in C and can be downloaded from the KanGal website.

Based on the steady-state structure of ε-MOEA, Borg incorporates more advanced features into a unified framework, including ε-dominance, ε-progress (a measure of convergence speed), randomised restart, and auto-adaptive multi-operator recombination (similar to AMALGAM). The advantages of Borg are threefold: (1) usage of ε-box dominance archive contributes to maintaining the convergence and diversity concurrently throughout the search; (2) the combination of time continuation, adaptive population sizing, and two types of randomised restart (i.e. ε-progress triggered restart and population-to-archive ratio triggered restart) boosts the algorithm towards global optima; (3) simultaneous employment of multiple recombination operators enhances performance on a wide assortment of problem domains. In addition, the adoption of the steady-state, elitist model of ε-MOEA make it easily extendable for use on parallel architectures.

More details about Borg readers are referred to the following paper:

• Hadka, D., Reed, P., 2013. Borg: An Auto-Adaptive Many-Objective Evolutionary Computing Framework. Evolut. Comput. 21(2), 231-259.

The source code of Borg was written in C and can be obtained by request from the BorgMOEA website.

The ε-NSGA-II method goes beyond the common implementation of MOEA by building on NSGA-II and three key components, namely ε-dominance archiving, adaptive population sizing with archive injection, and automatic termination. The ε-NSGA-II differs from the NSGA-II primarily in two aspects: (1) while the population evolves in the same manner as NSGA-II, an offline archive is frequently updated by selecting the ε-non-dominated solutions from the elitist population at current generation; (2) the optimisation is implemented in consecutive epochs, each of which is terminated automatically according to the user-specified improvement criteria. The next epoch is populated by injecting the members in the archive and generating new random solutions. The ε-dominance archiving maintains the convergence and diversity of the archive concurrently. It also allows users to specify the precision of each objective and thus is more flexible in practice. Adaptive population sizing contributes to balancing the exploration and exploitation throughout the search, which is achieved by increasing or decreasing the capacity of the population based on the number of members in the archive. Additionally, several connected runs, known as time continuation, enhance the possibility to explore other regions of search space.

More details about ε-NSGA-II readers are referred to the following paper.

• Kollat, J. B., Reed, P. M., 2006. Comparing state-of-the-art evolutionary multi-objective algorithms for long-term groundwater monitoring design. Adv. Water Resour. 29(6), 792-807.

The source code of ε-NSGA-II was written in C and can be obtained by sending the request to the authors.

TRN has eight undetermined pipes and nine prefixed pipes, two reservoirs fixed at 365.76 m (left) and 371.86 m (right) and nine demand nodes. New and cleaned pipes have the same Hazen-Williams roughness coefficient of 120. The minimum pressure of all the nodes under three demand patterns is specified in Table TRN.1. The decision variables are the pipe diameters for five new pipes and alternative options (duplication or cleaning or leaving alone) for three existing pipes. Each pipe has eight diameter options to choose from. Table TRN.2 shows available options for pipe diameter and the corresponding unit costs. Figure TRN.1 depicts the layout of TRN.

Two loop network (TLN) consists of one reservoir, six demand nodes and eight pipes organised in two loops. The reservoir has a constant head fixed at 210 m. As a hypothetical network, all pipes have the same length (1000 m) and the Hazen-Williams coefficient of 130. The pressure is set to be at least 30.0 m at all demand nodes. Table TLN.1 shows commercially available diameters and the corresponding unit costs (1 in.=0.0254 m). Figure TLN.1 depicts the layout of TLN.

Table TLN.1 Diameter options and associated unit costs of TLN

Figure TLN.1. Layout of Two Loop Network

BakRyan Network (BAK) has fifty-eight pipes including nine new pipes to be sized, thirty-five demand nodes, one reservoir with a fixed head of 58 m. The Hazen-Williams roughness coefficient for each new pipe is 100. The minimum pressure head above the ground elevation of each node is 15 m. Among the new pipes, six of them are parallel. Table BAK.1 shows commercially available diameters and the corresponding unit costs. Figure BAK.1 depicts the layout of BAK.

Table BAK.1 Diameter options and associated unit costs of BAK

Figure BAK.1 Layout of BakRyan Network (Undetermined pipes are shown in red lines.)

The NYT is comprised of twenty-one pipes organised in two loops, nineteen demand nodes, and one reservoir with a fixed head of 300 ft (1 ft=0.3048 m). All the existing pipes are considered for duplication in order to meet the projected future demand. The Hazen-Williams roughness coefficient for both new and existing pipes is 100. The minimum pressure of all demand nodes is fixed at 255 ft except for node 16 and 17 that are 260 ft and 272.8 ft, respectively. A selection of fifteen diameter sizes are available as well as a ‘do nothing’ option. Table NYT.1 shows the diameter options and associated unit costs. Figure NYT.1 depicts the layout of NYT.

Blacksburg Network (BLA) consists of thirty-five pipes of which twelve have fixed diameters, one reservoir with a fixed head of 715.56 m, and thirty demand nodes. A universal Hazen-Williams coefficient of 120 is applied to all the pipes under consideration. The pressure requirement of each node is limited within a specified range under the single loading condition. The minimum pressure head for each node is 30 m, while the maximum pressure head varies from node to node and is provided in Table BLA.1. Table BLA.2 shows commercially available diameters and the corresponding unit costs. Figure 5 depicts the layout of BLA.

Hanoi network consists of thirty-four pipes organised in three loops, thirty-one demand nodes and one reservoir with a fixed head of 100 m. The Hazen-Williams roughness coefficient for all pipes is 130. The minimum head above the ground elevation of each node is 30 m. There are six commercially available pipe sizes, ranging from 12 in. to 40 in. (1 in.=0.0254 m). Table HAN.1 shows the diameter options and associated unit costs. Figure HAN.1 depicts the layout of HAN.

GoYang Network includes thirty pipes, twenty-two demand nodes, and one constant pump of 4.52 kW linking to one reservoir with a constant head of 71 m. The Hazen-Williams roughness coefficient for each new pipe is 100. The minimum pressure head above the ground elevation of each node is 15 m. Table GOY.1 shows commercially available diameters and the corresponding unit costs. Figure GOY.1 depicts the layout of GOY..

Fossolo Network (FOS) includes fifty-eight pipes, thirty-six demand nodes, and one reservoir with a fixed head of 121.00 m. The material for all the pipes is polyethylene. Due to the feature of polyethylene, a relatively high roughness coefficient of 150 is applied to all the pipes. The minimum pressure head of all the demand nodes is maintained at 40 m, while the maximum pressure head of each node is specified in Table FOS.1. In addition, the flow velocity in each pipe is enforced to be less than or equal to 1 m/s. Table FOS.2 shows commercially available diameters and the corresponding unit costs. Figure FOS.1 depicts the layout of FOS.

Pescara Network (PES) includes ninety-nine pipes, sixty-eight demand nodes, and three reservoirs with fixed head within 53.08 m to 57.00 m. The pipe material is cast iron. A uniform Hazen-Williams roughness coefficient of 130 is applied to all pipes. The minimum pressure head of all the demand nodes is maintained at 20 m, while the maximum pressure head of each node is specified in Table PES.1. In addition, the flow velocity in each pipe is enforced to be less than or equal to 2 m/s. Table PES.2 shows commercially available diameters and the corresponding unit costs. Figure PES.1 depicts the layout of PES.

Modena Network (MOD) includes three hundred and seventeen pipes, two hundred and sixty-eight demand nodes, and four reservoirs with fixed head within 72.0 m to 74.5 m. The pipe material is the same as PES. A uniform Hazen-Williams roughness coefficient of 130 is applied to all pipes. The minimum pressure head of all the demand nodes is maintained at 20 m. The maximum pressure head of each node of MOD is provided in Table MOD.1 In addition, the flow velocity in each pipe is enforced to be less than or equal to 2 m/s. Table MOD.2 shows commercially available diameters and the corresponding unit costs. Figure MOD.1 depicts the layout of MOD.

Balerma Irrigation Network (BIN) includes four hundred and fifty-four relatively small length pipes, four hundred and forty-three demand nodes (hydrants), and four reservoirs with fixed heads within 112 m to 127 m. The material of pipes is polyvinyl chloride (PVC). The Darcy-Weisbach roughness coefficient of 0.0025 mm is applied to all the pipes. The minimum pressure head above ground elevation is 20 m for all the demand nodes. Table BIN.1 shows commercially available diameters and the corresponding unit costs. Figure BIN.1 depicts the layout of BIN.

Table BIN.1 Diameter options and associated unit costs of BIN

‌

Figure BIN.1. Layout of Balerma Irrigation Network

‌

Exeter network has three thousand and thirty-two pipes including five hundred and sixty-seven considered for duplication, five valves, one thousand eight hundred and ninety-one junction nodes and seven water sources. Two major reservoirs (node 3001 and 3002) supply water to the system at fixed head of 58.4 m and 62.4 m respectively. The system is also fed by its neighbour systems via node 3003 to 3007 at fixed rates. Three non-return valves (also known as check valves) are connected to node 3001 and 3002 to control the flow direction into and outside the system. One pressure reducing valve locates in the downstream of node 3004 to maintain the downstream pressure within 58.4 m. One throttle control valve is also in the link downstream of node 3004 to control the flow and pressure of system.

The minimum pressure requirement of demand nodes is 20.0 m. There are ten available discrete pipe sizes and one extra option as 'do nothing'. The unit cost for duplicating the existing pipe depends on both the diameter selected and the road type. Table EXN.1 shows the pipe diameters, the corresponding Colebrook-White friction factors (following Darcy-Weisbach formula) and unit costs. The location of major roads is specified in Table EXN.2 in terms of pipe ID. Figure EXN.1 depicts the layout of EXN.

1 This network is a bit different from the one available at . The modifications are summarised as follows: (1) Node 1610 has been removed to avoid isolated junction; (2) 20 PM in the section of “TIMES” of input file has been changed to 8 PM; (3) Since it is impossible for junction 1107 to meet the minimum pressure requirement, it is ignored in the calculation of constraint violation. Also, it would be too complicated to highlight all the pipes considered for duplication, these pipes are tagged in the input file given.