Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 UDK - UDC 628.1:53.08 Izvirni znanstveni članek - Original scientific paper (1.01) Izbira merilnih mest v vodovodnih sistemih z genetskimi algoritmi Sampling Design for Water Distribution System Models by Genetic Algorithms Primož Banovec - Daniel Kozelj - Sašo Šantl - Franci Steinman (Fakulteta za gradbeništvo in geodezijo, Ljubljana) Obravnavana je izbira merilnih mest za umerjanje hidravličnih modelov vodovodnih sistemov. Izbira merilnih mest za umerjanje hidravličnih modelov je podana kot optimizacijski problem, ki je sestavljen iz dveh normaliziranih ciljnih funkcij. S prvo ciljno funkcijo se povečuje natančnost umerjanja parametrov hidravličnega modela, z drugo pa zmanjšuje število potrebnih merilnih mest. Predstavljeno je reševanje optimizacijskega problema z uporabo genetskih algoritmov. Overitev in uporaba razvitega optimizacijskega modela (imenovan IMMe) je bila opravljena na hidravličnem modelu teoretičnega vodovodnega sistema "Anytown", ki je namenjen kot primerjalni model za testiranje različnih raziskav pri hidravličnem modeliranju. Overjeni model IMMe je bil uporabljen na stvarnem vodovodnem sistemu mesta Sežane. Uporaba genetskih algoritmov se je v obeh primerih izkazala za zelo učinkovito optimizacijsko orodje pri izjemno kombinatornih optimizacijskih problemih. Razvita modela umerjanja in izbire merilnih mest omogočata vzpostavitev kar se da natančnih hidravličnih modelov vodovodnih sistemov, ki bodo v prihodnosti ključnega pomena za zagotavljanje gospodarnosti in učinkovitosti oskrbe s pitno vodo. © 2006 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: hidravlika, vodovodi, modeliranje, optimiranje, merilna mesta, algoritmi genetski) In this paper we discuss sampling design for the calibration of water distribution system hydraulic models. The sampling design for the calibration of water distribution-system models is formulated as an optimisation problem consisting of two normalised objective functions. The first objective function is used to increase the calibration accuracy of the model parameters, and the second one is used to reduce the number of necessary measurement locations. The optimisation problem was solved by using genetic algorithms. The verification and application of the developed optimisation model (called IMMe) were carried out on the artificial water distribution system of Anytown, which serves as a reference model for testing various researches in hydraulic modelling. The verified IMMe model was applied to a real water-distribution system in the town of Sežana. For both water distribution models, the use of genetic algorithms proved very efficient with extremely combinatorial optimisation problems. The developed calibration and sampling design allow very accurate hydraulic modelling of the water distribution systems, which is of key importance for ensuring the economy and efficiency of drinking-water supplies in the future. © 2006 Journal of Mechanical Engineering. All rights reserved. (Keywords: hydraulic water distribution systems, modelling, optimisation, measurement locations, genetic algorithms) 0 UVOD 0 INTRODUCTION Hidravlično modeliranje vodovodnih sistemov (v nadaljevanju VS) je znanstveno zelo dobro razvita panoga, ki rabi kot učinkovito orodje za podporo pri odločanju, upravljanju, načrtovanju in obnovi VS. Podpora informacijske tehnologije pri vodenju katastra komunalnih naprav in zbiranju podatkov ter meritev omogoča učinkovito The hydraulic modelling of water distribution systems (hereinafter referred to as WDS) is a scientifically well-developed discipline serving as an efficient decision-support tool for the management, development and rehabilitation of WDS. The information technology supports the asset management of the WDS and the data acquisition allows the effi- 817 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 vzpostavitev hidravličnih modelov in njihovo vključitev v analize, vsakdanje obratovanje in načrtovanje ter v končni fazi tudi izvajanje potrebnih ukrepov. Informacijski sistem se uporablja kot vir razpoložljivih podatkov o fizičnih značilkah VS, ki izhajajo iz dejansko znanih podatkov oziroma meritev in pa iz ocen posameznih hidravličnih parametrov, če količine niso natančno znane. S temi podatki je mogoče postaviti “surov” hidravlični model, katerega obsežnost je treba prilagoditi upravljavsko obvladljivim razmeram. Hidravlični modeli istega VS se lahko med seboj razlikujejo glede na namen analize, ki bo izvedena s tem modelom. Namen modela je bistvenega pomena, saj določa stopnjo natančnosti modela in njegove poenostavitve. Poenostavitev hidravličnega modela se imenuje ogrodenje (skeletiranje), cilj katerega je, iz modela izključiti elemente, ki niso bistveni za njegovo hidravlično enakost z dejanskim dogajanjem v VS. Po postavitvi takega modela se najprej izvede postopek grobega umerjanja oziroma makrokalibracije (sl. 1), cilj katerega je prilagajanje parametrov hidravličnega modela, dokler delovanje hidravličnega modela VS ne izkazuje ujemanja s sedanjimi meritvami z odstopanjem največ 30 odstotkov [1]. Makrokalibracija je usmerjena v odpravljanje posameznih virov odstopanj, to so napačni podatki o topologiji omrežja, nastavitev tlačnih con, parametrov elementov VS, napak merilnih naprav in odčitavanja meritev kakor tudi odpravljanje človeških napak. Običajno z makrokalibracijo hidravlični model postane grob približek stvarnega VS z določeno stopnjo natančnosti. Hidravlični model je namenjen podpori pri odločanju na tehničnem, ekonomskem in pravnem področju, kar terja, da je hidravlični model natančneje umerjen. Kot uvod v postopek natančnejšega umerjanja oziroma mikrokalibracije (v INFORMACIJSKI SISTEM GIS podpora HIDRAVLIČNO MODELIRANJE <.......?¦ OGRODENJE IN OCENA KALIBRACIJSKIH PARAMETROV A 1 ' ' IZVEDBA / STORITEV -I MAKROKALIBRACIJA t > ' ANALIZA IN NAČRTOVANJE 1 MIKROKA LIBRACIJA cient building of hydraulic models and their integration into analysis, daily operation and planning, and finally also the carrying out of the necessary measures. The information system serves as a source of available data on the physical characteristics of WDS deriving from actually known data or measurements as well as from the evaluations of individual hydraulic parameters if the exact quantities are not known. These data allow us to build a rough hydraulic model, the size of which has to be adapted to a manageable extent. Hydraulic models of the same WDS can vary substantially in their configuration with regard to the purpose of the model and the analysis to be performed with it. The model's purpose is essential since it determines the accuracy level to be applied. The model's adaptation involves a procedure of skeletonization, i.e., simplification of the model, the aim of which is to exclude those elements that are not essential to represent the model's hydraulic behaviour according to the real WDS. With such a model, the procedure of macro-calibration is first carried out (Fig. 1), with the adjustment of certain model parameters to achieve correspondence with the hydraulic behaviour of WDS, i.e., the system variables should not exceed 30 percent, based on the existing measurements [1]. Macro-calibration strives to eliminate the sources of differences, such as incorrect data on network topology, pressure-zone settings, the parameters of network elements, the errors of the measurement equipment and readings, as well as human error. Normally, macro-calibration turns the hydraulic model into a rough approximation of the real WDS, with a certain level of accuracy. Decision making should tackled with technical, economic and legal issues, so the hydraulic model has to be calibrated more precisely. As an introduction to the so-called micro-calibration (hereinafter referred to as INFORMATION SYSTEM GIS support HYDRAULIC MODELLING <.......* SKELETONIZATION AND CALIBRATION PARAMETER ESTIMATION A i MEASURES / SERVICE -1 MACRO CALIBRATION 1 T ANALYSIS AND DESIGN <— ¦ MICRO CALIBRATION Sl. 1. Upravljanje vodovodnih sistemov s poudarkom na modeliranju Fig. 1. Water distribution system management with the emphasis on modelling 818 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 nadaljevanju umerjanje) se uporablja postopek izbire merilnih mest, ki zagotavlja zbiranje pomembnih vzorcev meritev. Izbira merilnih mest za potrebe umerjanja je osredotočena na zbiranje meritev za razpoznavanje značilk in parametrov hidravličnega modela VS, odkrivanje virov težav pri vsakodnevnem obratovanju VS in za določene raziskovalne potrebe. Namen pričujočega prispevka je določitev merilnih mest in zbiranje meritev za natančno razpoznavanje, tj. umerjanje, fizičnih parametrov hidravličnih modelov VS. 1 UMERJANJE HIDRAVLIČNIH MODELOV VS kjer so: E - vrednost ciljne funkcije umerjanja; y*ijk -meritve hidravličnih veličin na VS; yijk - napovedi modela za (i=1,...N; j=1,...NM; k=1,...NV); NL -število obtežnih primerov; NM -število merilnih mest; N - tip hidravlične veličine (tj. tlaki, pretoki ...); ai -utežni koeficient Na področju umerjanja VS je bilo razvitih več postopkov in metod, ki jih v splošnem delimo na metodo poskus - napaka ter izrecne in posredne metode. Razvite posredne metode umerjanja so metode, ki so formulirane in se rešujejo kot optimizacijski problemi in so se izkazale za zelo učinkovite ([2] in [3]). Njihova ciljna funkcija je običajno izražena v obliki, ki omogoča zmanjšanje razlik med meritvami in napovedmi oziroma rezultati modela (en. 1). Razvoj optimizacijskih modelov za umerjanje je v veliki meri pripomogel k povečani natančnosti hidravličnih modelov VS. Merila natančnosti napovedovanja hidravličnih veličin so podana v različnih smernicah, ki določajo meje "calibration") level, a sampling design programme would provide representative samples of measurements for the calibration. Sampling design is focused on collecting measurements for the determination of WDS model properties, on the detection of problems in the daily operation of WDS, as well as covering certain research needs. The aim of the presented paper is to determine the measurement locations in which the measurements allow accurate identification, i.e., the calibration of the physical parameters of WDS hydraulic models. 1 CALIBRATING HYDRAULIC MODELS OF WDS where E is the value of the objective function; y*ijk are measurements of the system variables; yijk are model predictions of the system variables for (i=1,...NL; j=1,.. NM; k=1,-•-NV); NL is the number of loading conditions; NM is the number of measurement locations; NV is the type of system variables (e.g. pressure, flow); and ai are a weighting coefficients. In the area of WDS model calibration, several approaches and methods were developed, which, in general, comprise the trial-and-error method and the explicit and implicit methods. The developed implicit methods of calibration, formulated and solved as optimisation problems, have proven their effectiveness ([2] and [3]). Their objective function is expressed in a form that allows minimisation of the differences between the measurements and predictions of the model (Eq. 1). The developments of optimisation models for calibration have to a great extent contributed to the increased accuracy of WDS models. The levels of accuracy according to the purpose of the WDS model Postopek umerjanja se izvaja zaradi The calibration process is conducted to vzpostavitve zaupanja v napovedi hidravličnega provide confidence in the predictions of the WDS modela. Poleg zanesljivosti napovedovanja daje model. Besides the reliability of the predictions, umerjanje tudi natančen vpogled v delovanje VS, calibration offers a deep insight into the WDS operation, kar omogoča tudi vrednotenje občutljivosti modela which enables an assessment of the model's sensitivity na spremembe posameznih fizikalnih in/ali to changes in individual physical and/or non-physical nefizikalnih parametrov. Umerjanje je torej postopek parameters. The calibration of hydraulic models is thus določitve posameznih neznanih parametrov a procedure of determining individual unknown model hidravličnega modela, s katerim se zmanjšajo razlike parameters, which minimises the differences of med meritvami opravljenimi na stvarnem VS, in predicted and measured system variables. The napovedmi oz. rezultati hidravličnega modela. calibration problem is formulated to minimise the differ- Nastavljen problem umerjanja se lahko rešuje z ences of predicted and measured system variables, and zapisom ciljne funkcije v naslednji obliki: its general objective function is expressed as: \nm nl Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 819 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 odstopanj med meritvami in rezultati modela, vezane na namene analiz hidravličnih modelov [4]. Za uspešno umerjanje je treba najprej zbrati niz meritev, ki se pridobijo z načrtnim zbiranjem podatkov hidravličnih veličin pri obratovanju na pomembnih mestih na VS. Kakovost informacij, pridobljenih iz meritev, ima velik vpliv na natančnost umerjanja hidravličnega modela, večje število informacij pa daje v končni fazi tudi večjo stopnjo zaupanja v model. 2 IZBIRA MERILNIH MEST ZA UMERJANJE HIDRAVLIČNIH MODELOV VS Izbira merilnih mest se v praksi pogosto izvaja po načelu “ad hoc”, pri katerem se izdelovalec hidravličnega modela s pomočjo svojih strokovnih ocen odloči in predlaga kraje merilnih mest. Glavni poudarek pri zagotovitvi kakovosti in uporabnosti rezultatov izbire merilnih mest obsega določevanje [5]: (a) katere hidravlične veličine opazovati, (b) kje opazovati, (c) kdaj opazovati in (d) v kakšnih okoliščinah oz. obtežnih primerih opazovati. Odgovore na vprašanja pod točko (a), (c) in (d) mora predhodno podati inženir s svojim strokovnim znanjem. Glavni poudarek optimizacije izbire merilnih mest je osredotočen na vprašanje (b), ki je najzahtevnejše in obsega določevanje najboljših krajev merilnih mest. Izkazalo se je, da je občutljivost merilnih mest bistvenega pomena za določevanje najboljših merilnih mest. Za določevanje občutljivosti hidravličnih veličin merilnih mest glede na spremembe parametrov hidravličnega modela se uporablja t.i. Jacobijeva matrika. Koeficienti Jacobijeve matrike (i,j) so parcialni odvodi izrazov hidravličnih veličin glede na parametre modela in jih je mogoče določiti z numerično aproksimacijo, metodo končnih razlik [3]: are expressed as the differences between the measurements and the model's predictions [4]. For a successful calibration, a set of measurements has to be gathered, first by means of systematic sampling of the hydraulic quantities on a WDS. Since the relationship between the quality and quantity of a measurement is not predefined and self-evident, much attention needs to be paid to evaluating the informational content and its impact on the calibration accuracy. 2 SAMPLING DESIGN FOR THE CALIBRATION OF WDS MODELS Sampling design is often carried out according to the ad-hoc principle, where a designer of a WDS model determines and proposes the measurement location on the basis of his or her expertise. To ensure the quality and relevance of the measurements, the main emphasis in sampling design involves determining [5]: (a) which model parameters to observe, (b) where to observe them, (c) when to observe them and (d) in what circumstances or loading conditions to observe them. While the answers to questions under points (a), (c) and (d) have to be provided in advance by an engineer using his or her expert knowledge, the main emphasis of sampling design is focused on question (b), which in turn is the most demanding and involves a determination of the optimal measurement locations. It has been proven that model parameter sensitivities are essential for the determination of optimal measurement locations. To determine the optimal measurement locations with regard to model sensitivities, the so-called Jacobian matrix is used. The coefficients (i,j) of the Jacobian matrix are partial derivatives of the model predictions with regard to the model parameters and can be determined by applying numerical approximations, e.g., the finite-difference method [3]: dyi daj = yi (a*j ) - yi(aj ) a*j -aj vsak/for each (i=1,..., NO; j=1,..., Na) (2), kjer so: d y - sprememba hidravlične veličine i;Qa -sprememba parametra umerjanja hidravličnega modela j; yi(a*) - vrednost hidravlične veličine pri izhodiščni vrednosti parametra umerjanja; yi(a) -vrednost hidravlične veličine pri spremembi vrednosti parametra umerjanja; a*j - vrednost izhodiščnega parametra umerjanja; aj - vrednost spremenjenega parametra umerjanja; NO - število meritev in Na - število parametrov umerjanja. Za where d y is the change of the hydraulic quantity i; d a is the change of the hydraulic parameter of the model j; yi(a*) is the value of the hydraulic quantity at the initial calibration parameter value; yi(a) is the value of the hydraulic quantity at the change of the calibration parameter value; a*j is the value of the initial calibration parameter value; aj is the value of the hydraulic quantity at the changed calibration parameter value; NO is the number of observations and Na is the number of 820 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 rešitev izraza (2) uporabimo metodo končnih razlik, za katero je potrebno Na+1 hidravličnih simulacij, pri čemer je dodatna simufacija pridobljena s predhodno oceno vrednosti parametrov modela. Bolje umerjeni parametri hidravličnega modela dajejo natančnejše vrednosti koeficientov Jacobijeve matrike. Iz tega izhaja, da je smiselno izvajati iterativni postopek umerjanja in izbire merilnih mest (sl. 1) in to do sprejemljive natančnosti glede na namen hidravličnega modela [6]. Optimizacijski problem izbire merilnih mest je obravnavan z vidika izpolnjevanja dveh ciljnih funkcij, ki bosta podrobneje obravnavani v nadaljevanju. 2.1 Ciljna funkcija natančnosti umerjanja Z večanjem števila merilnih mest se povečuje tudi natančnost umerjanja parametrov hidravličnega modela. Metoda, ki je uporabljena za vrednotenje prve ciljne funkcije natančnosti umerjanja hidravličnega modela, je povzeta s področja teorije regresijske analize in je bila uspešno uporabljena pri razvoju modelov za umerjanje in izbiro merilnih mest modelov podtalnice [7]. Kasneje se je ta metoda uspešno uporabila tudi na področju izbire merilnih mest za izvedbo umerjanja hidravličnih modelov VS. S prvo ciljno funkcijo se vrednoti prostornina območja zaupanja parametrov. V nasprotju z določevanjem intervalov zaupanja se prostornina območja zaupanja parametrov ukvarja z verjetnostjo, da so iskane vrednosti N parametrov hkrati v določenem N - razsežnem območju. Prostornina območja zaupanja je sorazmerna kvadratnemu korenu determinante kovariančne matrike parametrov hidravličnega modela in se ga matematično lahko izrazi takole [6]: kjer sta: Cov - kovariančna matrika parametrov hidravličnega modela; det() - determinanta matrike. Kovariančna matrika iz enačbe (3) je podana z izrazom: kjer so: s2 - varianca regresijske napake; J - Jacobijeva matrika z elementi matrike Qy/Qaj (i=1,...,N ; j=1,...,N); W - simetrična, pozitivno definirana matrika utežnih koeficientov; JT - transponirana Jacobijeva matrika. calibration parameters. Eq. (2) is solved using the finite-difference method with Na+1 hydraulic simulations, where the additional simulation is obtained for the initial values, i.e., by a preliminary parameter-value assessment. Better calibrated model parameters give more precise values of the Jacobian matrix coefficients. Consequently, it is reasonable to carry out an iterative procedure of calibration and sampling design (Fig. 1) to reach an acceptable accuracy level with regard to the hydraulic model's purpose [6]. The optimisation problem of the sampling design has two objectives and will be further discussed in the next sections. 2.1 The Objective Function of Calibration Accuracy An increase in the number of measurement locations will consequently increase the confidence level or the accuracy of the obtained parameter assessments. The method used to evaluate the first objective function of the calibration accuracy derives from the regression analysis theory and was successfully used in the development of models for the calibration and sampling design of groundwater models [7]. Later on it was also successfully used in the area of WDS hydraulic models. The first objective function is to evaluate the parameter's confidence region volume. In contrast to the determination of confidence intervals, the volume of a parameter's confidence region deals with the probability that the sought values of Na parameters can at the same time be found in a certain Na dimensional area. The confidence region volume is proportional to the square root of the determinant of the covariance matrix of hydraulic model parameters and can be mathematically expressed as follows [6]: where Cova is the covariance matrix of the hydraulic model parameters; and det() is the matrix determinant. The covariance matrix from Eq. (3) is expressed as follows: where s2 is the regression error variance; J is the Jacobian matrix with the matrix elements d y/d aj (i=1,.. .,N ; j=1,.. .,N ); W is the symmetrical, positively defined matrix of weight coefficients; and JT is the transposed Jacobian matrix. (detCova 1 (3), Cova=s2-(JTWJ )1 (4), Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 821 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 Pri oblikovanju prve ciljne funkcije se lahko brez večje izgube splošnosti izrazov v enačbi (4) predpostavi, da veljajo tipične domneve regresijske analize: natančnost meritev je neodvisna od kraja na VS; vsa merilna oprema, ki bo uporabljena pri zbiranju meritev, ima podobno natančnost; in samo tlaki so predmet obravnave pri optimizaciji izbire merilnih mest. Posledično se lahko matriko utežnih koeficientov W približno izrazi kot diagonalno matriko, katere diagonalni elementi zavzemajo vrednosti 1/a2H, kjer je Na detCov- (8), where Cova-1F is the full inverse covariance matrix taking into account all the potential measurement locations [5]. The determinant of the inverse covari-ance matrix is calculated by means of a numerical method for defining the lower and upper triangular matrix (LU Decomposition) [8]. After the decomposition of the matrices, the determinant is a product of the diagonal elements of the upper triangular matrix. 2.2 The Objective Function of Measurement Costs The second objective function is optimising the costs related to measurements performed on a system. Considered here are the following: (a) capital or investment costs and (b) variable or operational costs. It is difficult to determine general equations to estimate the measurement costs; therefore, the procedure is simplified by the assumption that the main measurement costs for each measurement performed are related only to the operational part of the total costs. The objective function can thus be expressed with regard to the number of measurement locations. Its purpose is to minimize the measurement costs and indirectly also the number of measurement locations. It is desirable to use the second objective function in a normalised form [5]: min F =N max F =1 N NF (9), kjer sta: N - število merilnih mest na sistemu; NF -število vseh možnih merilnih mest v sistemu. Iz izraza (9) je razvidno, da tako oblikovana druga ciljna funkcija teži k čim manjšemu številu merilnih mest. 2.3 Vzpostavitev optimizacijskega problema Ker sta si zgoraj navedeni ciljni funkciji protislovni, je treba najti rešitev, ki bo v največji meri zadovoljevala tako prvo kakor drugo ciljno funkcijo. Prva ciljna funkcija bo najboljša, če bodo meritve zbrane na vseh možnih merilnih mestih, medtem ko bo druga najboljša, če bo število merilnih mest čim manjše, saj bodo s tem povezani tudi najnižji stroški. Optimizacijski problem je sestavljen iz naslednjih delov: (a) ciljne funkcije, (b) optimizacijskih spremenljivk oziroma neznank in (c) robnih pogojev. Formulacija optimizacijskega problema za izbiro merilnih mest je sestavljena iz dveh ciljnih funkcij, opredeljenih v zgornjih where N is the number of measurement locations in the system; NF is the number of all potential measurement locations in the system. Eq. (9) shows that the thus formulated second objective function tends towards the lowest possible number of measurement locations. 2.3 Definition of the Optimisation Problem Since the above-mentioned objective functions are mutually contradictory, a solution has to be found that will, to the largest extent, satisfy both the objective functions. The first objective function will be optimal if measurements are collected at all possible measurement locations, while the second will be optimal if the number of measurement locations is zero, since this will incur the lowest costs. The optimisation problem involves the following parts: (a) the objective function; (b) the optimisation variables or unknowns; and (c) the constraints. The optimisation problem formulation for the sampling Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 823 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 odstavkih. Normalizirana izraza (8) in (9), ki sta oblikovana na način, da se njuni vrednosti zveča, sta združena v en izraz: design consists of two objective functions defined in the previous paragraphs. The normalised Eq. (8) and Eq. (9), formulated so as to maximise their values, are joined into a single expression: maxi?= H>>-^ Pe (10), N>Nm 0 , Nmm 0); N - največje Število merilnih mest v sistemu (N < NF); NF - število vseh možnih merilnih mest v s ax stemu; pc1 in pc2 - stroškovna koeficienta kazenske funkcije. Optimizacijska orodja se uporabljajo za reševanje zahtevnih in obsežnih optimizacijskih problemov. Genetski algoritmi (v nadaljevanju GA) so razred nelinearnih, prilagodljivih in hevrističnih metod za iskanje in optimizacijske probleme in spadajo v skupino razvojnih algoritmov. GA posnemajo naravno načelo reprodukcije, mutacije in naravne izbire za zagotovitev preživetja najbolj sposobnega oziroma najboljšega osebka, tj. rešitve. Načelo GA in njegova uporaba pri optimizaciji VS je podano v [9] do [11]. GA so optimizacijska metoda, ki se posebej dobro izkaže pri reševanju velikih in zapletenih problemov z mnogimi lokalnimi ekstremi in s katero se skoraj vedno najdejo rešitve blizu najboljše [12]. Ta lastnost izvira iz dejstva, da GA raziskujejo prostor rešitev s skupnostjo (populacijo) kromosomov, tj. možnimi rešitvami, ki so naključno razpršene po celotnem prostoru rešitev. Ena od prednosti GA je tudi ta, da zahtevajo le vrednotenje ciljne funkcije za optimizacijski postopek brez zahtevnih numeričnih opravil ter možnost uporabe tako where E is the common objective function; wi are the weight coefficients to determine the importance of an individual objective function; p is the norm order; Fi is the i-th objective function; and Pe is the penalty function. The weight coefficients w1 and w2 are selected so that their sum is equal to 1. The values assumed by the joint objective function E are within the interval (0, 1), if this does not exceed the constraints. The penalty function is used to introduce explicit constraints into an optimisation problem and will represent the maximum and minimum values of the number of measurement locations: N 0); Nmax is the maximum number of measurement locations on the system (Nmax < NF); NF is the number of all the potential measurement locations in the system; and pc1 and pc2 are the cost coefficients of the penalty function. Optimisation tools are used for solving demanding and comprehensive optimisation problems. Genetic algorithms (hereinafter referred to as GAs) are a class of nonlinear, adaptive and heuristic methods for search and optimisation problems and belong to the group of evolutionary algorithms. GAs mimic nature's principles of reproduction, mutation and natural selection to ensure the survival of the fittest and therefore the best individual, i.e., the best solution. The principle of GAs and their application to WDS optimisation are given by [9] to [11]. GAs are an optimisation method especially useful in solving large and complex problems with many local minimums and maximums that almost always provides a solution close to the optimum one [12]. This feature arises from the fact that GAs explore the solution space with a population of chromosomes, i.e., possible solutions randomly distributed across the entire solution space. One of the advantages of GAs is that they require only the evaluation of the objective function for the optimisation procedure, without demanding numerical operations, as well as 824 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 diskretnih kakor tudi zveznih spremenljivk v postopku optimizacije [13]. 3 OVERITEV MODELA ZA IZBOR MERILNIH MEST NA VS ANYTOWN Za uporabo in overitev prikazane metode je bil izdelan optimizacijski model za najboljšo izbiro merilnih mest z uporabo GA ki je poimenovan IMMe. Samo preizkušanje pa je bilo izvedeno na hidravličnem modelu “Anytown“, ki ga je prvi definiral Thomas M. Walski [14]. Omenjeni model je bil izbran zaradi njegove razširjenosti na področju preizkušanja različnih orodij za analizo VS in zasnove, ki vključuje tudi določene značilnosti dejanskih VS. Optimizacijski model izbire merilnih mest je namenjen določevanju merilnih mest, ki bodo sporočali najbolj še informacije v fazi umerjanja izbranih parametrov hidravličnega modela. Koeficienti hrapavosti cevi po Hazen-Williamsu so bili izbrani kot parametri umerjanja. Čeprav je v hidravličnem modelu “Anytown“ število parametrov enako številu cevi (tj. 34 cevi), se lahko število parametrov znatno zmanjša prek združevanja koeficientov hrapavosti, s čimer se je določilo pet skupin (N = 5). Umerjanje parametrov hidravličnih modelov tj. koeficientov hrapavosti cevi, zahteva kakovostne meritve hidravličnih veličin, ki bodo v največji meri podajale zadostno količino informacij za učinkovito umerjanje [15]. Optimizacijski problem je bil oblikovan na način, da določa najboljša merilna mesta za pet neodvisnih ustaljenih hidravličnih simulacij, tj. štirje neodvisni požarni odvzemi vode in ob normalni porabi. Ker je skupno število vozlišč N = 16, je največje število meritev NO = 80 vrstic (16 vozlišč krat 5 obtežnih primerov). Izhajajoč iz teoretičnega ozadja izbire merilnih mest, se tlačna občutljivost vseh možnih merilnih mest zapiše v Jacobijevi matriki, ki ima NO = 80 vrstic in N = 5 stolpcev. Optimizacija ciljne funkcije (enačba (10)) z GA se je posebno dobro izkazala v izjemno kombinatornih problemih, kamor spadata tako umerjanje kakor tudi izbira merilnih mest [12]. Uporabljeni so bili Simple GA v povezavi z binarnim kodiranjem kromosomov, sestavljenih iz 16 genov (16 možnih merilnih mest). Populacija 100 kromosomov je bila začeta in iz nje so se izbirali starševski kromosomi z uporabo t.i. “ruletnega kolesa” ter verjetnostjo križanja 0,75 in verjetnostjo pojava mutacije 0,07. Vzpostavitev nove generacije the possibility of using both discrete and continuous variables in the optimisation procedure [13]. 3 SAMPLING DESIGN MODEL VERIFICATION FOR AN ARTIFICIAL WDS IN ANYTOWN For the application and verification of the presented method, an optimisation model (called IMMe) for the optimal selection of measurement locations using GAs was developed. The verification process was carried out on the Anytown hydraulic model, which was first defined by Thomas M. Walski [14]. His model is seen as a benchmarking model for testing various tools of WDS analysis and implies realistic concepts of real WDS characteristics. The sampling design optimisation model was applied to determine the measurement locations that will provide the most information for the model's parameter calibration. Pipe-roughness coefficients according to Hazen-Williams were selected as the calibration parameters. Although the Anytown model consists of only 34 individual pipe-roughness coefficients, their number was seriously reduced by introducing pipe grouping criteria, which resulted in five groups (N = 5). Calibrating the model parameters, i.e., the pipe roughness coefficients, requires high-quality measurements of system variables, which will, to the largest extent possible, provide sufficient information for an efficient calibration [15]. The sampling design optimisation problem was formulated to determine optimal measurement locations for five independent steady-state loading conditions, i.e., four independent fire flow tests and a normal operation loading condition. Since the total number of nodes is N = 16, the maximum number of observations is NO max 80 rows (16 nodes x 5 loading conditions). Following the theoretical background of the sampling design, the pressure sensitivity of the possible measurement locations is expressed by the Jacobian matrix consisting of NO = 80 rows and N = 5 columns. The optimisation of the objective function (Eq. (10)) by the GA thus proved to be successful in extremely combinatorial problems, like sampling design and calibration [12]. Simple GAs were applied and solutions were presented in binary coding for the chromosome composed of 16 genes (16 possible measurement locations). A population of 100 chromosomes was initialised to perform an evolution chromosome based on a roulette-wheel parent selection with a probability of 0.75 and a mutation probability of 0.07. Full generation replacement with elitism was Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 825 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 potomcev iz starševskih kromosomov je potekala s popolno zamenjavo populacije skupaj s funkcijo odličnosti [13]. Poleg opisanega primera Simple GA so bili za potrebe overitve modela in njegove uporabe na primeru VS Sežana uporabljeni tudi ustaljeni GA s celoštevilčnim kodiranjem kromosomov. Ostali parametri GA so ostali enaki kakor v zgornjem primeru. Pri reševanju optimizacijskega problema izbire merilnih mest so bili uporabljeni tako Simple kakor ustaljeni GA. Rezultati optimizacijskega postopka so prikazani na sliki 2, na kateri je prikazana prva ciljna funkcija F1, tj. natančnosti umerjanja, v odvisnosti od števila merilnih mest. Na splošno se lahko podata dve ugotovitvi, tj. vključevanje dodatnih merilnih mest povečuje natančnost umerjanja in krivulja ciljne funkcije F1 spremeni nagib. V pričujočem primeru se nagib spremeni med 4. in 5. merilnim mestom, kar pomeni, da je uvajanje nadaljnjih merilnih mest manj učinkovito. Rezultati na sliki 2 so prikazani skupaj s primerjavo z rezultati modela Kapelan idr. [5], ki so povzeti iz literature in so namenjeni postopku verifikacije. Opravljena overitev modela za izbiro merilnih mest v obeh primerih uporabe posameznih tipov GA izkazuje enake rezultate. Ker je obsežnost optimizacijskega problema na dejanskem VS Sežane prevelika za uporabo Simple GA z binarnim kodiranjem, bodo uporabljeni le ustaljeni GA v kombinaciji s celoštevilčnim kodiranjem kromosomov. applied to create a new generation of offspring chromosomes [13]. Besides the described example of the Simple GA, also a Steady-state GA with integer coding were used for model verification for its later use on the Sežana WDS example. The other GA parameter settings remained the same as those above. The optimisation problem of sampling design was solved by using both Simple and Steady-state GAs. The results of the optimisation process are presented in Fig. 2, where the first objective function F1, i.e., the objective function of the calibration accuracy, is presented in relation to the number of measurement locations. In general, two characteristics can be perceived, i.e., the inclusion of additional measurement locations results in a higher calibration accuracy, and the curve of the objective function F has a change of slope. In the presented case the slope changes between the 4th and 5th measurement locations, which indicates that the introduction of further measurement locations would be far less efficient. The results in Fig. 2 are also compared to the sampling design model of Kapelan et al. [5] by literature review for model verification purposes. The performed verification of the sampling design model shows the same results in both cases of the use of individual types of GA. Since the application of the optimisation problem to the real Sežana WDS is considered to be too large for solving the problem by the use of the Simple GA with a binary coding, only the steady-state GA in combination with integer coding will be applied to the aforementioned case study. 1.000 0.900 0.800 0.700 0.600 0.500 0.400 0.300 0.200 0.100 0.000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Število merilnih mest N / Number of measuring locations N Sl. 2. Rezultati modela izbire merilnih mest IMMe in primerjava s Kapelan idr. [5] Fig. 2. Results of "IMMe" model and a comparison to Kapelan et al. "CAO1" model [5] 826 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 4 PRIMER VS SEŽANA Overjena metoda izbire merilnih mest je bila uporabljena na dejanskem VS mesta Sežana, da bi vzpostavili niza merilnih mest na VS za zbiranje kakovostnih meritev za razpoznavo parametrov umerjanja. Uporaba optimizacijskega modela z uporabo genetskih algoritmov je bila izvedena za določevanje merilnih mest tlakov za umerjanje koeficientov hrapavosti cevovodov pod neodvisnimi požarnimi odvzemi vode, tj. odpiranje hidrantov VS mesta Sežana je na Primorskem in oskrbuje približno 5.500 prebivalcev, povprečna poraba pa je ocenjena na 16,55 l/s. Popoln hidravlični model VS je bil vzpostavljen z uporabo ustreznih podatkov geografskega informacijskega sistema (GIS) in računalniško podprtega načrtovanja upravljalca Kraški vodovod Sežana. Postavljeni model sestavljajo 1 vodni vir, 6 vodnih zbiralnikov, 4črpalke, 696 vozlišč, 738 cevi in 1 zniževalni ventil tlakov. Osrednji oz. mestni del VS je oskrbovan prek dveh vodnih zbiralnikov, ta dva sta v bližini prenosnega cevovoda, ki dovaja vodo naprej na obalno področje. Popoln hidravlični model je bil poenostavljen, tako da je ogrodni model sestavljalo le še 132 vozlišč in 173 cevi. Oba hidravlična modela sta bila grobo umerjena z meritvami pretoka v cevovodih in ravni vode v vodohranih. 4.1 Oblikovanje problema izbire merilnih mest Koeficienti hrapavosti cevovodov ogrodnega hidravličnega modela so bili razvrščeni po “ameriškem” kriteriju združevanja [2]. Končno število skupin koeficientov hrapavosti je bilo 48, kar pa bi posledično privedlo do izjemno velikega števila merilnih mest, potrebnega za rešitev inverznega problema določevanja parametrov, tj. umerjanja [15]. Nanašajoč se na ciljno funkcijo stroškov izvajanja meritev, lahko ugotovimo, da je množično zbiranje meritev zelo drag postopek. Zato je bilo število skupin koeficientov hrapavosti zmanjšamo z uporabo ohlapnejših kriterijev, vezanih samo na podatke materiala in starosti cevovodov, ki so bili najbolj nezanesljivi. Tako je bilo določenih 16 skupin hrapavosti (Na = 16), kar naj bi omogočalo vzpostavitev dobro določenega problema umerjanja. Za potrebe določitve občutljivostnih koeficientov za postavitev Jacobijeve matrike so bile določene predhodne ocene koeficientov hrapavosti za vsako skupino na podlagi strokovnih ocen in ustreznih preglednic. 4 CASE STUDY OF SEŽANA The verified IMMe sampling design model was applied to the real-life WDS of the town of Sežana, to find an optimal set of measurement locations on the WDS to collect quality measurements for the identification of model parameters. To identify the pressure measurement locations for the calibration of the pipe roughness values, the multiple independent fire flow loading conditions, i.e., hydrant flushing, were assessed and GAs were applied to perform the optimisation task. The WDS of Sežana is located in the coastal region of Slovenia, supplying a population of around 5,500 residents, while the average residential and industrial demand is estimated to be 16.55 l/s. A full-pipe WDS model was established using the relevant GIS and CAD data, resulting in a WDS model consisting of 1 reservoir, 6 tanks, 4 pumps, 696 junctions, 738 pipes and 1 pressure reducing valve. The inner part of the WDS is supplied through two tanks, which are located near the transmission main, delivering water to the coastal region. For the purposes of the sampling design analysis the full pipe model was skeletonized to a model of 132 junctions and 173 pipes. Both, full pipe and skeletonized WDS models were macro-calibrated for demands using flow and tank level measurements. 4.1 Formulation of the Sampling-Design Problem Using the sampling design approach on the skeletonized WDS model, pipe roughness values were grouped using the "American" grouping criterion [2]. The resulting number of pipe roughness groups is 48, which would consequently lead to a high number of measurement locations for the inverse problem of parameter identification, i.e., the calibration [15]. According to the second objective function, measurement collection is a costly process. Therefore, the number of pipe roughness groups was reduced according to loosened criteria of the pipe material and age, which were unreliable and sparse. A total of 16 pipe roughness groups (N = 16) were created, which should ennsure a well-posed calibration problem. The pipe roughness values for each group were previously estimated using expert judgment and relevant pipe roughness tables for the purpose of sensitivity analysis and Jacobian matrix determination. 827 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 Poleg krajev tlačnih meritev je bilo treba določiti tudi kraje odpiranja hidrantov, število mogočih lokacij je 95 (NLd, = 95) od skupaj 132 vozlišč. Izvedena je bila občutl ax ivostna analiza krajev odpiranja hidrantov, kjer so vozlišča najbolj občutljiva na povečanje hitrosti v ceveh [16]. Skupaj je bilo določenih 14 krajev odpiranja hidrantov (NL d = 14), pri katerih se je reševal problem izbire merilnih mest za umerjanje koeficientov hrapavosti. Optimizacijski problem izbire merilnih mest je bil oblikovan skladno s ciljem določitve najboljših krajev merilnih mest za umerjanje 16 skupin hrapavosti cevovodov (N = 16). Kraji zbiranja tlačnih meritev na sistemu so bile omejene na 95 (N = 95) mogočih krajev merilnih mest, kjer bodo ma zbrane meritve pri 14 (NL d = 14) neodvisnih ustaljenih obtežnih primerih. Izvedena je bila analiza občutljivosti tlakov v vozliščih za vse mogoče kraje merilnih mest in vse obtežne primere za določitev tlačnih občutljivosti za 16 skupin hrapavosti cevovodov. Postavljena je bila ti. “cela” Jacobijeva matrika za vsa mogoča merilna mesta z NO = 1330 vrsticami (95 vozlišč x 14 obtežnih primerov) in N = 16 stolpcev (16 skupin koeficientov hrapavosti cevovodov). Ker je Jacobijeva matrika edinstvena matrika za definiran problem izbire merilnih mest VS, jo je treba le enkrat izračunati pred optimizacijskim postopkom [5], medtem ko so vse rešitve optimizacijskega postopka izpeljane iz polne Jacobijeve matrike. Rešitve postopka izbire merilnih mest so bile pridobljene z ustaljenim GA skupaj s celoštevilčnim kodiranjem kromosomov, ki predstavljajo indekse krajev merilnih mest. Kodiranje s celimi števili je dobilo prednost pred binarnim kodiranjem, ker je primernejše za reševanje izbire merilnih mest na velikih realnih VS [5]. Možnost ponavljanja ista merilna mesta v eni in isti rešitvi je bila odpravljena z izbrisom vsakega dodatnega kraja merilnega mesta iz te rešitve, če bi se le-ta ponavljala. V optimizacijskem postopku GA je bila uporabljena skupnost 200 kromosomov z možnostjo križanja v dveh točkah kromosoma z verjetnostjo 0,85 in verjetnostjo mutacije v genu 0,07. Za določevanje funkcije sposobnosti so bile uporabljene naslednje vrednosti utežnih koeficientov ciljnih funkcij w1 = 1 in w = 0 ter potenca p = 1. Večkratni zagoni GA so bili uporabljeni v optimizacijskem postopku izbire merilnih mest. Besides the determination of pressure measurement locations, hydrant flushing locations needed to be identified. A total number of 95 (NL d, = 95) out of 132 junctions were identified. A sensitivity analysis was performed to identify the hydrant flushing locations, i.e., junctions at which pipes were most sensitive to increased velocities [16]. A total of 14 locations (NL d = 14) were determined, at which the sampling design problem for the calibration of the pipe roughness values was solved. The sampling design problem was formulated in order to obtain the optimal measurement locations for identifying a total number of 16 pipe roughness groups (N = 16). The pressure data collection locations were reduced to 95 (N = 95) possible measurement locations, where data could be obtained from 14 (NL d = 14) independent steady-state loading conditions. A pressure sensitivity analysis was performed for all the possible measurement locations and all the loading conditions to obtain the pressure sensitivities of the 16 pipe roughness groups. A full Jacobian matrix was written with NO = 1330 rows (95 nodes x 14 loading conditions) and Na = 16 columns (16 pipe roughness groups). Since the Jacobian matrix is a unique matrix for a defined sampling design problem of a WDS it has to be calculated only once prior to the optimisation process [5], while the estimations on sampling design solutions are derived from the full Jacobian matrix. The sampling design solutions were obtained using a Steady-State GA together with integer coding of the chromosomes, which in turn represent the IDs of the measurement locations. Integer coding was preferred to binary coding since integer coding is more suitable for large, real-life sampling design problems [5]. The possibility of repeated measurement locations in one sampling design solution was handled with the exclusion of all the additional measurement devices at one and the same measurement location. In the GA search process a population of 200 chromosomes was used with a two-point crossover probability of 0.85 and a gene mutation probability of 0.07. The weighting coefficients w1 = 1 and w2 = 0, and an exponent of p = 1 were used to evaluate the fitness function. Trivial solutions (with N = 0 and N = 95) were excluded and multiple GA runs were performed to identify non-trivial sampling design solutions. 828 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 r...........> -IMMe Število merilnih mest N / Number of measurement locations N Sl. 3. Rezultati izbora merilnih mest modela IMMe v VS Sežana Fig. 3. Results of IMMe sampling design model on WDS of Sežana 4.2 Rezultati izbire merilnih mest VS Sežana Pri izbiri merilnih mest se določa razmerje med prvo in ciljno funkcijo z uporabo utežnih koeficientov w1 in w2. Ker je razmerje utežnih koeficientov težko natančno določiti, se lahko v postopku uporabi stalno število iskanih merilnih mest. Zato je bil izbran utežni koeficient w = 0. Z uporabo celoštevilčnega kodiranja vseh mogočih merilnih mest (indeksacija) in z določitvijo dolžine kromosoma z želenim številom merilnih mest je možno točno določiti najboljša merilna mesta. Rezultat takšnega postopka je diagram na sliki 3, ki pomeni natančnost umerjanja parametrov (prva ciljna funkcija) v odvisnosti od določenega števila merilnih mest (druga ciljna funkcija). Na sliki 3, ki prikazuje natančnost umerjanja parametrov, tj. prvo ciljno funkcijo, je razvidno strmo naraščanje funkcije F1 do 13 merilnih mest. Zatem se z dodajanjem števila merilnih mest rast funkcije F1 upočasni, kar pomeni, da vsako dodano merilno mesto prispeva manj “informacije” k natančnosti umerjanja parametrov. Optimizacijski model podaja potrebno pomoč pri določevanju razporeditve merilnih mest po VS. Rezultati s slike 3 so lahko pomoč v dveh primerih odločanja: (a) če je vnaprej izbrana natančnost umerjanja parametrov, ki jo želimo doseči v samem postopku umerjanja, lahko ugotovimo koliko merilnih mest je potrebnih; (b) ocenimo kakšno natančnost umerjanja lahko pričakujemo pri izbranem številu 4.2 Results of the Sampling Design Case Study -WDS of Sežana The sampling design problem deals with the trade-off between the first and the second objective functions using the weighting coefficients w1 and w2. Since such a trade-off and the corresponding weights are hard to correctly identify, it is preferable to apply the search process for a fixed number of measurement locations; therefore, w2 = 0. Using integer coding of all the measurement locations and a chromosome length equal to the number of desired measurement locations, it is possible to correctly identify a sampling design solution within those constraints. The result of such a search process is a diagram of the calibration parameter accuracy (the first objective function) against the number of measurement locations (the second objective function), and is shown Fig. 3. Fig. 3 shows that the calibration parameter accuracy, i.e., the objective function 1, rapidly increases until it reaches a total of 13 measurement locations. Later, the slope rises more slowly, indicating that every additional measurement location adds less "information" to the calibration parameter accuracy. The optimisation model provides the necessary support in determining how the selected number of measurement locations is to be distributed across the WDS. There are two ways to interpret the results from Fig. 3: (1) one can determine in advance what level of calibration parameter accuracy is desirable for the calibration process, and through that the number of measurement locations can be identified; (2) the level of calibration parameter accuracy can be estimated from a certain Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 829 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 Preglednica 1. Rezultati izbire merilnih mest za primer VS Sežane Table 1. Results of sampling design for WDS of Sežana Ciljna funkcija Objective function ID vozlišč / Node ID F 1 N 13 41 42 45 49 50 52 55 67 68 70 83 90 97 98 99 112 114 117 118 119 132 0.502 10 1 111 0.556 11 0.608 12 1 0.646 13 11 0.671 14 0.693 0.712 15 16 111 111 111 111 111 11 1 11 11 111111 11 11 111 1 11 111 1 1 111 111 111 111 1 111 0.731 17 1111 0.748 1111 0.764 0.777 0.789 19 20 21 111 11 1 111 1 111 111111 11111 1111 1111111 11111 1 11 111 111 11 1 11111 11111111111111111 1 111 111 111 111 0.800 22 11111111111111111 11 111 merilnih mest oziroma razpoložljivi merilni opremi. Končni rezultat je določitev najboljših merilnih mest z uporabo GA. Optimizacijski rezultati s slike 3 so ločeno podani v preglednici 1, kjer so prikazana najboljša vozlišča za izbrano število merilnih mest. V preglednici 1 je podan le delež celotnih rešitev optimizacije in predstavlja rešitve za 10 do 22 merilnih mest, tj. določitev vozlišč, kjer bo nameščena merilna oprema. Metodologija izbire merilnih mest modela IMMe sloni na vrednotenju tlačnih občutljivosti na spremembe parametrov umerjanja, zato je primerno postaviti vprašanje tlačnih občutljivosti in merilnih mest [8]. Vsota tlačnih občutljivosti posameznih merilnih mest, ki je podana na sliki 4, prikazuje, da večja ko je tlačna občutljivost vozlišča, bolj je vozlišče primerno, da postane merilno mesto. Kot primer bo obravnavano vozlišče 99, ki ima veliko tlačno občutljivost pri spremembi parametrov umerjanja in je blizu odvzema požarne vode, kar povzroča povečane pretoke in s tem tudi hidravlične izgube, poleg tega pa je tudi oddaljeno od vodnih virov. Izsledki, ki izhajajo iz predhodnih ugotovitev, so v skladu z ugotovitvami drugih raziskovalcev ([5] in [6]), ki trdijo, da naj se tlačne meritve zbirajo blizu vozlišč z veliko porabo (odjemom) in naj bodo na obrobju VS, daleč proč od vodnih virov. Določevanje najboljših N merilnih mest z uporabo kriterija občutljivosti posameznih merilnih mest ni vedno tudi najboljše za določevanje skupine N-1 merilnih mest [6]. Upoštevanje načela nalaganja v tem primeru lahko vodi v napačne razlage, če upoštevamo povezavo med parametri umerjanja ob izračunu prve ciljne funkcije. number of available measurement locations, e.g., the measurement equipment that can be installed. The final result is an optimal set of measurement locations obtained within the GA search process. The optimisation results in Fig. 3 are directly related to Table 1, where optimal sets of measurement location IDs are given. Table 1 is just a segment of the entire sampling design results and presents solutions from 10 to 22 measurement locations, i.e., the table determines the node IDs where the measurement devices are to be placed. The sampling design methodology of the IMMe model is based on quantifying the pressure sensitivities to the calibration parameter changes; therefore, the pressure sensitivities and measurement location selection should be addressed [8]. Fig. 4 shows briefly the sums of the pressure sensitivities at individual measurement locations, just to indicate that the higher the node sensitivity the better the node is suited to being selected as a measurement location. The case of node 99, with the high pressure sensitivity for all the calibration parameters changes, situated near the fire flow discharges, which causes high flows and thus large hydraulic losses, is also quite remote from the water sources. This behaviour is also in agreement with the general findings by different researchers ([5] and [6]) stating that pressure measurements should be collected near the high consumption nodes and on the margin of the WDS far away from the water sources. Determination of an optimal set of N measurement locations by using the sensitivity criterion for a certain measurement location is not always optimal for determining the set of N-1 measurement locations [6]. Using the superposition principle could be misleading if the correlation between the calibration parameters becomes significant when calculating the first objective function. 1 1 1 1 1 1 1 1 1 1 1 830 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 a i * S, 1-5 -t 1 " , l n - .l n n n Sl. 4. Vsota tlačnih občutljivosti vozlišč Fig. 4. Sum of pressure sensitivities Sl. 5. Najbolj«e lokacije merilnih mest za primer 13 merilnih mest Fig. 5. Optimal locations for 13 measurement locations Izjavo lahko podkrepimo kar z rezultati izbire najboljših merilnih mest iz preglednice 1 in tlačnih občutljivosti s slike 4. Zanimiva primerjava z vidika tlačnih občutljivosti je med vozliščema 99 in 112. S This case can be underlined by examining the sampling design results from Table 1 and the pressure sensitivities from Fig. 4. From the point of view of the pressure sensitivity of the measurement Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 831 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 slike 4 je razvidno, da izkazuje vozlišče 99 precej večjo tlačno občutljivost kakor vozlišče 112, medtem ko je mogoče iz preglednice 1 razbrati, da je vozlišče 112 najboljše merilno mesto v primeru N = 12, medtem ko se vozlišče 99 ne uvršča v najboljši niz merilnih mest. Načelo nalaganja merilnih mest se izkaže za napačno, saj se vozlišče 112 ne pojavlja v nobenem od naslednjih petih naborov najboljših merilnih mest. Obstaja več razlogov za omenjene razlike, ki pa imajo odločilen vpliv na izbiro merilnih mest: (a) razvrščanje parametrov umerjanja, (b) hidravlične razmere, ki jih povzročijo požarni preizkusi in povečane hidravlične izgube, (c) bližina vozlišča 112 vozlišču s povečano porabo in (d) vpliv topologije omrežja. Pri razlagi primera N = 12 merilnih mest prispevajo vozlišča 112 in preostala izmed najboljših merilnih mest večjo natančnost umerjanja parametrov, kakor to izkazujejo njihove posamične tlačne občutljivosti. Opazovana lastnost izhaja iz povezave med koeficienti Jacobijeve matrike, ki določa strukturo najboljših merilnih mest glede na največjo natančnost umerjanja parametrov hidravličnega modela. Prostorska porazdelitev najboljših 13 merilnih mest, podanega z vozlišč ID, je prikazana na sliki 5. Od 14 leg povečanega odvzema je bilo za namestitev merilne opreme izbranih samo pet vozlišč, medtem ko je preostalih 8 razporejenih drugod po VS Sežane. Z upoštevanjem dejstva, da največ “informacije” podajo prav vozlišča s povečano porabo, obravnavani primer dokazuje, da to le delno drži. Glede na dejstvo, da so se koeficienti hrapavosti cevi razvrstiti glede na podane kriterije, so najboljša merilna mesta določena na krajih, kjer bodo meritve zagotavljale največ “informacij” za čim večjo natančnost umerjanja koeficientov hrapavosti cevi. 5 SKLEPI Razvoj, overitev in uporaba računalniškega optimizacijskega modela IMMe za najboljšo izbiro merilnih mest z uporabo GA so bili uspešni. Metodologija izbire merilnih mest upošteva lastnosti občutljivostne matrike, ki je določena s strukturo parametrov umerjanja, hidravličnimi razmerami ob zbiranju meritev, hidravličnimi veličinami, ki se merijo, in kraji zbiranja meritev. Optimizacijski problem izbire merilnih mest je določen z dvema kriterijema, in sicer največje natančnosti umerjanja in najmanjšega števila merilnih mest. Uporaba GA v postopku izbora locations, a comparison of the nodes 112 and 99 is interesting. As can be seen from Fig. 4., node 99 has a much higher pressure sensitivity than node 112, while Table 1 in turn shows that node 112 presents the optimal measurement location in the case of N = 12, when node 99 is not selected. Differences to the superposition principle arise because node 112 does not occur in any of the following five sets of optimal measurement locations. There could be several reasons for the mentioned differences, all having a decisive impact on the sampling design: (a) calibration parameter grouping, (b) hydraulic conditions caused by the fire flow tests and its increased head losses, (c) proximity of node 112 to a node with increased consumption, (d) influence of network topology. When considering N = 12 measurement locations, node 112 and others from the optimal set contribute to a higher calibration parameter accuracy due to the first objective function, regardless of the individual pressure sensitivities. This property can be observed because of the correlation of the coefficients of the sensitivity matrix, which indicates that the optimal measurement locations are those which contribute the most to the identification of the calibration parameters. The resulting node IDs for the 13 most informative measurement locations from Table 1 are presented in Fig. 5. Out of 14 hydrant flushings only 5 measurement locations correspond to the same location, while the remaining 8 are located elsewhere throughout the WDS. When referring to the fact that measurement data provides the most "information" at locations of high discharge, the presented case study shows this is only partly true. Optimal measurement locations were placed at positions where measurements provide most "information" for calibrating those parameters, i.e., the calibration grouped pipe roughness coefficients. 5 CONCLUSIONS The development, verification and application of the optimisation model called IMMe for optimal sampling design by using GAs were successful. The sampling design methodology takes into account the properties of a sensitivity matrix determined by the structure of the calibration parameters, the hydraulic conditions during measurement collection, the hydraulic quantities measured, and the measurement locations. The optimisation problem of the sampling design is determined by two criteria, i.e., on the maximisation of the calibration accuracy and on the 832 Banovec P. - Kozelj D. - Šantl S. - Steinman F. Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 najboljših merilnih mest hidravličnega modela Anytown se je izkazala za zelo učinkovito. Po opravljeni overitvi je bil model IMMe uporabljen na dejanskem VS Sežana, kjer so bila določena najboljša merilna mesta za umerjanje koeficientov hrapavosti cevovodov. Nadaljnje raziskovalno delo naj bi bilo usmerjeno v določitev ustreznejšega zapisa druge ciljne funkcije, ki bi bila izražena oziroma odvisna neposredno od stroškov izvajanja meritev, hkrati pa tudi v vrednotenje uporabe metodologij na dejanskih VS. Zahvala Rezultati raziskave so delno financirani v okviru raziskovalnega programa P2-180 in raziskovalnega projekta L2-6468, za katerega je sredstva zagotovila Agencija za raziskovalno dejavnost Republike Slovenije, s tesnim sodelovanjem University of Exeter, VB. minimisation of the number of measurement locations. The use of GAs in the sampling design procedure on the artificial hydraulic model of Anytown proved very efficient. After verification, the IMMe model was applied to a real WDS of Sežana, where optimal measurement locations were obtained for the pipe roughness calibration. Further research work is focused on a more appropriate expression for the second objective function, which would be directly dependent on the measurement costs and in parallel research, on other assessments of the sampling on the WDS. Acknowledgments The obtained results are partially supported by the research programme P2-180 and research project L2-6468-0792 by the Slovenian Research Agency, with the close collaboration of the University of Exeter, UK. 6 LITERATURA 6 REFERENCES [I] Ormsbee, L.E., Lingireddy, S. (1997) Calibrating hydraulic network models, Journal AWWA, Volume 89, Number 2, 1997, p. 42-50. [2] Walters, G.A., Savic, DA., Morley, M., de Schaetzen, W. (1998) Calibration of water distribution network models using genetic algorithms, Proc. 7th International Conference on Hydraulic Engineering Software - Hydrosoft 98, Southampton, UK, p. 131-140. [3] Lansey, K.E., El-Shorbagy, W., Ahmed, I., Araujo, J., Haan, C.T (2001) Calibration assessment and data collection for water distribution networks, Journal of Hydraulic Engineering, Volume 127, Number 4, 2001, p. 270-279. [4] ECAC (1999) Calibration guidelines for water distribution modelling, Proc. AWWA 1999 Imtech Conference, Seatlle, USA. [5] Kapelan, Z., Savic, DA., Walters, GA. (2003) Multiobjective sampling design for water distribution model calibration, Journal of Water Resources Planning and Management, Volume 129, Number 6, 2003, p. 466-479. [6] Bush, CA., Uber, J. (1998) Sampling design methods for water distribution model calibration, Journal of Water Resources Planning and Management, Volume 124, Number 6, 1998, p. 334-344. [7] Knopman, D.S., Voss, C.I. (1989) Multiobjective sampling design for parameter estimation and model discrimination in groundwater solute transport, Water Resources Research, Volume 25, Number 10, 1989, p. 2245-2258. [8] Kozelj, D., Šantl, S., Steinman, F., Banovec, P. (2005) Sampling design for calibration of water distribution system models by genetic algorithms, Proceedings of the Eight International Conference on Computing and Control for the Water Industry, University of Exeter, UK, p. 173-178. [9] Goldberg, D.E. (1989) Genetic algorithms in search, optimization and machine learning, Addison-Wesley Publishing Company, USA. [10] Steinman, F, Banovec, P., Šantl, S. (2001) Genetic-algorithms-supported planning of water supply systems, Journal of Mechanical Engineering, Volume 47, Number 6, 2001, p. 263-279. [II] Keedwell, E., Khu, S.T (2005) A hybrid genetic algorithm for the design of water distribution networks, Engineering Applications of Artificial Intelligence, Volume 18, Number 4, June 2005, p. 461-472. Izbor merilnih mest na vodovodnih sistemih - Sampling Design for Water Distribution System 833 Strojniški vestnik - Journal of Mechanical Engineering 52(2006)12, 817-834 [12] Simpson, A.R., Dandy, C.G. (1994) Genetic algorithms compared to other techniques for pipe optimization, Journal of Water Resources Planning and Management, Volume 120, Number 4, 1994, p. 423-443. [13] Wall, M., Galib (1996) A C++ library of genetic algorithm components, Mechanical Engineering Department, Massachusetts Institute of Technology, USA. [14] Walski, T.M. et al. (1987) Battle of the network models: Epilogue, Journal of Water Resources Planning and Management, Volume 113, Number 2, 1987, p. 191-203. [15] Mallick, K.N., Ahmed, I., Tickle, K.S. Lansey, K.E. (2002) Determining pipe groupings for water distribution network, Journal of Water Resources Planning and Management, Volume 128, Number 2, 2002, p. 130-139. [16] Meier, R.W., Barkdoll, B.D. (2000) Sampling design for network model calibration using genetic algorithms, Journal of Water Resources Planning and Management, Volume 126, Number 4, 2000, p. 245-250. Naslov avtorjev: doc. dr. Primož Banovec Authors’ Address: Doc. Dr. Primož Banovec Daniel Kozelj Daniel Kozelj Sašo Šantl prof. dr. Franci Steinman Prof. Dr. Franci Steinman Univerza v Ljubljani University of Ljubljana Fakulteta za gradbeništvo in Faculty of Civil and Geodetic geodezijo Engineering Hajdrihova 28 Hajdrihova 28 1000 Ljubljana 1000 Ljubljana, Slovenia primoz.banovec@fgg.uni-lj.si primoz.banovec@fgg.uni-lj.si daniel.kozelj@fgg.uni-lj.si daniel.kozelj@fgg.uni-lj.si saso.santl@evj-kabel.net saso.santl@evj-kabel.net fsteinma@fgg.uni-lj.si fsteinma@fgg.uni-lj.si Prejeto: Sprejeto: Odprto za diskusijo: 1 leto 5.5.2005 Received: Accepted: 25.10.2006 Open for discussion: 1 year 834 Banovec P. - Kozelj D. - Šantl S. - Steinman F.