Optimizacija roja čestica
U računarskoj nauci, optimizacija roja čestica (particle swarm optimization, PSO)[1] je računarski metod koji optimizuje problem iterativnim pokušajem da se poboljša rešenje kandidata s obzirom na datu meru kvaliteta. On rešava problem tako što ima populaciju kandidata rešenja, ovde nazvanih česticama, i pomera ove čestice u prostoru za pretragu prema jednostavnoj matematičkoj formuli preko položaja i brzine čestice. Kretanje svake čestice je pod uticajem njene lokalne najbolje poznate pozicije, ali je takođe vođeno ka najpoznatijim pozicijama u prostoru za pretragu, koje se ažuriraju kako bolje pozicije pronalaze druge čestice. Očekuje se da će to pomeriti roj ka najboljim rešenjima.
PSO se prvobitno pripisuje Kenediju, Eberhartu i Šiju[2][3] i inicijalno je bio namenjen simulaciji društvenog ponašanja,[4] kao stilizovani prikaz kretanja organizama u jatu ptica ili jatu riba. Algoritam je pojednostavljen i primećeno je da vrši optimizaciju. Knjiga Kenedija i Eberharta[5] opisuje mnoge filozofske aspekte PSO i inteligencije roja. Poli je napravio opsežnu anketu o PSO aplikacijama.[6][7] Godine 2017, Bonjadi i Mihalevič su objavili sveobuhvatan pregled teorijskih i eksperimentalnih radova o PSO.[1]
PSO je metaheurističan jer daje malo ili nimalo pretpostavki o problemu koji se optimizuje i može pretraživati veoma velike prostore rešenja kandidata. Takođe, PSO ne koristi gradijent problema koji se optimizuje, što znači da PSO ne zahteva da problem optimizacije bude diferencibilan kao što se zahteva klasičnim metodama optimizacije poput gradijentnog spuštanje i kvazi-njutnovske metode. Međutim, metaheuristika kao što je PSO ne garantuje da će se ikada naći optimalno rešenje.
Reference
[уреди | уреди извор]- ^ а б Bonyadi, M. R.; Michalewicz, Z. (2017). „Particle swarm optimization for single objective continuous space problems: a review”. Evolutionary Computation. 25 (1): 1—54. PMID 26953883. S2CID 8783143. doi:10.1162/EVCO_r_00180.
- ^ Kennedy, J.; Eberhart, R. (1995). „Particle Swarm Optimization”. Proceedings of IEEE International Conference on Neural Networks. IV. стр. 1942—1948. doi:10.1109/ICNN.1995.488968.
- ^ Shi, Y.; Eberhart, R.C. (1998). „A modified particle swarm optimizer”. Proceedings of IEEE International Conference on Evolutionary Computation. стр. 69—73. doi:10.1109/ICEC.1998.699146.
- ^ Kennedy, J. (1997). „The particle swarm: social adaptation of knowledge”. Proceedings of IEEE International Conference on Evolutionary Computation. стр. 303—308. doi:10.1109/ICEC.1997.592326.
- ^ Kennedy, J.; Eberhart, R.C. (2001). Swarm Intelligence. Morgan Kaufmann. ISBN 978-1-55860-595-4.
- ^ Poli, R. (2007). „An analysis of publications on particle swarm optimisation applications” (PDF). Technical Report CSM-469. Архивирано из оригинала (PDF) 2011-07-16. г. Приступљено 2010-05-03.
- ^ Poli, R. (2008). „Analysis of the publications on the applications of particle swarm optimisation” (PDF). Journal of Artificial Evolution and Applications. 2008: 1—10. doi:10.1155/2008/685175
.
Literatura
[уреди | уреди извор]- Liu, Yang (2009). „Automatic calibration of a rainfall–runoff model using a fast and elitist multi-objective particle swarm algorithm”. Expert Systems with Applications. 36 (5): 9533—9538. doi:10.1016/j.eswa.2008.10.086.
Spoljašnje veze
[уреди | уреди извор]
- Particle Swarm Central is a repository for information on PSO. Several source codes are freely available.
- A brief video of particle swarms optimizing three benchmark functions.
- Simulation of PSO convergence in a two-dimensional space (Matlab).
- Applications of PSO.
- Links to PSO source code Архивирано на сајту Wayback Machine (15. април 2021)