Metodi di soluzione

Generare le soluzioni ottime secondo Pareto costituisce la parte essenziale della programmazione multi obiettivo e anzi, da un punto di vista strettamente matematico, il problema (3.123) si considera risolto una volta che sia stata individuata la frontiera di Pareto.

Da un punto di vista pratico, invece, non sempre ci si può accontentare semplicemente di avere trovato l’insieme degli ottimi di Pareto. In molti casi, infatti, è necessario ordinare tutte le soluzioni trovate e quindi selezionare la migliore rispetto a tale ordinamento. Quest’ultima operazione è effettuata, solitamente, dal decisore, cioè, nel caso di un generico sistema di invasi a scopo plurimo come quello oggetto di studio, dal gestore del sistema stesso. Tale decisore dovrà fornire tutte le informazioni necessarie per effettuare l’ordinamento degli ottimi di Pareto secondo le sue preferenze. In base a tale ordinamento, alla fine, si giungerà alla soluzione ottima (secondo Pareto) e preferita.

Ottimi deboli di Pareto

I metodi risolutivi della programmazione multi obiettivo (cioè i metodi che permettono di generare tutti i punti della frontiera di Pareto e scegliere la soluzione preferita dal decisore), vengono spesso suddivisi in quattro grandi categorie:

• Metodi senza preferenze: nei quali il decisore non ha nessun ruolo e si considera soddisfacente l’aver trovato un qualunque ottimo di Pareto;

• Metodi a posteriori: nei quali si genera l’insieme di tutti gli ottimi di Pareto e poi lo si presenta al decisore che sceglie l’azione preferita sulla base delle sue esigenze e della sua esperienza;

• Metodi a priori: nei quali il decisore specifica le sue preferenze prima che abbia inizio il processo risolutivo. In base alle informazioni avute dal decisore viene direttamente trovata la soluzione ottima migliore senza dover generare tutti gli ottimi di Pareto;

• Metodi interattivi: nei quali il decisore specifica le sue preferenze man mano che l’algoritmo procede, guidando in tal modo il processo risolutivo verso la soluzione per lui più soddisfacente.

Si noti, comunque, che al di là di tale distinzione formale, tutte i metodi sopraelencati, si basano sulla medesima idea di fondo: cioè trasformare il problema originario a più obiettivi in un problema con una sola funzione obiettivo. La tecnica mediante la quale si ottiene un problema mono-obiettivo a partire da un altro con più obiettivi è noto come scalarizzazione.

Le tecniche maggiormente usate nell’ambito della ricerca operativa sono:

• per quanto riguarda i metodi senza preferenze si ricorda il metodo “GOAL” (detto anche “GLOBAL”), che comprende quello detto “MIN-MAX” (di Tchebycheff);

• per quanto riguarda i metodi a posteriori si ricordano:

o metodo della funzioni aggregate (A.O.F., acronimo di Aggregate Objectives Functions), generalizzazione del metodo dei pesi (o della somma pesata);

o metodo degli ε-vincoli (detto anche “Trade-off”); • per quanto riguarda i metodi a priori si ricordano:

o metodo della “value function”;

Nel paragrafo successivo si analizzeranno da un punto di vista teorico i metodi poi implementati nell’applicazione al caso reale di gestione ottima del sistema Ariamacina-Cecita-Mucone: il metodo AOF e dei pesi.

3.10.1.1 Metodi AOF e dei pesi

Si consideri il problema:

( )

∑

= ⋅ k i i i f w 1 min x (3.125)

( )

x ≤0 g

dove il vettore w (le cui componenti sono wi) appartiene allo spazio ℜ . Le suddette componenti, k+

inoltre, si intendono “normalizzati”, cioè tali che:

1 1 =

∑

= k i i w

Si può dimostrare che esiste una stretta relazione tra le soluzioni del problema scalarizzato secondo la (3.125) e il problema originario (3.123):

Ogni soluzione globale (locale) del problema (3.125) è un ottimo debole globale (locale) di Pareto per il problema (3.123). Se, in particolare, il problema (3.125) ammette soluzione unica allora essa è un ottimo di Pareto per il problema (3.123).

In maniera analoga, se i pesi wi sono tutti strettamente positivi è possibile dimostrare che ogni soluzione globale (locale) del problema (3.125) è un ottimo globale (locale) di Pareto per il problema (3.123).

