L’algoritmo di ottimizzazione SCE-UA

Il metodo SCE-UA è basato sostanzialmente sulla sintesi di quattro concetti fondamentali: (1) combinazione dell’approccio deterministico e probabilistico; (2) evoluzione sistematica di un complesso (Complex) di punti nello spazio dei parametri; (3) evoluzione competitiva; (4) permutazione del complesso. I primi tre concetti sono stati mutuati da metodologie già esistenti e collaudate (Holland, 1975; Price, 1978) mentre l’ultima caratteristica e stata recentemente introdotta (Duan et al., 1992; Sorooshian et al., 1993). Grazie a tali caratteristiche il metodo SCE-UA è dimostrato essere molto efficace e stabile ma anche flessibile ed efficiente. L’algoritmo SCE-UA inizia con la selezione di un insieme di punti, campionati casualmente nello spazio dei parametri ammissibili. i quali vengono partizionati in una serie di complessi. Ogni complesso (Complex) evolve (Evolution) indipendentemente dagli altri, basandosi su un processo di riproduzione statistica che utilizza il metodo del simplesso. Periodicamente l’intero insieme viene rimescolato (Shuffled) e vengono formati nuovi complessi in modo tale che le informazioni ottenute dai complessi precedenti vengano condivise. I passi di evoluzione

e rimescolamento vengono ripetuti fino a che il criterio di convergenza prestabilito non è soddisfatto.

Una rappresentazione schematica di come è strutturato l’algoritmo SCE-UA è la seguente: Fase 1 Inizializzazione: Selezionare e = numero di complessi ed m = numero di punti all’interno di ciascun complesso. Calcolare la dimensione (s) del campione s = p x m;

Fase 2 Generazione di campioni: Selezionare un insieme di punti

x

₁

,... ,x

_s campionati nello spazio dei parametri ammissibili Ω⊂ℜⁿ. Calcolare il valore della funzione obiettivo

f

_iper ciascun punto

x

_i. In assenza di precedenti informazioni circa il posizionamento del punto di minimo globale utilizzare una distribuzione di probabilità uniforme per generare un campione;

Fase 3 Classificazione dei punti: Ordinare gli s punti in funzione del valore assunto dalla funzione obiettivo

f

_iin modo tale che il primo punto sia quello associato al valore della funzione obiettivo minore mentre l’ultimo punto quello con il valore maggiore. Raggruppare i punti in un insieme

D={x

_i

, f

_i

, i=1,...,s}

dove i = 1 rappresenta il punto con il valore della funzione obiettivo minore;

Fase 4 Suddivisione in complessi: Partizione dell’insieme D in modo da formare un numero p di complessi

A

¹

,...,A

^p ognuno dei quali è composto da m punti, ovvero:

{x f x x f f j m}

A

^k

=

^k_j

,

_j^k

|

^k_j

=

_k+p(j−1)

,

_j^k

=

_k+p(j−1)

, =1,...,

(4.1) Fase 5 Evoluzione dei complessi: Evoluzione di ciascun complessoA^k, k = 1, … ,p utilizzando l’algoritmo CCE (Competitive Complex Evolution basato sull’algoritmo del simplesso introdotta da Nelder e Mead) che verrà illustrato successivamente;

Fase 6 Mescolamento dei complessi: Sostituire

A

¹

,...,A

^pnell’insieme D in modo c

{A k p}

D=

^k

, =1,...,

. Ordina l’insieme D in funzione del valore assunto dalla funzione obiettivo (dal valore minore a quello maggiore);

Fase 7 Criterio di arresto: Se il criterio di convergenza è soddisfatto arrestare la procedura altrimenti ritornare alle Fase 4.

Figura 4.3: Diagramma di flusso del metodo SCE-UA.

L’algoritmo CCE (Competitive Complex Evolution) richiesto per l’evoluzione di ciascun complesso (Fase 5) è così strutturato:

Fase 5.1 Inizializzazione: Selezionare q,

α

,

β

dove 2≤q≤m,

α

≥1e

β

≥1;

Fase 5.2 Assegnazione dei fattori peso: Assegnare una distribuzione di probabilità di tipo triangolare ad ogni complessoA^kcome ad esempio:

m

i

m

m

i

m

p

_i

=2( +1− )/ ( +1), =1,...,

Il punto

x

₁^kpossiede la probabilità maggiore

p

₁

=2/m+1,

mentre il punto

x

_m^k possiede la probabilità minore

p

_m

=2/m(m+1);

Fase 5.3 Selezione dei genitori: Selezionare in modo casuale dal complessoA^kun numero q di punti distinti

u ,...,

₁

u

_q (dove q punti definiscono un sub-complesso) in accordo con la distribuzione di probabilità sopra definita (la distribuzione di probabilità è definita in modo tale che il punto associato alla funzione obiettivo con il valore minore

abbia la maggiore probabilità di essere scelto per formare un sub-complesso e viceversa). Raggruppare i punti in un insieme

B={u

_i

,v

_i

,i =1,...,q}

in cui

v

