Optimización multi-enjambre

La optimización multi-enjambre es una variante de la optimización de enjambres de partículas (PSO) basada en la utilización de sub-enjambres en lugar de un único enjambre. La idea consiste en que cada sub-enjambre se concentre en una región específica del espacio de búsqueda mientras un método de diversificación decide dónde y cuándo lanzar los sub-enjambres. El paradigma multi-enjambre es especialmente efectivo en la optimización de problemas multi-modales, aquellos con múltiples óptimos (locales).

En los problemas multi-modales es importante balancear adecuadamente la exploración y explotación durante la búsqueda. Los sistemas multi-enjambre brindan un nuevo enfoque a la hora de lograr dicho balance. En lugar de alcanzar un compromiso que pueda debilitar tanto a los mecanismos de exploración como de explotación durante el proceso de búsqueda, los sistema multi-enjambres separan estos mecanismo en dos fases distintas. En cada una de estas fases la búsqueda se enfoca en efectuar un proceso independiente de exploración o explotación.

La manera en que se coordinan los sub-enjambres depende del método específico de diversificación que implemente el sistema. Por ejemplo, el sistema "Wave of Swarm of Particles" (WOSP)[1] basa su mecanismo de diversificación en la colisión de partículas. Cuándo las partículas se acercan demasiado una fuerza de repulsión las expele formando nuevas ondas/sub-enjambres, evitando así una convergencia completa. El sistema "Dynamic Multi-Swarm-Particle Swarm Optimizer" (DMS-PSO)[2] reagrupa periódicamente las partículas de los sub-enjambres (una vez que estos han convergido) en nuevos sub-enjambres. Los nuevos sub-enjambres se inician con partículas de los viejos enjambres. El sistema "Locust swarm" (enjambre de langostas)[3] se basa en una estrategia de "devorar e irse", luego de que un sub-enjambre ha "devorado" una región relativamente pequeña (hasta el punto de que encontrar una mejor solución sea improbable), se despliegan exploradores para buscar nuevas regiones prometedoras hacia las cuales desplazarse.

Una característica distintiva de los sub-enjambres es que tanto las posiciones como velocidades iniciales no se seleccionan aleatoriamente al igual que en los enjambres normales. En su lugar, estas conservan cierta información respecto a las trayectorias previas de las partículas. En general, el desarrollo de un sistema multi-enjambre conlleva a decisiones de diseño que no estaban presentes durante el desarrollo original de la optimzación de enjambres, tales como el número óptimo de partículas para cada sub-enjambre, el valor óptimo del factor de restricción o los efectos de velocidades y posiciones iniciales no aleatorias. Estas cualidades han sido rigurosamente estudiadas y existen directrices bien establecidas para su configuración, por ejemplo, es conocido que la utilización de posiciones y velocidades no aleatoria mejoran el resultado de los sistemas multi-enjambre, lo cual no ocurre con los enjambres comunes.[4][5] Otras decisiones de diseño, como por ejemplo, qué método de diversificación utilizar o cuál estrategia de búsqueda seguir para seleccionar las posiciones y velocidades iniciales, no tienen aun directrices establecidas y constituyen preguntas abiertas en el campo de los sistemas multi-enjambres.

Algunas de estas decisiones de diseño pueden ser tratadas como sub-componentes independientes, permitiendo la integración de diferentes técnicas de optimización. Por ello, los sistemas multi-enjambres han mostrado ser un marco propicio para el desarrollo de algoritmos híbridos. Por ejemplo, el sistema multi-enjambre UMDA-PSO[6] combina de manera efectiva componentes de optimización de enjambres de partículas, algoritmo de estimación de distribución, y evolución diferencial en un sistema híbrido.

Referencias
  1. T. Hendtlass, “WoSP: A Multi-Optima Particle Swarm Algorithm,” in Proceedings IEEE Congress on Evolutionary Computation, 2005, pp. 727–734.
  2. S. Z. Zhao, J. J. Liang, P. N. Suganthan, and M. F. Tasgetiren, “Dynamic Multi-Swarm Particle Swarm Optimizer with Local Search for Large Scale Global Optimization,” in Proceedings IEEE Congress on Evolutionary Computation, 2008, pp. 3845–3852.
  3. S. Chen, “Locust Swarms – A New Multi-Optima Search Technique”, in Proceedings of the IEEE Congress on Evolutionary Computation, 2009, pp. 1745–1752.
  4. Antonio Bolufé Röhler and Stephen Chen, “An Analysis of Sub-swarms in Multi-swarm Systems”, in Lecture Notes in Artificial Intelligence, Vol. 7106: Proceedings of Joint Australasian Conference in Artificial Intelligence, D. Wang and M. Reynolds Eds. Springer-Verlag 2011, pp. 271–280.
  5. S.Chen and J. Montgomery “Selection Strategies for Initial Positions and Initial Velocities in Multi–optima Particle Swarms”, in Proceedings of the Genetic and Evolutionary Computation Conference, 2011 pp. 53–60.
  6. Antonio Bolufé Röhler and S. Chen, “Multi-swarm hybrid for multi-modal optimization”, in Proceedings of the IEEE Congress on Evolutionary Computation, 2012, pp. 1759-1766.

Véase también
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.