Una variante della PSO

Sebbene la PSO si presti molto bene alla risoluzione di problemi NP-Hard molto complessi, presenta un limite nella prematura convergenza: ogni qual volta il problema di ottimizzazione risulti eccessivamente complesso o articolato, l’algoritmo potrebbe fallire nella ricerca dell’ottimo globale, facendo in modo che l’intero sciame sia bloccato in quello che in realtà è il l’ottimo locale, senza continuare la ricerca verso aree teoricamente più promettenti. Questo problema di prematura convergenza verso l’ottimo locale è stato risolto da una serie di studiosi39 nel 2014 grazie alla modifica dell’originale versione dell’algoritmo, che viene illustrata all’interno del seguente paragrafo.

38 _{“Particle swarm optimization”, R. Poli, J. Kennedy e T. Blackwell; 2007.}

39 _{“A survey: Particle swarm optimization based algorithms to solve premature convergence problem”; M.}

N. R. Bahareh Nakisa, Mohd Zakree Ahmad Nazri e S. Abdullah; Journal of Computer Science vol. 10, pag. 1758-1765; 2014.

2.5.1 L’approccio del peso di inerzia

Un’alternativa al classico approccio di PSO è stato fornito da R. Eberhart e Y. Shi nel 1998 all’interno di una loro pubblicazione40, con lo scopo di ridurre l’importanza attribuita alla determinazione manuale dei parametri, come per esempio il . Con il

loro lavoro, viene introdotto un nuovo parametro “ ", denominato “peso di inerzia”, che va a modificare la prima equazione esposta in precedenza nel sistema della PSO originaria. Questa modifica consente un maggior controllo delle due principali caratteristiche degli algoritmi di PSO, ovvero sia l’esplorazione e lo sfruttamento, facilitando una convergenza dello sciame più accurata verso le reali soluzioni ottime, senza che l’individuazione di soluzioni locali impedisca il l’evolversi dell’attività di ricerca. L’introduzione di questo parametro va a modificare l’algoritmo nel seguente modo:

Il peso di inerzia va dunque a modificare l’impatto della velocità assunta fino a quella iterazione da parte della i-esima particella, grazie ad un valore che può essere espresso sia in maniera statica e prefissata, sia in maniera dinamica: se il peso di inerzia presenta un valore ≥ 1, la nuova velocità intrinseca della particella i-esima tenderà a crescere maggiormente nel corso del tempo, rendendo così difficoltoso un eventuale cambio di direzione all’interno dell’area di ricerca dell’ottimo e facendo divergere così l’intero sciame. Qualora invece il parametro sia ≤ 1, comporterebbe la possibilità di effettuare anche brevi cambiamenti di direzione, riducendo l’importanza della velocità passata in favore dell’ottimo personale di ogni elemento e globale dell’intero sciame. Infine, se = , l’importanza relativa della velocità assunta dalla i-esima particella nell’iterazione passata si annulla del tutto, facendo in modo che il futuro movimento sia influenzato esclusivamente dal fattore cognitivo e dalla componente sociale, senza alcun tipo di conoscenza preliminare in merito alla precedente velocità.

40 _{“Parameter selection in particle swarm optimization”, in Proc. 7th Int. Conf. Evol. Program. (EP), pag.}

Generalmente, nonostante l’algoritmo performi bene anche con valori fissi del parametro del peso di inerzia, nella maggior parte dei casi si tende ad utilizzare un parametro dinamico, date le capacità gestire i due processi di esplorazione e sfruttamento nello spazio di ricerca.

L’approccio che viene comunemente adottato è quello di attribuire al peso di inerzia ( )un importanza via via decrescente con il passare del numero delle iterazioni, in modo tale da bilanciare l’esplorazione a livello locale e globale, oltre che ottenere una veloce individuazione della convergenza verso l’area migliore nella quale è possibile trovare la soluzione ottima. In questo modo, la prima parte dell’esplorazione viene svolta molto velocemente, per individuare in tempi rapidi l’area più promettente all’interno dello spazio di ricerca; successivamente, con il passare delle iterazioni, il valore del peso di inerzia diminuisce, comportando così una diminuzione nell’importanza della velocità e dunque un rallentamento delle particelle proprio intorno alla zona più interessante. Per determinare il valore assunto da " "al susseguirsi delle iterazioni, è stata proposta41 da M. Corazza, G. Fasano e R. Gusso nel 2013una possibile formulazione, che viene di seguito riportata:

dove:

• " ”e" ” rappresentano rispettivamente i valori massimi e minimi

desiderati per il peso di inerzia;

• “K” indica il numero massimo di iterazioni e viene stabilito a priori dall’operatore;

• “k” si riferisce al corrente numero di iterazione al quale si è giunti.

Il settaggio dei parametri e tendenzialmente parte da un valore di partenza

intorno a 0.9, per poi decrescere gradualmente fino alla conclusione del processo, che

41 _{“Particle Swarm Optimization with non-smooth penalty reformulation, for a complex portfolio}

selection problem”, M. Corazza, G. Fasano, R. Gusso; Applied Mathematics and Computation 224; pag. 611-624; 2013.

solitamente viene fatta coincidere con il valore di 0.4. In questo nuovo tipo di approccio, unitamente al settaggio dei pesi di inerzia, è necessario attribuire dei valori che siano coerenti con essi anche ai coefficienti di accelerazione introdotti in precedenza Ø e Ø . Tuttavia, nonostante questo metodo risulti migliore rispetto alla classica forma di PSO per la risoluzione di problemi di ottimizzazione, un problema potrebbe essere individuato nella impossibilità da parte dell’algoritmo di riprendere velocità spostare l’area di ricerca in un’altra zona potenzialmente proficua, facilitando così una precoce interruzione dell’attività di esplorazione. In letteratura sono stati proposti differenti metodi per il settaggio di tali coefficienti del peso di inerzia, come per esempio l’utilizzo di una logica “fuzzy” finalizzata a migliorare la performance dell’intero algoritmo, oppure l’adozione di componenti casuali per l’assegnazione del valore di " ", in modo tale da impedirne l’andamento decrescente con il susseguirsi delle iterazioni.