Particle Swarm Optimization: differenze tra le versioni

Versione delle 16:55, 9 mar 2011

Versione attuale delle 15:48, 23 giu 2022

(29 versioni intermedie di 16 utenti non mostrate)

Riga 1:

{{F|programmazione|luglio 2011}}

In informatica, la particle swarm optimization (PSO, traducibile come "ottimizzazione con sciami di particelle") è un metodo computazionale iterativo per l'ottimizzazione di problemi. Ad ogni iterazione, l'algoritmo identifica un nuovo "candidato all'ottimo" nello spazio di ricerca, sulla base di una specifica misura di qualità (fitness). La PSO rientra nell'egida delle meta-euristiche, poiché non fa alcuna assunzione sul problema e consente l'esplorazione di larghissimi spazi di soluzioni. Per come è strutturato l'algoritmo, tuttavia, non c'è alcuna garanzia che la soluzione ottima verrà mai trovata.

[[File:PSO Meta-Fitness Landscape (12 benchmark problems).JPG|thumb|Esempio di funzionamento del PSO]]

In [[informatica]], l''''ottimizzazione con sciami di particelle''', nota anche come '''particle swarm optimization''' ('''PSO'''), è un [[algoritmo]] di ottimizzazione e appartiene ad una particolare classe di algoritmi utilizzati in diversi campi, tra cui l'[[intelligenza artificiale]]. È un metodo [[euristico]] di ricerca ed ottimizzazione, ispirato al movimento degli [[Formazione a sciame|sciami]].

In informatica, la particle swarm optimization (PSO, traducibile come "ottimizzazione con sciami di particelle") è un metodo computazionale iterativo per l'ottimizzazione di problemi. Ad ogni iterazione, l'algoritmo identifica un nuovo "candidato all'ottimo" nello spazio di ricerca, sulla base di una specifica [[misura di qualità]] (fitness). La PSO rientra nell'egida delle meta-euristiche, poiché non fa alcuna assunzione sul problema e consente l'esplorazione di larghissimi spazi di soluzioni. Per come è strutturato l'algoritmo, tuttavia, non c'è alcuna garanzia che la soluzione ottima verrà 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 [[discesa del gradiente]]. Per questa ragione, può essere utilizzata con successo in problemi di ottimizzazione irregolari, rumorosi, variabili nel tempo, eccetera.

La particle swarm optimizationL'algoritmo 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 [[discesa del gradiente]]. Per questa ragione, può essere utilizzata con successo in problemi di ottimizzazione irregolari, rumorosi, variabili nel tempo, eccetera.

La PSO ottimizza un problema utilizzando una popolazione 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 casuali per minimizzare la possibilità di intrappolamento in minimi locali.

La PSO ottimizza un problema utilizzando una popolazione di soluzioni candidate (dette "particelle", le ''particle'') 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 hanhanno esplorato finora) e la conoscenza condivisa (cioécioè la miglior soluzione generale identificata). L'algoritmo consente di pesare queste tre componenti (inerzia, cognitiva e sociale) e utilizza dei piccoli jittering casuali 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.

La PSO è generalmente attribuita a Kennedy, Eberhart and Shi,<ref>Kennedy, J.; Eberhart, R. (1995). "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942–1948.</ref> che la introdussero nello studio dei comportamenti sociali simulati, studiando il movimento degli stormi di uccelli o dei banchi di pesci. L'algoritmo fu semplificato quando si comprese che poteva effettuare ottimizzazione.

Anche l'algoritmo del PSO può essere implementato per risolvere dei problemi di ottimizzazione multiobiettivo, dove il [[Ottimo paretiano|fronte di Pareto]] aiuta a scegliere le soluzioni ottimali del problema.<ref name=coellocoello02MOPSO>Coello Coello, Salazar Lechuga, "MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization", Congress on Evolutionary Computation (CEC'2002), pp. 1051--1056</ref><ref name=parsopoulos02particle>Parsopoulos K., Vrahatis M., "Particle swarm optimization method in multiobjective problems", Proceedings of the ACM Symposium on Applied Computing (SAC), 2002, pp. 603–607</ref>

==Note==

<references/>

==Voci correlate==

* [[Algoritmo genetico]]

== Altri progetti ==

{{interprogetto}}

{{Genetica}}

{{Apprendimento automatico}}

{{Portale|ingegneria|statistica|informatica|Biologia|matematica}}

[[Categoria:Intelligenza artificiale]]

[[Categoria:Apprendimento automatico]]

[[Categoria:Algoritmi di ottimizzazione]]

[[Categoria:Matematica per la genetica]]