Skip to content

Clase 6 — Particle Swarm Optimization (PSO) y ABC (abejas)

Resumen Ejecutivo

Segunda metaheurística poblacional bioinspirada: Particle Swarm Optimization (PSO) de Kennedy & Eberhart (1995). A diferencia de ACO (grafos discretos), PSO trabaja en espacios continuos \(\mathbb{R}^n\), lo que abre la puerta a problemas de optimización continua multidimensional. Se estudian los tres comportamientos emergentes (separación, alineación, cohesión), los cuatro parámetros de la fórmula de actualización de velocidad (inercia, cognitivo, social, aleatoriedad) y se introduce de pasada ABC (Artificial Bee Colony) como variante con tres roles (exploradoras, observadoras, empleadoras). Se presenta la actividad de implementación en MATLAB con entrega el 30 de abril de 2026. ⚠️ EXAMEN: la fórmula de velocidad, el significado de cada parámetro y la diferencia explotación/exploración son los puntos centrales.

Conceptos Clave

  • Nube/enjambre de partículas: conjunto de soluciones candidatas que se mueven por el espacio de búsqueda compartiendo información. Cada partícula representa una posible solución.
  • Partícula: en la metáfora natural es un ave, pez o abeja. En el algoritmo es un vector posición en \(\mathbb{R}^n\) + un vector velocidad.
  • Espacio continuo vs discreto: PSO se mueve en \(\mathbb{R}^n\) (optimización continua); ACO se mueve sobre grafos (optimización combinatoria). ⚠️ EXAMEN — pregunta típica.
  • Fitness: medida de la calidad de la solución. No es necesariamente la función objetivo: puede ser una transformación que la escale entre 0 y 1, o que la "invierta" para maximizar cuando minimizas, etc.
  • \(p_{\text{best}}\): mejor posición personal visitada por una partícula concreta.
  • \(g_{\text{best}}\): mejor posición global encontrada por el enjambre completo.
  • Explotación vs exploración: ⚠️ EXAMEN
  • Explotación = refinar búsqueda local, afinar alrededor de una buena zona.
  • Exploración = salir de zonas conocidas y buscar en nuevas regiones. Evita quedarse atascado en óptimos locales.
  • Comportamientos emergentes (de la vida real al algoritmo):
  • Separación — los agentes no se amontonan; cada uno explora su propio espacio.
  • Alineación — todos se mueven en una dirección común (hacia el mejor conocido).
  • Cohesión — los agentes convergen hacia las zonas prometedoras.

Desarrollo del Temario

1. Del comportamiento natural al algoritmo

Observación base: una bandada de pájaros o un cardumen de peces se mueven en perfecta armonía sin líder explícito. Las reglas son locales: cada individuo solo "habla" con sus vecinos. Aun así logran tareas complejas (evitar depredadores, encontrar comida).

Traducción al algoritmo (Kennedy & Eberhart, 1995): ⚠️ EXAMEN año

  • Cada partícula guarda su posición actual y su velocidad.
  • En cada iteración, comparte con vecinos su mejor resultado personal.
  • Ajusta su velocidad combinando: inercia previa + tirón hacia su mejor histórico + tirón hacia el mejor del grupo.

2. Metáfora operativa: patitos en un lago

Ejercicio visual usado por la profesora:

  • Un lago con fondo irregular; el objetivo es encontrar el punto más profundo (mínimo de una función).
  • Dos patitos nadan en la superficie. Cada uno mide la profundidad donde está.
  • Se comunican: "yo tengo 2 m"; "yo tengo 1 m".
  • El patito con peor profundidad se dirige hacia el otro (alineación + cohesión).
  • Cada patito guarda su mejor profundidad histórica (\(p_{\text{best}}\)) y conoce la mejor del grupo (\(g_{\text{best}}\)).
  • Si en el camino uno encuentra algo mejor, actualiza \(g_{\text{best}}\) y el grupo cambia de rumbo.

La clave: ningún patito ve el todo. Todos van descubriendo la topografía del lago y convergen hacia el mínimo por información compartida local.