_i

rappresenta il valore della funzione obiettivo associata al punto

u

₁. Raggruppare in un insieme L le posizioni occupate dai punti di A^k che sono utilizzati per formare l’insieme B.

Fase 5.4 Generazione di nuovi individui:

(a) Ordinare l’insieme B ed L in modo tale che i q punti siano disposti (ordinati) a seconda del valore della funzione obiettivo associata (dal valore minore al maggiore). Calcolare il centro di massa g del sub-complesso utilizzando la seguente espressione: − =

−

=

1 1

.

)]

1

/(

1

[

q j j

u

q

g

Operando in tale maniera si è calcolato il centro di massa del sub-complesso eliminando il punto associato al maggior valore della funzione obiettivo.

b) Calcolare un nuovo punto

r= 2g−u

_q (procedura di riflessione). Così operando si è riflesso attraverso il centro di massa g del sub-complesso il punto associato al maggior valore della funzione obiettivo;

c) Se il punto r appartiene allo spazio dei parametri ammissibili Ω⊂ℜⁿ

calcolare il valore della funzione obiettivo e passare al punto d), altrimenti calcolare il minore ipercubo H ⊂ℜⁿ (ovvero un politopo che generalizza in dimensione più alta i concetti di punto, segmento, quadrato e cubo) che contiene

k

A , generare casualmente un punto z all’interno di H , calcolare

f

_z, porre r =

z e

f

_r

= f

_z(procedura di riflessione);

d) Se

f

_r

< f

_q sostituire

u

_q con il punto r ed andare al punto f) altrimenti calcolare

c=(g+u

_q

)/2

e successivamente

f

_c (procedura di contrazione); e) Se

f

_c

< f

_q sostituire

u

_q con il punto c ed andare al punto f), altrimenti generare casualmente un punto z all’interno di H e calcolare

f

_z (procedura di mutazione). Sostituire

u

_q con z;

f) Ripetere il procedimento dal punto a) al punto e) per

α

volte, dove

α ≥1

è un parametro specificato dall’utente;

Figura 4.4: Diagramma di flusso relativa alla strategia dell’algoritmo CCE (Competitive Complex Evolution).

Fase 5.5 Sostituzione dei genitori con i nuovi individui: Ricollocare i punti dell’insieme

B inA^kutilizzando la posizione originaria registrata in L. OrdinareA^kin funzione del valore assunto dalla funzione obiettivo (dal valore minore a quello maggiore);

Fase 5.6 Iterazione: Ripetere il procedimento dalla Fase 5.2 alla Fase 5.5 per

β

volte, dove

β

≥1è un parametro specificato dall’utente che determina quanti nuovi individui

devono essere generati (ovvero per quanto a lungo ogni singolo complesso deve evolvere);

La filosofia che sta alla base al metodo SCE-UA è quella di considerare il procedimento di ricerca globale come un processo di evoluzione naturale. Gli s punti campionati costituiscono una popolazione. Tale popolazione è partizionata, suddivisa, in molteplici comunità (complessi) ad ognuno dei quali è consentito di evolversi indipendentemente (ovvero cercare lo spazio delle soluzioni in diverse direzioni). Dopo un certo numero di generazioni le comunità sono costrette a mischiarsi e pertanto vengono a formarsi nuove comunità attraverso un processo di mescolamento. Questa fase migliora la sopravvivenza attraverso lo scambio di informazioni che sono state generate in modo indipendente da ciascuna comunità (complesso) i cui membri risultano essere potenziali genitori con la capacità di partecipare al processo di creazione di nuovi individui. Un sub-complesso selezionato da un complesso è pertanto paragonabile ad una coppia di genitori con la differenza che un sub-complesso può essere composto anche da più di due elementi. Per assicurarsi che il processo di evoluzione sia competitivo è richiesto che la probabilità che genitori migliori producano nuovi individui sia maggiore rispetto a quella di genitori peggiori. L’impiego di una distribuzione di probabilità di tipo triangolare assicura la competitività. L’algoritmo di Nelder e Mead è applicato a ciascun sub-complesso per generare la maggior parte dei nuovi individui. Questa strategia utilizza le informazioni contenute in un sub-complesso per indirizzare l’evoluzione verso direzioni migliori. I nuovi individui inoltre sono introdotti in maniera casuale nello spazio dei parametri ammissibili sotto certe condizioni in modo tale da assicurare che il processo di evoluzione non venga effettuato in regioni dello spazio poco promettenti. Tale strategia è in analogia con quanto accade in natura nella selezione della specie. Infine ogni singolo nuovo individuo andrà a sostituire il punto peggiore del relativo sub-complesso anziché il peggior punto dell’intera popolazione assicurando così che sia assicurata ad ogni genitore almeno una possibilità di contribuire al processo di riproduzione prima di essere sostituito oppure scartato. Pertanto nessuna delle informazioni contenute nel campione sarà ignorata.

4.4.1 Determinazione dei parametri dell’algoritmo SCE-UA

