Descrizione dei componenti del pacchetto

Il pacchetto di ottimizzazione realizzato consiste principalmente di tre fun- zioni principali (HYB, ALF, PSO_ALF) e una per impostare i parametri dell’ot- timizzatore (optimset_pso).

4 – Implementazione del problema di ottimizzazione di traiettorie

Inizializzazione.

Si introducono: Costanti

Stime iniziali del parametro di penalizzazione e dei moltiplicatori di Lagrange

In base ai parametri di penalizzazione e moltiplicatori del passo k- mo si determina l’Augmented Lagrangian Penalty Function che diventa così funzione della sola variabile x.

Risoluzione del problema di ottimizzazione non vincolata.

La funzione obiettivo coincide con l’Augmented Lagrangian

Penalty Function determinata al passo precedente.

La soluzione ottenuta terminato il ciclo interno del risolutore èx*k.

k

I vincoli sono rispettati secondo le tolleranze obiettivo? Termina il ciclo esterno. SI NO

I vincoli sono rispettati secondo le tolleranze minime richieste al

passo k-mo?

Aggiornamento dei moltiplicatori di Lagrange NO SI Aggiornamento del parametro di penalizzazione k = k + 1

Figura 4.1: Ottimizzazione vincolata mediante utilizzo dell’ Augmented Lagran- gian Penalty Function.

4 – Implementazione del problema di ottimizzazione di traiettorie

PSO ALF

Si tratta del “cuore” dell’ottimizzatore: in questo programma si riesce a risolvere un qualsiasi problema di ottimizzazione, a partire dall’algoritmo descritto nel paragrafo 2.2 e sintetizzato in Fig. 2.1.

Pu`o esser direttamente utilizzato per trovare la soluzione in caso di controllo ottimo non vincolato.

`

E possibile utilizzarlo direttamente anche nel caso di ottimizzazione vincolata se si sceglie di adottare un metodo di penalizzazione basato sulla “feasibility” oppure su Exterior Penalty Function.

Come anticipato, `e in PSO_ALF che si creano le particelle (inizializzazione) e si d`a loro la possibilit`a di spostarsi con una certa velocit`a (aggiornamento del vettore velocit`a) cambiando posizione nello spazio (aggiornamento del vettore posizione) al fine di trovare la soluzione migliore.

`

E quindi necessario decidere il valore dei numerosi parametri che compaiono in tale algoritmo ed aggiungere criteri (o forzanti) alternative sul movimento delle particelle.

Tali scelte sono state fatte saggiando il comportamento del programma in una serie di problemi di prova, utilizzando inizialmente i valori proposti in letteratura e provandone poi di nuovi, come verr`a discusso a breve.

I parametri di base possono comunque essere agevolmente modificati grazie a optimset_pso.

In seguito riportiamo una breve descrizione dei principali parametri, dei valori e dei metodi di base scelti:

- Numero di particelle. Abbiamo scelto una popolazione di base di 20 individui, tuttavia problemi complessi possono richiedere un aumento di tale numero. In letteratura si ritrovano valori che vanno solitamen- te da 10 fino a 50 individui (Bessette[8] _{e Hassan}[9]_{). Nello studio di}

Venter[4] si trovano anche prove con ben 300 particelle: ovviamente la grandezza della popolazione da utilizzare dipende dal problema e da come lo si vuole risolvere (direttamente o riducendosi ad un sotto- problema).

4 – Implementazione del problema di ottimizzazione di traiettorie

Se in problemi complessi si utilizza direttamente il risolutore qui svilup- pato `e bene non avvalersi popolazioni con pi`u di 50 particelle: ci`o com- porterebbe notevoli aumenti del tempo di calcolo senza necessariamente migliorare le prestazioni.

- Parametro di inerzia, w. Rappresenta l’inerzia della particella. Compare nel primo termine dell’ Eq. (2.3) ed `e il peso che si d`a nello spostamento risultante della particella alla casualit`a con cui esplora lo spazio circostante. Valori alti aumentano la mobilit`a delle particelle, valori bassi le confinano in una zona limitata. In accordo con Venter[4] si `e scelto di far variare l’inerzia durante le iterazioni in maniera da privilegiare l’agitazione iniziale delle particella che cala via via fino ad un comportamento marcatamente locale una volta che si `e individuato l’intorno della soluzione ottima.

Per questo si sono utilizzati diversi metodi: abbiamo provato, seguendo Venter[4], ad utilizzare un coefficiente di variazione della funzione obiet- tivo, COV (coefficient of variation), dato dal rapporto fra deviazione standard e media, monitorato su un insieme di particelle (le migliori): se COV scende al di sotto di un valore soglia il coefficiente w viene ag- giornato. Questo metodo, interessante dal punto di vista matematico, non si `e dimostrato particolarmente versatile, perci`o abbiamo pensato di utilizzare metodi pi`u semplici ma efficaci;

partendo da un valore di w pari a 1.3 si arriva fino a 0.351: la domanda `

e relativa a quale sia il momento adatto in cui eseguire l’aggiornamento del parametro, e le scelte possibili sono tre:

1. Decrescita del parametro di inerzia in base al numero di iterazione. Si scala linearmente con l’iter i, a partire da i = 0 fino a i = 300, valori modificabili.

2. Decrescita con l’iterazione che avviene solo quando la soluzione corrente al passo i-mo `e uguale da quella al passo i − 1:

Ci`o per far s`ı che, nel caso in cui le particelle stiano esplorando

1_{In letteratura si trovano valori leggermente diversi, ad esempio Venter}[4] _{utilizza w :}

1.4 → 0.35, Bessette[8] e Parsopoulos[10]w : 1.2 → 0.1, mentre Hassan[9] mantiene w fisso a 1.5.

4 – Implementazione del problema di ottimizzazione di traiettorie

adeguatamente lo spazio con un valore adeguato di w, questo non scali troppo velocemente rischiando di bloccare troppo presto la ricerca globale.

3. Decrescita con l’iterazione solo quando le soluzioni ottime di due iterazioni consecutive differiscono per un valore inferiore ad una certa soglia. Si amplifica cos`ı il risultato che si vorrebbe ottene- re col metodo precedente, visibile come caso particolare in cui il valore soglia coincide con 0.

Nella maggior parte dei problemi affrontati nel nostro lavoro il pri- mo metodo `e risultato sufficiente. Il terzo caso rappresenta un’ottima alternativa in casi particolari

- Parametri di cognizione c1 e c2. Compaiono nell’ Eq. (2.3) e rap-

presentano la “fiducia” della particella in se stessa e nel gruppo. In accordo a Venter[4] si sono scelti rispettivamente pari a 1.5 e 2.5; avere c1 < c2 significa che ogni particella tende a dare maggior rilevanza alla

posizione migliore dell’intero gruppo rispetto alla migliore incontrata nel proprio percorso.

- Parametro di costrizione χ. Questo `e un parametro collegato alla scalatura del problema e comunque dipendente dai valori scelti per w, c1 e c2. Le prime versioni dell’algoritmo non prevedevano l’utilizzo

di χ e sono perci`o visibili come casi in cui χ = 1 (es. in Venter[4]

e in Hassan[9]_{). Valori comunemente riscontrabili sono poi χ = 0.79}

(in Bessette[8]_{)e χ = 0.73 (in Parsopoulos}[10]_{): come gi`a anticipato, la}

scelta dipende fortemente dal tipo di problema e scalatura in gioco. Nel nostro caso si `e dimostrato efficace in un gran numero di casi (compresi alcuni di quelli presentati da Venter[4], da Parsopoulos[10] e problemi di meccanica del volo spaziale) un valore diverso, pari a χ = 0.55.

- Massimo numero di iterazioni, me. Il massimo numero di iterazio- ni, visibile come il massimo numero di passi discreti che possono fare le particelle nella loro “vita”, dopodich`e il programma termina anche senza aver raggiunto convergenza. `E un numero solitamente alto; si `e posto pari a 2000.

4 – Implementazione del problema di ottimizzazione di traiettorie

- Errore massimo ammissibile, ergrd. Valore soglia: se due soluzioni differiscono per un valore inferiore ad esso, possono esser considerate uguali ai fini della convergenza.

- Massimo numero di iterazioni a convergenza, ergrdep. Il con- trollo per terminare il ciclo viene fatto sulle ultime tre soluzioni (i-ma, (i − 1)-ma, (i − 2)-ma): se queste differiscono per un valore inferiore a ergrd per ergrdep volte consecutive allora il ciclo termina. Basandosi solo sulle ultime due soluzioni si avrebbe il rischio di terminare prima di essere arrivati a convergenza. In alternativa si pu`o utilizzare anzich´e la differenza semplice tra le soluzioni la differenza relativa (differenza fra le soluzioni per unit`a di soluzione). In Fig. 4.2 si riporta uno schema del controllo per la convergenza.

- Coefficiente di velocit`a massima delle particelle, V tau. I limiti della velocit`a assumibile dalle particelle giocano un ruolo molto impor- tante: velocit`a alte permettono un’esplorazione globale, ma rischiano di proiettare le particelle fuori dal dominio e pregiudicano una ricerca di tipo locale: `e quindi necessario un compromesso. In letteratura si trova il generico valore ±4; nel presente lavoro si `e preferito sceglie- re i limiti di velocit`a in funzione delle dimensioni del dominio, scalate con V tau: diminuire V tau significa aumentare i limiti di velocit`a fa- vorendo quindi un comportamento di tipo globale. Il valore di questo parametro pu`o dipendere dai vincoli semplici che si danno inizialmente, se pi`u o meno stringenti.

- Crazy Operator. Si tratta di un operatore che aggiunge casualit`a nel gruppo di particelle: esistono versioni che prevedono la scelta tramite il COV di una serie di particelle le cui posizioni vengono riassegnate casualmente e le cui velocit`a vengono modificate secondo 2_:

vi_k+1 = χc1r1

(pi− xi k)

∆t (4.20)

Sono state fatte alcune prove ma ancora una volta si `e abbandonata la scelta del COV, e le possibilit`a sono:

2_{Riferimento a Venter}[4]_{, sebbene non compaia il parametro χ}

4 – Implementazione del problema di ottimizzazione di traiettorie

Iterazione i-ma del ciclo PSO_ALF Aggiornamento velocità e posizione delle

particelle e determinazione del valore in corrispondenza del quale si ha la soluzione

ottima, .xi Funzione obiettivo, non vincolata

}

f

~

) ( ~ ) ( ~ 2 ) ( ~ ) ( ~ 1 2 1 i i i i x f x f tmp x f x f tmp − = − = − − ergrd tmp1≤ ergrd tmp2≤ SI SI ; 0 = cnt NO NO ; 1 + = cnt cnt ergrdep cnt= ? ? ? Termina il ciclo PSO_ALF

Figura 4.2: Funzioni di penalizzazione: equivalenza fra problema originario e derivato.

0. Non utilizzare il Crazy Operator.

1. Applicare il Crazy Operator ad un numero di particelle estratte in maniera aleatoria dalla popolazione, prima del controllo dei vincoli semplici.

2. Applicare il Crazy Operator ad un numero di particelle estratte in maniera aleatoria dalla popolazione, dopo del controllo dei vincoli semplici.

Solitamente `e sufficiente adottare la via (0), tuttavia esistono casi in cui il metodo (1) e (2) riescono ad accelerare la convergenza.

4 – Implementazione del problema di ottimizzazione di traiettorie

velocit`a sia fuori dai limiti previsti la si riporta semplicemente al valore ammissibile.

- Metodo dei disertori. `E il metodo con cui trattare i vincoli semplici, a scelta fra i seguenti:

1. Si individuano le particelle uscite dai confini e si riportano all’in- terno del dominio.

2. Si individuano le particelle uscite dai confini e si riportano all’in- terno del dominio e se ne cambia la velocit`a.

3. Non intervenire.

Il terzo metodo, risalente ai primordi della PSO, non `e assolutamente efficente. Il secondo `e senz’altro il migliore ed `e quello che utilizzeremo di default.

- Termine brusco del ciclo, Hardstopper. `E un parametro che abbia- mo introdotto per terminare immediatamente il ciclo appena i vincoli siano soddisfatti. Agisce solo se attivato. In alcune situazioni in cui il metodo di implementazione dei vincoli (in ALF, vedi prossimo para- grafo) andava incontro a problemi numerici `e risultato utile applicare questo operatore, almeno nelle prime iterazioni del ciclo esterno (ALF). - Parametri di memoria, event tau, eventualeX, event taumin. Si tratta di parametri che abbiamo deciso di introdurre legati all’utilizzo abbinato con ALF. Consiste nella possibilit`a di assegnare una ben de- terminata posizione iniziale ad un certo numero di particelle. Maggiori approfondimenti nel seguito.

Gli ingressi alla funzione sono: - Funzione obiettivo. - Dimensioni del problema. - Limiti inferiori.

- Limiti superiori.

4 – Implementazione del problema di ottimizzazione di traiettorie

- Opzioni, ossia valore modificato di alcuni dei parametri a cui abbiamo accennato definiti in optimset_pso.

- Vincoli.

- Numero di equazioni di vincolo. - Numero di disequazioni di vincolo.

- Valore di variabili necessarie al calcolo della funzione obiettivo o di vincoli.

- Variabili passate da ALF (tolleranze, parametri di penalizzazione, mol- tiplicatori di Lagrange).

- Parametri di memoria.

In uscita si ha la soluzione ottima in termini di posizione e valore.

ALF

ALF `e il “coordinatore”: risolve problemi di ottimo vincolato e non, appog- giandosi a PSO_ALF e gestendo e fornendo a quest’ultimo gli ingressi adeguati. L’algoritmo `e descritto in 4.3.1 e rappresentato dallo schema di Fig.4.1: con- siste in un ciclo che ad ogni iterazione k calcola l’ottimo del problema tra- mite PSO_ALF adottando alcuni parametri di penalizzazione e moltiplicatori di Lagrange che, insieme alle tolleranze di convergenza e a quelle sui vincoli, rimangono costanti a parit`a di k, ma possono cambiare ad ogni iterazione. Passiamo in rassegna i parametri e metodi di cui si compone:

- Numero di penalizzazione e indice di crescita, rp, tau. rp `e il valore di partenza per <sub>2µ</sub>1 dell’Eq. (2.10), mentre tau `e il coefficiente secondo cui aumentare la penalizzazione in caso di necessit`a. Si sono scelti entrambi pari a 10.

Sono inoltre presenti alcuni controlli per evitare che il parametro di penalizzazione diverga comportando ovvi problemi numerici.

- Parametri sul numero di iterazioni. Si sceglie un numero massimo di iterazioni per il ciclo esterno, pari ad un valore non eccessivamente alto, ad esempio 300, dopo i quali ALF termina anche senza che i criteri

4 – Implementazione del problema di ottimizzazione di traiettorie

di convergenza siano soddisfatti. `E necessario poi occuparsi dell’im- postazione del numero di iterazioni per confermare la convergenza del ciclo interno, ergrdep in PSO_ALF: abbiamo scelto di partire con un valore minimo pari a 80 che cresce fino 100. Questo per far s`ı che nei primi passi del ciclo esterno la ricerca dell’ottimo sia pi`u grossolana e andando avanti, man mano che la stima dei moltiplicatori di Lagrange si fa migliore, si procede verso un’indagine pi`u raffinata. La crescita di questo valore non `e lineare con il numero di iterazione (esterna), bens`ı tiene conto, indirettamente, della bont`a della soluzione trovata in quell’iterazione del ciclo esterno.

Il ciclo esterno si ferma invece quando la soluzione del ciclo interno soddisfa, per la prima volta, i requisiti di tolleranza richiesti (descritti nel punto successivo), oppure dopo aver raggiunto il massimo numero di iterazioni previste per il ciclo esterno.

- Parametri di tolleranza. Sono i coefficienti introdotti in (4.2). Si tratta di parametri in grado di far evolvere il valore della tolleranza sui vincoli e quella necessaria a verificare la convergenza in maniera adeguata in base alla bont`a della soluzione. Il meccanismo di aggior- namento `e quello descritto dalle Eq. (4.10) - (4.19). I valori iniziali sono stati scelti in riferimento a Conn[2]_.

`

E anche necessario scegliere i valori di tolleranza obiettivo sui vincoli e sulla convergenza, impostati di base a 10−2.

Si sono inoltre inseriti controlli per evitare che i valori di tolleranza assumano valori inferiori a quelli obiettivo.

- Metodo misto, grad. Se attivato, si passa ad ogni iterazione del ci- clo esterno il risultato ottenuto dall’ottimizzatore PSO_ALF a fmincon (oppure fminunc 3, algoritmo gradientale contenuto nell’Optimization Toolbox di MATLAB.

Tale soluzione non si `e dimostrata particolarmente interessante ed au- menta eccessivamente i tempi di calcolo.

