Particle Swarm Optimization

In informatica, la particle swarm optimization (PSO, traducibile come "ottimizzazione con sciami di particelle") è un metodo computazionale iterativo per ottimizzare problemi. L'algoritmo, ad ogni iterazione, ricerca un nuovo "candidato all'ottimo" nello spazio di ricerca, sulla base di una specifica misura di qualità (detta fitness). Questi metodi sono noti come meta-euristiche, poiché non fanno alcuna assunzione sul problema in ottimizzazione e possono esplorare larghissimi spazi di soluzioni. Ad ogni modo, per come è strutturato l'algoritmo di base della PSO, non c'è nessuna garanzia che la soluzione ottima sarà mai trovata.

La particle swarm optimization non fa uso di un gradiente nel corso dell'ottimizzazione, dunque non è richiesta la differenziabilità del problema da analizzare, cosa che invece avviene nei metodi di ottimizzazione tradizionali come la #REDIRECT discesa del gradiente. La PSO può dunque essere utilizzata con successo in problemi di ottimizzazione irregolari, rumorosi, variabili nel tempo, eccetera.

La PSO ottimizza un problema utilizzando una popolazioni di soluzioni candidate (dette "particelle") che si spostano nello spazio di ricerca sulla base di semplici formule, che tengono in considerazione la loro velocità di spostamento corrente, le loro conoscenze dello spazio di fitness (ovvero la migliore soluzione che han esplorato finora) e la conoscenza condivisa (cioé la miglior soluzione generale identificata). L'algoritmo consente di pesare queste tre componenti (inerzia, cognitiva e sociale) e utilizza dei piccoli jittering stocastici per minimizzare la possibilità di intrappolamento in minimi locali.

La PSO è generalmente attribuita a Kennedy, Eberhart and Shi, che la introdussero nello studio dei comportamenti sociali simulati. L'algoritmo fu semplificato quando si comprese che poteva effettuare ottimizzazione.