Come già menzionato l’algoritmo SCE-UA è costituito sia da componenti di tipo deterministico sia di tipo probabilistico le quali vengono controllate da alcuni parametri presenti all’interno dell’algoritmo. Affinchè l’algoritmo di ottimizzazione raggiunga la sua

massima efficienza è necessario assegnare accuratamente i valori a tali parametri. In particolare i parametri sono i seguenti:

• m, numero di punti presenti in ciascun complesso;

• q,numero di punti presenti in ciascun sub-complesso; • p, numero di complessi;

•

p

_min

,

numero minimo di complessi in una popolazione;

•

α,

numero di nuovi individui generati consecutivamente da ogni sub-complesso;

•

β

, numero di evoluzioni effettuato da ogni complesso;

Teoricamente il numero m di punti all’interno di ciascun complesso può assumere qualsiasi valore maggiore o uguale a due anche se qualora ci siano pochi punti all’interno di ciascun complesso potrebbe accadere che la procedura di ricerca risulti essere del tutto simile a quella effettuata dal metodo del simplesso e pertanto le capacità di ricerca globali del metodo SCE-UA sarebbero annullate. Al contrario se al parametro m viene assegnato un valore particolarmente elevato aumenterebbe notevolmente il tempo computazionale senza riscontri in termini di efficienza. Alcune ricerche (Duan et al., 1993) hanno evidenziato come imponendo m = 2n+1, dove n corrisponde al numero di parametri che devono essere ottimizzati, e variando il numero il numero di complessi, p, si ottengono risultati migliori rispetto la variazione del solo parametro m. Relativamente al parametro q, ovvero Il numero di punti presenti in ogni sub-complesso, esso può variare tra 2 ed m.

Il numero

α

di nuovi individui che ogni sub-complesso genera può assumere un numero maggiore o uguale all’unità. Se

α =1

allora soltanto uno solo dei genitori originari verrà sostituito. All’aumentare di

α

la ricerca diventa maggiormente influenzata in favore di una ricerca di tipo locale nello spazio dei parametri.

Il numero

β

di evoluzioni effettuate da ciascun complesso prima che i complessi siano mescolati può assumere qualsivoglia valore intero positivo. Nel caso

β

assuma valori modesti allora i complessi saranno mescolati frequentemente ma non sarà possibile effettuare molte ricerche indipendenti nello spazio dei parametri; al contrario qualora

β

assuma valori elevati è molto probabile si perda il criterio di ricerca di tipo globale. Il numero p di complessi richiesti è fortemente dipendente dalla natura del problema. Maggiore risulta essere il grado di difficoltà del problema e maggiore deve essere il numero p di complessi utilizzati al fine di ottenere una ricerca di tipo globale.

Il parametro

p

_minovvero il numero minimo di complessi (compreso tra uno e p) è introdotto nell’algoritmo SCE-UA per migliorarne l’efficienza.

Riassumendo si può concludere che in base alle esperienze effettuate su numerosi bacini idrografici da Duan e Sorooshian (Duan et al., 1992, 1993; Sorooshian et al., 1993) i valori da associare ai parametri dell’algoritmo SCE-UA sono quelli riportati nella Tabella 4.1 (n corrisponde al numero di parametri che devono essere ottimizzati):

Tabella 4.1: Valori da associare ai parametri dell’algoritmo SCE-UA.

problema del à complessit di grado del funzione p= 1 2 + = n m 1 + = n q 1 = α m = β

4.4.2 Determinazione del criterio di arresto

I processi di ottimizzazione a causa della loro natura di tipo iterativo necessitano di un criterio che stabilisca quando terminare la ricerca. Teoricamente la soluzione ottimale sarebbe quella di fermare la ricerca quando è stato calcolato il valore della funzione obiettivo che rappresenta il minimo assoluto ma poiché risulta essere complicato stabilire quando si è raggiunto questo punto è prassi utilizzare altri criteri d’arresto. Fondamentalmente se ne possono individuare tre, ovvero:

1. Terminare la ricerca quando l’algoritmo non è in grado di migliorare in modo apprezzabile il valore della funzione obiettivo dopo un certo numero di iterazioni ovvero è stata raggiunta la posizione di un ottimo oppure una zona molto piatta della superficie della risposta;

2. Terminare la ricerca quando l’algoritmo non è in grado di cambiare in modo apprezzabile i valori dei parametri e contemporaneamente migliorare il valore della funzione obiettivo. Tale situazione può indicare la localizzazione di un ottimo oppure che è stata raggiunta una zona della superficie della risposta di alta interazione tra i parametri;

3. Terminare la ricerca quando un numero massimo predefinito di iterazioni è stato raggiunto. La definizione di tale numero non è immediata in quanto il valore può essere legato sia al sistema oggetto di studio che all’algoritmo in uso. Risulta pertanto necessario svolgere alcuni tentativi modificando il valore del numero di iterazioni e stabilire successivamente, in funzione dei risultati ottenuti, quale valore assegnare al numero stesso.

Nel documento Modellazione numerica a scala di bacino del fiume Ledra (pagine 115-123)