Mejorando el rendimiento del algoritmo metaheurístico a través de población estructurada y teoría de juegos evolutivos
Autores: Escobar-Cuevas, Héctor; Cuevas, Erik; Luque-Chang, Alberto; Barba-Toscano, Oscar; Pérez-Cisneros, Marco
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Mejorando el rendimiento del algoritmo metaheurístico a través de población estructurada y teoría de juegos evolutivos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Diversidad
Algoritmos metaheurísticos
Estrategias
Exploración
Explotación
Competencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 19
Citaciones: Sin citaciones
La diversidad es crucial para los algoritmos metaheurísticos. Evita la convergencia temprana, equilibra la exploración y la explotación, y ayuda a evitar óptimos locales. Los algoritmos metaheurísticos tradicionales tienden a depender de una sola estrategia para generar nuevas soluciones, lo que a menudo resulta en una falta de diversidad. Por el contrario, el empleo de múltiples estrategias fomenta una variedad de comportamientos de búsqueda y un grupo diverso de soluciones potenciales, mejorando así la exploración del espacio de búsqueda. La Teoría de Juegos Evolutiva (EGT) modifica las estrategias de los agentes a través de la competencia, promoviendo estrategias exitosas y eliminando las más débiles. Las poblaciones estructuradas, en contraposición a las no estructuradas, conservan estrategias diversas a través de la competencia localizada, lo que significa que la estrategia de un individuo es influenciada solo por un subconjunto o grupo de la población y no por todos los elementos. Este documento presenta un nuevo método metaheurístico basado en EGT aplicado a poblaciones estructuradas. Inicialmente, los individuos se posicionan cerca de regiones óptimas utilizando el algoritmo Metropolis-Hastings. Posteriormente, a cada individuo se le dota de una estrategia de búsqueda única. Considerando un cierto número de grupos, la población completa se segmenta. Dentro de estos grupos, el método mejora la eficiencia de búsqueda y la calidad de la solución adaptando todas las estrategias a través de una competencia intra-cluster. Para evaluar la efectividad del método propuesto, se ha comparado con varios algoritmos metaheurísticos conocidos a través de un conjunto de 30 funciones de prueba. Los resultados indicaron que la nueva metodología superó a las técnicas establecidas, ofreciendo soluciones de mayor calidad y tasas de convergencia más rápidas.
Descripción
La diversidad es crucial para los algoritmos metaheurísticos. Evita la convergencia temprana, equilibra la exploración y la explotación, y ayuda a evitar óptimos locales. Los algoritmos metaheurísticos tradicionales tienden a depender de una sola estrategia para generar nuevas soluciones, lo que a menudo resulta en una falta de diversidad. Por el contrario, el empleo de múltiples estrategias fomenta una variedad de comportamientos de búsqueda y un grupo diverso de soluciones potenciales, mejorando así la exploración del espacio de búsqueda. La Teoría de Juegos Evolutiva (EGT) modifica las estrategias de los agentes a través de la competencia, promoviendo estrategias exitosas y eliminando las más débiles. Las poblaciones estructuradas, en contraposición a las no estructuradas, conservan estrategias diversas a través de la competencia localizada, lo que significa que la estrategia de un individuo es influenciada solo por un subconjunto o grupo de la población y no por todos los elementos. Este documento presenta un nuevo método metaheurístico basado en EGT aplicado a poblaciones estructuradas. Inicialmente, los individuos se posicionan cerca de regiones óptimas utilizando el algoritmo Metropolis-Hastings. Posteriormente, a cada individuo se le dota de una estrategia de búsqueda única. Considerando un cierto número de grupos, la población completa se segmenta. Dentro de estos grupos, el método mejora la eficiencia de búsqueda y la calidad de la solución adaptando todas las estrategias a través de una competencia intra-cluster. Para evaluar la efectividad del método propuesto, se ha comparado con varios algoritmos metaheurísticos conocidos a través de un conjunto de 30 funciones de prueba. Los resultados indicaron que la nueva metodología superó a las técnicas establecidas, ofreciendo soluciones de mayor calidad y tasas de convergencia más rápidas.