Ottimizzazione di Traiettorie Interplanetarie con l'Ausilio di Metodologia PSO

(1)

(2)

Sommario

Nel presente lavoro di tesi si `e sviluppato un metodo di ottimizzazione ba-sato su algoritmi PSO in grado di risolvere problemi di ottimo di traiettorie interplanetarie di veicoli spaziali dotati di apparati propulsivi a bassa spinta. La prima e seconda parte dell’elaborato trattano i problemi di ottimizzazio-ne e di controllo ottimo. Vengono inoltre descritti l’algoritmo di base della Particle Swarm Optimization e il pacchetto di ottimizzazione vincolata svi-luppato.

Nella terza parte si applica l’ottimizzatore a trasferimenti interplanetari rea-lizzati con veicoli spaziali dotati di particolari sistemi propulsivi a bassa spin-ta, le vele solari. Si analizzano trasferimenti bidimensionali e tridimensionali e si saggiano le prestazioni del risolutore.

(3)

Ringraziamenti

Un primo ringraziamento va sicuramente al Prof. Giovanni Mengali per la sua disponibilità, per la sua fiducia nei miei confronti... e per la sua pazienza. Altro importante ringraziamento è per il grande Alessandro Quarta (senza titoli, i titoli li lasciamo ai giornali!), che mi ha aiutato e incoraggiato du-rante questi mesi di tesi. Si è rivelato non solo un ottimo relatore ma anche un vero amico.

E ora la famiglia: non ci sono parole per ringraziare adeguatamente. In-somma, la comprensione, il sostegno e la pazienza che hanno mostrato sono stati qualcosa di inverosimile e unico.

Inoltre un ringraziamento particolare va al mio stratega personale per le stra-tegie di pianificazione esami.

Un grazie alle mie sorelle e a Morena per avermi sopportato. Un grazie mastodontico a Thomas.

Un grazie agli amici di Sarzana e alle massesine incontrati indirettamente grazie all’Universit`a, in particolare Mattia, Simone, Giacomo, Chiara, Me-molina, Daniela e Irene.

Ricordiamo poi gli amici di Carrara, fra cui Linda e Alessia.

(4)

Indice

Sommario II

Ringraziamenti III

Elenco dei simboli VII

I

Ottimizzazione vincolata a singolo obiettivo

3

1 Ottimizzazione 4

1.1 Introduzione . . . 4 1.2 Formulazione del problema . . . 4

2 Particle Swarm Optimization 6

2.1 Introduzione . . . 6 2.2 Algoritmo di base . . . 7 2.3 Ottimizzazione vincolata . . . 13 2.3.1 Metodi basati sul mantenimento della “feasibility” . . . 13 2.3.2 Funzioni di penalizzazione . . . 14

II

Controllo ottimo e sua implementazione

20

3 Cenni sul controllo ottimo 21

3.1 Formulazione del problema . . . 21 3.2 Soluzione del problema di controllo ottimo . . . 23 3.2.1 Soluzione del problema con metodi diretti . . . 24

(5)

4 Implementazione del problema di ottimizzazione di

traietto-rie 26

4.1 Introduzione . . . 26

4.2 Istante finale libero o fissato . . . 26

4.3 Descrizione dell’algoritmo ottimizzatore . . . 27

4.3.1 Schema per l’implementazione di vincoli non lineari . . 27

4.3.2 Descrizione dei componenti del pacchetto . . . 31

4.4 Discretizzazione del dominio e della dinamica del sistema . . . 43

5 Problema di trasferimento orbitale con N-impulsi 45 5.1 Introduzione . . . 45

5.2 Impostazione del problema di controllo ottimo . . . 46

5.2.1 Simulazioni . . . 48

III

Traiettorie ottime di rendez-vous

interplaneta-rio con vele solari

51

6 Vele solari ed impostazione del problema 52 6.1 Introduzione . . . 52

6.2 Pressione di radiazione solare . . . 53

6.3 Parametri di prestazione della vela . . . 54

6.4 Modelli di spinta . . . 54

6.5 Equazioni di moto . . . 59

7 Problemi bidimensionali 63 7.1 Introduzione . . . 63

7.2.1 Equazioni di moto . . . 65

7.2.2 Condizioni iniziali . . . 67

7.2.3 Condizioni al contorno . . . 67

7.2.4 Vincoli sulle variabili di controllo . . . 68

7.3 Simulazioni . . . 68

7.3.1 Trasferimento Terra-Marte . . . 69

7.3.2 Trasferimento Terra-Venere . . . 74

(6)

7.4 Missione Terra-Mercurio con una manovra di fly-by su Venere 76

7.4.1 Introduzione alla schematizzazione della manovra . . . 77

7.4.2 Simulazioni . . . 77

8 Problemi tridimensionali 80 8.1 Introduzione . . . 80

8.2 Impostazione del problema . . . 80

8.2.1 Equazioni di moto . . . 81

8.2.2 Condizioni iniziali e condizioni al contorno . . . 82

8.2.3 Vincoli sulle variabili di controllo . . . 83

8.3 Simulazioni . . . 83 8.3.1 Trasferimento verso Marte senza il calcolo delle effemeridi 84 8.3.2 Trasferimento verso Marte con il calcolo delle effemeridi 87

9 Conclusioni e sviluppi futuri 90

Bibliografia 92

Elenco delle Figure 94

Elenco delle Tabelle 96

(7)

Elenco dei Simboli

α Angolo di cono della vela solare

β Parametro di snellezza della vela solare

γ Moltiplicatori di Lagrange, associati a disequazioni di vincolo ˆ

ap Versore dell’accelerazione della vela per il modello parametrico

ˆ

n Versore normale alla superficie della vela solare ˆ

r Versore della direzione radiale

λ Moltiplicatori di Lagrange, associati a equazioni di vincolo a Accelerazione propulsiva della vela solare

g Vettore delle disequazioni di vincolo h Vettore delle equazioni di vincolo

p Vettore di parametri indipendenti dal tempo r Vettore posizione

s Slack Variables

u Vettore delle variabili di controllo v Vettore velocit`a

x Vettore di variabili di ottimizzazione y Vettore delle variabili di stato

(8)

χ Parametro di costrizione

δ Angolo di azimut della vela solare

δturn Angolo di svolta in un incontro iperbolico

f r, b Coefficienti di emissivit`a della superficie illuminata e di quella in

ombra della vela solare

η∗ Tolleranza obiettivo sui vincoli

λ, ϕ Angoli che definiscono l’orientamento relativo tra le terne T e Torb

T Matrice di trasformazione di coordinate T Sistema di riferimento eliocentrico-eclittico

Torb Sistema di riferimento orbitale

µ Parametro di penalizzazione

ω∗ Tolleranza obiettivo sulla convergenza

Φ Termine di penalizzazione φ Funzione di penalizzazione ψ Condizioni al contorno

ρ Coefficiente di riflessione della superficie della vela solare θp Angolo di cono della spinta della vela solare

