Saltar al contenido
Volver a los resultados

Optimización por Enjambre de Partículas (PSO)

Año
1995
Tipo
Population-based metaheuristic / swarm intelligence

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La Optimización por Enjambre de Partículas (PSO) es un algoritmo metaheurístico basado en poblaciones, introducido por Kennedy y Eberhart en 1995, inspirado en el movimiento colectivo de bandadas de aves y cardúmenes de peces.

Cada solución candidata —denominada partícula— se mueve a través del espacio de búsqueda actualizando su velocidad y posición basándose en su propia mejor experiencia y la mejor experiencia de todo el enjambre, lo que permite una rápida convergencia en problemas de optimización continua.

La intuición detrás del método

Imagine una bandada de pájaros buscando en un gran campo la fuente de alimento más rica. Ningún pájaro tiene un mapa, pero cada uno recuerda el mejor lugar que ha visitado personalmente y es consciente del mejor lugar encontrado por cualquier pájaro cercano. Cada pájaro dirige su vuelo en parte hacia su propia mejor ubicación recordada y en parte hacia la mejor ubicación colectiva del enjambre, ajustando la velocidad en consecuencia. A lo largo de muchos ajustes de este tipo, toda la bandada converge en el área más rica. La PSO funciona exactamente de esta manera: cada partícula es una solución candidata, su posición es la solución misma, y el enjambre converge colectivamente hacia el óptimo al compartir la memoria individual y social.

Historia

La PSO fue introducida por James Kennedy y Russell Eberhart en la Conferencia Internacional sobre Redes Neuronales de la IEEE de 1995, basándose directamente en modelos de simulación del comportamiento social en bandadas de aves y cardúmenes de peces. El artículo fundamental de 1995 estableció las ecuaciones de actualización de velocidad y posición que siguen siendo centrales para el algoritmo. En 1998, Shi y Eberhart introdujeron el parámetro de peso de inercia en la actualización de velocidad, mejorando significativamente el control de la convergencia y convirtiéndose en la modificación estándar adoptada por la investigación posterior. La PSO ganó rápidamente tracción como una alternativa práctica a los algoritmos genéticos para la optimización continua, debido a su simplicidad y velocidad de convergencia competitiva, y desde entonces se ha aplicado en ingeniería, ajuste de hiperparámetros de aprendizaje automático, procesamiento de señales y modelado científico.

Cuándo usarlo

La PSO es adecuada para problemas de optimización continua donde la función de aptitud puede evaluarse en cualquier punto del espacio de búsqueda, pero puede ser no diferenciable, multimodal o costosa de calcular analíticamente. No requiere suposiciones de normalidad ni un tamaño de muestra mínimo, lo que la hace aplicable en diversos dominios. El método funciona mejor cuando los límites del espacio de búsqueda se conocen de antemano, cuando el peso de inercia y los coeficientes de aceleración se ajustan cuidadosamente, y cuando se asigna un número suficiente de iteraciones. Si el número de iteraciones es demasiado bajo (menos de unos pocos cientos en problemas no triviales), es probable que ocurra una convergencia prematura y la optimización bayesiana puede ser una alternativa más segura.

Limitaciones y consideraciones

  • Diseñada para espacios de búsqueda continuos; no aplicable directamente a problemas discretos o combinatorios sin modificación.
  • La convergencia prematura es un riesgo conocido: el enjambre puede agruparse alrededor de un óptimo local si el peso de inercia y los coeficientes se eligen mal.
  • La velocidad de convergencia y la calidad de la solución son sensibles a la elección del peso de inercia y los coeficientes de aceleración.
  • No hay garantía teórica de encontrar el óptimo global en un número finito de iteraciones.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Rápida convergencia en espacios de búsqueda continuos en comparación con muchos métodos basados en poblaciones.
  • Muy pocos parámetros para ajustar —principalmente el peso de inercia y dos coeficientes de aceleración.
  • No requiere información de gradiente o derivada, lo que la hace aplicable a funciones de aptitud no diferenciables y de caja negra.
  • Escala naturalmente a problemas continuos de alta dimensionalidad.
  • Conceptualmente simple y fácil de implementar.

Aplicaciones

  • Ajuste de hiperparámetros para modelos de aprendizaje automático en espacios de parámetros continuos.
  • Optimización de diseño de ingeniería — diseño estructural, aerodinámico y de sistemas eléctricos.
  • Entrenamiento de pesos de redes neuronales y búsqueda de arquitectura.
  • Procesamiento de señales y diseño de antenas.
  • Despacho económico y optimización de sistemas de potencia.
  • Estimación de parámetros en modelos científicos y de simulación.

Cómo funciona

Cómo funciona

1

Se coloca un enjambre de partículas en posiciones aleatorias dentro del espacio de búsqueda definido, y a cada partícula se le asigna una velocidad inicial aleatoria. Cada partícula también registra su posición personal óptima —la mejor solución que ha encontrado hasta ahora— y el enjambre rastrea la posición global óptima encontrada por cualquier partícula. El peso de inercia, el coeficiente cognitivo y el coeficiente social se establecen antes de que comience la ejecución, ya que su equilibrio rige directamente si el enjambre explora ampliamente o explota regiones conocidas y buenas.

