La importancia de la función de transferencia en la resolución del problema de la mochila de unión de conjuntos basado en el algoritmo de búsqueda de polillas discreto
Autores: Feng, Yanhong; An, Haizhong; Gao, Xiangyun
Idioma: Inglés
Editor: MDPI
Año: 2018
Acceso abierto
Artículo científico
2018
La importancia de la función de transferencia en la resolución del problema de la mochila de unión de conjuntos basado en el algoritmo de búsqueda de polillas discreto
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Algoritmo de búsqueda de polillas
Problemas de optimización discreta
Función de transferencia
Espacio de búsqueda
Problema de mochila de unión de conjuntos
Tasa de convergencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 35
Citaciones: Sin citaciones
El algoritmo de búsqueda de polillas (MS), originalmente propuesto para resolver problemas de optimización continua, es un novedoso algoritmo metaheurístico inspirado en la naturaleza. En la actualidad, parece haber poco interés en utilizar MS para resolver problemas de optimización discreta. Una de las formas más comunes y eficientes de discretizar MS es utilizar una función de transferencia, que se encarga de mapear un espacio de búsqueda continuo a un espacio de búsqueda discreto. En este documento, se combinan doce funciones de transferencia divididas en tres familias, en forma de S (llamadas S1, S2, S3 y S4), en forma de V (llamadas V1, V2, V3 y V4), y otras formas (llamadas O1, O2, O3 y O4), con MS, y luego se proponen doce versiones discretas de algoritmos MS para resolver el problema de la mochila de la unión de conjuntos (SUKP). Se emplean tres grupos de quince instancias de SUKP para evaluar la importancia de estas funciones de transferencia. Los resultados muestran que O4 es la mejor función de transferencia cuando se combina con MS para resolver SUKP. Mientras tanto, se demuestra la importancia de la función de transferencia en términos de mejorar la calidad de las soluciones y la tasa de convergencia también.
Descripción
El algoritmo de búsqueda de polillas (MS), originalmente propuesto para resolver problemas de optimización continua, es un novedoso algoritmo metaheurístico inspirado en la naturaleza. En la actualidad, parece haber poco interés en utilizar MS para resolver problemas de optimización discreta. Una de las formas más comunes y eficientes de discretizar MS es utilizar una función de transferencia, que se encarga de mapear un espacio de búsqueda continuo a un espacio de búsqueda discreto. En este documento, se combinan doce funciones de transferencia divididas en tres familias, en forma de S (llamadas S1, S2, S3 y S4), en forma de V (llamadas V1, V2, V3 y V4), y otras formas (llamadas O1, O2, O3 y O4), con MS, y luego se proponen doce versiones discretas de algoritmos MS para resolver el problema de la mochila de la unión de conjuntos (SUKP). Se emplean tres grupos de quince instancias de SUKP para evaluar la importancia de estas funciones de transferencia. Los resultados muestran que O4 es la mejor función de transferencia cuando se combina con MS para resolver SUKP. Mientras tanto, se demuestra la importancia de la función de transferencia en términos de mejorar la calidad de las soluciones y la tasa de convergencia también.