ac Accelerazione caratteristica della vela solare

b1, b2, b3 Coefficienti di forza della vela solare

Bf r, Bb Coefficienti di non lambertianit`a della superficie illuminata e di

quella in ombra della vela solare

c1 Coefficiente associato alla memoria delle particelle PSO

c2 Coefficiente associato al gruppo di particelle PSO

(9)

J Indice di prestazione

P Pressione di radiazione solare

ps Numero di particelle costituenti la popolazione

r, θ Componenti radiale e azimutale del vettore posizione in un sistema di riferimento polare

s Frazione di fotoni specularmente riflessi dalla vela solare t Istante di tempo generico

u, v Componenti radiale e azimutale del vettore velocit`a in un sistema di riferimento polare

w Coefficiente d’inerzia delle particelle PSO

(10)

Introduzione

Il generico problema di ottimizzazione vincolata riveste una notevole impor-tanza in molti ambiti ingegneristici. Nonostante la disponibilit`a in commercio di numerosi algoritmi ottimizzatori, molti casi rimangono tutt’ora di difficile risoluzione.

In questo elaborato ci proponiamo di sviluppare un risolutore basato su un approccio denominato Particle Swarm Optimization in grado di affrontare questo tipo di problema. Vengono inoltre analizzati alcuni problemi di con-trollo ottimo, riferendoci al caso di ottimizzazione di traiettorie di veicoli spaziali dotati di particolari sistemi propulsivi a bassa spinta, le vele solari. L’analisi di missione di questi veicoli `e di grande interesse pratico e numerosi studi sono stati eseguiti al fine di riuscire ad ottimizzare il tempo di missione, o il consumo di propellente nel caso di generici veicoli spaziali.

Calcolare la legge di controllo ottima nel caso di vele solari è un compito par-ticolarmente arduo: l’accelerazione sviluppata da questi sistemi propulsivi è continua lungo tutta la durata della missione e questo aumenta notevolmente la complessità del problema.

Organizzazione della Tesi

La Tesi `e divisa in tre parti. Nella Parte I si presenta il problema generale di ottimizzazione vincolata e si introduce il concetto di Particle Swarm Optimi-zation (PSO). Nella Parte II si espone il problema di controllo ottimo e la sua implementazione, passando poi alla descrizione dettagliata dell’ottimizzatore sviluppato e all’applicazione ad un semplice problema di Meccanica del Volo Spaziale. L’ultima parte `e dedicata alla validazione del risolutore PSO su

(11)

alcuni problemi, pi`u complessi, ancora nell’ambito della Meccanica del Volo Spaziale.

Pi`u in dettaglio, nel Capitolo 1 viene sinteticamente presentato e for-mulato il generico problema di ottimizzazione vincolata; nel Capitolo 2 si espongono i principi base della Particle Swarm Optimization e, dato che si tratta di una tecnica per ottimizzazione non vincolata, si d`a una panoramica dei possibili metodi per implementare i vincoli focalizzando l’attenzione sulle funzioni di penalizzazione.

Il Capitolo 3 riassume brevemente il problema di controllo ottimo e, nel Capitolo 4 si danno le indicazioni riguardanti la sua implementazione nume-rica; in quest’ultimo Capitolo si descrive non solo il tipo di schematizzazione adottata per affrontare il problema di ottimizzazione di traiettorie, ma si presenta anche il pacchetto di ottimizzazione creato: si analizza in dettaglio la tecnica utilizzata per poter implementare i vincoli e si descrivono i vari parametri e metodi alla base del risolutore sviluppato.

Nel Capitolo 5, si d`a una prima dimostrazione dell’efficienza del pacchetto di ottimizzazione riportando un primo problema di Meccanica del Volo Spazia-le, il caso di trasferimento a N -impulsi di un generico veicolo spaziaSpazia-le, dando una breve descrizione del problema e dei risultati.

Nel Capitolo 6 vengono introdotti i sistemi propulsi a vela solare e se ne analizzano i modelli matematici utili alla schematizzazione del comportamen-to della vela in funzione della sua geometria e del suo assetcomportamen-to, impostando poi il problema generale di rendez-vous interplanetario. Nel Capitolo 7 si affron-ta dapprima il caso di trasferimenti bidimensionali dalla Terra verso Marte e verso Venere e, nell’ultimo paragrafo, si presenta il problema di una missione pi`u complessa, dalla Terra verso Mercurio, includendo un incontro iperbolico con Venere. Nel Capitolo 8 si analizzano trasferimenti tridimensionali, in particolare vengono riportati i risultati relativi a due diverse schematizza-zioni del trasferimento dalla Terra verso Marte, con e senza il calcolo delle effemeridi.

I risultati presentati nella Parte III sono ottenuti col pacchetto di ottimizza-zione che abbiamo sviluppato ispirandoci alla Particle Swarm Optimization.

(12)

Parte I

Ottimizzazione vincolata a

singolo obiettivo

(13)

1

Ottimizzazione

1.1 Introduzione

L’ottimizzazione è uno dei problemi più diffusi e importanti in molti ambiti dell’ingegneria ed è per questo oggetto di numerosi studi.

In questo Capitolo ci occuperemo in particolare di ottimizzazione vincola-ta con singolo obiettivo: lo scopo `e di determinare un vettore di variabili di controllo tali da minimizzare una funzione scalare obiettivo considerata, soddisfacendo al contempo i generici vincoli imposti dal sistema.

1.2 Formulazione del problema

La pi`u generica forma con cui possiamo scrivere un problema di ottimizza-zione vincolata a singolo obiettivo `e la seguente:

min

x f (x), x ∈ S ⊂ <

n_, _(1.1)

soggetto ai vincoli

gi(x) ≤ 0, i = 1, . . . , m (1.2)

dove nell’equazione (1.1) compare la funzione scalare di cui si vuole trovare il minimo e il vettore delle variabili x da cui essa dipende; nell’equazione (1.2) sono compresi vincoli lineari e non lineari, di uguaglianza, di disuguaglianza (includendo anche vincoli del tipo gi(x) ≥ 0, basta porre infatti −gi(x) ≤ 0)

e vincoli semplici (valori massimi e minimi ammissibili per x).

(14)

1 – Ottimizzazione

Per comodit`a, nel seguito, potremmo riferirci al problema definito dalle equazioni (1.1)-(1.2) nella forma analoga ma meno sintetica:

min x f (x) (1.3) soggetta a: - Equazioni di vincolo hi(x) = 0; i = 0, 1, . . . , p (1.4) - Disequazioni di vincolo gj(x) ≤ 0; j = 0, 1, . . . , m (1.5) - Vincoli semplici xL≤ x ≤ xU (1.6)

dove p e m sono numeri naturali che rappresentano il numero di equazioni e di disequazioni di vincolo, xL e xU sono i limiti inferiori (Lower ) e superiori

(15)

2

Particle Swarm Optimization

2.1 Introduzione

Nelle applicazioni industriali il generico problema di ottimizzazione presen-tato nel Cap.1 viene solitamente affronpresen-tato mediante l’utilizzo di algoritmi gradientali, per via della loro efficienza computazionale.

Tuttavia questo tipo di approccio mostra i suoi limiti se adottato in caso di problemi non differenziabili.

Considerando che la maggior parte dei problemi di interesse ingegneristico `e di tipo non lineare, si pu`o comprendere il poderoso sviluppo di ricerche volte a trovare metodi di soluzione alternativi.

In particolare, grande attenzione si `e riversata su algoritmi di tipo stocasti-co. Una tecnica probabilistica appartenente a questa classe di ottimizzatori `

e proprio la Particle Swarm Optimization (PSO).

La PSO `e stata introdotta la prima volta da Kennedy e Eberhart [1] _e

