Calcolo delle reti idrauliche in
pressione mediante una tecnica
mista algoritmi genetici / metodo
di Gauss-Newton
Relatore:
Chiar.mo Prof. Ing.
Michele Mastrorilli
Correlatore:
dott. Ing.
Orazio Giustolisi
Laureando:
Enrico Masini
Una delle
RETI in
PRESSIONE
verificata
applicando la
“tecnica mista”:
algoritmi
genetici/metodo
di Gauss-Newton
Sistema di equazioni

Scopo della tesi è la verifica delle reti idrauliche in pressione,
ossia risolvere il seguente sistema di equazioni “misto” :
i qi + j qj = 0
hj – hj+1 = (Li ki Di-n) qi2 = ri qi2
 nodo
 tronco
Forma matriciale del sistema

Per rendere il calcolo e la scrittura del codice più agevole, si è
posto lo stesso sistema nella forma matriciale proposta da
G.Curto e A.Tumbiolo:
ANT q + Q = 0
R abs(q)q + (AN hN + AS hS) = 0
ESEMPIO: “RETE di CAO”
SERBATOIO
100 m.s.l.m
6
1
3
5
1
2
3
2
4
7
3
4
8
I NODI 2,3,4,5,6 SONO A QUOTA 0 m.s.l.m
6
Sistema di equazioni
 q1  q 2  q 5  Q 2  0
 q 2  q 3  q 4  Q3  0
 q5  q 4  q8  Q4  0
 q 6  q 3  Q5  0
 q3  q8  Q6  0
 h1  h 2  r q  0
2
1 1
13 equazioni in 13 incognite:
 h 2  h 3  r2 q 22  0
q1 q 2 q 3 q 4 q 5 q 6 q 7 q 8
 h1  h 3  r3q 32  0
h 2 h3 h 4 h5 h6
 h 3  h 4  r4 q 24  0
 h 2  h 4  r5q 52  0
 h1  h 5  r6 q 62  0
 h 5  h 6  r7 q 72  0
 h 4  h 6  r8q 82  0
Per una soluzione approssimata:
q1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 h 2 h 3 h 4 h 5 h 6
 q1  q 2  q 5  Q 2  e1
 q 2  q 3  q 4  Q3  e 2
 q 5  q 4  q 8  Q 4  e3
 q 6  q 3  Q5  e 4
 q 3  q 8  Q 6  e5
2
 h1  h 2  r1 q1  e 6
Il sistema diventa:
2
 h 2  h 3  r2 q 2  e 7
2
 h1  h 3  r3 q 3  e8
2
 h 3  h 4  r4 q 4  e 9
2
 h 2  h 4  r5 q 5  e10
2
 h1  h 5  r6 q 6  e11
2
 h 5  h 6  r7 q 7  e12
2
 h 4  h 6  r8 q 8  e13
Per cui risolvere il sistema è equivalente a “minimizzare” la funzione:
13
e   e i2
i 1
ossia risolvere il seguente problema di “ottimizzazione non vincolata”:
min e 
X
13
2
e
i
i 1
funzione obiettivo del problema
detto anche “problema dei minimi quadrati”
dove:
X  (q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 h 2 h 3 h 4 h 5 h 6 )  13
La funzione da “minimizzare” è una funzione “non lineare”, del tipo:
Per esempio, nel caso unidimensionale, si ha una funzione del tipo:
e
x
O
Ci sono più minimi “locali”
e un unico minimo “globale”
>>
Algoritmi tradizionali di “ottimizzazione”:
metodo di Newton, quasi-Newton, Gauss-Newton
Si tratta di metodi che per convergere al minimo usano il
calcolo delle derivate fino al 2° ordine, ossia del:
•vettore gradiente
•matrice hessiana
gk
Gk
Dallo sviluppo in serie di Taylor arrestato ai termini del 2°ordine:
qk = f (xk) + (x  xk)T gk +
1
(x  xk)T Gk (x  xk)
2
Supposto che qk(x) abbia un minimo in x*, annullando il gradiente:
Gk (x*  xk) + gk = 0

x* = xk  Gk-1 gk
Da cui si ottiene, più genericamente:
xk+1 = xk  k*Gk-1 gk
Dove:
-Gk-1 gk
è la direzione di ricerca
k*
è il passo di ricerca
I metodi si differenziano per la determinazione della direzione di ricerca, ossia
per la tecnica usata per calcolare la matrice “hessiana”
Per la determinazione del passo di ricerca, si rifanno ad algoritmi esterni che
risolvono essenzialmente un problema di minimizzazione unidimensionale detto
“ricerca di linea”, ossia ricercano il minimo della funzione:
  f (xk+1  k Gk-1 gk)
