Optimización por enjambre de partículas
Investigación de Operaciones - Ingeniería Informática
Facultad de Ingeniería - Universidad Nacional de Itapúa
2023
Autores:
Camila Roa Silvero
Encarnación, Paraguay
camila.roa@fiuni.edu.py
Encarnación, Paraguay
camila.roa@fiuni.edu.py
Lorena Soledad Osuch Zubko
Encarnación, Paraguay
lorena.osuch2019@fiuni.efu.py
Resumen
El Algoritmo de Optimización por Enjambre de Partículas (PSO) es una metaheurística inspirada en el comportamiento social observado en la naturaleza, como el enjambre de abejas. Este enfoque colaborativo utiliza un enjambre de partículas que ajustan sus posiciones y velocidades en función de experiencias individuales y colectivas para encontrar soluciones óptimas en el espacio de búsqueda. A pesar de su rápida convergencia y capacidad para abordar una amplia gama de problemas, el PSO enfrenta el desafío de gestionar velocidades excesivas de las partículas. La versatilidad y adaptabilidad de este algoritmo lo han posicionado como una herramienta valiosa en aplicaciones prácticas, desde la optimización logística hasta la clasificación de arritmias cardíacas en el ámbito de la salud.
1. Introducción
Los métodos metaheurísticos pueden ser definidos como procesos iterativos que emplean una combinación inteligente de diversos conceptos para explorar y explotar el espacio de búsqueda, ofreciendo estrategias efectivas con el fin de hallar soluciones aproximadas a problemas de optimización [1]. Cuando hablamos de optimización significa escoger el mejor elemento de un conjunto de elementos posibles.
Los algoritmos de optimización metaheurísticos son enfoques que se inspiran en procesos naturales o conceptos abstractos para resolver problemas de optimización. A diferencia de los métodos específicos que se diseñan para un problema en particular, los metaheurísticos son herramientas generales que se pueden aplicar a una amplia variedad de problemas [2]. Estos métodos no aseguran encontrar la solución óptima absoluta, pero están diseñados para obtener resultados aceptables o de buena calidad en un tiempo razonable. Además, no sabemos a ciencia cierta cómo irá avanzando nuestro algoritmo, aunque sí debemos estar seguros de que nos estamos acercando al óptimo [3].
2. Características
La metaheurística de optimización llamada Particle Swarm Optimization (PSO), desarrollada por Kennedy y Eberhart en 1995 como una herramienta para la optimización de funciones no lineales. Se inspira en la observación del comportamiento social presente en grupos de seres vivos, como bandadas de pájaros, enjambres de insectos y cardúmenes de peces. Este comportamiento se basa en la transmisión de información entre individuos del grupo, generando un proceso sinérgico que les permite satisfacer de manera óptima necesidades inmediatas, como encontrar alimentos o refugio [1].
Es un método orientado a encontrar mínimos o máximos globales.
PSO es un algoritmo iterativo que se basa en una población de individuos llamada "enjambre". Cada individuo, conocido como "partícula", se mueve a través del espacio de decisiones en busca de soluciones óptimas [1]. Cuando se habla de Individuos se refiere a las entidades que forman parte de un grupo o población en el algoritmo de optimización PSO. La principal característica de estos algoritmos es la comunicación que existe entre los miembros del enjambre, con el objetivo de resolver un problema en común, en este caso un problema de optimización [2].
3. Funcionamiento
Cada partícula del enjambre está definida por 4 elementos: una posición que representa una determinada combinación de valores de las variables, el valor de la función objetivo en la posición donde se encuentra la partícula, una velocidad que indica cómo y hacia dónde se desplaza la partícula, y un registro de la mejor posición en la que ha estado la partícula hasta el momento.
Según los principios teóricos de este método, el desplazamiento de cada una de estas partículas hacia un objetivo común en un espacio de búsqueda se ve influenciado por dos factores fundamentales: la "memoria autobiográfica" de la partícula, que registra su propia experiencia pasada, y la "influencia social" del colectivo, que se basa en la interacción con otras partículas en el enjambre [6]. En este enfoque, no se crean ni eliminan individuos en cada generación, en su lugar, se trabaja con una población constante cuyas posiciones se ajustan en cada iteración. La posición y velocidad futura de cada partícula se determina en función de su propio comportamiento y del comportamiento colectivo del enjambre en la iteración previa. Para llevar a cabo este cálculo, cada partícula dispone de una memoria que registra tanto su mejor desempeño individual hasta el momento (mejor posición local) como la mejor solución encontrada por todo el enjambre (mejor posición global). Por lo tanto, las partículas ajustan su velocidad mediante la influencia de estos dos aspectos. De esta manera, las partículas se dirigen hacia soluciones más óptimas en su búsqueda por alcanzar el óptimo global [7].
En un algoritmo PSO, se comienza con un grupo de partículas distribuidas al azar en el espacio de búsqueda, donde cada partícula representa una posible solución.
Cada partícula se evalúa mediante la función objetivo, y la mejor solución global y la posición inicial de cada partícula se registran. La velocidad de cada partícula se ajusta según su velocidad actual, su mejor posición local (memoria cognitiva) y la mejor posición global (memoria social), utilizando coeficientes estocásticos para evitar óptimos locales. Se recalculan los valores de la función objetivo según las nuevas posiciones, y este proceso se repite hasta que se cumpla un criterio de finalización o se alcance el número máximo de iteraciones. La solución óptima se encuentra en la mejor posición global al final de las iteraciones [7].
En cada iteración, la conducta de una partícula se basa en un equilibrio entre tres posibles escenarios: seguir su propio camino, regresar a su mejor posición previa o dirigirse hacia la mejor posición entre sus vecinos, si es más beneficiosa, o bien, hacia el mejor vecino disponible [8].
Cada partícula (individuo) tiene una posición, p (que en 2 dimensiones vendrá determinado por un vector de la forma (px,py)), en el espacio de búsqueda y una velocidad, v (que en 2 dimensiones vendrá determinado por un vector de la forma (vx,vy)), que determina su movimiento a través del espacio. Además, como partículas de un mundo real físico, tienen una cantidad de inercia, w, que los mantiene en la misma dirección en la que se movían, así como una aceleración (cambio de velocidad), que depende principalmente de dos características:
Cada partícula es atraída hacia la mejor localización que ella, personalmente, ha encontrado en su historia (pibest).
Cada partícula es atraída hacia la mejor localización que ha sido encontrada por el conjunto de partículas en el espacio de búsqueda (pgbest).
La fuerza con que las partículas son empujadas en cada una de estas direcciones depende de dos parámetros que pueden ajustarse (c1 y c2) de forma que, a medida que las partículas se alejan de estas localizaciones mejores, la fuerza de atracción es mayor. También se suele incluir un factor aleatorio que influye en cómo las partículas son empujadas hacia estas dos localizaciones (r1 y r2) [3] .
Formalmente, para la partícula i-ésima lo podemos escribir como una dependencia temporal de la siguiente forma:
Figura 1. Movimiento de una partícula en PSO
Ecuación de la futura velocidad de la partícula
Ecuación de la nueva posición de la partícula
La relación entre las componentes cognitivas y sociales regula la exploración del algoritmo. Un valor alto de c1 en comparación con c2 otorga mayor independencia a las partículas para explorar, aunque puede ralentizar la convergencia. Por otro lado, un valor alto de c2 en comparación con c1 obliga a las partículas a moverse hacia la mejor solución actual, reduciendo la exploración pero acelerando la convergencia [9].
4. Algoritmo PSO
5. Ventajas y Desventajas
El PSO puede abordar problemas similares a los Algoritmos Genéticos (GAs), pero con una diferencia fundamental. En el PSO, la interacción dentro del grupo tiende a mejorar el progreso en lugar de limitarlo. Además, el PSO incorpora memoria; las partículas que se alejan de la solución óptima son redirigidas hacia ella, y todas las partículas retienen el conocimiento de soluciones efectivas encontradas [8]. Además, la ventaja principal del algoritmo de PSO es su rápida convergencia en comparación con otros algoritmos de optimización global, como los Algoritmos Genéticos (GA), la colonia de hormigas, el enfriamiento simulado y otros métodos similares [10].
Un desafío principal en PSO es que las partículas pueden alcanzar velocidades excesivas, lo que puede llevarlas a salir de los límites del espacio de búsqueda o dificultar su convergencia hacia la región óptima.
5. Complejidad y costo computacional
Dada la simplicidad del algoritmo PSO, resulta relativamente sencillo analizar
el costo computacional del mismo. Excluyendo la inicialización del enjambre con
sus N partículas, el proceso iterativo consiste en un ciclo repetitivo de n iteraciones, donde en cada iteración se realizan N evaluaciones de la función objetivo, se actualizan la velocidad y posición, se comparan óptimos locales y globales y se realizan cálculos de error y de dispersión. Esto llevaría a concluir que el algoritmo es O(n2), sin embargo, para un número de partículas N fijo, la complejidad resulta ser O(n) donde n es el número de iteraciones a realizar [4].
6. Problemas clásicos que resuelve
El algoritmo de Optimización por Enjambre de Partículas (PSO) resuelve problemas clásicos como el Problema del Vendedor Viajero (TSP), el Problema del Ruteo de Vehículos y problemas de programación (scheduling) mediante la exploración cooperativa y la adaptación de soluciones en un enjambre. PSO utiliza la información de las mejores soluciones locales y globales para guiar las partículas hacia soluciones óptimas, optimizando rutas en TSP, rutas de vehículos y programación de tareas, lo que lo convierte en una herramienta versátil para una amplia gama de aplicaciones de optimización.
Un ejemplo clásico para explicar este algoritmo son las abejas que buscan la región con más flores, volando y compartiendo información sobre las áreas más ricas en flores. Cuando encuentran una región con más flores de lo conocido, el enjambre ajusta su búsqueda en esa dirección, repitiendo el proceso si encuentran una región aún más densa en flores. Este enfoque colaborativo permite a las abejas encontrar de manera eficiente las zonas óptimas en la búsqueda de alimento [11].
7. Estado del arte
El algoritmo de enjambre de partículas fue aplicado por primera vez en optimización de diseño estructural en 2003 por Schutte y Groenwold (Schutte, 2003). En la actualidad, se ha demostrado que es adecuado para resolver una amplia gama de problemas de optimización en diversas áreas.
En el ámbito de la logística, PSO se utiliza para abordar problemas de abastecimiento y transporte en organizaciones, optimizando la gestión de recursos y rutas [12], [13]. La optimización de rutas se basa en planificar y determinar las rutas más eficientes.
En problemas matemáticos, PSO se ha beneficiado de la formulación de problemas de optimización convexa, lo que garantiza la búsqueda de mínimos globales. Esto se aplica en una amplia gama de aplicaciones del mundo real, como la programación polinómica restringida (GPP) [11].
En el ámbito de la salud, se ha utilizado PSO en combinación con redes neuronales convolucionales para la clasificación de arritmias cardíacas en electrocardiogramas, lo que permite un diagnóstico más preciso y eficiente de problemas de salud cardíaca [15].
En resumen, PSO ha evolucionado desde su uso inicial en comportamientos sociales hacia una herramienta versátil para la resolución de problemas logísticos, matemáticos, de recomendación y de salud. Su capacidad de optimización lo convierte en una técnica valiosa en una amplia variedad de aplicaciones.
8. Benchmarks comunes en PSO: Funciones Objetivo
Función de Rosenbrock: Es una función continua no convexa, utilizada frecuentemente para probar algoritmos de optimización. Tiene un mínimo global en un valle estrecho, lo que la hace desafiante para los algoritmos.
La función de Rosenbrock es una función de prueba estándar de optimización. Tiene un valor mínimo único de 0 alcanzado en el punto [1,1].
La función de Rosenbrock es una función de prueba estándar de optimización. Tiene un valor mínimo único de 0 alcanzado en el punto [1,1].
Función de Sphere: Es una función simple, convexa y unimodal, con un mínimo global en el origen (0,0). Tiene un mínimo global bien definido en el punto cero, puede ayudar a verificar la capacidad del PSO para encontrar este mínimo global.
Se utiliza la Función de Sphere como un caso simple y la Función de Rosenbrock como un caso de complejidad media, en la \textit{tabla 1} se puede observar un cuadro comparativo de estas dos funciones aplicadas a diferentes números de partículas.
Tabla 1: Tabla de comparaciones.
9. Posibles mejoras
Una de estas variantes, presente en algunos algoritmos dentro del enfoque de PSO, se centra en introducir una fuerza repulsiva entre las partículas. Este ajuste busca prevenir la convergencia prematura de todas las partículas hacia una región específica del espacio de búsqueda. Esta dinámica implica que cuando dos partículas se acercan demasiado, experimentan una fuerza repulsiva que las separa y evita la acumulación en una zona particular del espacio.
Otra consideración común es permitir que una partícula pueda pertenecer a múltiples "familias", fomentando así la comunicación a larga distancia entre diversas partículas, incluso si no pertenecen a la misma "familia".
Además, se ha explorado la idea de considerar múltiples máximos globales divididos por "familias" de partículas. Esto permite un funcionamiento en paralelo, donde cada "familia" de partículas trabaja independientemente, limitando el conocimiento de cada partícula a su entorno inmediato y no al conjunto global de individuos. Se han desarrollado variantes donde estas "familias" son dinámicas, permitiendo que las partículas cambien de "familia" a medida que avanza el algoritmo.
Finalmente, surge la interrogante de cómo se comportaría el enjambre de partículas en una búsqueda dinámica, donde la función a optimizar varía con el tiempo. Modificar el modelo para reflejar una función cambiante en el tiempo permite explorar cómo las partículas del enjambre siguen los movimientos de los máximos a medida que estos se desplazan por el espacio de búsqueda [3] .
10. Código
# Ejemplo optimización
def funcion_objetivo(x_0, x_1):
""" Función de Rosenbrock """
f = (1 - x_0)*2 + 100(x_1 - x_0*2)*2
return(f)
Proyecto ejemplo:
https://github.com/JoaquinAmatRodrigo/optimizacion_PSO_python/blob/master/PSO_python.ipynb
def funcion_objetivo(x_0, x_1):
""" Función de Rosenbrock """
f = (1 - x_0)*2 + 100(x_1 - x_0*2)*2
return(f)
Proyecto ejemplo:
https://github.com/JoaquinAmatRodrigo/optimizacion_PSO_python/blob/master/PSO_python.ipynb
11. Conclusión
La investigación sobre Particle Swarm Optimization (PSO) destaca la eficacia de este algoritmo metaheurístico en la resolución de problemas de optimización. PSO, inspirado en el comportamiento de enjambres de partículas en la naturaleza, presenta una estructura que permite a las partículas del enjambre colaborar para encontrar soluciones óptimas en el espacio de búsqueda. La interacción entre las partículas y la incorporación de memoria contribuyen a una convergencia rápida y eficiente en comparación con otros algoritmos globales.
En el estado del arte, se evidencia la evolución del PSO desde su introducción en comportamientos sociales hasta convertirse en una herramienta valiosa en campos como logística, matemáticas y salud. Su capacidad para resolver problemas de optimización en estos contextos demuestra su relevancia y aplicación en la actualidad.
REFERENCIAS
[5] J. E. Rengel-hernández, “Inteligencia Computacional para la Planificación y Dimensionamiento de Sistemas Inalámbricos de Comunicaciones Satelitales,” no. June, 2023.
[6] C. Millán-Páramo and E. Millán-Romero, “Topological optimization using particles swarm metaheuristic,” Ing. y Desarro., vol. 36, no. 2, pp. 343–358, 2018, doi: 10.14482/inde.36.2.10127.
[7] F. Casado Bravo, “Optimización Estructural Mediante Algoritmos Computacionales Inspirados En La Naturaleza,” 2022, [Online]. Available: https://oa.upm.es/70277/3/TFM_Francisco_Casado_Bravo.pdf
[8] F. Suárez and J. Cabascango, “Optimización Con Enjambre De Partículas Para Identificación Forense Optimization With Swarm of Particles for Forensic Identification,” Cienc. y Tecnol., vol. 21, pp. 16–20, 2017.
[9] J. Rodrigo, “Introducción — Optimización PSO 0.0.1 documentation.” Accessed: Oct. 18, 2023. [Online]. Available: https://joaquinamatrodrigo.github.io/optimizacion_PSO_python/pso.introduccion.html
[10] C. E. M. López, “Búsqueda de parámetros por optimización de enjambre de partículas para un solver de problemas de satisfacción de restricciones. cristoffer eduardo morales lópez,” 2010.
[11] F. Mesa, G. Correa-Vélez, and J. J. Barba-Ortega, “Optimización de ecuaciones con restricciones no lineales: comparativo entre técnicas heurística y convexa,” Rev. UIS Ing., vol. 21, no. 2, 2023, doi: 10.18273/revuin.v21n2-2022005.
[12] R. Cies et al., “Problemas de optimización en logística : una propuesta de solución aplicando el algoritmo Particle Swarm Optimization ( PSO ),” pp. 211–224, 2023.
[13] C. V. Neicer, C. C. Carlos, B. Z. L. Maribel, and S. B. J. Luis, “Métodos Algorítmicos para la optimización de rutas en el Sistema del Transporte Urbano,” Proc. LACCEI Int. Multi-conference Eng. Educ. Technol., pp. 1–9, 2022, doi: 10.18687/LEIRD2021.1.1.32.
[14] J. G.-R. Gelvez-García, Nancy Yaneth and and J. Fredy, “Optimización de sistemas recomendadores usando enjambre de partículas,” vol. 28, pp. 1–13, 2023.
[15] N. H. ́andez-R. F. Santander-Baños, “Vista de Clasificación de Arritmias Cardíacas mediante Redes Neuronales Convolucionales y Optimización por Enjambre de Partículas.” Accessed: Oct. 18, 2023. [Online]. Available: https://repository.uaeh.edu.mx/revistas/index.php/icbi/article/view/8655/9010