si ispira al comportamento di animali che si muovono in gruppo (come api, pesci, uccelli). Tali individui si spostano per la ricerca di un obiettivo (cibo, luogo, etc.) in base al proprio istinto, alla memoria del proprio percorso ed a quella associata alle informazioni ottenute dagli altri individui.

Questo algoritmo ha il pregio di esser relativamente facile da programmare e non richiede che il problema o i vincoli siano continui. Inoltre, si adat-ta bene alla ricerca di una soluzione di tipo globale: le particelle vengono infatti inizializzate in maniera casuale e tendono a esplorare l’intero spazio

(16)

2 – Particle Swarm Optimization

circostante verso l’ottimo assoluto; la maggior parte di algoritmi di ottimiz-zazione si basa invece su di una prima stima della soluzione data dall’utente cercando poi di trovare un minimo nell’intorno di questa, assumendo quindi un comportamento di tipo locale.

La PSO `e stata applicata con successo in molte aree di ricerca: ottimizzazione di funzioni, reti neurali, sistemi di controllo fuzzy, e in tutti quegli impieghi dove fin dalla met`a degli anni070 si era soliti utilizzare gli Algoritmi Genetici (GA), altra tecnica stocastica di tipo evolutivo.

Dalla sua introduzione molti autori si sono per`o limitati a testare e svilup-pare la PSO solo su semplici problemi matematici, osando solo raramente l’applicazione diretta (quindi senza avvalersi di reti neurali o altro) a proble-mi di maggior interesse pratico.

La PSO `e stata infatti principalmente sfruttata per problemi o sotto-problemi1

di ottimizzazione solitamente non vincolata e con un basso numero di varia-bili (xh, h = 1, . . . n, con n solitamente non superiore a 7). Per quanto

riguarda l’implementazione dei vincoli si trovano solo alcuni criteri che, se dimostrano una certa efficienza nella risoluzione di semplici problemi, si ri-velano completamente inadeguati in casi di maggior complessit`a.

Nel presente lavoro si `e sviluppato in forma originale un algoritmo PSO che prevede un’implementazione dei vincoli basata sul metodo proposto, per altri ambiti, da Conn[2] e Lewis[3].

In questo Capitolo verr`a descritto l’algoritmo di base e i principali metodi per implementare i vincoli.

2.2 Algoritmo di base

La Particle Swarm Optimization è un algoritmo population based, ossia si basa sull’inizializzazione di una popolazione di particelle, ad ognuna delle quali è associato un vettore di variabili x e un valore della funzione obietti-vo, f (x). Questi individui, ad ogni passo dell’ottimizzatore, si spostano nel campo delle soluzioni al fine di raggiungere la posizione ottima, corrispon-dente cioè al minimo della funzione obiettivo. Lo spostamento è indirizzato

1_{Per sotto-problema intendiamo un caso pi`}_{u semplice da risolvere a cui ci si riduce a}

(17)

dalla posizione e velocit`a della particella nell’istante2 _{precedente, dalla}

me-moria della migliore posizione raggiunta nel proprio percorso e dalla migliore posizione in assoluto trovata dal gruppo.

Da questi semplici concetti si pu`o arrivare[4] ad un algoritmo caratteriz-zato dai seguenti punti principali (vedi Fig. 2.1):

1. Inizializzazione di una popolazione in maniera casuale. 2. Aggiornamento del vettore velocit`a per ogni particella. 3. Aggiornamento del vettore posizione per ogni particella. 4. Ritorno al passo 2 fino a convergenza.

Inizializzazione della popolazione

Aggiornamento della velocità delle particelle

Aggiornamento della posizione delle particelle

Criterio di convergenza

rispettato?

Termine del ciclo SI NO

Figura 2.1: Particle Swarm Optimization: algoritmo di base.

2_{Ogni istante corrisponde ad un passo di integrazione.}

(18)

Inizializzazione

La popolazione iniziale viene scelta in maniera casuale, all’interno dello spazio ammissibile definito dai vincoli semplici:

xi₀ = xL+ r3(xU − xL) (2.1)

vi₀ = xL+ r4(xU− xL)

∆t (2.2)

Dove xi

0 è il vettore posizione iniziale e vi0 è il vettore velocità iniziale,

en-trambi riferiti alla particella i-ma, r3 e r4 sono numeri casuali fra loro

indi-pendenti che assumono valori compresi fra 0 e 1. Una versione alternativa, anzich`e moltiplicare ogni componente del vettore posizione per lo stesso nu-mero casuale, utilizza valori differenti per ogni componente; xL `e il vettore

dei vincoli semplici di limite inferiore (lower bounds) e xU `e il vettore dei

vincoli semplici di limite superiore (upper bounds).

L’influenza della distribuzione iniziale delle particelle è stata studiata da Venter[4]: facendo alcune prove con diversa posizione iniziale delle particelle si è scoperto che questa non andava ad incidere sulle prestazioni o sulla con-vergenza dell’ottimizzatore. La ragione di questo comportamento è dovuta al continuo cambiamento di posizione che interessa ogni particella e che quindi fa perdere di importanza alla posizione iniziale.

Aggiornamento del vettore velocit`a

Sono possibili diverse metodologie di aggiornamento a seconda della versione di PSO adottata. Nella forma più generale la velocità della singola parti-cella costituente la popolazione è data dalla somma vettoriale di tre termini opportunamente pesati:

1. Il primo termine `e associato alla velocit`a della particella al passo cor-rente, vi

k.

2. Il secondo termine `e associato alla memoria della particella, dipendendo dalla migliore posizione incontrata dalla stessa nel proprio percorso, pi. 3. L’ultimo termine `e infine associato all’influenza da parte dell’intero

(19)

gruppo di particelle ed `e legato alla migliore posizione incontrata in assoluto nel passo corrente, pg_k.

i k

x

k

i

+

1

i

p

g k

p

i

k

v

t

v

_ki₊₁

Δ

Inerzia della particella

Memoria della particella

Influenza dello “sciame”

