Le modifiche alla PSO

4.4.2.1 Peso d’inerzia

Una prima modifica all’algoritmo generale della PSO fu proposta da Shi e Eberhart nel 1998 e va sotto il nome di Inertia Weight. L’equazione che definisce il valore della velocità futura di ciascuna particella diventa così la seguente:

115

{𝑉𝑖

𝑘+1 _{= 𝜔𝑉}

𝑖𝑘+ 𝑈(0, 𝜙1) ⊗ (𝑃𝑖− 𝑋𝑖𝑘) + 𝑈(0, 𝜙2) ⊗ (𝐺 − 𝑋𝑖𝑘)

𝑋_𝑖𝑘+1 = 𝑋_𝑖𝑘+ 𝑉_𝑖𝑘+1 ,

dove 𝜔 è il peso d’inerzia.

Con questa modifica si è cercato di migliorare la potenzialità risolutiva

dell’algoritmo; ponendo un freno inerziale sulla velocità iniziale di ogni singola particella, infatti, si dona maggiore stabilità al modello che altrimenti

raggiungerebbe facilmente una condizione di seria instabilità.

Un’altra funzione molto importante del coefficiente inerziale è quella di bilanciare i due fondamentali comportamenti delle particelle, ossia lo

sfruttamento e l’esplorazione. Lo sfruttamento è determinato dagli ultimi due addendi dell’equazione, mentre il comportamento esplorativo è specificato

dalla componente 𝜔𝑉𝑖𝑘. Questa componente inerziale ha estrema rilevanza nel

modello, in quanto, all’aumentare del valore attribuito a 𝜔, aumenta l’influenza

della velocità corrente su quella futura. Al contrario, un peso d’inerzia basso rende la velocità futura più dipendente dalla migliore posizione passata della singola particella e dell’intero vicinato.

Un criterio che permette di sfruttare il peso d’inerzia in modo razionale consiste nell’attribuirgli un valore decrescente all’aumentare del numero di iterazioni.

Nella fase iniziale del processo di ricerca, infatti, risulta utile una maggiore esplorazione dello spazio 𝑛-dimensionale e quindi un valore elevato di 𝜔.

Successivamente, diminuendo il valore del peso d’inerzia, si predilige l’azione di sfruttamento consentendo all’algoritmo di approfondire la ricerca della soluzione ottima in una determinata regione dello spazio considerata

“promettente”. Si riporta di seguito una delle possibili formulazioni per determinare il valore del coefficiente inerziale all’aumentare delle iterazioni

116 𝜔𝑘 _{= 𝜔} 𝑚𝑎𝑥− 𝜔𝑚𝑎𝑥− 𝜔𝑚𝑖𝑛 𝐾 𝑘, dove:

- 𝜔𝑚𝑎𝑥 è un prefissato valore massimo per il peso d’inerzia; - 𝜔𝑚𝑖𝑛 è un prefissato valore minimo per il peso d’inerzia; - 𝐾 è il numero massimo di iterazioni consentite;

- 𝑘 rappresenta il numero dell’iterazione attuale.

La prassi è quella di attribuire a 𝜔𝑚𝑎𝑥 e 𝜔𝑚𝑖𝑛 rispettivamente i valori 0.9 e 0.4.

Inoltre, per agevolare la convergenza verso l’ottimo del problema, deve essere rispettata la seguente relazione tra il peso d’inerzia e i due coefficienti di

accelerazione 𝜙1 e 𝜙2:

𝜙₁+ 𝜙₂

2 − 1 < 𝜔.

Il corretto settaggio del peso d’inerzia e dei coefficienti di accelerazione rende quindi la PSO più stabile rispetto al modello originale, tanto che la convergenza

all’ottimo del problema è assicurata anche nel caso in cui venga assegnato un valore alto al parametro 𝑉𝑚𝑎𝑥 oppure questo non venga neanche settato.

4.4.2.2 Constriction coefficients

Un’altra variante della PSO molto utilizzata sfrutta un metodo di limitazione

dei coefficienti introdotto da Clerc e Kennedy nel 2002. In questo modo si riesce a prevenire l’instabilità del modello a causa di un’eccessiva velocità e viene

garantita la convergenza delle particelle verso il punto di ottimo, risultando così superfluo il settaggio del parametro 𝑉𝑚𝑎𝑥. Il calcolo della velocità futura diventa

117 {𝑉𝑖 𝑘+1 _{= 𝜒 (𝑉} 𝑖𝑘+ 𝑈(0, 𝜙1) ⊗ (𝑃𝑖 − 𝑋𝑖𝑘) + 𝑈(0, 𝜙2) ⊗ (𝐺 − 𝑋𝑖𝑘)) 𝑋_𝑖𝑘+1 = 𝑋_𝑖𝑘+ 𝑉_𝑖𝑘+1 , dove: - 𝜒 = 2 𝜙−2+√𝜙2_−4𝜙; - 𝜙 = 𝜙1+ 𝜙2, con 𝜙 > 4.

Clerc e Kennedy nella prassi hanno posto 𝜙 pari a 4.1, con 𝜙1 = 𝜙2 = 2.05; da

ciò ne consegue un valore del moltiplicatore 𝜒 pari approssimativamente a 0.7298. A differenza di quanto si è visto in precedenza con riferimento al peso d’inerzia, il coefficiente di costrizione 𝜒 moltiplica tutte le componenti dell’equazione relativa alla velocità futura. Di conseguenza, mentre la velocità

corrente è moltiplicata per 0.7298, gli ultimi due addendi, che esprimono lo sfruttamento dello spazio di ricerca, vengono moltiplicati per un valore casuale

appartenente all’intervallo di valori equiprobabili [0, 1.49618]10_{. Si noti poi che} le due varianti della PSO viste finora possano coincidere se si pone 𝜔 = 𝜒 e 𝜙𝑖 = 𝜒𝜙𝑖; in questo modo nella PSO con il peso d’inerzia il valore del

coefficiente inerziale diventa pari a 0.7298 e i due coefficienti di accelerazione diventano uguali e pari a 1.49618.

4.4.2.3 Fully Informed Particle Swarms (FIPS)

Kennedy e Mendes nel 2002 hanno proposto un’ulteriore versione della PSO, modificando il modo in cui avviene la trasmissione delle informazioni tra le

particelle. Il metodo FIPS ha come obiettivo quello di sfruttare l’informazione inutilizzata che si trova nel vicinato di ciascuna particella, intendendo con il termine “vicinato” un determinato intorno di ogni particella. Mentre

10 _{Dato che 𝜙1= 𝜙}

2= 2.05, allora nel secondo e terzo addendo si ha 𝑈(0, 2.05) e

quindi, applicando il moltiplicatore, il vettore di numeri casuali diventa 𝑈(𝜒 × 0, 𝜒 × 2.05) ≃ 𝑈(0, 1.49618).

118

nell’algoritmo originale ogni particella è influenzata solamente dalla propria migliore posizione e dalla migliore posizione del vicinato, in questa versione le

particelle dipendono dalle migliori posizioni di tutti i loro vicini. L’equazione della PSO è stata quindi modificata ulteriormente nel seguente modo:

{ 𝑉_𝑖𝑘+1= 𝜒 (𝑉_𝑖𝑘+ 1 𝐾𝑖 ∑ 𝑈(0, 𝜙) ⊗ (𝑃_𝑛𝑏𝑟 𝑛𝑖 − 𝑋𝑖 𝑘₎ 𝐾𝑖 𝑛=1 ) 𝑋_𝑖𝑘+1 = 𝑋_𝑖𝑘+ 𝑉_𝑖𝑘+1 , dove:

- 𝜒 è sempre il coefficiente di costrizione; - 𝜙 è il coefficiente di accelerazione;

- 𝐾𝑖 è il numero di vicini della particella 𝑖-esima;

- 𝑛𝑏𝑟𝑛𝑖 rappresenta l’𝑛-esimo vicino della particella 𝑖-esima;

- 𝑃_{𝑛𝑏𝑟𝑛}𝑖, per ogni 𝑛, rappresenta la migliore posizione raggiunta da ciascuna particella appartenente al vicinato della particella 𝑖-esima.

Come si può notare, in questa variante della PSO la velocità della particella 𝑖-esima viene aggiornata facendo la media pesata tra le migliori posizioni raggiunte da tutte le particelle appartenenti al vicinato di 𝑖. Quindi, mentre nel modello originale l’informazione utilizzata ai fini dello spostamento delle

particelle deriva dalla migliore posizione della particella stessa e dalla migliore posizione del vicinato, nella versione FIPS l’informazione risulta essere più

completa, in quanto viene fornita da ciascuno dei 𝐾𝑖 vicini della particella

𝑖-esima.

Analizzando questo modello si può osservare che esso coincide con la versione

tradizionale della PSO se 𝐾𝑖 viene posto pari a 2. Dai risultati di Kennedy e

119

possibile determinare delle soluzioni migliori e in un numero inferiore di iterazioni rispetto all’algoritmo originale.