Se il problema (3.123) è convesso ed x* è un suo ottimo di Pareto, allora esistono dei pesi k

+ ℜ ∈ w (con 1 1 =

∑

= k i i

w ) e tali che x* _{è soluzione anche del problema (3.125).}

Da quest’ultima proposizione si può pertanto dedurre che se il problema è convesso, modificando l’insieme dei pesi wi si può ottenere l’intera frontiera ottima secondo Pareto. L’inconveniente di tal metodo è che se lo spazio ammissibile degli obiettivi e delle variabili decisionali non è convesso, il metodo dei pesi non è capace di “catturare”, al variare dei pesi wi, tutti i punti della frontiera di

Pareto: in particolare ben documentato in letteratura è l’incapacità di “cogliere” quelli che giacciono sulle zone non-convesse della frontiera (Athan e Papalambros, 1996; Chen et al., 1998; Das e Dennis, 1997; Das e Dennis, 1998; Koski, 1985; Messac et al., 2000a; Osyczka, 1984; Rakowska et al., 1991).

Questo è un grave problema in quanto la scelta della soluzione “preferita” da parte del decisore avviene sulla base dei punti Pareto-ottimi forniti dalla programmazione multi obiettivo: quindi, affinchè tale soluzione “preferita” dal decisore sia la migliore possibile, è necessario che si generino il maggior numero di punti della frontiera di Pareto (teoricamente tutti), siano essi giacenti su zone convesse, siano essi giacenti su zone concave.

Il problema della “catturabilità” dei punti Pareto ottimi su frontiere non-convesse può essere risolto (almeno in via teorica) mediante l’uso del metodo cosiddetto delle funzioni aggregate (AOF). (Messac et al., 2000b).

Esso può essere considerato come la generalizzazione del metodo dei pesi esposto in precedenza, in quanto anch’esso si basa sulla ottimizzazione di una funzione (scalare) che è combinazione delle diverse funzioni obiettivo del problema originario (3.123).

In particolare si consideri una qualunque funzione scalare _u

( )

_{f :}ℜk →ℜ _{che aggreghi le diverse} funzioni obiettivo scalari fi del problema (3.123) in modo da generare un valore scalare. Tale funzione u(f) sarà caratterizzata dalla presenza di un set di parametri liberi.

Per una fissata combinazione di valori di tali parametri, la risoluzione del problema:

( )

{

u f | f ∈Z

}

min (3.126)

genera un punto Pareto ottimo (giacenti su zone anche non-convesse della frontiera di Pareto) se la funzione u(f) soddisfa una serie di condizioni.

Innanzitutto la funzione u(f) deve essere ammissibile, ovvero deve risultare monotona crescente rispetto ad ogni singolo obiettivo (a prescindere dai valori a cui gli altri obiettivi sono mantenuti costanti (Steuer, 1989): si può dimostrare che tali funzioni catturano punti Pareto ottimi (almeno) locali.

Sebbene la proprietà dell’ammissibilità (da rispettare da parte delle funzioni aggregate) appena definita sia condizione necessaria per la catturabilità di tutti i punti Pareto ottimi, essa non risulta sufficiente.

aggregata è convessa. Ossia se la curvatura della funzione aggregata è maggiore di quella della regione Pareto ottima.

Per questo motivo il metodo dei pesi riesce a catturare i soli punti che appartengono a regioni convesse della frontiera.

Una implicazione interessante di quanto osservato è che una funzione aggregata, la cui curvatura può essere incrementata aggiustando il valore dei parametri, riesce a cogliere sempre più punti e, al limite, tutti i punti pareto-ottimi.

Una funzione con queste caratteristiche è la seguente:

( )

_∑

( )

= ⋅ = k i s i i f w f u 1 x (3.127)

nella quale la curvatura è controllata dal parametro s. Per un valore unitario di tale parametro si ritrova la funzione del metodo dei pesi descritta precedentemente. Si osserva infine che se i valori degli obiettivi possono essere minori di zero i valori di s, per fare in modo che la funzione sia ammissibile (monotonicità crescente), devono essere limitati ai soli interi dispari.

Nel documento Ottimizzazione della gestione di sistemi multi-invaso a scopo plurimo: il caso del sistema Ariamacina-Cecita-Muone (pagine 104-108)