lungo la direzione di ricerca stabilita -Gk-1 gk
Tali metodi convergono se risulta:
cioè se la matrice
-1
Gk
gkT Gk-1 gk > 0
è definita positiva:
In tal caso i vettori -Gk-1 gk e -gk sono concordi:
-Gk-1 gk
direzione
di ricerca
-gk direzione di massima
pendenza negativa
xk
La direzione di ricerca è allora direzione di discesa, per cui
risulta:
f (xk+1) < f ( xk )
k
che rappresenta la condizione di convergenza
I metodi di Newton, essendo algoritmi di discesa, convergono
ad un minimo locale, funzione del punto iniziale di ricerca
e
punti iniziale di ricerca
soluzioni
percorsi di discesa
O
<<
x
ALGORITMI GENETICI
Si tratta di una nuova metodologia che consente di determinare
il minimo globale di funzioni spiccatamente non lineari oppure
non continue o non derivabili
POPOLAZIONE INIZIALE
SELEZIONE
FITNESS FUNCTION
Algoritmi genetici:
RIPRODUZIONE
OPERATORI GENETICI
CROSSOVER
MUTAZIONE
CONDIZIONE TERMINALE
START
Funzionamento
degli
Algoritmi genetici
Crea popolazione iniziale
Valuta l’adattività
Selezione
per ciascun
cromosoma
Crossover
riproduzione
Mutazione
Sostituisci vecchia generazione
con generazione nuova
no
Condizione
terminale ?
si
END
POPOLAZIONE INIZIALE
Si scelgono casualmente N individui (cromosomi) tra tutte le
soluzioni possibili del problema di ottimizzazione non vincolata
ogni INDIVIDUO (o CROMOSOMA) = SOLUZIONE POSSIBILE, cioè:
X  (q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 h 2 h 3 h 4 h 5 h 6 )  13
OPERATORI GENETICI
CROSSOVER PUNTUALE: si tratta della riproduzione sessuata
di 2 individui
cromosoma genitore 1
cromosoma genitore 2
1
0
1
0
0
1
0
1
0
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
0
1
0
0
1
0
1
cromosoma figlio 1
cromosoma figlio2
CROSSOVER UNIFORME : è un tipo di riproduzione sessuata più
efficiente del precedente, in quanto prescinde dall’ordinamento dei bit
cromosoma genitore 1
cromosoma figlio 1
1
0
0
1
0
0
1
1
1
0
1
1
0
0
1
0
0
0
1
1
1
1
1
0
0
0
0
1
0
1
1
1
cromosoma genitore 2
cromosoma figlio2
MUTAZIONE: si tratta della variazione casuale di un gene (= 1 bit)
di un individuo (o cromosoma) a caso della popolazione
cromosoma genitore
1
0
1
0
0
1
1
1
0
1
1
0
1
0
0
1
0
1
0
1
cromosoma figlio
SELEZIONE
La selezione determina quali individui (cromosomi) si
riprodurranno e quali saranno scartati è grazie alla selezione
che la popolazione si evolve di generazione in generazione
Il cuore della selezione è la FITNESS FUNCTION (=funzione di “adattività”)
con cui è possibile ordinare per FITNESS (adattività) gli individui della
popolazione e quindi assegnare ad essi, in base alla posizione in
graduatoria, una probabilità di selezione maggiore o minore
La funzione di adattività coincide allora con la funzione obiettivo del
problema di ottimizzazione
CONDIZIONE TERMINALE
La condizione terminale può essere di più tipi, ossia basata sul:
•numero di generazioni
•grado di uniformità della popolazione
•“adattività” dell’individuo migliore
PROBLEMA DELLO “SLOW-FINISH”
Si è sperimentato in fase di elaborazione (ma è un fenomeno riportato da
diversi autori), un evidente rallentamento progressivo della convergenza
Risultati ottenuti applicando
gli Algoritmi genetici
alla risoluzione della rete di
TorreMaggiore(FG)
composta di
165 tronchi e 107 nodi
Le 10000 generazioni sono
state effettuate in circa 2 ore
con un Pentium III 350 Mhz
5
10
4
10
3
10
e
2
10
1
10
0
10
-1
10
0
10
1
10
2
10
N° di generazioni
3
10
4
10
TECNICA MISTA:
algoritmi genetici / metodo di Gauss-Newton
Il problema dello “slow-finish” è stato risolto utilizzando
gli algoritmi genetici per determinare un punto iniziale
“buono”, ossia interno alla concavità del minimo globale,
e quindi proseguendo la ricerca del minimo con gli
algoritmi tradizionali di “discesa”.
Come si è già visto, trovare un “buon” punto
iniziale per gli algoritmi di “discesa”, significa:
e
“buon” punto iniziale di
ricerca per gli algoritmi
di “discesa”
minimo globale
percorso di discesa
O
x
Occorre stabilire un criterio per verificare che gli algoritmi
genetici abbiano “trovato” la concavità del minimo globale:
e
popolazione iniziale
degli algoritmi
genetici
O
x
dopo N generazioni si esegue un controllo per verificare se tutti
gli individui sono interni della concavità del minimo globale
popolazione degli
algoritmi genetici
dopo N generazioni
e
algoritmi di discesa
O
x
lanciando gli algoritmi di “discesa” a partire da ciascun individuo
della popolazione e verificando che convergano allo stesso punto.
Un’altra possibilità più rapida consiste, sempre dopo N
generazioni, nel lanciare gli algoritmi di discesa a partire dal solo
individuo migliore della popolazione (“fittest individual”)
popolazione degli
algoritmi genetici
dopo N generazioni
e
algoritmi di discesa
O
x
verificando che il punto finale (minimo locale) coincida con lo 0,
avvalendosi della conoscenza del valore del minimo globale
IN CONCLUSIONE:
Testando l’implementazione della “tecnica mista” su 4 reti
con diverse complessità, precedentemente risolte con altre
metodologie , si è avuto risconto del corretto
funzionamento del metodo
Il software è inoltre piuttosto efficiente in termini di velocità, per
cui si è potuto agevolmente implementare anche la ricerca
iterativa dei coefficienti alfa di ripartizione delle portate
uniformemente distribuite e l’uso della formula di Colebrook per
la determinazione degli indici di resistenza lambda, ampliando il
campo delle portate al regime di transizione