Figura 2.2: Particle Swarm Optimization: vettore velocit`a risultante.

Come mostrato in Fig. 2.2 la velocità di ogni particella sarà diretta secondo la risultante di questi tre termini, coerentemente con l’analogia dello “scia-me” in cui ogni individuo si sposta alla ricerca di cibo (minimo della funzione obiettivo) in base non solo alla propria inerzia (intesa come tendenza a non cambiare direzione nel proprio moto), ma anche alle informazioni relative alla migliore posizione trovata da esso e dal gruppo. Lo spostamento risultan-te sarà un compromesso fra l’inerzia a mantenere direzione di spostamento uguale alla precedente e la tendenza a dirigersi verso zone considerate pro-mettenti in base all’esperienza personale e del gruppo.

La velocit`a aggiornata assume quindi la seguente forma:

vi_k+1= χ · wvi_k+ c1r1 pi− xi k ∆t + c2r2 pg_k− xi k ∆t (2.3) dove xi

k `e il vettore posizione della particella i-ma alla k-ma iterazione, vik

`

e il corrispondente vettore velocit`a, r1 e r2 sono numeri casuali indipendenti

compresi fra 0 ed 1. Come nel caso di r3 e r4 si pu`o scegliere anche in questo

caso di moltiplicare ogni componente per un valore casuale diverso; pi `e la 10

(20)

migliore posizione trovata dalla particella i-ma, pg_k è la migliore posizione trovata nell’intero gruppo di particelle all’iterazione k-ma. Una possibile va-riante è utilizzare una memoria più forte, ossia considerare pg al posto di pg_k, cioè la migliore posizione trovata dall’intero gruppo a partire dall’inizio del ciclo iterativo; ∆t è invece il passo temporale fittizio con cui si muovono gli individui e solitamente viene preso unitario;

w rappresenta l’inerzia di ogni particella e controlla le proprietà esplorative dello “sciame”: con valori più grandi si favorisce una ricerca di tipo globale, con valori più piccoli si favorisce una ricerca di tipo locale.

Aumentando w si amplifica infatti il peso del primo dei tre termini dell’e-quazione (2.3) privilegiando un moto della particella verso spazi inesplorati da lei o dal gruppo, mentre diminuendo w si aumenta il peso relativo degli altri due termini di (2.3) forzando quindi l’individuo verso zone già indagate e considerate promettenti in termini di valore minimo della funzione obiet-tivo. Il valore di questo termine può essere preso variabile con il numero di iterazione k: come verrà esposto in seguito si tratta di un ottimo espediente per far s`ı che inizialmente venga favorita una ricerca globale per esplorare tutto lo spazio accumulando informazioni su di esso per poi indirizzare tutte le particelle verso la zona in cui sono state individuate le migliori posizioni. Cos`ı nelle iterazioni finali tutte le particelle potranno concentrarsi nell’intor-no della soluzione ottima;

c1 e c2 sono i pesi del secondo e terzo termine di (2.3) e sono detti

parame-tri di “cognizione”: il primo è legato alla “fiducia” che la particella ha in se stessa, il secondo è invece correlato alla “fiducia” nel gruppo; aumentare c1, a parità degli altri parametri, si traduce in un’amplificazione del secondo

termine dell’Eq. (2.3) e quindi la particella tende maggiormente a seguire la posizione migliore incontrata fino a quel momento nella sua ricerca; aumen-tare c2 porta ad un incremento del terzo termine dell’Eq. 2.3: ci`o significa

forzare la particella in direzione della migliore posizione trovata dal gruppo. I valori che possono assumere sono generalmente tali che

c1+ c2 ≤ 4

χ è un fattore di costrizione e regola la velocità di ricerca: può assumere valore uguale o inferiore all’unità; nel caso in cui i bordi del dominio siano

(21)

eccessivamente ampi si pu`o migliorare l’esplorazione dello spazio andando invece ad aumentare questo parametro.

Aggiornamento del vettore posizione

Lo schema per aggiornare la posizione di ogni particella `e

xi_k+1 = xi_k+ vi_k+1∆t (2.4) dove xi_k+1`e la posizione della particella i-ma all’iterazione k +1 e ∆t `e ancora il passo temporale fittizio con cui si muovono gli individui.

L’aggiornamento di velocit`a e di posizione, come riportato in Fig. 2.3, sono mossi dai tre componenti di inerzia, memoria e influenza del gruppo di cui abbiamo discusso nel paragrafo precedente.

Inerzia della particella Memoria della particella Influenza da parte del gruppo Aggiornamento velocità e posizione della particella

Figura 2.3: Particle Swarm Optimization: aggiornamento di posizione e di

velocit`a.

Controllo di convergenza

Il controllo per verificare la convergenza `e essenziale per terminare il ciclo solo quando `e necessario. Se il ciclo si ferma precocemente si arriva ad un risultato impreciso o addirittura ad un minimo locale, se invece termina troppo tardi si hanno inutili sprechi in termini di tempi di calcolo.

Il principio di base `e semplice: il ciclo converge se la variazione della funzione obiettivo soluzione (pg_k) degli ultimi n passi non varia oltre un valore soglia.

(22)

`

E evidente la necessit`a di stabilire il numero n di cicli consecutivi dopo i quali si ha convergenza e il valore soglia.

2.3 Ottimizzazione vincolata

Il punto chiave dell’ottimizzazione vincolata (Constrained Optimization, CO) consiste nel trovare un adeguato metodo con cui implementare i vincoli. L’algoritmo PSO di base `e infatti definito esclusivamente per problemi non vincolati (ad eccezione dei vincoli semplici) ed `e pertanto necessario scegliere il modo adeguato con cui trattare vincoli lineari e non lineari.

Sono disponibili molte tecniche, gi`a esistenti in letteratura poich´e necessarie per adattare ai problemi CO gli algoritmi evolutivi, presenti in circolazione da un maggior numero di anni.

Koziel[5] ha proposto una divisione in quattro categorie:

- Metodi basati sul mantenimento della “feasibility” (posizione ammis-sibile3).

- Metodi basati sulle funzioni di penalizzazione.

- Metodi basati su una chiara distinzione fra soluzione ammissibile e non. - Metodi ibridi vari.

Ci limiteremo a focalizzare l’attenzione sui primi due metodi dato che il terzo gruppo `e poco utilizzato e il quarto gruppo pu`o essere visto come derivante dai primi due.

2.3.1 Metodi basati sul mantenimento della

“feasibili-ty”

I metodi basati sul mantenimento della “feasibility” sono i pi`u semplici: in vista di trovare una soluzione le particelle esplorano l’intero spazio a dispo-sizione, ma vengono utilizzate solo quelle associate a soluzioni ammissibili

(23)

(feasible solutions). Per velocizzare il processo tutte le particelle sono inizia-lizzate come ammissibili.

Nel presente studio si sono fatte prove su questo tipo di approccio ma `

e risultato efficiente solo se applicato a problemi molto semplici di interesse esclusivamente accademico.

2.3.2 Funzioni di penalizzazione

L’idea di base dei metodi di penalizzazione consiste nel trasformare il pro-blema di ottimizzazione vincolata originario in un propro-blema equivalente di ottimizzazione non vincolata.

