Algoritmo de aceptación de umbral basado en listas con operador de vecindario mejorado para el problema de la mochila 0-1
Autores: Wu, Liangcheng; Lin, Kai; Lin, Xiaoyu; Lin, Juan
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Algoritmo de aceptación de umbral basado en listas con operador de vecindario mejorado para el problema de la mochila 0-1
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Búsqueda local
Lista de umbrales
Ajuste de parámetros
Problema de la mochila
Bit-flip
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 37
Citaciones: Sin citaciones
El algoritmo de aceptación de umbral basado en listas (LBTA) es un método sofisticado de búsqueda local que utiliza una lista de umbrales para agilizar el proceso de ajuste de parámetros en el algoritmo de aceptación de umbral tradicional (TA). Este artículo propone una versión mejorada de búsqueda local del algoritmo LBTA específicamente diseñada para resolver el problema de la mochila 0-1 (0-1 KP). Para mantener una lista dinámica de umbrales, se diseña una estrategia de actualización de umbrales factible para aceptar modificaciones adaptativas durante el proceso de búsqueda. Además, el algoritmo incorpora un operador de cambio de bits mejorado diseñado para generar una solución vecina con un nivel controlado de perturbación, fomentando así la exploración dentro del espacio de soluciones. Cada solución de prueba producida por este operador pasa por una fase de reparación utilizando un operador de reparación codicioso híbrido que incorpora tanto un operador de adición basado en densidad como un operador de adición basado en valor para facilitar la optimización. El rendimiento del algoritmo LBTA fue evaluado frente a varios enfoques metaheurísticos de vanguardia en una serie de instancias a gran escala. Los resultados de la simulación demuestran que el algoritmo LBTA supera o es competitivo con otras metaheurísticas líderes en el campo.
Descripción
El algoritmo de aceptación de umbral basado en listas (LBTA) es un método sofisticado de búsqueda local que utiliza una lista de umbrales para agilizar el proceso de ajuste de parámetros en el algoritmo de aceptación de umbral tradicional (TA). Este artículo propone una versión mejorada de búsqueda local del algoritmo LBTA específicamente diseñada para resolver el problema de la mochila 0-1 (0-1 KP). Para mantener una lista dinámica de umbrales, se diseña una estrategia de actualización de umbrales factible para aceptar modificaciones adaptativas durante el proceso de búsqueda. Además, el algoritmo incorpora un operador de cambio de bits mejorado diseñado para generar una solución vecina con un nivel controlado de perturbación, fomentando así la exploración dentro del espacio de soluciones. Cada solución de prueba producida por este operador pasa por una fase de reparación utilizando un operador de reparación codicioso híbrido que incorpora tanto un operador de adición basado en densidad como un operador de adición basado en valor para facilitar la optimización. El rendimiento del algoritmo LBTA fue evaluado frente a varios enfoques metaheurísticos de vanguardia en una serie de instancias a gran escala. Los resultados de la simulación demuestran que el algoritmo LBTA supera o es competitivo con otras metaheurísticas líderes en el campo.