Evaluación de Importancia de Características por Permutación por Lotes y Bigrafo Específico del Problema para Aprender a Ramificar
Autores: Niu, Yajie; Peng, Chen; Liao, Bolin
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Evaluación de Importancia de Características por Permutación por Lotes y Bigrafo Específico del Problema para Aprender a Ramificar
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Eléctrica y Electrónica
Palabras clave
Algoritmo
Ramificación y acotación
Aprendizaje para ramificar
Modelos de aprendizaje automático
Aprendizaje por imitación
Esquema de entrenamiento rápido de conjuntos de datos pequeños
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
El algoritmo de ramificación y acotamiento para optimización combinatoria generalmente se basa en una gran cantidad de heurísticas expertas hechas a mano, y una dirección de investigación, llamada aprendizaje para ramificar, propone reemplazar las heurísticas expertas en ramificación y acotamiento con modelos de aprendizaje automático. Los estudios actuales en esta área suelen utilizar un enfoque de aprendizaje por imitación (IL); sin embargo, en la práctica, el IL a menudo sufre de muestras de entrenamiento limitadas. Por lo tanto, se ha enfatizado que un esquema de entrenamiento rápido con un pequeño conjunto de datos para IL en aprendizaje para ramificar vale la pena estudiar, de modo que otros métodos, como el aprendizaje por refuerzo, puedan ser utilizados para el entrenamiento posterior. Por lo tanto, este documento se centra en la parte de IL de un enfoque de entrenamiento mixto, donde se considera un esquema de entrenamiento rápido con un pequeño conjunto de datos. Las contribuciones son las siguientes. Primero, para calcular métricas de importancia de características para que la representación de bigraph de vanguardia pueda reducirse de manera efectiva para cada tipo de problema, se propone un método de evaluación de importancia de características por permutación por lotes, que permuta características dentro de cada lote en el pase hacia adelante. En segundo lugar, basándose en la importancia evaluada de las características de bigraph, se propone una representación de bigraph reducida para cada uno de los problemas de referencia. Los resultados experimentales en cuatro problemas de referencia de MILP muestran que nuestro método mejora la precisión de ramificación en un 8% y reduce el tiempo de solución en un 18% en promedio bajo el esquema de entrenamiento rápido con un pequeño conjunto de datos en comparación con el método de aprendizaje para ramificar basado en bigraph de vanguardia. El código fuente está disponible en línea en GitHub.
Descripción
El algoritmo de ramificación y acotamiento para optimización combinatoria generalmente se basa en una gran cantidad de heurísticas expertas hechas a mano, y una dirección de investigación, llamada aprendizaje para ramificar, propone reemplazar las heurísticas expertas en ramificación y acotamiento con modelos de aprendizaje automático. Los estudios actuales en esta área suelen utilizar un enfoque de aprendizaje por imitación (IL); sin embargo, en la práctica, el IL a menudo sufre de muestras de entrenamiento limitadas. Por lo tanto, se ha enfatizado que un esquema de entrenamiento rápido con un pequeño conjunto de datos para IL en aprendizaje para ramificar vale la pena estudiar, de modo que otros métodos, como el aprendizaje por refuerzo, puedan ser utilizados para el entrenamiento posterior. Por lo tanto, este documento se centra en la parte de IL de un enfoque de entrenamiento mixto, donde se considera un esquema de entrenamiento rápido con un pequeño conjunto de datos. Las contribuciones son las siguientes. Primero, para calcular métricas de importancia de características para que la representación de bigraph de vanguardia pueda reducirse de manera efectiva para cada tipo de problema, se propone un método de evaluación de importancia de características por permutación por lotes, que permuta características dentro de cada lote en el pase hacia adelante. En segundo lugar, basándose en la importancia evaluada de las características de bigraph, se propone una representación de bigraph reducida para cada uno de los problemas de referencia. Los resultados experimentales en cuatro problemas de referencia de MILP muestran que nuestro método mejora la precisión de ramificación en un 8% y reduce el tiempo de solución en un 18% en promedio bajo el esquema de entrenamiento rápido con un pequeño conjunto de datos en comparación con el método de aprendizaje para ramificar basado en bigraph de vanguardia. El código fuente está disponible en línea en GitHub.