Questo pu`o esser ottenuto andando ad ottimizzare una nuova funzione obiet-tivo, ottenuta dalla principale aggiungendo termini di penalizzazione dipen-denti dai vincoli e da opportuni parametri.

I termini aggiuntivi sono definiti in maniera tale che se i vincoli sono soddi-sfatti non c’è penalizzazione, ma se qualcuno di essi è violato, un cospicuo termine aggiuntivo graverà sulla funzione obiettivo. Dato che lo scopo del-l’ottimizzatore è quello di minimizzare la funzione obiettivo, il termine di penalizzazione aggiuntivo forzerà indirettamente i vincoli ad esser soddisfat-ti.

In definitiva `e necessario passare dal problema originario (Eq. (1.1)): min

x f (x)

soggetto ai vincoli di uguaglianza e disuguaglianza (Eq. (1.2)): hi(x) = 0; i = 0, 1, . . . , p gj(x) ≤ 0; j = 0, 1, . . . , m al problema min x φ(x, µ) (2.5) 14

(24)

con

φ(x, µ) = f (x) + Φ(hi(x), gj(x), µ), (2.6)

dove µ è un generico parametro di penalizzazione, Φ è il termine di penalizza-zione aggiuntivo dipendente dalle equazioni e dalle disequazioni di vincolo e da µ; φ è la nuova funzione obiettivo da minimizzare, non soggetta a vincoli. In Fig. 2.4 riportiamo un semplice schema sull’equivalenza fra problema originario e derivato. Problema di ottimizzazione vincolata Problema di ottimizzazione non vincolata - Funzione obiettivo f(x) - Equazioni e Disequazioni di vincolo Funzione obiettivo (x) = f(x) + termine di penalizzazione φ Soluzione Soluzione Teoricamente coincidono

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

Esistono diverse possibilit`a con cui definire i termini di penalizzazione: - Exterior Penalty Function

- Interior Penalty Function

- Funzioni di penalizzazione esatte (Augmented Lagrangian Penalty Func-tion)

(25)

Exterior Penalty Function

Le Exterior Penalty Function sono le funzioni di penalizzazione pi`u semplici. Il problema vincolato viene trasformato nell’equivalente problema di ottimiz-zazione non vincolata della seguente funzione:

φ(x, µ) = f (x) + 1 2µ " _m X j=1 (max[0, gj(x)]) 2 + p X i=1 (hi(x)) 2 # (2.7)

dove µ `e un numero positivo “piccolo”, e viene detto numero di penalizza-zione.

Se gj(x) ≤ 0 si avr`a max[0, gj(x)] = 0 e quindi il termine aggiuntivo non

dar`a contributo in φ(x,µ); solita conclusione se hi(x) = 0.

Se invece i vincoli vengono violati si avr`a gj(x) > 0 (e quindi max[0, gj(x)] 6=

0) e/o hi(x) 6= 0 e quindi un termine “grande” verr`a aggiunto a φ(x, µ).

Affinch´e il metodo funzioni `e necessario che µ sia molto “piccolo” e di con-seguenza _2µ1 sia molto “grande”. Infatti, in teoria, il minimo di φ(x, µ) corrisponde con il minimo del problema originario solo se µ → 0 e quindi

1

2µ → ∞.

Esistono versioni in cui il parametro di penalizzazione `e assunto dinamico, ossia cambia col numero di iterazione corrente: in questa maniera si riducono i possibili problemi numerici associati al valore di µ.

Nel presente lavoro sono stati intrapresi tentativi anche con questo ap-proccio: indubbiamente la presenza di un parametro di penalizzazione va-riabile riduce, ma non elimina, i problemi numerici connessi all’utilizzo di questo metodo.

Interior Penalty Function

Nell’Interior Penalty Function il termine di penalizzazione viene definito in maniera tale da evitare che la soluzione esca dalla regione possibile (feasible). In questo metodo non `e possibile trattare direttamente i vincoli di uguaglian-za, per i quali si ricorre alla formulazione della Exterior Penalty Function. Esistono diverse Interior Penalty Function, le pi`u comuni sono la funzione di

(26)

penalizzazione (funzione di barriera o confine) logaritmica e quella inversa:

φ(x, µ) = f (x) − µ " _m X j=1 lg[−gj(x)] # (2.8) φ(x, µ) = f (x) + µ " _m X j=1 −1 gj(x) # (2.9) dove µ `e un numero positivo, noto come numero di penalizzazione.