2

La función de aptitud se calcula para cada partícula en su posición actual. Este es el único paso específico del problema: la PSO no impone restricciones a la forma de la función de aptitud más allá del requisito de que sea evaluable en cualquier punto del espacio de búsqueda continuo. La mejor posición personal de cada partícula y la mejor posición global del enjambre se actualizan cada vez que una nueva posición produce un valor de aptitud mejor.

3

La velocidad de cada partícula se actualiza utilizando tres componentes: el término de inercia (velocidad previa escalada, que promueve el momento), el término cognitivo (atracción hacia la mejor posición personal de la partícula) y el término social (atracción hacia la mejor posición global del enjambre). La nueva posición se calcula sumando la velocidad actualizada a la posición actual. El peso de inercia controla el equilibrio entre exploración y explotación: un valor más alto favorece la exploración amplia, mientras que un valor más bajo promueve la explotación detallada de regiones conocidas y buenas.

4

Los pasos de evaluación y actualización se repiten para el número de iteraciones prescrito. El enjambre reduce progresivamente su búsqueda alrededor de la región más prometedora. La ejecución concluye cuando se alcanza el límite de iteraciones, momento en el cual se informa la posición global óptima como solución. Es necesario un número suficiente de iteraciones —típicamente al menos varios cientos a mil para problemas no triviales— para permitir que el enjambre converja; detenerse demasiado pronto corre el riesgo de devolver un resultado subóptimo.

Errores comunes

  • Ejecutar muy pocas iteraciones —en problemas no triviales, iteraciones insuficientes impiden que el enjambre converja; preferir la optimización bayesiana cuando el presupuesto de cómputo es muy limitado.
  • Elegir un peso de inercia demasiado alto mantiene a las partículas explorando indefinidamente y retrasa la convergencia; demasiado bajo provoca una agrupación prematura alrededor de un óptimo local.
  • Ignorar los límites del espacio de búsqueda —las partículas que se desvían fuera de los límites previstos exploran regiones irrelevantes y distorsionan la mejor solución global.
  • Tratar la PSO como adecuada para problemas discretos o combinatorios sin adaptación —las ecuaciones estándar de actualización de velocidad y posición asumen un espacio continuo.
  • La convergencia prematura pasa desapercibida si no se supervisa el progreso de la aptitud a lo largo de las iteraciones; siempre rastrear la mejor aptitud global frente al recuento de iteraciones.

Preguntas frecuentes

¿Cómo difiere la PSO de un algoritmo genético?

Ambos son metaheurísticos basados en poblaciones para la optimización, pero difieren en el mecanismo. Un algoritmo genético evoluciona una población a través de operadores de selección, cruce y mutación inspirados en la evolución biológica. La PSO, en cambio, mueve partículas a través de un espacio continuo actualizando las velocidades basándose en la memoria personal y social —no hay cruce ni mutación. La PSO típicamente tiene menos parámetros que ajustar y a menudo converge más rápido en problemas continuos, mientras que los algoritmos genéticos pueden adaptarse más naturalmente a espacios discretos o combinatorios.

¿Cuáles son los parámetros clave y cómo deben configurarse?

Los tres parámetros principales son el peso de inercia (w), que controla cuánta de la velocidad anterior se retiene; el coeficiente cognitivo (c1), que escala la atracción hacia la mejor posición personal de una partícula; y el coeficiente social (c2), que escala la atracción hacia la mejor posición global. Un punto de partida común de la literatura es w alrededor de 0.7–0.9, c1 y c2 alrededor de 1.5–2.0. El peso de inercia a menudo se reduce linealmente a lo largo de las iteraciones para cambiar el enjambre de la exploración temprana a la explotación posterior.

¿Puede la PSO manejar problemas discretos o combinatorios?

La PSO estándar se define para espacios de búsqueda continuos y aplica actualizaciones de velocidad y posición que asumen coordenadas de valor real. Existen variantes discretas o combinatorias —como la PSO binaria— pero estas requieren modificaciones no triviales a las ecuaciones de actualización. Para problemas puramente combinatorios como enrutamiento o programación, la Optimización por Colonia de Hormigas es a menudo la opción más natural.

¿Cómo sé si el enjambre ha convergido prematuramente?

Rastree el valor de la mejor aptitud global a lo largo de las iteraciones. Si la curva se aplana mucho antes de que se agote el presupuesto de iteraciones y la solución informada no es satisfactoria, es probable que haya ocurrido una convergencia prematura. Los remedios comunes incluyen aumentar el peso de inercia, reiniciar el enjambre desde nuevas posiciones aleatorias o aumentar el tamaño del enjambre. Si el presupuesto de cómputo no permite más iteraciones, la optimización bayesiana puede ser una alternativa más eficiente.

Métodos relacionados

Fuentes

  1. Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.

    Abrir referencia DOI
    Copiado.
  2. Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).

    Abrir referencia de la publicación
    Copiado.