3. Formalización: la fórmula de actualización

Para cada partícula \(i\) y cada dimensión \(j\): ⚠️ EXAMEN

\[ v_{ij}(t+1) = \underbrace{\omega \cdot v_{ij}(t)}_{\text{inercia}} + \underbrace{c_1 \cdot r_1 \cdot (p_{ij}^{\text{best}} - x_{ij}(t))}_{\text{componente cognitivo}} + \underbrace{c_2 \cdot r_2 \cdot (g_j^{\text{best}} - x_{ij}(t))}_{\text{componente social}} \]
\[ x_{ij}(t+1) = x_{ij}(t) + v_{ij}(t+1) \]

Parámetros: ⚠️ EXAMEN — qué significa cada uno

Parámetro Significado Efecto
\(\omega\) (omega/inercia) Cuánto conserva la partícula de su velocidad anterior Grande → saltos grandes, más exploración, menos convergencia. Pequeño → pasos cortos, más explotación.
\(c_1\) (cognitivo, personal) Cuánto tira la partícula hacia su propia mejor historia Grande → individualista, confía en lo que ya conoce.
\(c_2\) (social, global) Cuánto tira la partícula hacia la mejor del enjambre Grande → gregario, todos convergen rápido al mejor conocido.
\(r_1, r_2\) Aleatorios \(\in [0,1]\) en cada iteración Inyectan estocasticidad; evitan trayectorias deterministas. Pueden fijarse para reproducibilidad en ejercicios a mano.

Balance crítico: \(c_1\) y \(c_2\) equilibran individualismo vs seguir al grupo. Si \(c_2 \gg c_1\), el enjambre converge prematuramente en el óptimo local conocido. Si \(c_1 \gg c_2\), las partículas vagan sin compartir eficientemente.

Por dimensión: la fórmula se aplica independientemente en cada coordenada (\(x\), \(y\), \(z\), …). Una partícula en \(\mathbb{R}^3\) tiene 3 velocidades y 3 posiciones que se actualizan por separado. ⚠️ EXAMEN

4. Esqueleto del algoritmo

1. Inicializar M partículas dentro del rango [LB, UB] con posiciones aleatorias
   y velocidades pequeñas aleatorias.
2. Evaluar fitness de cada partícula.
3. Inicializar p_best_i = x_i para cada partícula, g_best = mejor p_best.
4. Mientras no se cumpla el criterio de parada:
   a. Para cada partícula i:
      - Actualizar velocidad v_i con la fórmula.
      - Actualizar posición x_i = x_i + v_i.
      - Evaluar fitness.
      - Si mejor que p_best_i → actualizar p_best_i.
   b. g_best = mejor p_best del enjambre.
5. Devolver g_best.

5. Vecindario: global vs local

  • Vecindario global: toda partícula "ve" al mejor del enjambre entero. Convergencia rápida pero riesgo de convergencia prematura a un óptimo local.
  • Vecindario local: cada partícula comparte solo con un subconjunto (p. ej., las 5 más cercanas). Exploración más amplia, convergencia más lenta.
  • Vecindario dinámico: se recalcula cada iteración según distancias.
  • Vecindario predeterminado/fijo: cada partícula tiene un grupo fijo de vecinos toda la ejecución. Mantiene grupos separados → buena exploración pero puede converger prematuramente en cada grupo.

6. Inicialización de partículas

Patrón recomendado: ⚠️ EXAMEN $\(x_{ij}^{(0)} = LB_j + r \cdot (UB_j - LB_j), \quad r \in [0,1]\)$

donde \(LB_j\) y \(UB_j\) son los límites inferior y superior de la dimensión \(j\) del espacio de búsqueda. Esto garantiza que todas las partículas arranquen dentro del rango permitido.

Velocidad inicial pequeña y aleatoria.

7. Criterio de parada

Opciones habituales: - Número máximo de iteraciones (el más usado por la profesora). - Convergencia: varias iteraciones sin mejora de \(g_{\text{best}}\). - Tiempo máximo.

8. Complejidad

Depende de: - Número de partículas \(M\). - Dimensión del problema \(d\). - Número de iteraciones \(T\).

Complejidad por iteración: \(O(M \cdot d)\). Total: \(O(T \cdot M \cdot d)\).

Muy escalable comparado con algoritmos exactos, especialmente para grandes dimensiones.

9. Introducción a ABC (Artificial Bee Colony)

Variante inspirada en abejas en lugar de aves. La gran diferencia: tres roles claros en la colmena: ⚠️ EXAMEN

Rol Función
Exploradoras (scouts) Buscan zonas nuevas de néctar aleatoriamente.
Observadoras (onlookers) En la colmena; reciben información de las exploradoras/empleadoras y deciden probabilísticamente a qué fuente ir.
Empleadoras (employed) Ya asignadas a una fuente conocida; la explotan mientras el néctar dure. Cuando se agota, se reconvierten en exploradoras.

Fitness en ABC: valor entre 0 y 1 que mide la calidad de la fuente. No es la función objetivo directamente, sino una transformación (p. ej., \(1/(1+f)\) si se minimiza \(f \geq 0\)). Esto permite que las probabilidades de elección estén bien definidas y escaladas.

Probabilidad de elegir una fuente \(i\) (observadoras):

\[P_i = \frac{\text{fitness}_i}{\sum_k \text{fitness}_k}\]

Igual que en ACO, la mejor fuente no se escoge con certeza — solo con mayor probabilidad. Esa aleatoriedad evita quedarse atrapado.

10. Ejemplo pequeño de ABC (función multimodal)

Función objetivo con senos y cosenos en \(\mathbb{R}^2\) sobre el rango \([-\pi, \pi]^2\). Dos abejas inicializadas:

\[x_1 = LB + r_{11} \cdot \text{paso}, \quad y_1 = LB + r_{12} \cdot \text{paso}$$ $$x_2 = LB + r_{21} \cdot \text{paso}, \quad y_2 = LB + r_{22} \cdot \text{paso}\]

Para cada una: 1. Evaluar \(f(x_i, y_i)\). 2. Calcular fitness (transformación). 3. Calcular probabilidades relativas. 4. Observadoras tiran dados, deciden a qué fuente ir. 5. Si una fuente se agota (varias iteraciones sin mejora) → empleadora pasa a ser exploradora y busca en otra región.

Lo crítico de este ejemplo: hacer el cálculo por partícula Y por dimensión. Con 2 partículas en \(\mathbb{R}^2\) ya hay 4 actualizaciones de posición por iteración.

Diferencias clave ACO vs PSO vs ABC

Aspecto ACO PSO ABC
Espacio de búsqueda Grafos (discreto) \(\mathbb{R}^n\) (continuo) \(\mathbb{R}^n\) (continuo)
Memoria compartida Feromonas en arcos \(p_{\text{best}}\) y \(g_{\text{best}}\) Fitness transmitido en la colmena
Roles Exploradoras/recolectoras Todas iguales Exploradoras/observadoras/empleadoras
Año base 1992 (Dorigo) 1995 (Kennedy, Eberhart) 2005 (Karaboga)
Aplicación típica TSP, rutas, scheduling Funciones continuas, entrenamiento de redes Funciones continuas, clustering

Actividad práctica (entrega 30 abril 2026)

Objetivo: implementar un algoritmo de enjambre y aplicarlo a una instancia concreta.

