Swarm Particle

Swarm Particle Optimization u optimización por enjambre de partículas OEP es un conjunto de algoritmos de optimización que resuelven problemas de manera natural como los seres vivos. Su origen fue gracias a los investigadores Kennedy y Ebarhart. Al principio la idea era utilizarlo para elaborar modelos de conductas sociales en grupos de animales. Después de comprobar su utilizad, terminó siendo un algoritmo para resolver problemas de optimización. En particular este tipo de algoritmos evocan la manera de resolver problemas de los enjambres de abejas.

OEP es utilizado cuando se tienen pocas o ninguna hipótesis sobre el problema que se quiere analizar, y se cuenta con muchas posibles soluciones. Para imaginar el funcionamiento se puede pensar en una caja que sólo tiene un agujero y se encuentra llena de partículas que quieren salir. Las partículas recorrerán el espacio de manera independiente siguiendo reglas matemáticas y recordando los espacios por los cuales han estado lo cual afectará su movimiento, y cuando una partícula encuentre la salida, esta les avisará a las demás y todas se desplazarán hacia el agüero. Por dicha razón se relaciona tanto a este tipo de algoritmos con enjambres de abejas. Cuando buscan algo, cada abeja hace su recorrido de manera individual, recordando cada cosa que va encontrando. Cuando encuentra lo mejor de lo que busca, le avisa al resto del enjambre.

Si bien se habla de que las OEP pueden ser aplicadas en problemas de optimización de manera general, son utilizados de mayor forma en optimizaciones de donde se cuenta con espacios de búsqueda continuos, un ejemplo sería encontrar la ruta óptima para la distribución de algún producto. Actualmente se están trabajando en adaptaciones para solucionar problemas discretos.

En el siguiente video se puede ver una demostración de cómo 40 mil partículas van recorriendo un espacio y se puede ver como a medida que lo conocen van alterando sus movimientos de tal manera que su espacio de inspección se va haciendo más chico a medida que tienden a la solución correcta.

http://www.youtube.com/watch?v=iM7VIxgLe5s

En el siguiente video se puede ver una aplicación real de OEP, donde se hace la réplica de una imagen.

http://www.youtube.com/watch?v=4bcJREArY_g

 Bibliografía:

Shi, Yuhui. “Particle swarm optimization: developments, applications and resources.” Evolutionary Computation, 2001. Proceedings of the 2001 Congress on. Vol. 1. IEEE, 2001.
Kennedy, J.; Eberhart, R. (1995). “Particle Swarm Optimization”. Proceedings of IEEE International Conference on Neural Networks Vol. IV: 1942–1948.

Advertisements