Un algoritmo de búsqueda armónica discreta simplificado guiado por heurísticas para resolver el problema de la mochila 0-1
Autores: Zheng, Fuyuan; Cheng, Kanglong; Yang, Kai; Li, Ning; Lin, Yu; Zhong, Yiwen
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Un algoritmo de búsqueda armónica discreta simplificado guiado por heurísticas para resolver el problema de la mochila 0-1
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Búsqueda de armonía
Algoritmo
Optimización discreta
Problema de la mochila
Heurísticas
Metaheurística
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
El algoritmo de búsqueda de armonía (HS) es una metaheurística novedosa que se ha utilizado ampliamente para resolver problemas de optimización tanto continuos como discretos. Con el fin de mejorar el rendimiento y simplificar la implementación del algoritmo HS para resolver el problema de la mochila binaria (0-1KP), este artículo propone un algoritmo de búsqueda de armonía discreta simplificado guiado por heurísticas (SDHS) que no utiliza operadores de búsqueda aleatoria y tiene solo un parámetro intrínseco, el tamaño de la memoria de armonía. El algoritmo SDHS utiliza un operador de consideración de memoria para construir una solución factible, y luego la solución construida se mejora aún más mediante un operador de ajuste de tono a nivel de solución. Dos heurísticas, la razón de beneficio-peso de un artículo y el beneficio de un artículo, se utilizan para guiar de forma codiciosa el operador de consideración de memoria y el operador de ajuste de tono a nivel de solución, respectivamente. En el operador de consideración de memoria, los artículos se consideran en orden no ascendente de la razón de beneficio-peso asignada desde la memoria de armonía. En el operador de ajuste de tono a nivel de solución, se intenta seleccionar los artículos que no están en la mochila en orden no ascendente de beneficio. El algoritmo SDHS supera a varios algoritmos de última generación, con una mejora promedio del 0.55% en la calidad de las soluciones en instancias de problemas grandes.
Descripción
El algoritmo de búsqueda de armonía (HS) es una metaheurística novedosa que se ha utilizado ampliamente para resolver problemas de optimización tanto continuos como discretos. Con el fin de mejorar el rendimiento y simplificar la implementación del algoritmo HS para resolver el problema de la mochila binaria (0-1KP), este artículo propone un algoritmo de búsqueda de armonía discreta simplificado guiado por heurísticas (SDHS) que no utiliza operadores de búsqueda aleatoria y tiene solo un parámetro intrínseco, el tamaño de la memoria de armonía. El algoritmo SDHS utiliza un operador de consideración de memoria para construir una solución factible, y luego la solución construida se mejora aún más mediante un operador de ajuste de tono a nivel de solución. Dos heurísticas, la razón de beneficio-peso de un artículo y el beneficio de un artículo, se utilizan para guiar de forma codiciosa el operador de consideración de memoria y el operador de ajuste de tono a nivel de solución, respectivamente. En el operador de consideración de memoria, los artículos se consideran en orden no ascendente de la razón de beneficio-peso asignada desde la memoria de armonía. En el operador de ajuste de tono a nivel de solución, se intenta seleccionar los artículos que no están en la mochila en orden no ascendente de beneficio. El algoritmo SDHS supera a varios algoritmos de última generación, con una mejora promedio del 0.55% en la calidad de las soluciones en instancias de problemas grandes.