3_{Se si usa fminunc si passa ad esso il problema non vincolato descritto dalla funzione}

aumentata, mentre nel caso di fmincon si inseriscono separatamente funzione obiettivo e vincoli)

4 – Implementazione del problema di ottimizzazione di traiettorie

- Parametri di memoria. Si tratta di un sistema, attivabile o meno, che permette di partire con una popolazione iniziale non completamente casuale; abbiamo gi`a accennato al fatto che ALF, scegliendo parametri di penalizzazione e moltiplicatori di Lagrange, imposta il problema del tipo rappresentato dall’Eq. (2.10) che PSO_ALF deve risolvere; una volta trovata la soluzione viene passata nuovamente ad ALF dove, in base ad essa, si modificano i parametri e si imposta un nuovo problema che PSO_ALF dovr`a risolvere: se si scegliesse di non attivare l’opzione di memoria le particelle dovrebbero iniziare la loro ricerca senza alcuna informazione relativa alla loro precedente indagine. Per migliorare la convergenza e i tempi di calcolo si `e scelto di introdurre la possibilit`a di assegnare ad un certo numero di particelle la posizione uguale a quella ottenuta come soluzione al passo di iterazione (k, esterno) precedente. Tale assegnazione viene eseguita, in PSO_ALF, dopo la generazione della popolazione iniziale (vedi 2.2): nel caso in cui durante l’inizializzazione si trovi un valore migliore a quello corrispondente al vettore soluzione xk del passo esterno precedente (ottenuto quindi per altri valori di

numero di penalizzazione moltiplicatori di Lagrange) si rinuncia alla sostituzione.

- Moltiplicatori di Lagrange. Si parte da una stima iniziale in cui ven- gono tutti i moltiplicatori sono posti a zero e vengono successivamente modificati (tramite le Eq. (4.10) - (4.19)).

I parametri in ingresso alla funzione ALF sono: - Funzione obiettivo.

- Dimensioni del problema. - Limiti inferiori.

- Limiti superiori.

- Opzioni, ossia valore modificato di alcuni dei parametri a cui abbiamo accennato definiti in optimset_pso.

- Vincoli.

4 – Implementazione del problema di ottimizzazione di traiettorie

- Numero di disequazioni di vincolo.

- Valore di variabili necessarie al calcolo della funzione obiettivo o di vincoli.

In uscita si ha la soluzione ottima in termini di posizione e valore.

HYB

Questa funzione risolve il problema avvalendosi semplicemente di ALF, do- podich`e utilizza la soluzione cos`ı ottenuta come prima stima da passare al- l’algoritmo per l’ottimizzazione vincolata fmincon o, a scelta, fminunc per ottimizzazione non vincolata a cui si passa il lagrangiano aumentato. Nel secondo caso `e necessario fare attenzione ai vincoli semplici, non implemen- tabili direttamente. Ingressi e uscite nella sintassi della funzione sono i soliti di ALF.

In Fig. 4.3 si riporta lo schema di funzionamento dei programmi presentati.

ALF

PSO_ALF

fmincon

La soluzione di ALF+PSO_ALF viene

utilizzata come prima stima per fmincon

La soluzione di HYB ALF passa a PSO_ALFvi parametri della simulazione e quelli necessari per creare la funzione di

penalizzazione

PSO_ALFrisolve il problema di ottimizzazione non vincolata relativo alla

funzione di penalizzazione PSO_ALFpassa

ad ALF la soluzione ottenuta con quei

particolari parametri di penalizzazione

Figura 4.3: Schema di funzionamento di HYB.

4 – Implementazione del problema di ottimizzazione di traiettorie

optimset pso

Si tratta di una funzione per impostare o cambiare direttamente i parametri e i metodi gi`a incontrati nella descrizione di PSO_ALF e di ALF.

In pi`u `e presente l’opzione per visualizzare i passi dell’ottimizzazione, del ciclo esterno e/o di quello interno.

optimset_pso si `e dimostrato molto utile nell’esecuzione di simulazioni in se- rie per confrontare l’effetto dei vari ingredienti del pacchetto di ottimizzazione sviluppato, automatizzando il processo.

Nel documento Ottimizzazione di Traiettorie Interplanetarie con l'Ausilio di Metodologia PSO (pagine 40-52)