Recepción: 01 Noviembre 2019
Aprobación: 02 Marzo 2020
Resumen: Mejorar el comportamiento de los algoritmos metaheurísticos ha sido, es y será un reto para la comunidad científica. Estrategias dirigidas a una mejora exploración del espacio de búsqueda y evitar el estancamiento de las soluciones, son algunas de las premisas más estudiadas en la literatura. La metaheurística optimización basada en lobos Grises (GWO) es capaz de resolver problemas de optimización continua aplicando un esquema de asignación de roles en la manda que proporciona un balance adecuado entre exploración e intensificación de las soluciones. En este artículo, analizaremos algunas estrategias para la definición de roles en GWO y mediremos su influencia sobre la calidad del proceso de búsqueda en un espacio continuo. Para las estrategias, se utiliza un método de selección probabilística, por seguidores de distancia y una combinación de ambos. Los resultados experimentales mostraron que las variantes basadas en seguidores otorgan una mayor estabilidad en los resultados, y además, los modelos basados en probabilidades presentan mayor efectividad bajo un valor de probabilidad 0.9.
Palabras clave: Grey Wolf Optimization (GWO), Optimización continua, estrategias basadas en roles.
Abstract: Improving the behavior of metaheuristic algorithms has been, is and will be a challenge for the scientific community. Strategies aimed at improving exploration of the search space and avoiding stagnation of solutions are some of the most studied premises in the literature. The Gray wolf-based optimization (GWO) metaheuristic is capable of solving continuous optimization problems by applying a command role assignment scheme that provides an adequate balance between exploration and intensification of solutions. In this article, we will analyze some strategies for defining roles in GWO and measure their influence on the quality of the search process in a continuous space. For strategies, a probabilistic selection method is used, by distance followers and a combination of both. The experimental results showed that the follower-based variants provide greater stability in the results, and in addition, the probability-based models present greater effectiveness under a probability value of 0.9.
Keywords: Gray Wolf Optimization (GWO), Continuous Optimization, role-based strategies.
INTRODUCCIÓN
El mundo real está compuesto por muchos problemas de optimización con variables en dominios continuos, problemas de optimización continua. Existen varias dimensiones en los problemas y mientras mayor sea la dimensionalidad más complejo será obtener una solución que se considere óptima. Los algoritmos meta heurísticos fueron desarrollados con la finalidad de encontrar soluciones viables, realizando exploraciones en el espacio de búsqueda aplicando al menos un proceso estocástico.
Si bien los algoritmos metaheurísticos tienen un buen rendimiento para la optimización, pueden tener obstáculos en cuanto a la convergencia de los resultados, como lentitud en la convergencia, requerir muchas iteraciones para encontrar la mejor solución o estancarse en óptimos locales. Esto evidencia que existe la posibilidad de mejorar estos algoritmos. Este tema ha permitido el surgimiento de nuevas derivaciones y experimentaciones de este tipo de algoritmos.
Los problemas de optimización continua pueden existir en todos los campos de estudios, siendo importante el análisis de una meta heurística que satisfaga las necesidades de la investigación. Los algoritmos bioinspirados son un área muy estudiada, siendo una de sus características principales el intercambio de información entre todos los agentes de búsqueda. Además de técnicas de exploración que muestran la capacidad de descubrir nuevas posibles soluciones.
Gray Wolf Optimizer (GWO) es una meta heurística poblacional que reubica una solución alrededor de otras mediante una jerarquía inspiradas en las manadas de lobos grises, implementando la búsqueda en un espacio n-dimensional para simular las principales características de la caza (persecución, rodear, atacar). GWO es un algoritmo de mayor crecimiento investigativo [1], la prosperidad de este algoritmo ha motivado a otros investigadores que han implementado métodos para diferentes tipos de problemas de optimización. Este algoritmo se utiliza para resolver problemas en diferentes áreas de estudio tales como, ingeniería eléctrica, ingeniería energética, ingeniería en control, programación, planificación de rutas, robótica, planificación ambiental, optimización global y muchos otros.
Los roles de los lobos en GWO representa la característica fundamental de esta meta heurística y es la responsable del desempeño alcanzado por el algoritmo. En este trabajo analizaremos algunas estrategias para definir los roles en GWO y mediremos la influencia sobre la calidad del proceso de búsqueda en un espacio continuo.
Trabajos relacionados
Los algoritmos basados en inteligencia colectiva logran ofrecer resultados adecuados para los problemas de optimización, que se pueden presentar en diversas áreas de estudio o al momento de realizar una aplicación de estas metaheurísticas en un campo más real. Por su parte el algoritmo GWO (Grey Wolf Optimization) mediante la simulación del comportamiento de caza de los lobos grises, establece tres roles jerárquicos , alpha, beta, delta y los lobos gamma utilizando para ello la calidad de las soluciones encontradas [2]. De esta manera GWO realiza la exploración del espacio de búsqueda orientada a minimizar o maximizar una función objetivo.
El algoritmo GWO ha sido aplicado para la resolución de problemas en varios campos de estudios, entre los que se destacan lo siguientes:
● En un contexto de aprendizaje asistido por computadora en [3] se propone un enfoque de localización de nodos sumideros en las redes de sensores inalámbricos (WSN), respaldado por GWO para hallar los puntos nodales con más miembros vecinos en la red. Se estableció una función objetivo para evaluar tanto el tiempo de convergencia como el costo de energía, y mediante una serie de simulaciones apoyadas en experimentos para escenarios con nodos de diferentes tamaños, se encontró que el enfoque propuesto logró minimizar el costo promedio de energía y el tiempo requerido para crear una topología.
● Por otra parte, en [4] se presenta una versión multiobjetivo de GWO que recopila todas las soluciones óptimas de Pareto, y mediante un mecanismo de distancia basado en la cobertura de soluciones y GWO se eligen las mejores soluciones. Los resultados muestran su eficiencia en términos de tiempo de ejecución, distancia generalizada y, métrica de diversidad en un problema de ingeniería.
● Orientado a la seguridad en una central nuclear, en [5] se presenta un marco basado en una metaheurística inspirada en la naturaleza llamada Optimizador de Lobo Gris Multiobjetivo (MOGWO), que optimiza las especificaciones técnicas del sistema que elimina el calor residual en una central nuclear. La eficiencia de esta implementación en la optimización de las TS se demuestra comparando sus resultados con una técnica basada en enjambres denominada optimización multiobjetivo de enjambres de partículas (MOPSO).
● Dentro del marco de una optimización, en [6] se propone optimizar la fiabilidad y costo del Sistema de Soporte de Vida (SSL) en una cápsula espacial mediante el uso de un Optimizador de Lobo Gris Multiobjetivo (MOGWO). Esta implementación genera un frente interactivo de fiabilidad-coste, de los cuales los responsables de la toma de decisiones pueden elegir un punto de interés. Su rendimiento ha sido validado mediante la comparación de sus resultados con una técnica de optimización basada en el enjambre reconocida como optimización de enjambres de partículas multiobjetivo.
● Otro ejemplo de aplicación de GWO se describe en [7] donde se utiliza la fuerza de PSO y GWO para localizar la fuente de olor por un robot móvil, de tal forma que la pluma de olor se modela utilizando la distribución Gaussiana, el robot siempre está buscando la pluma en el espacio de trabajo y llegado el momento de que uno de los robots ingrese en las proximidades de la pluma, se calculan las nuevas posiciones del robot aplicando primero la concatenación de PSO y luego el Optimizador de Lobo Gris y viceversa. Este enfoque resulta válido y superior al realizar una comparación con el PSO Híbrido Refinado
Por otra parte, los estudios teóricos para mejorar el comportamiento de la metaheurística han derivado con las siguientes propuestas:
● Una propuesta que combina GWO con algunos mecanismos de PSO [8]. Este enfoque, mediante una secuencia caótica inicializa la posición de los lobos, de manera que se puede aumentar la diversidad de la manada, además se aplica la idea de PSO de escoger el mejor valor del individuo y el mejor valor de la manada de lobos para actualizar la información de posición de cada lobo gris, teniendo como resultado una mejor exploración global y manteniendo una mayor robustez frente a otros algoritmos.
● Así mismo en [9] se propone un nuevo algoritmo al que los autores denominaron Optimizador de Lobo Gris de distancia ponderada (wdGWO), el cual perturba la estrategia de reajuste de la localización, y usa la adición ponderada de las mejores localizaciones, reemplazando la estrategia anterior que consistía en imponer un simple promedio de las localizaciones mejores. La dimensión de los problemas puestos a prueba oscila entre 10 y 50 obteniendo resultados que respaldan el superior rendimiento de la propuesta.
● De manera similar un análisis de agrupamiento fue propuesto en [10] donde se hibrida el algoritmo Optimizador de Lobos Grises (GWO) con la Búsqueda Tabú (TS), surgiendo así (GWOTS) que puede ser utilizado para aplicaciones de agrupamiento. Para conocer el rendimiento de GWOTS se lo compara con diferentes metaheurísticas en varios conjuntos de datos de agrupamiento, y se obtiene que esta variante muestra un rendimiento mejorado en comparación con GWO.
● Otra mejora se propone en [11] donde se implementó una versión paralela del GWO. En este enfoque, la población se separa y divide en varias subpoblaciones, de manera que éstas exploran de forma independiente e intercambian los mejores individuos en cada número determinado de iteraciones. Los autores compararon esta nueva versión con el GWO original y obtuvieron que la versión paralela logra un mayor rendimiento en términos de calidad de la solución y velocidad de ejecución en cuatro funciones diferentes.
Como se puede apreciar, son pocos los esfuerzos que se han desarrollado en la comunidad científica para mejorar el rendimiento de la metaheurística QWO. Según nuestro criterio, esto no se debe a la falta de interés sobre la metaheurística, sino, porque se ha demostrado que su desempeño es muy bueno en su versión original.
MATERIALES Y MÉTODOS
El algoritmo de optimización de Lobos Grises fue propuesto en el 2014 como una forma de simular el comportamiento de las manadas de Lobos Grises en la actividad de caza de una presa. Este método comprende una jerarquía social entre los integrantes de la manada que oscilan entre 5 a 12 individuos. El líder de la manada de lobos grises (alpha) es el responsable de tomar decisiones para la manada, el siguiente nivel en la jerarquía (beta) ayuda al alpha en la toma de decisiones, el tercer nivel son lobos (delta) exploradores y centinelas, y finalmente el nivel más débil de la manada (omega) parece ser el menos importante y debe obedecer las órdenes de otros individuos [12].
En [13] los autores consideran que las características principales en la conducta de la manada de lobos son rastrear a la presa, iniciar la persecución y finalmente rodearla hasta que entre en un estado de inmovilidad. A continuación se describe a groso modo las dos etapas principales:
● Caza de la presa: Este proceso supone que los principales lobos tienen un mejor conocimiento de la ubicación de la presa y bajo esta premisa, obligan a los lobos omegas a cambiar de posición hacia donde ellos se encuentran. En este proceso la ubicación de la presa es revelada para que se lleven a cabo las otras acciones de la manada.
● Rodear a la presa: Luego que la presa está localizada, la manada comienza a rodearla. En esta actividad el lobo alpha, beta y delta guían la caza, mientras que los lobos omega buscan posiciones ventajosas alrededor de la presa. Para ello cada lobo de la manada actualiza su posición siguiendo unas funciones definidas en el modelo que determinan una nueva ubicación alrededor de la presa.
En cada iteración del algoritmo se actualiza la jerarquía de la manada y el proceso de caza y rodeo de la presa se vuelve a efectuar hasta que se alcance un máximo de ejecuciones. Las funciones involucradas en cada una de las etapas son descritas en [12] y [13] y su funcionamiento general se describe seguidamente.
Algoritmo GWO
Crear aleatoriamente la manada
Para cada iteración
Calcular los valores de aptitud de los lobos de la manada
Seleccionar:
Aplicar operador de caza
Aplicar operador de rodeo
Fin del para
Con el fin de evitar caer en óptimos locales, el algoritmo integra en la etapa de rodeo de la presa, un vector A que puede ser mayor que 1 o mejor que -1 de manera que fuerce a lobo a encontrar la presa, de esta forma, cuando A < 1 el lobo se aleja de un óptimo local (el lobo se aleja de la presa) para buscar otras mejores soluciones. Esta etapa también posee un elemento C que ayuda a descubrir nuevas soluciones y de esta forma fomentar la exploración del algoritmo.
Operadores de cambio de roles
Como se pudo observar en la descripción del algoritmo GWO, existen jerarquías (alpha, beta y delta) bien delimitadas entre los integrantes de la manada. Cada uno de ellos asume un rol diferente y va desde tomar las decisiones hasta quien busca la presa.
En todo caso, la propuesta original determina estos roles dependiendo únicamente de la calidad de cada uno de los agentes, de manera que el lobo alpha es el de mejor calidad en la manada, el beta el segundo mejor y delta el agente con tercera mejor calidad de la manada. Este mecanismo de selección elitista supone una rápida convergencia, pero en algunos casos se puede estancar en óptimos locales.
Por este motivo, a continuación definiremos 3 operadores para determinar las jerarquías en GWO y analizaremos su desempeño.
Asignación probabilística: Este método asigna roles de forma elitista como el modelo original, pero adicionalmente incorpora una probabilidad de cambio (prob), que determina cuándo se va a producir un cambio del lobo alpha por el beta y del beta con el delta.
Si random() < prob
cambio
por
Si random() < prob
cambio
por
Este operador intenta cambiar parcialmente las direcciones de búsqueda de la manada para evitar estancamientos.
Asignación por seguidores: En este método se asignan roles dependiendo de la cantidad de seguidores que tienen los lobos en la manda. Para ellos, se calcula la distancia euclidiana de cada lobo con los restantes de la manada y se selecciona como alpa el lobo con menor distancia promedio, beta el segundo menos distante y delta el tercero.
Calcular matriz de distancia (M_dist)
Obtener vector de distancia promedio de cada lobo(V_dist)
← lobo con menor distancia
← lobo con segunda menor distancia
← lobo con tercera menor distancia
Este mecanismo puede producir un exploración en grupo de la manada lo que puede derivar con la intensificación de las zonas exploradas.
Asignación combinada: En este operador se utilizan los dos criterios anteriores, de manera que la asignación de roles se desarrolla normalmente de manera elitista por calidad, y además se integra la posibilidad de realizar reasignación por seguidores. En este caso se establece una probabilidad de cambio, que de cumplirse, se hace efectiva la asignación de roles por seguidores.
Si random() < prob:
asignación de roles por seguidores
Esta idea intenta aprovechar los beneficios de la selección elitista y la selección por seguidores para establecer un mecanismo robusto de exploración.
RESULTADOS
En este apartado realizaremos el estudio experimental de la investigación. Para ello, utilizaremos la codificación presentada en el proyecto Evolopy y publicada en [14] y como conjunto de prueba utilizaremos 14 funciones continuas unimodales, multimodales descritas en [15] e implementadas también en el proyecto Evolopy.
Para el análisis comparativo, utilizamos un framework de técnicas estadísticas no paramétricas publicado en [16][17] y recomendadas para la comparación de resultados de técnicas metaheurísticas. Específicamente utilizaremos el test de Friedman para identificar diferencias significativas entre más de dos grupos y el test de Holm para identificar las diferencias.
Los parámetros utilizados en el estudio se detallan en la siguiente tabla:
Para el caso de los algoritmos GMO-Prob y GMO-Comb se realizó un estudio comparativo para determinar qué valor de probabilidad de cambio resulta más conveniente para el estudio. La tabla … muestra los resultados del análisis estadístico donde se puede notar que el test de Friedman identificó diferencias en los dos estudió (valor-p < 0.05) y en ambos casos la variante de mejor ranking (*) fue la que utiliza probabilidad de cambio de 0.9.
Seguidamente se presenta en la tabla .. los resultados del test de comparaciones múltiples de Holm. Se puede apreciar que los resultados obtenidos con probabilidad 0.9 son significativamente (valor-p < alpha) mejores que los obtenidos con probabilidad 0.3 en los dos algoritmos. En cambio, las diferencias encontradas con los resultados de 0.6, son diferentes pero no de manera significativa.
De lo anterior se puede concluir que los mejores resultados se obtienen utilizando probabilidad de cambio de 0.9 en cada algoritmo. En los análisis que siguen, cuando se presente el término GWO-Prob y GWO-Comb estaremos utilizando la variante con probabilidad 0.9.
En términos generales, las comparaciones estadísticas realizadas entre todos los algoritmos presentes en la gráfica xx determinaron que no son significativas las diferencias computadas en cuanto a la calidad de los resultados. No obstante se puede observar que el comportamiento de todos es muy similar, aunque las variantes que utilizan asignación por seguidores (GWO-Seg y GWO-Comb) presentan un mejor comportamiento en la función f9.
Analizando más detenidamente los resultados alcanzados en las 10 ejecuciones independientes de cada algoritmo (Figura.. ) se puede notar que GWO obtiene resultados bastante dispersos en las funciones F5, F9 y F14 al igual que GWO-Prob algo que determina algún grado de aleatoriedad en las soluciones. En cambio las variantes basadas en seguidores, presentan una mejor estabilidad de los resultados lo que resulta muy importante en el desempeño de una metaheurística.
CONCLUSIONES
En el presente trabajo se estudió el desempeño de algunas estrategias de selección de roles para la metaheurística GWO. En su comportamiento se utiliza una selección totalmente elitista que determina la jerarquía de los lobos en la manada. Nuestra propuesta tuvo en cuenta una selección probabilística, por seguidores y una combinación de ambos. Los resultados mostraron que:
● Los modelos basados en probabilidades como el GWO-Prob y GWO-Comb son más efectivo cuando utilizan un valor de probabilidad de cambio de 0.9 s (alpha-beta, beta-delta), incluso sus resultados resultaron ser significativamente diferentes a los obtenidos con valores bajo de probabilidad como 0.3.
● En el análisis comparativo general, los algoritmos basados en seguidores como el GWO-Comb y GWO-Seg consiguieron mejor desempeño en la función de prueba F9, aunque para los otros casos, los resultados fueron similares.
● Por último, un análisis de estabilidad de las soluciones corroboró que el algoritmo original GWO obtiene soluciones muy dispersas para varias de las funciones de prueba, no siendo así para el caso de los algoritmos basado en seguidores.
De manera general se pudo constatar que; tener en cuenta otras técnicas para seleccionar las jerarquías en la metaheurística GWO puede contribuir a un mejor desempeño del algoritmo, específicamente para mejorar la estabilidad en la convergencia del mismo.
Por tal motivo recomendamos que se utilicen los resultados de este trabajo para explorar otras técnicas que permitan seleccionar los roles de manera diferente. Asimismo se sugiere probar estas ideas en otras metaheurísticas que utilizan el mismo mecanismo elitista para elegir las jerarquías sociales en modelos de inteligencia colectiva.
Referencias
[1] H. Faris, I. Aljarah, M. A. Al-Betar, y S. Mirjalili, «Grey wolf optimizer: a review of recent variants and applications», Neural Comput. Appl., vol. 30, n.o 2, pp. 413-435, jul. 2018, doi: 10.1007/s00521-017-3272-5.
[2] «Grey Wolf Optimization-Based Improved Closed-Loop Speed Control for a BLDC Motor Drive | SpringerLink». https://link.springer.com/chapter/10.1007/978-981-13-1921-1_14 (accedido ago. 27, 2020).
[3] M. M. Fouad, A. I. Hafez, A. E. Hassanien, y V. Snasel, «Grey Wolves Optimizer-based localization approach in WSNs», en 2015 11th International Computer Engineering Conference (ICENCO), dic. 2015, pp. 256-260, doi: 10.1109/ICENCO.2015.7416358.
[4] P. Jangir y N. Jangir, «A new Non-Dominated Sorting Grey Wolf Optimizer (NS-GWO) algorithm: Development and application to solve engineering designs and economic constrained emission dispatch problem with integration of wind power», Eng. Appl. Artif. Intell., vol. 72, pp. 449-467, jun. 2018, doi: 10.1016/j.engappai.2018.04.018.
[5] A. Kumar, S. Pant, y M. Ram, «Gray wolf optimizer approach to the reliability-cost optimization of residual heat removal system of a nuclear power plant safety system», Qual. Reliab. Eng. Int., vol. 35, n.o 7, pp. 2228-2239, 2019, doi: 10.1002/qre.2499.
[6] A. Kumar, S. Pant, M. Ram, y S. Chaube, «Multi-objective grey wolf optimizer approach to the reliability-cost optimization of life support system in space capsule», Int. J. Syst. Assur. Eng. Manag., vol. 10, n.o 2, pp. 276-284, abr. 2019, doi: 10.1007/s13198-019-00781-1.
[7] U. Jain, R. Tiwari, y W. W. Godfrey, «Odor Source Localization by Concatenating Particle Swarm Optimization and Grey Wolf Optimizer», en Advanced Computational and Communication Paradigms, Singapore, 2018, pp. 145-153, doi: 10.1007/978-981-10-8237-5_14.
[8] Z. Teng, J. Lv, y L. Guo, «An improved hybrid grey wolf optimization algorithm», Soft Comput., vol. 23, n.o 15, pp. 6617-6631, ago. 2019, doi: 10.1007/s00500-018-3310-y.
[9] M. R. S. Malik, E. R. Mohideen, y L. Ali, «Weighted distance Grey wolf optimizer for global optimization problems», en 2015 IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), dic. 2015, pp. 1-6, doi: 10.1109/ICCIC.2015.7435714.
[10] I. Aljarah, M. Mafarja, A. A. Heidari, H. Faris, y S. Mirjalili, «Clustering analysis using a novel locality-informed grey wolf-inspired clustering approach», Knowl. Inf. Syst., vol. 62, n.o 2, pp. 507-539, feb. 2020, doi: 10.1007/s10115-019-01358-x.
[11] T.-S. Pan, T.-K. Dao, T.-T. Nguyen, y S.-C. Chu, «A Communication Strategy for Paralleling Grey Wolf Optimizer», en Genetic and Evolutionary Computing, Cham, 2016, pp. 253-262, doi: 10.1007/978-3-319-23207-2_25.
[12] H. Rezaei, O. Bozorg-Haddad, y X. Chu, «Grey Wolf Optimization (GWO) Algorithm», en Advanced Optimization by Nature-Inspired Algorithms, O. Bozorg-Haddad, Ed. Singapore: Springer, 2018, pp. 81-91.
[13] C. Muro, R. Escobedo, L. Spector, y R. P. Coppinger, «Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations», Behav. Processes, vol. 88, n.o 3, pp. 192-197, nov. 2011, doi: 10.1016/j.beproc.2011.09.006.
[14] H. Faris, I. Aljarah, S. M. Mirjalili, P. Castillo, y J. J. M. Guervós, «EvoloPy: An Open-source Nature-inspired Optimization Framework in Python», 2016, doi: 10.5220/0006048201710177.
[15] Suganthan et al., «Problem Definitions and Evaluation Criteria for the CEC 2005 Special Session on Real-Parameter Optimization», Nat. Comput., pp. 341-357, ene. 2005.
[16] J. Derrac, S. García, D. Molina, y F. Herrera, «A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms», Swarm Evol Comput, 2011, doi: 10.1016/j.swevo.2011.02.002.
[17] J. Derrac, S. García, S. Hui, P. N. Suganthan, y F. Herrera, «Analyzing convergence performance of evolutionary algorithms: A statistical approach», Inf. Sci., vol. 289, pp. 41-58, dic. 2014, doi: 10.1016/j.ins.2014.06.009.