Pasos requeridos: ⚠️ ACTIVIDAD 1. Elegir un algoritmo de entre las variantes (PSO estándar, ABC, luciérnagas, cuco, ballena…). Páginas recomendadas: DataCamp (tres algoritmos ilustrados con Python), página con demos en Java, repositorio con muchas variantes. 2. Leer el artículo/código de referencia e interpretarlo. Se puede usar IA como apoyo, pero no basta con pedirle que genere todo. 3. Implementar en MATLAB. Python no se admite porque la asignatura se evalúa en MATLAB (en teoría el examen también). Formato aceptado: .m o .mlx (Live Script tipo RMD). 4. Elegir una instancia/aplicación: el problema concreto que resuelve. Ej.: búsqueda del mínimo de una función real, encontrar parámetros óptimos de un modelo, etc. Añadir novedad respecto a lo visto en clase. 5. Entregar: - PDF con portada, índice, introducción (breve), descripción del algoritmo, descripción de la instancia/problema, resultados + análisis, conclusiones y bibliografía. Máximo 4 páginas efectivas (sin contar portada/índice). - Archivo MATLAB con la implementación ejecutable. - Nombrar el PDF con el nombre completo del alumno, NO con el texto del enunciado. - Fórmulas limpias (LaTeX o Word), no a mano. 6. Fecha límite: 30 de abril de 2026.

La profesora prioriza el PDF: es donde ve la comprensión. El código se revisa después para confirmar que ejecuta. Pedir a la IA "lee este código y haz el PDF explicándolo" es perfectamente válido, siempre que el alumno revise y corrija la "basura que la IA mete".

Preguntas de Autoevaluación

  1. ¿Qué diferencia hay entre ACO y PSO respecto al espacio de búsqueda? ACO trabaja sobre grafos discretos; PSO trabaja sobre \(\mathbb{R}^n\) continuo.
  2. ¿Qué representa \(p_{\text{best}}\) y \(g_{\text{best}}\) en PSO? \(p_{\text{best}}\) es la mejor posición histórica de una partícula individual; \(g_{\text{best}}\) es la mejor posición conocida por el enjambre completo.
  3. ¿Qué efecto tiene aumentar \(\omega\) (inercia)? Aumenta la exploración (pasos más grandes, más tendencia a mantener la dirección). Demasiado grande → no converge; demasiado pequeño → se atasca rápido en óptimos locales.
  4. ¿Qué efecto tiene \(c_1 \gg c_2\)? Las partículas tiran más hacia su mejor personal que hacia el mejor global. Comportamiento más individualista, menos convergencia de grupo.
  5. ¿Por qué los multiplicadores \(r_1, r_2\) son aleatorios? Para romper el determinismo y permitir explorar trayectorias distintas en cada iteración.
  6. ¿Qué significa explotación vs exploración? Explotación = refinar en una zona conocida. Exploración = buscar en zonas nuevas del espacio.
  7. En ABC, ¿qué tres roles tienen las abejas y qué hace cada una? Exploradoras (buscan fuentes nuevas), observadoras (eligen probabilísticamente a qué fuente ir según el fitness reportado), empleadoras (explotan una fuente hasta que se agota; se reconvierten en exploradoras cuando eso ocurre).
  8. Diferencia entre función objetivo y fitness. La función objetivo es la función matemática del problema. El fitness es una transformación de la función objetivo que facilita el cálculo de probabilidades relativas (p. ej., escalada a [0,1]).
  9. ¿Por qué se inicializan las partículas con \(x = LB + r \cdot (UB - LB)\)? Para garantizar que todas las posiciones iniciales están dentro del rango permitido del espacio de búsqueda, con distribución uniforme.
  10. ¿Qué es la "convergencia prematura" y cuándo ocurre? Cuando el enjambre colapsa rápidamente hacia un óptimo local subóptimo sin explorar suficiente el espacio. Ocurre típicamente con \(c_2\) muy grande, \(\omega\) muy pequeño o vecindario global único.
  11. Complejidad de PSO por iteración. \(O(M \cdot d)\) donde \(M\) es el número de partículas y \(d\) la dimensión del problema.
  12. ¿Qué año se introdujo PSO y quién? 1995, Kennedy y Eberhart.

Referencias

  • Kennedy, J. & Eberhart, R. (1995) — formulación original de PSO.
  • Karaboga, D. (2005) — Artificial Bee Colony.
  • DataCamp tutorial — tres algoritmos bioinspirados en Python.
  • Próxima clase: algoritmos genéticos (variantes con mutación, cruzamiento, selección). Enlace natural con la variante MAX-MIN de ACO.