Introducción a la
Optimización por
Enjambre de Partículas
Tópicos Especiales en Telecomunicaciones
Mérida marzo 2019 Prof. José E. Rengel H., [Link].
Contenido
Optimización
Optimización Heurística
Heurísticas inspiradas en metáforas
PSO: Optimización basada en enjambre
de partículas
– Relevancia/presencia de PSO
– Algoritmo base
– Parámetros de PSO
Trampas de la Técnica PSO
Ejemplo PSO
Aplicación (Asignación)
Optimización
La optimización es un área ubicua
Presente en procesos de toma de decisión
Inversiones
Eficiencia de procesos productivos
Costos, lucros, Materiales, etc…
Optimización
Modelado:
– Función objetivo (f(x))
– Variables (x)
– Restricciones (R)
– Proceso de optimización -> Solución
• Métodos exactos
• Métodos Heurísticos
Optimización
Métodos exactos: Proporcionan el óptimo pero suelen ser
muy costosos
Métodos heurísticos: Son
encontrar el óptimo r ápidos pero no garantizan
Métodos heurísticos son adecuados para abordar
problemas:
– Complejos, que son difíciles de resolver con métodos
tradicionales/exactos
– Donde la función objetivo no es derivable
– Donde la función objetivo es no convexa, presenta muchos
mínimos locales o esta dominada por valles
En lo posible, siempre es preferible usar5 métodos
exactos
Optimización Heurística
Optimización estocástica es una clase de
algoritmos y técnicas que utilizan algún grado de
aleatoriedad para encontrar un óptimo (lo más
cerca del óptimo) para problemas difíciles.
• Essentials of Metaheuristics (Sean Luke)
Optimización Heurística
Mejora un conjunto de soluciones iterativamente
Poco conocimiento del problema
Requiere distinguir buenas soluciones
Generalmente encuentra buenas soluciones.
Posiblemente no el óptimo
Adaptable : parámetros ajustables
Heurísticas inspiradas en metáforas
Métodos de optimización heurística
inspirados en metáforas son muy
comunes hoy en día (e.g., GA, SA,
ACO, PSO, TS, GRASP, SS)
Cada día se publican artículos con
mejoras a heurísticas establecidas, o
bien, nuevas heurísticas para
optimización
Este tipo de métodos ha contribuido de
manera importante al área de
optimización
PSO: Optimización basada en
enjambres de partículas
PSO: Optimización basada en
enjambre de partículas
Método de optimización heurística inspirado en
el comportamiento de sociedades biológicas,
donde los individuos comparten objetivos y
presentan tanto comportamientos individuales
como sociales
– Bandadas de aves
– Bancos de peces
– Enjambres de abejas
PSO: Optimización basada en
enjambre de partículas
Método de optimización heurística i nspirado en
el comportamiento de sociedades biológicas,
donde los individuos comparten objetivos y
presentan tanto comportamientos individuales
como sociales
– Bandadas de aves
– Bancos de peces
– Enjambres de abejas
PSO: Optimización basada en
enjambre de partículas
Las partículas son atraídas hacia la comida
Cada partícula recuerda su posición más
cercana con respecto a la comida
Las partículas comparten información con
partículas vecinas sobre cuál ha sido su
posición más cercana a la comida
PSO: La analogía
Las partículas están asociadas a las soluciones del
problema a abordar
La distancia entre la comida y cada partícula se
representa por la función que se desea optimizar
El enjambre de partículas es la población de
soluciones que explorará el espacio de búsqueda
Las soluciones se representan por las posiciones
de las partículas en el espacio de búsqueda
PSO: La analogía
Idea:
Las soluciones tienen una posición en el espacio de
búsqueda (el óptimo tiene una posición también). El
objetivo es que las soluciones exploren el espacio de
búsqueda para llegar al óptimo del problema. No se
sabe donde está el óptimo pero se sabe que tan lejos
esta cada solución del óptimo.
* Asumiendo que existe un óptimo y que es único.
PSO: La analogía
No*: la población inicial
¿Es PSO un método
se mantiene durantede
todo el proceso
cómputo de
evolutivo?
optimización
Presencia de PSO
Algunos números:
PSO fue introducido en 1995 por J. Kennedy
(sociología) & R. Eberhart (cómputo)
~3000 citas en 2012
J. Kennedy, R. Eberhart. Particle swarm optimization. Proceedings., IEEE International
Conference on Neural Networks, pp. 1942--1948, IEEE, 1995.
Presencia de PSO
Algunos números:
Distribución de publicaciones (ISI web of
knowledge) en cuanto a diversas meta- Número de publicaciones sobre PSO ente
heurísticas 2001-2011
M. Eslami. A survey of the state of the art in particle swarm optimization. Research Journal of
Applied Sciences Engineering and Technology, 4(9):1181—1197, 2012
Inicialización: Al inicio las partículas
vuelan aleatoriamente
PSO
Elementos del algoritmo:
A : población de partículas.
xi : posición de la partícula pi en el espacio de soluciones.
f : función de evaluación.
vi : velocidad de la partícula pi.
V(pi) : conjunto fijo de vecinos de la partícula pi.
Todas las partículas están conectados, directa o
indirectamente
Notación PSO
Notación PSO
Actualización de la velocidad
Tres términos definen una nueva velocidad para
una partícula: aprendizaje
social
1. Término
de
inercia
2. Tér
mino
cognitiv
o
3. Término
de
Obliga a la partícula a
moverse en la misma
dirección
Tendencia para seguir la
propia dirección con la
misma velocidad
Mejora al individuo
Obliga a la partícula a
volver a una posición
anterior que sea mejor
de lo que la actual
Tendencia conservativa
Obliga a la partícula a
seguir la dirección de
sus mejores vecinos
Como en todo
rebaño, pero
siguiendo a los
mejores
Idea básica:
comportamiento
cognitivo
Cuál es la
mejor
dirección?
comida:
8
comida:
5
Un individuo recuerda la experiencia pasada
Idéia básica: comportamento
social
Cúál es la
mejor pássaro
dirección? 3
pássaro
1
comida:
comida:
pássaro
2 pássaro
comida: 4
Un individuo adquiere conocimientocomida:
de los demás miembros del
grupo
Actualización de velocidad y
posición
PSO tradicional – Eberhart, R. C. and Kennedy, J. (1995)
Para cada partícula pi :
inércia aprendizaje social
cognitivo
vi = wvi η[Link]().(pbesti - η[Link]().(gbesti - xi)
+ x i = x i xi) +
+ vi
donde:
pbesti es la mejor posición donde la partícula pi
estuvo gbesti es la mejor posición en la que
algún vecino de pi estuvo w es el peso de inercia
Inicio
Inicialice las partículas con posiciones
aleatorias y velocidades
nulas
Calcular los valores fitness
Compare los fitness con los mejores valores del
individuo (pbest) y de los demás
(gbest)
El criterio de SI
Fin
parada está
satisfecho?
NO
Actualice velocidades y posiciones
Algoritmo Enjambre de Partículas
Ejemplo: 1ª
Iteración Problema de
minimización
2
1. Inicialización de las velocidades
posiciones
2. Creando el vector
mejor partícula otra partícula
Ejemplo: 2ª
Iteración Problema de
minimización
1. Inicialización de las velocidades
posiciones
2. Creando el vector
mejor partícula otra partícula
Término de inercia
Posición actual (x)
Mejor posición del individuo (pbest)
Mejor posición individual (pbest)
Posición actual (x)
Mejor posición del individuo
(pbest) Mejor posición global
(gbest)
Mejor posición global (gbest)
Algunos detalles de implementación
Interpretación geométrica
Interpretación geométrica
Diversificación e Intensificación
Mejoras y Variantes
Reducción lineal de la ponderación de inercia;
Factor de constricción;
Modelos con vecindarios.
Reducción Lineal de la ponderación
de Inercia
Factor de Constricción
Factor de Constricción fue introducido por Clerc e
Kennedy (2002).
Se tornó muy popular en los algoritmos recientes
de enjambre de partículas.
Factor de Constricción
Trampas de la técnica PSO
Las partículas tienden a agruparse, o sea, debido
a una convergencia muy rápida, la solución
queda presa en un punto óptimo local
El movimiento de alguna partícula puede ser
llevado a un punto de solución no factible
Las partículas pueden mapear un espacio
inapropiado de soluciones factíbles
Problema: Las partículas tiendem agruparse,
reduciendo la capacidad de movimientos del
enjambre para mejores soluciones .
Solución: reiniciar algunas partículas en nuevas
posiciones, las cuales pueden moverse para áreas con
mejores soluciones. Las demás partículas pueden
moverse para estas áreas.
!
Principales elementos
Intensificación es la exploración de las
soluciones encontradas en búsquedas
anteriores
Diversificación es la búsqueda por soluciones
aun no visitadas
Encontra
Intensificación r el Diversificación
equilibrio
Encuentra rápidamente la Identifica rápidamente
mejor solución de una regiones con potencial para
región mejores soluciones
Ejemplo
Utilizar el algoritmo de PSO para encontrar puntos de
mínimo de la función abajo, usando las 3 partículas
dadas:
600
partículas x v 1
500
1 2,5 1 0
2 5,6 2 0 400
3 10, 3 0 300
5 200
Minimizar
100
f(x)=(x-4)^2-(x-
0
8)^3+5
-100 0 1 2 3 4 5 6 7 8 9 10 11 12 13
pso
Primera Iteración
posición f(x) velocidad actualización
2.5 173.625 13.59356994 16.09356994
5.6 21.384 0.559038295 6.159038295
10 33 mejor global
0.906237996
0.03726922
