Un nuevo algoritmo de optimización de mariposa monarca con operador de actualización de posición global para problemas de mochila 0-1 a gran escala
Autores: Feng, Yanhong; Yu, Xu; Wang, Gai-Ge
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Un nuevo algoritmo de optimización de mariposa monarca con operador de actualización de posición global para problemas de mochila 0-1 a gran escala
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problema de la mochila
Optimización de la mariposa monarca
Operador de actualización de posición global
Problema NP-completo
Esquema de codificación dicotómica
Diseño Ortogonal
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 30
Citaciones: Sin citaciones
Como un subconjunto significativo de la familia de problemas de optimización discreta, el problema de la mochila 0-1 (0-1 KP) ha recibido considerable atención entre los investigadores relevantes. La optimización de la mariposa monarca (MBO) es un algoritmo metaheurístico reciente inspirado en el comportamiento de migración de las mariposas monarca. El MBO original se propone para resolver problemas de optimización continua. Este artículo presenta una nueva optimización de la mariposa monarca con un operador de actualización de posición global (GMBO), que puede abordar el 0-1 KP conocido como un problema NP-completo. El operador de actualización de posición global se incorpora para ayudar a todas las mariposas monarca a moverse rápidamente hacia la mejor posición global. Además, se adopta un esquema de codificación de dicotomía para representar mariposas monarca para resolver el 0-1 KP. Además, se utiliza un operador de reparación de dos etapas específico para reparar las soluciones inviables y optimizar aún más las soluciones viables. Finalmente, se emplea el Diseño Ortogonal (OD) para encontrar los parámetros más adecuados. Se utilizan dos conjuntos de instancias de 0-1 KP de baja dimensionalidad y tres tipos de 15 instancias de 0-1 KP de alta dimensionalidad para verificar la capacidad del GMBO propuesto. Se lleva a cabo un estudio comparativo extenso del GMBO con cinco algoritmos clásicos y dos algoritmos de vanguardia. Los resultados experimentales indican claramente que el GMBO puede lograr mejores soluciones en casi todas las instancias de 0-1 KP y supera significativamente al resto.
Descripción
Como un subconjunto significativo de la familia de problemas de optimización discreta, el problema de la mochila 0-1 (0-1 KP) ha recibido considerable atención entre los investigadores relevantes. La optimización de la mariposa monarca (MBO) es un algoritmo metaheurístico reciente inspirado en el comportamiento de migración de las mariposas monarca. El MBO original se propone para resolver problemas de optimización continua. Este artículo presenta una nueva optimización de la mariposa monarca con un operador de actualización de posición global (GMBO), que puede abordar el 0-1 KP conocido como un problema NP-completo. El operador de actualización de posición global se incorpora para ayudar a todas las mariposas monarca a moverse rápidamente hacia la mejor posición global. Además, se adopta un esquema de codificación de dicotomía para representar mariposas monarca para resolver el 0-1 KP. Además, se utiliza un operador de reparación de dos etapas específico para reparar las soluciones inviables y optimizar aún más las soluciones viables. Finalmente, se emplea el Diseño Ortogonal (OD) para encontrar los parámetros más adecuados. Se utilizan dos conjuntos de instancias de 0-1 KP de baja dimensionalidad y tres tipos de 15 instancias de 0-1 KP de alta dimensionalidad para verificar la capacidad del GMBO propuesto. Se lleva a cabo un estudio comparativo extenso del GMBO con cinco algoritmos clásicos y dos algoritmos de vanguardia. Los resultados experimentales indican claramente que el GMBO puede lograr mejores soluciones en casi todas las instancias de 0-1 KP y supera significativamente al resto.