Optimización de lobo gris – Introducción

La optimización está esencialmente en todas partes, desde el diseño de ingeniería hasta la economía y desde la planificación de vacaciones hasta el enrutamiento de Internet. Dado que el dinero, los recursos y el tiempo siempre son limitados, la utilización óptima de estos recursos disponibles es de vital importancia.

En general, un problema de optimización se puede escribir como

optimize  _,
subject to,  
                      , 
                      , (

donde f ₁ , …, f _N son los objetivos, mientras que h _j y g _k son las restricciones de igualdad y desigualdad, respectivamente. En el caso de que N=1, se denomina optimización de un solo objetivo. Cuando N≥2, se convierte en un problema de optimización multiobjetivo cuya estrategia de solución es diferente a la de un solo objetivo. Este artículo trata principalmente de problemas de optimización de un solo objetivo.

Diferentes tipos de algoritmos de optimización.

Algoritmos de optimización deterministas:

Los enfoques deterministas aprovechan las propiedades analíticas del problema para generar una secuencia de puntos que convergen en una solución óptima global. Estos enfoques pueden proporcionar herramientas generales para resolver problemas de optimización para obtener un óptimo global o aproximadamente global.

Ejemplos: programación lineal, programación no lineal y programación no lineal de enteros mixtos, etc.

Heurísticas y metaheurísticas:

Una meta heurística es un procedimiento o heurística de nivel superior que tiene como objetivo encontrar, generar o seleccionar una heurística (algoritmo de búsqueda parcial) que pueda proporcionar una solución suficientemente buena para un problema de optimización. Se utilizan especialmente cuando se dispone de información incompleta o imperfecta o cuando la capacidad de cálculo es limitada.

Las metaheurísticas hacen relativamente pocas suposiciones sobre el problema de optimización que se está resolviendo y, por lo tanto, pueden usarse para una variedad de problemas.

Ejemplos: Optimización de enjambre de partículas (PSO) , Optimización de colonias de hormigas (ACO) , Algoritmos genéticos (GA) , Algoritmo de búsqueda Cuckoo, Optimización de lobo gris (GWO), etc.

Figura 1: Clasificación de algoritmos metaheurísticos con ejemplos de cada clase

Este artículo tiene como objetivo presentar los conceptos básicos de una metaheurística novedosa llamada optimización de lobo gris (GWO)

Inspiración del algoritmo

El optimizador de lobo gris (GWO) es un algoritmo metaheurístico basado en la población que simula la jerarquía de liderazgo y el mecanismo de caza de los lobos grises en la naturaleza, y es propuesto por Seyedali Mirjalili et al. en 2014.

Los lobos grises se consideran depredadores del ápice, que se encuentran en la parte superior de la string alimentaria.
Los lobos grises prefieren vivir en grupos (manadas), cada grupo contiene de 5 a 12 individuos en promedio.
Todos los individuos del grupo tienen una jerarquía de dominio social muy estricta, como se demuestra en la figura adjunta.

Figura 2: Jerarquía social de los lobos grises

El lobo alfa α se considera el lobo dominante en la manada y sus órdenes deben ser seguidas por los miembros de la manada.
Beta β son lobos subordinados, que ayudan al alfa en la toma de decisiones y son considerados como los mejores candidatos para ser el alfa.
Los lobos delta δ tienen que someterse al alfa y al beta, pero dominan al omega. Hay diferentes categorías de exploradores tipo delta, centinelas, ancianos, cazadores, cuidadores, etc.
Los lobos omega ω se consideran el chivo expiatorio de la manada, son los individuos menos importantes de la manada y solo se les permite comer al final.

Fases principales de la caza del lobo gris:

Seguimiento, persecución y acercamiento a la presa.
Perseguir, rodear y acosar a la presa hasta que deje de moverse.
Ataque hacia la presa.

La jerarquía social y el comportamiento de caza de los lobos grises se modelan matemáticamente para diseñar GWO.

Modelo matemático y algoritmo:

Jerarquía social:

La solución Fittest como un lobo Alfa ( α)
Segunda mejor solución como lobo Beta ( β)
Tercera mejor solución como lobo Delta ( δ)
Resto de soluciones candidatas como lobos Omega (ω)

Rodeando a la presa:

$\vec{D} = |\vec{C}.\vec{X_p}(t)-\vec{X_p}(t)|$ (1)

$\vec{X}(t+1) = \vec{X_p}(t)-\vec{A}.\vec{D}$ (2)

Donde t indica la iteración actual, $\vec{A}$ y $\vec{C}$ son vectores de coeficientes, $\vec{X_p}$ es el vector de posición de la presa e $\vec{X}$ indica el vector de posición de un lobo gris. $\vec{X_1}(t+1) = \vec{X_α}(t) - \vec{A_1}.\vec{D_α}$

$\vec{A} = 2\vec{a}\vec{r_1} - \vec{a}$ y $\vec{C} = 2\vec{r_2}$ (3)

los componentes de $\vec{a}$ se reducen linealmente de 2 a 0 en el transcurso de las iteraciones y $\vec{r_1}$ son $\vec{r_2}$ vectores aleatorios en [0, 1].

Caza:

En cada iteración, los lobos omega actualizan sus posiciones de acuerdo con las posiciones α, β y δ alfa, beta y delta porque α, β y δ conocen mejor la ubicación potencial de las presas.

$\vec{D_α} = |\vec{C_1}.\vec{X_α}(t)-\vec{X}(t)|$ , $\vec{D_β} = |\vec{C_2}.\vec{X_β}(t)-\vec{X}(t)|$ , $\vec{D_δ} = |\vec{C_3}.\vec{X_δ}(t)-\vec{X}(t)|$ (4)

$\vec{X_1}(t+1) = \vec{X_α}(t) - \vec{A_1}.\vec{D_α}$ , $\vec{X_2}(t+1) = \vec{X_β}(t) - \vec{A_2}.\vec{D_β}$ , $\vec{X_3}(t+1) = \vec{X_δ}(t) - \vec{A_3}.\vec{D_δ}$ (5)

$\vec{X}(t+1) = (\vec{X_1} + \vec{X_2} + \vec{X_3})/3$ (6)

Atacando a la presa (explotación):

Cuando la presa deja de moverse, el lobo gris termina la caza atacando a la presa y modelando matemáticamente que disminuimos el valor de $\vec{a}$ . $\vec{A}$ es un valor aleatorio en el intervalo [-2a, 2a], donde a disminuye de 2 a 0 en el transcurso de las iteraciones.

|A|<1 fuerza a los lobos a atacar a la presa (explotación)

Búsqueda de presas (exploración):

|A|>1 obliga a los lobos grises a alejarse de la presa para encontrar una presa más adecuada (explotación)

Otro componente de GWO que favorece la exploración es $\vec{C}$ . Contiene un valor aleatorio entre [0, 2]. C>1 enfatiza el ataque mientras que C<1 resta énfasis al ataque.

Pseudocódigo del algoritmo GWO:

Paso 1: Inicializar aleatoriamente la población de lobos grises X _i (i=1,2,…,n)
Paso 2: inicialice el valor de a = 2, A y C (usando eq.3)
Paso 3: Calcular la aptitud de cada miembro de la población
- X _α =miembro con el mejor valor de fitness
- X _β = segundo mejor miembro (en términos de valor de aptitud)
- X _δ = tercer mejor miembro (en términos de valor de aptitud)
Paso 4: PARA t = 1 a Max_number_of_iterations:
- Actualice la posición de todos los lobos omega por eq. 4, 5 y 6
- Actualice a, A, C (usando la ecuación 3)
- a = 2(1-t/T)
- Calcule Fitness de todos los agentes de búsqueda
- Actualizar Xα, Xβ, Xδ.
- FIN PARA
Paso 5: devolver X _α

Referencias:

https://www.sciencedirect.com/science/article/pii/S0965997813001853
https://www.slideshare.net/afar1111/grey-wolf-optimizer

Publicación traducida automáticamente

Artículo escrito por shaadk7865 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA