Nella Optimization Toolbox di MatLab si trovano gi`a implementati molti di questi algoritmi, di cui dallo stesso help possiamo ricavare una lista
MatLab accetta come input per i vincoli i parametri: • A e b per disequazioni lineari del tipo A · x ≤ b • Aeq e beq per equazioni lineari del tipo Aeq· x = beq
• lb e ub (low boundaries e up boundaries) come vincoli diretti della variabile
• le funzioni c e ceq per vincoli di tipo non lineare dove i due valori di c e ceq sono i vincoli del
tipo c(x) ≤ 0 e ceq(x) = 0
Nella tabella vengono illustrati gli algoritmi per la ricerca di un ottimo globale gi`a implementati in MatLab, con le loro caratteristiche
Solutore Convergenza Caratteristiche
GlobalSearch Convergenza veloce a punto di ottimo locale per problemi continui
Iterazioni deterministiche; Basato sul gradiente;
Punti iniziali stocastici automa- tici;
MultiStart Convergenza veloce a punto di ottimo locale per problemi continui
Iterazioni deterministiche; Basato sul gradiente;
Punti iniziali stocastici o deter- ministici, o combinazione; Permetta la scelta del solutore locale;
Patternsearch Convergenza provata ad ottimo locale, pi`u lento dei risolutori basati su gradiente
Iterazioni deterministiche; Nessun gradiente;
Punto iniziale definito dall’uten- te;
GA (Genetic Algorithm)
Nessuna prova di convergenza
Iterazioni stocastiche; Basato su una popolazione; Nessun gradiente;
Popolazione iniziale automatica o fornita dall’utente;
Tabella 6.1. Algoritmi implementati in MatLab e loro caratteristiche
Di questi algoritmi sono stati provati patternsearch e GA in quanto il fatto che non necessitano di un gradiente li rende pi`u adatti a problemi in cui la funzione da ottimizzare presenta delle discontinuit`a. Le prove eseguite con questi due algoritmi hanno dimostrato che:
6 – L’ottimizzazione
• patternsearch converge molto rapidamente, ma spesso su valori che risultano ancora molto alti
• L’algoritmo genetico invece dimostra una buona capacit`a di ricerca del minimo ma tempi eccessivamente lunghi.
Oltre agli algoritmi gi`a presenti in MatLab `e stato implementato l’algoritmo PSO ,descritto nel capitolo 7 il quale ha dato prova di essere il giusto compromesso tra qualit`a della ricerca e velocit`a di esecuzione.
Capitolo
7
L’algoritmo PSO
7.1
Descrizione
La Particle Swarm Optimization (PSO) rappresenta una nuova famiglia di algoritmi evolutivi, le cui basi furono sviluppate nel 1995 da sociologo J. Kennedy e dall’ingegnere elettronico R. Eberhart. La ricerca dell’ottimo nello spazio delle possibili soluzioni `e guidata dagli individui della popolazione che hanno maggior successo rispetto agli altri, creando un equilibrio tra ricerca globale e locale. Sebbene sia originariamente nata per simulare il comportamento sociale la PSO pu`o essere usata per risolvere in modo rapido ed efficiente diversi tipi di problema di ottimizzazione.
La PSO `e considerata nel contesto degli algoritmi evolutivi insieme agli algoritmi genetici. Infatti questi metodi hanno in comune la capacit`a di adattamento, cio`e la possibilit`a di modificare la propria struttura durante l’evoluzione, al fine di migliorare la performance dell’algoritmo stesso; tutti si basano su una ricerca stocastica dell’ottimo nello spazio delle possibili soluzioni e tutti considerano popolazioni di individui. Tuttavia la Particle Swarm Optimization presenta delle differenze importanti rispetto agli algoritmi genetici. Infatti, mentre in questi ultimi attraverso l’operazione di selezione nel passare da una generazione ad un’altra sopravvivono solo gli individui migliori (cio`e quelli a cui `e associato il miglior valore di fitness), nella PSO sopravvivono tutti gli individui della popolazione. La metafora che guida la PSO `e l’interazione sociale : gli individui imparano l’uno dall’altro e si modificano per diventare pi`u simili ai loro vicini. inoltre la particella non `e mutata attraverso l’aggiunta di un vettore, ma `e aggiornata sia in base alla propria esperienza di volo che a quella del gruppo.
In altre parole, ad ogni generazione, nella PSO ogni particella pu`o volare solo in un numero limitato di direzioni che si suppone siano quelle migliori suggerite dall’esperienza di gruppo. Invece,
7 – L’algoritmo PSO
nelle algoritmi genetici ogni individuo pu`o volare in qualunque direzione. Questo vuol dire che nella PSO l’operazione di mutazione avviene con coscienza, cio`e la particella ha la possibilit`a di volare pi`u rapidamente verso la soluzione migliore quando la coscienza fornisce un’informazione utile. Questo algoritmo evolutivo presenta il notevole vantaggio di convergere verso la soluzione migliore pi`u rapidamente rispetto agli algoritmi genetici.
Kennedy ed Eberhart concentrarono la loro attenzione sui modelli sviluppati dal biologo Frank Heppner, in particolare sulle dinamiche di affollamento notate in alcune specie di uccelli. Gli uccelli di Heppner iniziano a volare in circolo senza una meta precisa e formano diversi gruppi, ognuno di loro vola verso una zona in cui fermarsi. Quando il desiderio di sosta `e maggiore del desiderio di stare in stormo, gli uccelli lasciano lo stormo e si dirigono verso un’area in cui riposarsi, trascinandosi dietro anche i propri vicini. Trovare un trespolo `e analogo a trovare una soluzione in un campo di possibili soluzioni. Quindi, considerando il problema di ottimizzazione in questo contesto sociale, si pu`o pensare alle soluzioni candidate come delle particelle che volano in uno spazio di ricerca N-dimensionale, aggiornando la propria posizione e velocit`a, e considerando sia la propria esperienza che quella degli altri individui vicini. Lo scopo sar`a quello di posizionarsi sulla soluzione migliore. La PSO combina una ricerca locale dell’ottimo con una ricerca globale, cercando il giusto equilibrio tra esplorazione (cercare intorno per una buona soluzione) e sfruttamento (trarre vantaggio dai successi degli altri). Infatti, se l’esplorazione `e bassa l’algoritmo rischia di convergere prematuramente ad una soluzione non ottima (cade in un minimo locale), analogamente, un basso sfruttamento potrebbe far divergere l’algoritmo (tutte le particelle restano in uno stato di ricerca) o comunque ostacolare la convergenza (ognuno si ferma sulla prima soluzione che trova).