Si assume che tutti i vincoli di disuguaglianza siano sempre soddisfatti e che nel caso in cui la soluzione si avvicini alla zona di “confine” dei vincoli (cio`e gj(x) → 0) la penalizzazione della funzione obiettivo aumenti via via sempre

pi`u.

Per questo motivo ci si riferisce a questi metodi anche come metodi di barriera (barrier function method ).

Affinch`e il metodo funzioni `e necessario che µ sia “piccolo”. Infatti, in teoria, il minimo di φ(x, µ) corrisponde con il minimo del problema originario solo se µ → 0.

Funzioni di penalizzazione esatte (Augmented Lagrangian Penalty Function )

I metodi di penalizzazione che si avvalgono di funzioni exterior oppure inte-rior usano semplici idee di base per convertire il problema originario vincolato nell’equivalente non vincolato.

Tuttavia entrambi i metodi soffrono di problemi numerici legati al valore del numero di penalizzazione µ e, con valori finiti dello stesso, si arriva ad una soluzione diversa da quella del problema originario.

In questo contesto si sviluppano i metodi di penalizzazione esatta in cui `e possibile arrivare alla vera soluzione del problema, partendo da valori finiti di µ.

La Augmented Lagrangian Penalty Function `e un esempio di funzione di penalizzazione esatta e consiste nel definire la funzione obiettivo non vincola-ta (φ) aggiungendo il termine caratteristico della Exterior Penalty Function al Lagrangiano del problema originario, anzich´e alla funzione obiettivo di

(27)

2 – Particle Swarm Optimization esso: φ(x, γ, λ, s, µ) = f (x) + p X i=1 λi· hi(x) + m X j=1 γj · (gj(x) + s2j)+ + 1 2µ · " _p X i=1 (hi(x))2+ m X j=1 (gj(x) + s2j) 2 #

dove µ `e il parametro di penalizzazione, γ e λ sono i moltiplicatori di La-grange, s sono le slack variables, f (x) `e la funzione obiettivo, g(x) e h(x) sono le equazioni e disequazioni di vincolo.

Le slack variables s che compaiono nel Lagrangiano sono definite per le dise-quazioni di vincolo ed aumentano il numero di variabili del problema: tramite alcune semplici considerazioni `e comunque possibile rimuoverle conglobando-le in un termine che dipende da g(x) e da µ (vedi [6] per ulteriori approfon-dimenti).

Se il valore dei moltiplicatori `e noto, allora la soluzione dell’Eq. (2.10) corri-sponde con quella del problema originario, indipendentemente dal valore del parametro di penalizzazione.

Purtroppo il valore dei moltiplicatori di Lagrange ottimi non è noto. Tutta-via la presenza di questi parametri rende meno critica la scelta del numero di penalizzazione µ; il metodo consiste nel partire con una prima stima di γ e λ e sviluppare una procedura in grado di far evolvere tali parametri verso il valore ottimo. Cos`ı, vicino all’ottimo, la funzione φ non è più tanto sensibile al valore di µ e la procedura converge verso la vera soluzione ottima.

Sono quindi necessari due cicli annidati:

- Ciclo esterno, essenziale per far evolvere i parametri µ, γ e λ. La generica iterazione `e indicata con k.

- Ciclo interno, ovvero il ciclo di ottimizzazione necessario alla risoluzione del problema non vincolato. La generica iterazione `e indicata con i4_.

In Fig. 2.5 riportiamo lo schema di questa procedura. La risoluzione del pro-blema non vincolato pu`o essere affrontata con un qualunque ottimizzatore.

4_{Attenzione a non confondere gli indici i e k con quelli presentati in 4.3 che si riferivano}

alla particella e al numero di iterazione interna (ora i).

(28)

Stima iniziale di:

Parametro di penalizzazione, Moltiplicatori di Lagrange, 0

μ

Risoluzione del problema di ottimizzazione non vincolata

(la funzione obiettivo diventa il Lagrangiano aumentato) k k k

γ

λ

μ

,

Sono rispettati i criteri di convergenza? Termina la ricerca Nuova stima di , k=k+1 SI NO 0 0,λ γ k k k

γ

λ

μ

,

Figura 2.5: Procedura di risoluzione di un problema di ottimizzazione vincolata, basata sull’Augmented Lagrangian Penalty Function.

Esistono numerosi approcci, di differente complessit`a, con cui implemen-tare questo metodo.

Nel paragrafo 4.3.1 verr`a descritto in dettaglio quello utilizzato nel presente lavoro di tesi.

(29)

Parte II

Controllo ottimo e sua

implementazione

(30)

3

Cenni sul controllo ottimo

3.1 Formulazione del problema

Un problema di controllo ottimo, o anche di ottimizzazione di traiettoria, pu`o esser affrontato dividendo il dominio in N fasi. Per ogni fase k `e possibile definire la variabile indipendente t, spesso coincidente con il tempo:

t(k)_I ≤ t ≤ t(k)_F

dove t(k)_I e t(k)_F sono rispettivamente l’istante iniziale e finale della fase k-ma. Dato che le fasi sono in sequenza possiamo scrivere le seguenti equazioni di raccordo:

t(k+1)_I = t(k)_F

All’interno della fase k la dinamica del sistema `e descritta dalle variabili di stato, dalle variabili di controllo e da parametri p indipendenti dal tempo:

y(k)(t), u(k)(t), p

Al fine di rendere meno pesante la notazione nel seguito si abbandonano gli apici (k) _{che indicano la dipendenza dalla fase.}

La dinamica del sistema `e tipicamente descritta da un sistema di equazioni differenziali, le equazioni di stato:

˙

(31)

3 – Cenni sul controllo ottimo

Il sistema pu`o poi esser soggetto ai seguenti vincoli: - Vincoli algebrici sulla tariettoria

g_L≤ g[y(t), u(t), p, t] ≤ g_U, (3.2) - Condizioni iniziali ψ_0L ≤ ψ[y(t0), u(t0), p, t0] ≤ ψ0U, (3.3) - Condizioni finali ψ_{f L} ≤ ψ[y(tf), u(tf), p, tf] ≤ ψf U, (3.4) - Vincoli semplici y_L≤ y(t) ≤ y_U (3.5) uL≤ u(t) ≤ uU (3.6)

dove con i pedici L e U ci riferiamo sempre ad un limite inferiore o superiore

rispettivamente.

La risoluzione del problema di controllo ottimo consiste nel trovare il vettore di controllo u e il vettore dei parametri p che minimizzano una certa funzione obiettivo, o indice di prestazione.

Nel caso più generale la funzione obiettivo può essere espressa come somma di un termine integrale, contenente una certa funzione di quadratura w, e un termine puntuale, contenente quantità definite negli istanti finali delle fasi:

J = φ[y(t(1)₀ ), y(t(1)_f ), t(1)₀ , t(1)_f , p(1), . . . ,y(t(N )₀ ), y(t(N )_f ), t(N )₀ , t(N )_f , p(N )] +

Z t(j)_f

t(j)₀

w(j)[y(t), u(t), p, t]dt

(3.7) Si fa notare che l’indice di prestazione altro non `e che la funzione obiettivo f , definita in Cap. 1.

(32)

3.2 Soluzione del problema di controllo

otti-mo

Il problema di controllo ottimo pu`o essere visto come un’estensione del pro-blema di programmazione non lineare al caso di un numero infinito di varia-bili.

Nel calcolo delle variazioni `e possibile ricavare a partire dalle Eq. (3.1)-(3.6) alcune condizioni necessarie all’ottimo introducendo l’indice di prestazione aumentato e imponendo l’annullamento della corrispondente variazione pri-ma (vedi Betts[7] _{per approfondimenti).}

Si presentano a questo punto due diverse tecniche con cui affrontare il problema:

• Metodi Diretti • Metodi Indiretti

Entrambi gli approcci hanno vantaggi e svantaggi, come verr`a illustrato nel seguito.

Metodi diretti

I metodi diretti tentano di trovare la soluzione ottima cercando direttamente il vettore di variabili x che minimizzi la funzione obiettivo (Eq. (3.7)). A differenza dei metodi indiretti, non si richiede una formulazione analitica delle condizioni necessarie, n`e un valore di primo tentativo delle variabili aggiunte.

Un metodo di ottimizzazione di questo tipo cerca quindi di modificare le variabili di controllo u ed i parametri p ad ogni iterazione al fine di ridurre l’indice di prestazione.

Metodi indiretti

I metodi indiretti tentano di localizzare la soluzione ottima cercando di ri-solvere le condizioni necessarie del problema ricavate da un calcolo di tipo variazionale.

`

(33)

la risoluzione, non sempre ovvia, di un problema ai valori al contorno non lineare.

I principali inconvenienti di un simile approccio sono i seguenti:

1. Costruire le condizioni necessarie di ottimo non è facile e comporta notevole esperienza. Inoltre non è un approccio flessibile, dato che per ogni nuovo problema è necessario ricavare nuove condizioni.

2. La regione di convergenza può esser sorprendentemente piccola. In più si è costretti all’arduo e importante compito di sceglier valori di primo tentativo per le variabili aggiunte1_{: essi non sono intuitivi, ed una scelta}

errata pu`o portare ad un mal condizionamento del problema.

3. Per problemi con disequazioni di vincolo `e necessario scegliere la se-quenza delle sotto fasi vincolate e non vincolate prima che l’iterazione abbia inizio.

3.2.1 Soluzione del problema con metodi diretti

I passi fondamentali per la risoluzione del problema di ottimo mediante metodi diretti sono i seguenti:

1. Conversione del sistema dinamico in un problema ad un numero finito di variabili.

2. Risoluzione del problema di dimensione finita utilizzando un generico metodo di ottimizzazione.

3. Valutazione dell’accuratezza di discretizzazione del problema.

Il primo passo viene affrontato discretizzando il problema; si divide la durata della fase in un certo numero di intervalli, ad es (M − 1):

tI = t1 < t2 < . . . < tM −1< tM = tF

Gli M punti che definiscono gli intervalli sono detti nodi e il loro insieme `e detto griglia di discretizzazione. A questo punto, applicando appositi sche-mi numerici in grado di risolvere problesche-mi differenziali si riesce a costruire

1_{Le variabili aggiunte sono moltiplicatori di Lagrange che compaiono nell’espressione}

dell’indice di prestazione aumentato.

(34)

uno strumento in grado di fornire il valore assunto dai vincoli (g(x), h(x)) e dalla funzione obiettivo (f (x)) in corrispondenza di un ingresso di variabili x.

Il secondo punto consiste nell’applicazione vera e propria dell’ottimizza-tore: nel nostro caso abbiamo sviluppato e utilizzato un algoritmo ispirato alla PSO, che verr`a descritto in Cap. 4.3.

Il terzo punto comporta un controllo su quanto l’approssimazione delle variabili di stato e di controllo ottenuta `e vicino alla reale. Per la descrizione dell’argomento si rimanda ancora a Betts[7].

`

E infine opportuno fare un cenno alla scalatura: questa deve esser fatta prima del secondo passo ed `e fondamentale al fine di ottenere una convergenza alla soluzione rapida e robusta.

(35)

4

Implementazione del problema di

ottimizzazione di traiettorie

4.1 Introduzione

Nel presente Capitolo ci accingiamo a descrivere il risolutore del problema di ottimizzazione basato sulla PSO e il suo connubio con la suite ODE di MATLAB.

A partire da questi due strumenti, uno in grado di risolvere problemi di otti-mizzazione, l’altro problemi differenziali, `e possibile riuscire ad affrontare il generico problema di controllo ottimo.

4.2 Istante finale libero o fissato

I problemi fisici possono essere ad istante finale libero o fissato: nel primo caso il tempo di percorrenza diventa una delle variabili in funzione delle quali ottimizzare e rappresenta anche l’indice di prestazione, nel secondo caso invece la funzione obiettivo `e solitamente data dal valore assunto da alcune grandezze fisiche all’istante finale.

Le due tipologie descrivono ad esempio rispettivamente il problema di velivoli a vele solari e a propulsione elettrica; nella presente trattazione ci occuperemo pertanto di problemi ad istante finale libero.

(36)

4 – Implementazione del problema di ottimizzazione di traiettorie

4.3 Descrizione dell’algoritmo ottimizzatore

Durante il presente lavoro di tesi si `e creato in ambiente MATLAB un pac-chetto di ottimizzazione basato su algoritmi di tipo PSO.

Partendo dalle idee di base, descritte nel capitolo 2, e utilizzando un metodo per implementare i vincoli sperimentato in passato solo su algoritmi genetici, `

e stato possibile arrivare ad un ottimizzatore in grado di risolvere numerosi problemi: `e stato testato sia su semplici equazioni da minimizzare soggette a ulteriori equazioni di vincolo, sia a ben pi`u complessi problemi di meccanica del volo spaziale.

Questo algoritmo si adatta a priori ad un qualsiasi problema di ottimizzazio-ne, a patto di modificare opportunamente alcuni dei parametri che verranno presentati in seguito.

Nel paragrafo seguente descriveremo in dettaglio come abbiamo affrontato l’implementazione dei vincoli, mentre, successivamente, si analizzeranno gli aspetti salienti del pacchetto di ottimizzazione sviluppato.

4.3.1 Schema per l’implementazione di vincoli non

li-neari

Per poter includere nell’ottimizzatore i vincoli non lineari si sono fatte prove su alcuni dei metodi esposti nel Cap. 2.3.2:

- I metodi basati sulla “feasibility” si sono dimostrati totalmente ineffi-cienti; unica eccezione per problemi di ottimizzazione particolarmente semplici, o meglio, con vincoli poco stringenti.

- I metodi basati sull’ Exterior Penalty Function si sono comportati di-scretamente anche in problemi pi`u complessi: si sono riscontrate diffi-colt`a numeriche legate alla scelta del parametro di penalizzazione (µ), in parte superate adottando una versione in cui detto numero varia con l’iter.

- I metodi basati sull’Augmented Lagrangian Penalty Function (ALPF) sono risultati soddisfacenti: si sono fatte prove con diverse versioni, in seguito riportiamo quella che si `e mostrata pi`u efficace.

(37)

Descrizione di un algoritmo basato su ALPF

Il metodo che ci accingiamo a descrivere affonda le sue radici nel LANCELOT, un algoritmo in Fortran introdotto da Conn[2]_{, di cui esistono numerose}

in-terpretazioni e varianti.

La versione che viene riportata `e quella applicata nel pacchetto di ottimiz-zazione sviluppato ed `e stata opportunamente modificata per adattarsi il meglio possibile all’ottimizzatore PSO con cui deve dialogare.

Come anticipato nel paragrafo 2.3.2 la ricerca dell’ottimo vincolato viene ricondotta alla soluzione del problema equivalente:

min x φ(x, γ, λ, s, µ), φ(x, γ, λ, s, µ) = f (x) + p X i=1 λi· hi(x) + m X j=1 γj · (gj(x) + s2j)+ + 1 2µ · " _p X i=1 (hi(x))2+ m X j=1 (gj(x) + s2j) 2 #

Nel seguito si supporr`a di non avere vincoli di disuguaglianza: `e possibile ri-dursi facilmente a questo caso utilizzando la procedura descritta da Bhatti[6]

o da Conn[2]_{; le difficolt`}_{a nell’implementare i vincoli derivano principalmente}

dalle equazioni di uguaglianza e nell’ambito di questo studio riteniamo im-portante focalizzare l’attenzione su questo aspetto.

La funzione di penalizzazione considerata ha la seguente espressione:

φ(x, λ, µ) = f (x) + p X i=1 λi· hi(x) + 1 2µ · p X i=1 (hi(x))2 (4.1)

L’algoritmo che `e stato creato si basa su due cicli, uno esterno e l’altro in-terno. Inizialmente vengono introdotti i valori di partenza del numero di penalizzazione e dei moltiplicatori di Lagrange e le costanti che serviranno ad aggiornarli durante la simulazione.

Il ciclo esterno fissa cos`ı µk e λk ad ogni sua iterazione (k = 0 se siamo

al passo immediatamente successivo all’inizializzazione). Noti questi valori possiamo ricavare dall’ Eq. (4.1) la funzione penalizzata in funzione delle sole variabili di ottimizzazione, x: ci siamo quindi ricondotti ad un proble-ma di ottimizzazione non vincolata equivalente. Questo probleproble-ma pu`o essere

(38)

risolto (tramite un ciclo interno) con un generico risolutore di ottimizzazione non vincolata, come ad esempio l’algoritmo basato sulla PSO. Il criterio di convergenza del ciclo interno si basa su valori soglia definiti nel ciclo esterno e dipendenti dal numero di iterazione k: il pi`u importante di questi, ωk,

rappre-senta la tolleranza entro la quale considerare uguali due iterazioni successive. Terminata la ricerca dell’ottimo del problema equivalente si verifica se i vin-coli sono rispettati: se verificano le condizioni obiettivo il ciclo termina. Se questo non avviene possono presentarsi due casi:

1. I vincoli, pur non rispettando il valore soglia obiettivo, rientrano co-munque in un valore di tolleranza, ηk, stabilito nel ciclo esterno

al-l’iterazione k-ma; la ricerca sta andando nella giusta “direzione” e si prosegue aggiornando i moltiplicatori di Lagrange.

2. I vincoli non sono rispettati e non rientrano neanche nei valori di so-glia ηk: in questo caso non si aggiornano i moltiplicatori di Lagrange

ma il parametro di penalizzazione per indurre la soluzione verso valori ammissibili.

Riportiamo schematicamente i passi della procedura. 1. Inizializzazione.

Vengono specificate le seguenti costanti, definite come strettamente positive:

ηs, ωs, αω βω, αη βη, (4.2)

e

τ < 1, ω∗ 1 η∗ 1 (4.3)

I coefficienti di (4.2) e (4.3) sono costanti necessarie ad aggiornare, in maniera opportuna, il numero di penalizzazione (tramite τ ), i molti-plicatori di Lagrange (indirettamente, tramite i valori di tolleranza sui vincoli), le tolleranze sui vincoli (ηs, αη, βη, η∗) e sulla convergenza (ωs,

αω, βω, ω∗); I valori numerici di questi parametri sono stati scelti in

basi ad alcuni dati trovati nel pacchetto GADS di MATLAB e a diverse prove effettuate durante questo studio.

(39)

diretto: sono i valori obiettivo delle tolleranze sui vincoli e sulla con-vergenza.

Inoltre si specifica un parametro di penalit`a iniziale, positivo:

µ0 < 1. (4.4)

Ed infine si ricavano i seguenti valori:

ω0 = ωsµα0ω (4.5)

η0 = ηsµ αη

0 . (4.6)

2. Iterazione interna.

Consiste nel risolvere il problema di ottimizzazione definito dalla (2.10), utilizzando gli appositi valori del parametro di penalizzazione e dei mol-tiplicatori di Lagrange. L’ottimizzatore, di tipo PSO nel nostro caso, si avvarr`a di un suo ciclo interno, le cui iterazioni vengono identificate con l’indice i, che terminer`a quando saranno soddisfatte, per un certo numero di iterazioni consecutive, le generiche condizioni di convergenza: | efk(xi) − efk(xi−1)| ≤ ωk (4.7)

dove con ef ci riferiamo alla funzione obiettivo da minimizzare (φ(x) nel nostro caso), il pedice k indica il numero di iterazione del ciclo esterno, l’apice i è il numero dell’iterazione interna all’ottimizzatore e xi è il vettore di variabili in corrispondenza del quale si ha la soluzione ottima del passo i-mo. Da sottolineare che, alla k-ma iterazione avremo dei valori del parametro di penalizzazione e dei moltiplicatori di Lagrange ben definiti (µk e λk), per cui la funzione φ che compare in (2.10) è

funzione della sola variabile x. La soluzione dell’ottimizzatore sar`a in corrispondenza di x∗_k.

3. Test di convergenza. Se si verifica:

|h(x∗_k)| ≤ η∗, (4.8)

il ciclo esterno termina.

(40)

Se si verifica

|h(x∗

k)| ≤ ηk, (4.9)

allora `e necessario eseguire il passo 4, altrimenti si va al passo 5. 4. Aggiornamento del valore dei moltiplicatori di Lagrange.

Si pone: λk+1 = λk+ 2µk· h(x∗k) (4.10) µk+1 = µk (4.11) ξ = max η∗, 1 2µk (4.12) ωk+1 = ωkξβω (4.13) ηk+1 = ηkξβη (4.14)

5. Aggiornamento del parametro di penalizzazione. Si pone: λk+1 = λk (4.15) µk+1 = τ · µk (4.16) ξ = max η∗, 1 2µk (4.17) ωk+1 = ωsξαω (4.18) ηk+1 = ηsξαη (4.19)

Questi passi vengono ripetuti finch`e non `e verificata la convergenza al passo 3, oppure fino al raggiungimento di un certo numero di iterazioni nel ciclo esterno.

Lo schema dell’algoritmo `e riportato in Fig. 4.1.

4.3.2 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).

(41)

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.

(42)

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, è in PSO_ALF che si creano le particelle (inizializzazione) e si dà loro la possibilità di spostarsi con una certa velocità (aggiornamento del vettore velocità) 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 (Bessetsolitamen-te[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).

(43)

Se in problemi complessi si utilizza direttamente il risolutore qui svilup-pato è bene non avvalersi popolazioni con più di 50 particelle: ciò 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 è il peso che si dà nello spostamento risultante della particella alla casualità con cui esplora lo spazio circostante. Valori alti aumentano la mobilità delle particelle, valori bassi le confinano in una zona limitata. In accordo con Venter[4] si è 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 è 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 è dimostrato particolarmente versatile, perciò abbiamo pensato di utilizzare metodi più 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.

(44)

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 pottene-recedente, visibile come caso particolaottene-re 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è il programma termina anche senza aver raggiunto convergenza. È un numero solitamente alto; si è posto pari a 2000.

(45)

- 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ò utilizzare anziché la differenza semplice tra le soluzioni la differenza relativa (differenza fra le soluzioni per unità di soluzione). In Fig. 4.2 si riporta uno schema del controllo per la convergenza.

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

(46)

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.

(47)

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 è assolutamente efficente. Il secondo è senz’altro il migliore ed è quello che utilizzeremo di default.

- Termine brusco del ciclo, Hardstopper. È 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 è 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à 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.

(48)

- 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 è 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 è 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à 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 è il valore di partenza per _2µ1 dell’Eq. (2.10), mentre tau è il coefficiente secondo cui aumentare la penalizzazione in caso di necessità. 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

(49)

di convergenza siano soddisfatti. È 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ù grossolana e andando avanti, man mano che la stima dei moltiplicatori di Lagrange si fa migliore, si procede verso un’indagine più raffinata. La crescita di questo valore non è lineare con il numero di iterazione (esterna), bens`ı tiene conto, indirettamente, della bontà 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)

(50)

- Parametri di memoria. Si tratta di un sistema, attivabile o meno, che permette di partire con una popolazione iniziale non completamente casuale; abbiamo già 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à 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 è scelto di introdurre la possibilità 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 venven-gono 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.