La optimización por enjambre de partículas (PSO) es un método computacional en inteligencia artificial y ciencia computacional que optimiza un problema mejorando iterativamente una población de soluciones candidatas con respecto a una medida de calidad dada. Resuelve un problema mediante interacciones entre una población de soluciones candidatas, denominadas partículas, moviéndolas por el espacio de búsqueda según fórmulas matemáticas simples que ajustan la posición y la velocidad de cada partícula. El movimiento de cada partícula está influenciado por su mejor posición conocida hasta el momento y por la mejor posición conocida en su vecindario topológico, que puede incluir a toda la población si así se especifica. Los vectores se actualizan a medida que se encuentran mejores posiciones, y se espera que esto mueva al enjambre hacia buenas soluciones.
PSO es una metaheurística porque hace pocas o ninguna suposición sobre el problema a optimizar y puede explorar espacios de soluciones muy amplios. No utiliza el gradiente del problema, por lo que no requiere que la función de optimización sea diferenciable, a diferencia de métodos clásicos como el descenso por gradiente o los métodos cuasi-Newton. Sin embargo, las metaheurísticas como PSO no garantizan que se encuentre una solución óptima.
Orígenes y desarrollo
PSO fue originalmente atribuido a Kennedy y Eberhart, quienes lo concibieron inicialmente para simular el comportamiento social como una representación estilizada del movimiento de organismos en una bandada de aves o un banco de peces, o la evolución de actitudes en una población humana. La simulación de los principios del comportamiento social demostró ser capaz de resolver problemas matemáticos difíciles. El libro de Kennedy y Eberhart describe muchos aspectos filosóficos de PSO y de la inteligencia de enjambre. Una extensa revisión de las aplicaciones de PSO fue realizada por Poli, y en 2017 Bonyadi y Michalewicz publicaron una revisión exhaustiva de los trabajos teóricos y experimentales sobre PSO.
Algoritmo
Una variante básica del algoritmo PSO se inicializa con una población conectada (llamada enjambre) de soluciones candidatas (llamadas partículas). Una solución candidata es un vector de valores numéricos que pueden considerarse como las coordenadas de un punto en un espacio de búsqueda; como un punto que se mueve iterativamente, puede conceptualizarse como una partícula. Las partículas se mueven por el espacio de búsqueda según unas pocas fórmulas simples. Cada partícula tiene algunos vecinos con los que está conectada, y el vecindario puede ser un subconjunto pequeño o toda la población. La siguiente posición de una partícula se determina estocásticamente por su mejor posición hasta el momento y por la mejor posición de su vecino. Cuando se descubre una posición mejorada, que produce un mejor resultado en la función objetivo, se actualiza la mejor posición de la partícula. El proceso se repite y se espera, aunque no se garantiza, que con el tiempo se descubra una solución satisfactoria.
Formalmente, sea \( f: \mathbb{R}^n \to \mathbb{R} \) la función de costo a minimizar. La función toma una solución candidata como argumento en forma de un vector de números reales y produce un número real como salida que indica el valor de la función objetivo. No se conoce el gradiente de \( f \). El objetivo es encontrar una solución \( a \) tal que \( f(a) \le f(b) \) para todo \( b \) en el espacio de búsqueda, lo que significa que \( a \) es el mínimo global.
Sea \( S \) el número de partículas en el enjambre, cada una con una posición \( x_i \in \mathbb{R}^n \) y una velocidad \( v_i \in \mathbb{R}^n \). Sea \( p_i \) la mejor posición conocida de la partícula \( i \), y sea \( g \) la mejor posición conocida del vecindario de la partícula. Un algoritmo PSO básico para minimizar la función de costo es:
- Para cada partícula \( i = 1, \dots, S \):
- Inicializar la posición de la partícula con un vector aleatorio distribuido uniformemente: \( x_i \sim U(b_{lo}, b_{up}) \).
- Inicializar la mejor posición conocida de la partícula con su posición inicial: \( p_i \leftarrow x_i \).
- Si \( f(p_i) < f(g) \), actualizar la mejor posición conocida del enjambre: \( g \leftarrow p_i \).
- Inicializar la velocidad de la partícula: \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \).
- Mientras no se cumpla un criterio de terminación:
- Para cada partícula \( i = 1, \dots, S \):
- Para cada dimensión \( d = 1, \dots, n \):
- Elegir números aleatorios \( r_p, r_g \sim U(0,1) \).
- Actualizar la velocidad de la partícula: \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \).
- Actualizar la posición de la partícula: \( x_i \leftarrow x_i + v_i \).
- Si \( f(x_i) < f(p_i) \), actualizar la mejor posición conocida de la partícula: \( p_i \leftarrow x_i \).
- Si \( f(p_i) < f(g) \), actualizar la mejor posición conocida del enjambre: \( g \leftarrow p_i \).
Los valores \( b_{lo} \) y \( b_{up} \) representan los límites inferior y superior del espacio de búsqueda. El parámetro \( w \) es el peso de inercia. Los parámetros \( \phi_p \) y \( \phi_g \) se denominan a menudo coeficiente cognitivo y coeficiente social. El criterio de terminación puede ser el número de iteraciones realizadas o una solución donde se encuentre un valor adecuado de la función objetivo. Los parámetros \( w \), \( \phi_p \) y \( \phi_g \) son seleccionados por el practicante y controlan el comportamiento y la eficacia del PSO.
Selección de parámetros
La elección de los parámetros del PSO puede tener un gran impacto en el rendimiento de la optimización. La selección de parámetros que producen un buen rendimiento ha sido objeto de mucha investigación. Para evitar la divergencia ("explosión"), el peso de inercia debe ser menor que 1. Los otros dos parámetros pueden derivarse mediante el enfoque de constricción o seleccionarse libremente, pero los análisis sugieren dominios de convergencia para restringirlos. Los valores típicos están en el rango [1, 3]. Los parámetros del PSO también pueden ajustarse utilizando otro optimizador superpuesto, un concepto conocido como metaoptimización, o incluso ajustarse finamente durante la optimización, por ejemplo, mediante lógica difusa. También se han ajustado parámetros para diversos escenarios de optimización.
Vecindarios y topologías
La topología del enjambre define el subconjunto de partículas con las que cada partícula puede intercambiar información. La versión básica del algoritmo utiliza la topología global como estructura de comunicación del enjambre. Esta topología permite que todas las partículas se comuniquen entre sí, por lo que todo el enjambre comparte la misma mejor posición \( g \) de una sola partícula. Sin embargo, este enfoque puede hacer que el enjambre quede atrapado en un mínimo local, por lo que se han utilizado diferentes topologías para controlar el flujo de información entre las partículas. Por ejemplo, en topologías locales, las partículas solo comparten información con un subconjunto de partículas. Este subconjunto puede ser geométrico, por ejemplo, "las \( m \) partículas más cercanas", o más a menudo social, es decir, un conjunto de partículas que no depende de ninguna distancia. En tales casos, se dice que la variante del PSO es de mejor local (en contraposición a mejor global para el PSO básico). Una topología de enjambre comúnmente utilizada es el anillo, en el que cada partícula tiene solo dos vecinos, pero existen muchas otras. La topología no es necesariamente estática; puede cambiar durante el proceso de optimización.
Aplicaciones y métodos relacionados
PSO se ha aplicado a una amplia gama de problemas de optimización en campos como la ingeniería, la economía y el aprendizaje automático. Es particularmente útil cuando el espacio de búsqueda es amplio y la función objetivo no es diferenciable o es ruidosa. PSO comparte similitudes con otras metaheurísticas basadas en población, como los algoritmos genéticos y la optimización por colonia de hormigas, pero se distingue por su mecanismo de actualización de velocidad inspirado en el comportamiento social. En el contexto del aprendizaje automático, PSO puede utilizarse para el ajuste de hiperparámetros o el entrenamiento de redes neuronales, aunque a menudo se compara con métodos basados en gradiente. Su naturaleza estocástica y la falta de requisitos de gradiente lo convierten en una herramienta versátil en el campo más amplio de la inteligencia artificial.