Algoritmo genético de clave aleatoria sesgado con búsqueda local aplicado al problema de máxima diversidad
Autores: Silva, Geiza; Leite, André; Ospina, Raydonal; Leiva, Víctor; Figueroa-Zúñiga, Jorge; Castro, Cecilia
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Algoritmo genético de clave aleatoria sesgado con búsqueda local aplicado al problema de máxima diversidad
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problema de diversidad máxima
Subconjunto
Diversidad
Algoritmos
Algoritmo genético
Búsqueda local
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
El problema de máxima diversidad (MDP) tiene como objetivo seleccionar un subconjunto con un número predeterminado de elementos de un conjunto dado, maximizando la diversidad entre ellos. Este problema NP-duro requiere algoritmos eficientes que puedan generar soluciones de alta calidad en un tiempo computacional razonable. En este estudio, proponemos un enfoque novedoso que combina el algoritmo genético de tecla aleatoria sesgada (BRKGA) con la búsqueda local para abordar el MDP. Nuestro estudio computacional utiliza un conjunto completo de instancias de MDPLib y demuestra el rendimiento promedio superior de nuestro algoritmo propuesto en comparación con los resultados de la literatura existente. El MDP tiene una amplia gama de aplicaciones prácticas, incluyendo biología, ecología y gestión. Proporcionamos direcciones para investigaciones futuras para mejorar el rendimiento del algoritmo y explorar su aplicabilidad en escenarios del mundo real.
Descripción
El problema de máxima diversidad (MDP) tiene como objetivo seleccionar un subconjunto con un número predeterminado de elementos de un conjunto dado, maximizando la diversidad entre ellos. Este problema NP-duro requiere algoritmos eficientes que puedan generar soluciones de alta calidad en un tiempo computacional razonable. En este estudio, proponemos un enfoque novedoso que combina el algoritmo genético de tecla aleatoria sesgada (BRKGA) con la búsqueda local para abordar el MDP. Nuestro estudio computacional utiliza un conjunto completo de instancias de MDPLib y demuestra el rendimiento promedio superior de nuestro algoritmo propuesto en comparación con los resultados de la literatura existente. El MDP tiene una amplia gama de aplicaciones prácticas, incluyendo biología, ecología y gestión. Proporcionamos direcciones para investigaciones futuras para mejorar el rendimiento del algoritmo y explorar su aplicabilidad en escenarios del mundo real.