Il Particle Swarm Optimization (PSO) `e un metodo computazionale di ottimiz-zazione sviluppato per la prima volta a met`a degli anni ’90. L’idea nacque da un gruppo di scienziati che intuirono la possibilit`a di sviluppare un algoritmo di ottimizzazione basato su leggi naturali quali il movimento di uno stormo di uccelli o di un branco di pesci, in particolare ci si `e concentrati nell’analizzare le regole che permettono ad un grande numero di uccelli di muoversi in sincronia, spesso cambiando improvvisamente direzione, sparpagliandosi e ricongiungendosi. Gli uccelli inoltre tengono conto, nei loro spostamenti, di vari fattori quali predatori, cibo, temperatura, ecc. perci`o il loro comportamento sociale ben si adatta alla ricerca del punto di ottimo con diverse restrizioni da rispettare.
L’algoritmo `e nato come una simulazione semplificata di un modello sociale con agenti dal comportamento simile a quello di uno stormo d’uccelli e si `e poi sviluppato attraverso varie fasi.
§ 5.2.1. Velocit`a corrispondente a quella del vicino e follia
Un iniziale algoritmo si basava su due propriet`a: velocit`a corrispondente a quella del vicino e follia. Una popolazione di uccelli viene creata con posizione random su una griglia toroidale, con una certa velocit`a nelle direzioni X e Y. Ad ogni iterazione del programma viene determinato, per ogni agente, quale altro agente sia il pi`u vicino e a questo viene assegnata la stessa velocit`a X e Y dell’agente sotto osservazione. Essenzialmente questa piccola regola crea un movimento sin-cronizzato.
Cos`ı facendo per`o lo stormo prende una direzione unanime e priva di variazioni. Pertanto `e stata introdotta una variabile chiamata craziness (follia), ad ogni ite-razione viene introdotta una varizione di direzione ad una velocit`a X e Y random. Questo crea una variazione all’interno del sistema sufficiente a dare l’apparenza di un movimento naturale anche se in realt`a `e del tutto artificiale.
§ 5.2.2. Il vettore cornfield
Successivamente `e stata introdotta nella simulazione una forza dinamica che mo-difichi il comportamento dello stormo. Gli uccelli volano attorno ad un posatoio, una posizione della griglia che li attrae fino a farli atterrare in quel punto. In questo modo viene eliminato il bisogno di avere la variabile follia. A questo pun-to sorge un ulteriore problema: in quespun-to caso gli uccelli conoscono la posizione del posatoio mentre nella realt`a si vanno a posizionare su qualsiasi albero o cavo telefonico nelle vicinanze. Ancora pi`u importante gli uccelli vanno a posarsi dove c’`e presenza di cibo, tutti sappiamo che in presenza di cibo gli uccelli arrivano in grande quantit`a e in poco tempo pur non avendo precedenti conoscenze riguardo il luogo in questione. Ci`o fa supporre che qualcosa nello stormo di uccelli per-metta di condividere le singole conoscenze.
5.2 Sviluppo del PSO 57
grano), un vettore bidimensionale di coordinate XY. Ogni agente `e programmato in modo da valutare la sua attuale posizione secondo l’equazione (5.1).
Eval =p(presentx − 100)2+p(presenty − 100)2 (5.1) Ogni agente ricorda il miglior valore trovato e la sua posizione XY in cui si trova questo valore. Il valore viene chiamato personal best e indicato con pbest[] mentre le posizioni sono indicate con pbestx[] e pbesty[] (le parentesi quadre indicano che questi sono degli array con un numero di elementi pari al numero di agenti). Ogni volta che un agente si muove nello spazio le velocit`a X e Y vengono aggiustate in maniera semplice. Se `e a destra del suo pbestx allora la sua velocit`a X (chiamata vx) sar`a aggiustata negativamente con un valore casuale pesato con un parametro del sistema:
vx = vx[] − rand()· p increment
Se invece l’agente `e alla sinistra del pbestx l’incremento viene aggiunto: vx[] = vx[] + rand()· p increment
Similmente viene aggiustata anche la velocit`a nella direzione Y vy[] a seconda della posizione dell’agente rispetto a pbesty.
Ogni agente ricorda anche il global best ovvero il miglior risultato trovato dal-l’intero stormo. Per fare questo `e sufficiente assegnare l’array con il global best ad una variabile chiamata gbest, cos`ı pbestx[gbest] `e la migliore posizione X del-l’intero stormo e pbesty[gbest] quella Y, e questa informazione `e a disposizione di ogni agente dello stormo. Le velocit`a vx[] e vy[] di ogni agente vengono aggiustate come mostrato di seguito (g increment `e un paramero del sistema):
vx[] = vx[] − rand()· g increment se presentx[] > pbestx[gbest] vx[] = vx[] + rand()· g increment se presentx[] < pbest[xgbest] vy[] = vy[] − rand()· g increment se presenty[] > pbesty[gbest] vy[] = vy[] + rand()· g increment se presenty[] < pbesty[gbest]
(5.2)
Cos`ı facendo lo stormo di uccelli si muove finch`e trova il campo di grano simulato. I risultati sono sorprendenti. Con p increment e g increment impostati relativa-mente grandi lo stormo viene risucchiato violenterelativa-mente verso il campo di grano, in poche iterazioni l’intero stormo (usualmente dai 15 ai 30 individui) si ritrova in prossimit`a dell’obiettivo. Con p increment e g increment relativamente pic-coli lo stormo turbina attorno all’obiettivo, avvicinandosi oscillando ritmicamente fino ad “atterrare” su di esso.
§ 5.2.3. Eliminare le variabili dipendenti
Abbiamo capito che questo metodo riesce ad ottimizzare semplici funzioni lineari e bidimensionali, `e altres`ı importante capire quali sono le parti fondamentali al raggiungimento dell’obiettivo (ad esempio abbiamo visto che l’algoritmo lavora meglio ed in maniera pi`u realistica senza la variabile follia perci`o questa `e stata rimossa). Inoltre l’ottimizzazione avviene un po’ pi`u velocemente se si rimuove la velocit`a corrispondente a quella del vicino, ora lo stormo diventa uno sciame (swarm) per`o `e perfettamente in grado di trovare il campo di grano.
Le variabili pbest e gbest e i loro incrementi sono entrambi necessari. Concettual-mente il personal best ricorda la memoria autobiografica in cui ogni individuo ricorda le esperienze personali, gli aggiustamenti di velocit`a associati al pbest vengono chiamati “nostalgia” in quanto tendono a far ritornare l’individuo nel luogo che pi`u lo ha soddisfatto in passato. D’altra parte il global best pu`o essere paragonato ad una regola di gruppo che ogni individuo cerca di rispettare. Nelle simulazioni un alto valore di p increment rispetto a g increment si traduce in un eccessivo errore nello spazio di ricerca, mentre il contrario (g increment rela-tivamente grande) conduce ad una corsa prematura verso i minimi locali. Avere i valori dei due incrementi approssimativamente uguali risulta essere la soluzione pi`u efficiente.
§ 5.2.4. Ricerca multidimensionale
La maggior parte dei problemi da ottimizzare non sono n`e lineari n`e bidimen-sionali, `e quindi un passaggio naturale cambiare presentx e presenty (e quindi anche vx[] e vy[]) da un array monodimensionale ad una matrice D × N , dove D `
e il numero delle dimensioni e N `e il numero degli agenti.
Esperimenti multidimensionali sono stati fatti su problemi riguardanti reti neurali con 13 parametri. L’algoritmo ha funzionato molto bene risolvendo il problema con 31 iterazioni e utilizzando 20 agenti. Problemi pi`u complessi possono portare ad un tempo di elaborazione maggiore ma i risultati sono comunque molto buoni. § 5.2.5. Velocit`a in base alla distanza
Anche se cos`ı il PSO lavora bene c’`e qualcosa di esteticamente spiacevole e difficile da capire. Gli aggiustamenti di velocit`a avvengono in base a delle disuguaglianze (5.2). Alcuni esperimenti hanno dimostrato che ulteriori aggiustamenti possono rendere l’algoritmo pi`u efficiente e pi`u facilmente comprensibile, piuttosto che verificare delle disuguaglianze la velocit`a viene aggiustata facendo una semplice differenza tra posizione attuale e pbest:
vx[][] = vx[][] + rand()· p increment(pbestx[][] − presentx[][]) (5.3) Da notare come i parametri vx e presentx hanno due coppie di parentesi, questo perch`e ora sono delle matrici.