La PSO `e regolata da diversi parametri. I pesi,c1 e c2 ,e la velocit`a massima,vmax sono delle
costanti, il numero della popolazione, i cui valori una volta settati, restano fissi durante tutta l’evoluzione il peso di inerzia w rappresenta invece una variabile di controllo, che fu introdotta successivamente, al fine di migliorare la performance dell’algoritmo, χ `e legato alla scalatura del problema.
I due pesi c1 e c2 rappresentano in particolare l’importanza che viene attribuita alla migliore
soluzione trovata rispettivamente dall’individuo e dal gruppo, infatti come si pu`o notare dall’equazione 7.3 la costante c1 moltiplica il termine relativo alla posizione migliore della
7 – L’algoritmo PSO
particella pbest mentre la costante c
2 moltiplica il termine relativo alla posizione migliore
dell’intero gruppo gbest. Usare piccoli pesi , vuol dire aggiornare di una piccola quantit`a il
vettore velocit`a ad ogni iterazione; sicuramente dopo molte iterazioni questi piccoli incre- menti si sommano e la traiettoria della particella, eventualmente, si inverte verso le posizioni migliori. Al contrario, se i pesi c1e c2sono alti, le traiettorie tendono ad oscillare bruscamen-
te poich´e il vettore velocit`a `e sopraffatto dai grandi valori che gli vengono aggiunti.Kennedy, nel descrivere gli effetti dei pesi sulle traiettorie delle particelle afferma che ogni volta che la somma di due coefficienti `e maggiore di 4, sia il vettore posizione che le velocit`a tendono all’infinito. Quindi per la maggior parte degli algoritmi basati sulla PSO ci consiglia di non superare per ogni peso il valore di 2.0; inoltre se c1> c2la particella considera maggiormente
le informazioni ottenute in base alla propria esperienza, mentre se c2 > c1 l’informazione
relativa al miglior risultato globale ottenuto `e predominante.
La velocit`a massima Nel processo di ottimizzazione la velocit`a raggiunta da ogni particella ad ogni iterazione, `e limitata dal valore massimo vmaxfissato dall’utente. Ci`o significa che v deve
assumere valori che cadono nell’intervallo [−vmax, vmax]; Quando si raggiunge (o si supera)
il valore limite della velocit`a, ovvero quando questo vincolo non viene rispettato, si possono eseguire due azioni :
1. si impone che la velocit`a sia la massima o la minima possibile, seguendo la regola:
se vk> vmax vk= vmax
se vk< −vmax vk= −vmax
il valore assegnato a vmaxpu`o essere arbitrario, tuttavia in base al dominio della funzione
di fitness `e meglio scegliere un valore abbastanza grande in modo non restare bloccati in minimi locali. Ad esempio, se il vettore dei parametri pu`o variare tra [−100 100], vmax
dovrebbe essere proporzionale a ±100
2. si rigenera una velocit`a casuale utilizzando la formula 7.2, creando cos`ı una sorta di “so- stituzione parziale” della particella uscita dai confini; la sua posizione rimane invariata qualora sia compatibile con i confini assegnati.
Durante lo svolgimento delle prove si `e notato una maggiore efficenza della rigenerazione della velocit`a poich´e le particelle sono pi`u propense ad uscire dai limiti nelle prime fasi
7 – L’algoritmo PSO
dell’algoritmo e un imposizione della velocit`a come velocit`a massima crea una situazione in cui le particelle si ritrovano ad avere nella maggior parte dei casi la velocit`a massima o la velocit`a minima.
Un ragionamento identico si compie a seguito del calcolo della nuova posizione xnew; ricor-
diamo infatti che le particelle si devono trovare all’interno del dominio definito dai limiti inferiore lb e superiore ub, qualora la posizione aggiornata dovesse uscire dal dominio essa viene rigenerata seguendo la formula 7.1:
se xnew > ub xnew < lb
⇒ xnew= lb + random · (ub − lb)
Il peso di inerzia w Kennedy ed Eberhart , al fine di migliorare le prestazioni dell’algoritmo in- trodussero il nuovo parametro di controllo, il peso di inerzia w,che, moltiplicando la velocit`a della generazione corrente, influenza l’equilibrio tra esplorazione locale e globale delle parti- celle, controllando quanto la storia delle velocit`a precedenti influenzer`a il valore della velocit`a della generazione successiva. Pesi di inerzia grandi favoriscono una ricerca globale dell’otti- mo (si esplorano alle nove dello spazio di ricerca ) mentre pesi di inerzia piccoli tendono a facilitare una ricerca locale dell’ottimo, raffinando l’area di ricerca corrente. Generalmente w decresce linearmente con il tempo in modo che per le generazioni iniziali la particella abbia la possibilit`a di esplorare aree pi`u ampie ed invece vada ad esaminare zone pi`u ristrette ma mano che l’evoluzione prosegue.
La popolazione Il numero di popolazione `e il parametro che indica quanti individui vengono generati nell’inizializzazione dell’algoritmo; ogni individuo della popolazione avr`a una sua posizione e una sua velocit`a ad ogni passo di iterazione k oltre ad una memoria della miglior posizione trovata nelle precedenti iterazioni. Inoltre ad ogni passo di iterazione la funzione di fitness viene valutata per ogni individuo. Un numero alto di popolazione comporta quindi un numero maggiore di calcoli da dover eseguire per ogni iterazione, ma allo stesso tempo aumenta la probabilit`a di trovare delle buone posizioni verso le quali fare convergere l’algorit- mo grazie alle memoria di gruppo; un numero alto di individui comporta quindi in generale una diminuzione dei passi di iterazione necessari al raggiungimento della convergenza, `e ne- cessario quindi trovare un numero di popolazione che fornisca un buon equilibrio tra le due situazioni per evitare che i tempi di calcolo diventino inutilmente troppo lunghi.
Il parametro di costrizione χ Anche questo `e un parametro che nelle prime versioni dell’algo- ritmo non era previsto, essi sono visibili come casi in cui χ = 1 Questo parametro `e collegato
7 – L’algoritmo PSO
alla scalatura del problema ed `e dipendente dai valori scelti per gli altri parametri w , c1 e
c2. I valori utilizzati pi`u comunemente variano da 0.6 a 0.9.
Con la posizione migliore dell’individuo pbest
i si indica il vettore delle variabili per cui in tutti
i passi eseguiti dall’ algoritmo la funzione di fitness valutata per la particella i ha dato il risultato migliore (ovvero il valore minimo). Questo vine e in pratica ottenuto facendo coincidere pbesti con la posizione iniziale x0i nel ciclo di inizializzazione; in seguito, se nel generico ciclo k il valore della
funzione calcolata risulta minore di quella calcolata in precedenza, la pbest
i viene aggiornata con la
nuova posizione xik, altrimenti non viene eseguita alcuna azione.
se f (xik) < f (pbesti(k−1)) ⇒ p best i = xik
In modo molto simile si procede per la variabile gbestovvero la migliore posizione raggiunta dal
gruppo; essa viene inizializzata trovando per quale particella i la funzione `e minima
min
i f (p best i ) ⇒ i
a questo punto poniamo semplicemente
gbest= pbesti
nel seguito, per ogni iterazione k si ricerca il minimo tra il valore della funzione di fitness calcolata nelle nuove posizioni e se questo `e minore del valore relativo alla posizione gbest il valore di que-
st’ultima viene sostituito con la posizione della particella che ha fornito il minimo della funzione di fitness.
Il controllo sul proseguimento o l’arresto dell’algoritmo viene eseguito su 3 condizioni relative alla convergenza e al massimo numero di iterazioni dell’algoritmo; si impone che l’algoritmo si fermi al verificarsi di una sola delle seguenti condizioni
• i valori della funzione di fitness delle ultime 2 iterazioni in cui c’`e stato un miglioramento della ricerca (ovvero sono stati trovati valori minori dei precedenti) differiscono per meno di un certo valore di tolleranza (impostato come 10−3)
• il numero di iterazioni che hanno avuto successo arriva a 100
• il numero di iterazioni nelle quali non si `e avuto successo `e pari a 400
solo la prima di queste 3 condizioni garantisce che l’algoritmo abbia raggiunto una convergenza, le altre 2 servono a fermare l’algoritmo in caso di fallimento evitando tempi di calcolo troppo lunghi.
7 – L’algoritmo PSO
Occorre notare in ogni caso come la condizione di convergenza assicura la ricerca di un minimo, che per`o non `e necessariamente il minimo globale della soluzione L’ultima condizione garantisce invece che siano compiute almeno 400 · npop valutazioni della funzione prima di decidere di abbandonare
la ricerca.