logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro