Progetto CRESCO
S.P.III.3 “Modelli e Strumenti di
supporto alla Ottimizzazione e
Riconfigurazione delle Reti”
“Progettazione e sviluppo di un package per l’ottimizzazione delle
azioni di configurazione in presenza di guasto attraverso la
valutazione della loro capacità di incrementare la sostenibilità del
servizio compatibilmente con i costi di attuazione”
A. Chella, G. Lo Re, A. De Paola
Dipartimento di Ingegneria Informatica
Università degli Studi di Palermo
Roma, 06 luglio 2007 – Riunione di Coordinamento CRESCO SPIII
Introduzione
Obiettivi prima fase del progetto


Definizione modello di rete
Progettazione algoritmi di ottimizzazione
Obiettivi seconda fase del progetto


Implementazione degli algoritmi di
ottimizzazione
Valutazione sperimentale
Reti elettriche di distribuzione
Livello intermedio tra la trasmissione e l’utilizzazione
Elementi della rete a Media Tensione:




Stazioni di trasformazione AT/MT (substation transformer)
Feeder: forniscono energia alle sottostazioni di distribuzione
Branch: consentono di trasportare energia dalla stazione
trasformazione ai feeder
Switch: consentono di interrompere il flusso di energia attraverso un
collegamento
Struttura topologica:

Branch:
connessione tra i feeder
Struttura magliata -> configurazione radiale

Load
Feeder e relative sottostazioni
Valore equivalente di potenza assorbita
Esempio di rete di distribuzione
1
1
11
3
8
2
4
12
8
7
5
7
9
6
16
2
12
14
5
15
13
11
16
13
9
3
Load
20
19
18
17
22
21
14
10
17
Branch
23
Open switch
4
6
24
Closed switch
Substation trasformer
27
26
25
29
15
28
Esempio di rete di distribuzione
1
1
11
3
8
2
4
12
8
7
5
7
9
6
16
2
12
14
5
15
13
11
16
13
9
3
20
19
18
17
22
23
4
6
21
14
10
24
27
26
25
29
17
15
28
Esempio di rete di distribuzione
1
1
11
3
8
2
4
12
8
7
5
7
9
6
16
2
12
14
5
15
13
11
16
13
9
3
20
19
18
17
22
23
4
6
21
14
10
24
27
26
25
29
17
15
28
Esempio di rete di distribuzione
1
11
1
3
8
2
4
12
8
7
5
7
9
6
16
2
12
14
5
15
13
11
16
13
9
3
20
19
18
17
22
23
4
6
21
14
10
24
27
26
25
29
17
15
28
Esempio di rete di distribuzione
1
11
1
3
8
2
4
12
8
7
5
7
9
6
16
2
12
14
5
15
13
11
16
13
9
3
20
19
18
17
22
23
4
6
21
14
10
24
27
26
25
29
17
15
28
Esempio di rete di distribuzione
1
11
1
3
8
2
4
12
8
7
5
7
9
6
16
2
12
14
5
15
13
11
16
13
9
3
20
19
18
17
22
23
4
6
24
17
27
26
25
29
21
14
10
15
28
Gestione Ottimale
Obiettivi e vincoli




Minimizzazione delle perdite di potenza attiva
Regolarizzazione del profilo di tensione
Bilanciamento dei carichi fra le sottostazioni AT/MT
Mantenimento delle correnti nelle linee entro il limite stabilito
dalla portata
Strumenti


Compensazione = controllo in tempo reale di un insieme di
banchi di condensatori, installati in alcuni nodi di carico della rete
Riconfigurazione = controllo degli switch in modo da cambiare la
topologia della rete
Riconfigurazione in seguito a guasti


Obiettivo aggiuntivo: alimentare il maggior numero di carichi
Vincoli aggiuntivi: alimentazione di carichi strategici
Modello della rete
Struttura magliata descritta attraverso l’insieme dei
possibili collegamenti



Un collegamento viene indicato dal nodo sorgente e dal nodo
destinazione
Ad un collegamento è associato un valore di resistenza
Ad ogni nodo sono associati i valori di potenza attiva e potenza
reattiva
Topologia descritta attraverso lo stato degli switch

Lo stato della rete è descritto da un vettore di elementi binari
Individuazioni oggetti del problema
Rappresentazione matriciale per incrementare
l’efficienza
Funzioni Base
Valutazione Ammissibilità




Verifica se una certa topologia rispetta le leggi di Kirchhoff ai nodi
Verifica che la rete sia un albero (assenza di maglie)
Verifica che la potenza assorbita non superi la potenza erogata
Verifica del rispetto dei vincoli ad hoc
Operatore branch-exchange



Chiude un branch aperto, scelto casualmente
Apre i branch necessari per eliminare i cicli che si sono formati nella
rete
La scelta dei branch da aprire dipende dalla funzione da ottimizzare
Valutazione del costo di una topologia


Dipende dalla funzione da ottimizzare
Esempio:
Obiettivo = minimizzare le perdite per effetto Joule
Passa attraverso il calcolo del “Load Flow”
Operatore Branch-Exchange
Pseudocodice



Selezione casuale del branch da chiudere
Individuazione delle maglie generate dopo la chiusura
Per ogni maglia
Per ogni branch che costituisce la maglia



Apertura del branch
verifica ammissibilità della rete
Calcolo del costo della rete
Selezione della mossa associata al massimo della funzione
di utilità
L’operatore di branch-exchange spinge la
ricerca verso soluzioni migliori
Non vengono impedite mutazioni peggiorative
Approcci algoritmici
Problema Mono-obiettivo


Tabu Search
Algoritmi genetici
Problema Multi-obiettivo

Tabu search parallelo
Diverse istanze parallele del Tabu Search, ognuna
minimizzando un solo obiettivo
Scambio periodico dei risultati parziali

Non-Dominated Sorting GA
Applica il concetto di pareto dominanza per
assegnare la fitness agli individui
Tabu Search
Memoria delle mosse vietate


Definizione di una mossa: chiusura di un ramo
Rappresentazione di una mossa
identificativo del ramo e verso di percorrenza

Mosse vietate:
Inverso di mosse appena fatte
Mosse che portano a reti non ammissibili
Mosse che violano i vincoli ad hoc specificati
Perturbazione dello stato


Scelta casuale di un branch da chiudere, nel rispetto della
tabella delle mosse proibite
Applicazione dell’operatore di branch-exchange per il ripristino
dell’ammissibilità della rete
L’operatore Branch-Exchange spige la ricerca verso la
direzione di minore costo

Data la scelta casuale del punto cui applicare la mutazione,
questa avviene nel migliore modo possibile
Algoritmo Genetico
Viene considerato come genoma il vettore
dello stato degli switch
L’unico operatore applicato è l’operatore di
Branch-Exchange

A qualunque combinazione degli stati
aperto/chiuso dei sezionatori non corrisponde
una configurazione radiale della rete
Problema Multi - obiettivo e
Implementazione Parallela
Diverse funzioni obiettivo


Grandezze numeriche non confrontabili
Obiettivi contrastanti
Il processo di ottimizzazione non può essere ridotto alla
ottimizzazione di un singolo obiettivo globale
Criterio di Pareto-dominanza usato per individuare l’insieme delle
migliori soluzioni
Tabu Search Parallelo


Diverse esecuzioni del Tabu Search evolvono seguendo differenti
funzioni di costo
Periodicamente i risultati dei diversi rami di esecuzione vengono
scambiati
Algoritmo Genetico Parallelo

Applica ad un insieme di popolazioni il criterio di Pareto–dominanza per
individuare le soluzioni migliori
Modello a grana fine: un individuo per nodo
Modello a grana grossa: un deme per nodo
MPI
Message Passing Interface
Forme di Comunicazione

Comunicazione punto-punto:
Processo master e processo slave comunicano (grana fine)
Migrazione di un individuo da un demo ad un altro (grana
grossa)
Scambio soluzioni parziali (PTS)

Comunicazioni collettive
Barriere di sincronizzazione (PTS, PGA a grana grossa)
Broadcast (diffusione iniziale dati del problema)
Gather: un processo raccoglie dati diversi da processi diversi
(PTS, raccolta risultati intermedi)
Scatter: un processo diffonde dati diversi a processi diversi
(PGA a grana fine, diffusione individui della popolazione)
Sviluppi Futuri
Implementazione degli algoritmi di ottimizzazione



Approcci mono-obiettivo
Approcci multi-obiettivo
Implementazione parallela sulla griglia ENEA
Valutazione sperimentale dei diversi algoritmi



Qualità delle soluzioni individuate
Onere computazionale
Tempi di risposta