logo móvil
Contáctanos

Modelando y resolviendo el problema de la mochila con un algoritmo optimizador de equilibrio multiobjetivo basado en la distancia de congestión ponderada

Autores: Wang, Ziqian; Huang, Xin; Zhang, Yan; Lv, Danju; Li, Wei; Zhu, Zhicheng; Dong, Jian"e

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Modelando y resolviendo el problema de la mochila con un algoritmo optimizador de equilibrio multiobjetivo basado en la distancia de congestión ponderada


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Problema de la mochila
Algoritmo optimizador de equilibrio multiobjetivo
Distancia de congestión ponderada
Algoritmos de inteligencia de enjambre
Soluciones de frente de Pareto
Manejo de restricciones discretas

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 22

Citaciones: Sin citaciones


Descripción
El problema de la mochila es un típico problema de optimización combinatoria biobjetivo, en el que se logra maximizar el valor de los elementos empaquetados de forma concurrente con la minimización del peso de la carga. Debido a los objetivos conflictivos del problema de la mochila y a la propiedad discreta típica de los elementos involucrados, los algoritmos de inteligencia de enjambre son comúnmente empleados. La diversidad de combinaciones óptimas en el problema de la mochila se ha convertido en un punto focal, que implica encontrar múltiples soluciones de empaquetado con el mismo valor y peso. Con este propósito, este artículo propone un Algoritmo Optimizador de Equilibrio Multiobjetivo basado en la Distancia de Congestión Ponderada (MOEO_WCD). El algoritmo emplea un método de clasificación no dominada para encontrar un conjunto de soluciones de frente de Pareto en lugar de una sola solución óptima, ofreciendo múltiples opciones de toma de decisiones basadas en las necesidades variables de los tomadores de decisiones. Además, MOEO_WCD mejora el mecanismo de generación de pool balanceado e incorpora un incentivo de congestión ponderado, enfatizando la diversidad de soluciones de combinación de empaquetado bajo los objetivos de valor y peso para explorar más soluciones de frente de Pareto. Teniendo en cuenta las características discretas del problema de optimización de combinación de mochila, nuestro algoritmo también incorpora un manejo adecuado de restricciones discretas. Este artículo diseña múltiples conjuntos de problemas de optimización combinatoria de mochila multiobjetivo basados en el número de mochilas, el número de elementos y los pesos y valores de los elementos. Este artículo compara cinco algoritmos adecuados para resolver problemas multiobjetivo: MODE, MO-PSO-MM, MO-Ring-PSO-SCD, NSGA-II y DN-NSGAII. Para evaluar el rendimiento del algoritmo, este artículo propone un nuevo índice de cobertura de conjunto de soluciones para evaluación. También se utilizó el indicador de hipervolumen para evaluar la diversidad de los algoritmos. Los resultados muestran que nuestro algoritmo MOEO-WCD logra una cobertura óptima del frente de Pareto compuesto de referencia en el espacio de decisión de cuatro problemas de mochila. Los resultados experimentales indican que nuestro algoritmo MOEO_WCD logra una cobertura óptima del frente de Pareto compuesto de referencia en el espacio de decisión para cuatro conjuntos de problemas de mochila. Aunque nuestro algoritmo MOEO_WCD cubre menos del frente compuesto en el espacio objetivo en comparación con el algoritmo MODE para el problema de la mochila 1, su cobertura de las soluciones de referencia integradas en el espacio de decisión es mayor que la del algoritmo MODE. Los experimentos demuestran el rendimiento superior del algoritmo MOEO_WCD en instancias de problemas de optimización combinatoria de mochila biobjetivo, lo que proporciona una solución importante para la búsqueda de diversidad en soluciones de optimización combinatoria multiobjetivo.

Otros recursos que podrían interesarte

Temas Virtualpro