Revelando los límites de la heurística de búsqueda local aprendida: ¿eres el más poderoso entre los mansos?

Tabla de enlaces

Resumen e introducción

Trabajo relacionado

Evaluación para Max-Cut

Evaluación para el SAT

Resumen y perspectivas, referencias

Materiales complementarios

Abstracto

En los últimos años, la combinación de redes neuronales con heurísticas de búsqueda local se ha vuelto popular en el campo de la optimización combinatoria. A pesar de sus considerables demandas computacionales, este enfoque ha mostrado resultados prometedores con una ingeniería manual mínima. Sin embargo, hemos identificado tres limitaciones críticas en la evaluación empírica de estos intentos de integración. En primer lugar, los casos con complejidad moderada y líneas de base débiles plantean un desafío a la hora de evaluar con precisión la eficacia de los enfoques basados en el aprendizaje. En segundo lugar, la ausencia de un estudio de ablación dificulta cuantificar y atribuir mejoras con precisión a la arquitectura de aprendizaje profundo. Por último, la generalización de las heurísticas aprendidas en diversas distribuciones sigue sin explorarse. En este estudio, llevamos a cabo una investigación exhaustiva sobre estas limitaciones identificadas. Sorprendentemente, demostramos que una heurística aprendida simple basada en Tabu Search supera las heurísticas aprendidas de última generación (SOTA) en términos de rendimiento y generalización. Nuestros hallazgos desafían los supuestos predominantes y abren vías interesantes para futuras investigaciones e innovación en optimización combinatoria.

1. INTRODUCCIÓN

Diseñar heurísticas efectivas o algoritmos de aproximación para problemas de optimización combinatoria (CO) NP-hard es una tarea desafiante, que a menudo requiere conocimiento del dominio y una extensa prueba y error. Así, la idea de automatizar este exigente y tedioso proceso de diseño a través del aprendizaje automático para aprender algoritmos que exploten la estructura inherente de un problema ha ganado un gran interés entre los investigadores (Bello et al., 2016; Khalil et al., 2017; Bengio et al. ., 2021; Dong et al., 2021). En particular, una parte considerable de estos trabajos (Khalil et al., 2017; Barrett et al., 2020; Yolcu y P´oczos, 2019) se han concentrado en el empleo de Graph Neural Networks (GNN) para problemas de CO. A pesar de las demandas computacionales, estos enfoques basados en GNN han demostrado un rendimiento competitivo en comparación con las heurísticas SOTA adaptadas a problemas específicos.

Si bien estos posibles avances son muy prometedores, persisten algunas preocupaciones. El rendimiento superior de las heurísticas aprendidas se puede atribuir a la selección de instancias y líneas de base específicas. Específicamente, si las líneas de base son débiles, las heurísticas aprendidas pueden superarlas fácilmente. Sin instancias difíciles y una selección de referencia adecuada, las heurísticas aprendidas pueden mostrar fácilmente un rendimiento comparable al de las heurísticas SOTA, y esto puede llevar a una sobreestimación de las capacidades reales de las heurísticas aprendidas. Además, en ocasiones se omiten las comparaciones con las heurísticas SOTA debido a los desafíos de escalabilidad de las arquitecturas de aprendizaje profundo.

Un subconjunto de enfoques basados en el aprendizaje (Khalil et al., 2017; Yolcu y P´oczos, 2019; Barrett et al., 2020, 2022) incorporan la funcionalidad o el comportamiento de las heurísticas tradicionales, ofreciendo potencialmente un rendimiento mejorado o mejorado al integrar heurísticas. principios con componentes de aprendizaje automático. Si falta una comparación exhaustiva con las heurísticas integradas y un estudio de ablación de la arquitectura de aprendizaje profundo, resulta difícil determinar la contribución específica de la arquitectura de aprendizaje profundo. En consecuencia, si las heurísticas integradas son sólidas, las heurísticas aprendidas pueden superar sin problemas a las heurísticas básicas, mientras que la arquitectura de aprendizaje profundo juega un papel pequeño.

Otro gran logro de la heurística aprendida (Khalil et al., 2017; Barrett et al., 2020; Toenshof et al., 2019), inicialmente entrenada en instancias más pequeñas y específicas de una distribución particular, muestra un rendimiento impresionante cuando se prueba en instancias más grandes de diferentes distribuciones. Este logro es un logro significativo, que se alinea con el objetivo central de emplear enfoques basados en el aprendizaje: mitigar la necesidad de una amplia personalización y conocimiento de dominio específico que a menudo requieren las heurísticas. Aunque las heurísticas clásicas con hiperparámetros también pueden enfrentar desafíos si se ajustan para una distribución específica, también pueden generalizarse en diferentes distribuciones. La investigación principal gira en torno a si las heurísticas aprendidas realmente demuestran una generalización superior en comparación con las heurísticas clásicas. Una comparación exhaustiva y reveladora de las heurísticas aprendidas con las heurísticas clásicas proporciona información valiosa sobre la generalización de las heurísticas aprendidas.

Las heurísticas aprendidas a menudo carecen de garantías teóricas, lo que hace que la evaluación empírica sea el único método para comprender las fortalezas y limitaciones de las metodologías propuestas. Creemos que varias cuestiones fundamentales, aunque fundamentales, siguen sin explorarse en la evaluación empírica de estos trabajos. Si bien estas consultas son pertinentes para todo tipo de heurísticas aprendidas, las preguntamos y respondemos analizando publicaciones revisadas por pares recientes y muy citadas centradas en el aprendizaje de heurísticas de búsqueda local. Nuestro objetivo no es proporcionar puntos de referencia exhaustivos para los problemas de CO discutidos en nuestro trabajo, sino ayudar a los futuros investigadores a evaluar sus investigaciones.

Concretamente, planteamos y respondemos las siguientes preguntas:

1. ¿Se pueden sobreparametrizar las heurísticas aprendidas? Absolutamente. Reemplazando el GNN en ECO-DQN con regresión lineal y utilizando un subconjunto de características de ECO-DQN (Barrett et al., 2020) que se vincula a Tabu Search (Glover, 1990), presentamos una versión recortada de ECO-DQN denominada SoftTabu. . Nuestro estudio demuestra que SoftTabu presenta un rendimiento y una generalización superiores en comparación con ECO-DQN para el problema NPhard Maximum-Cut (Max-Cut).

2. ¿Se puede atribuir el sesgo inicial al desempeño superior de las heurísticas aprendidas? Sí, demostramos que SoftTabu, una heurística aprendida, puede superar a S2V-DQN (Khalil et al., 2017) para el problema Max-Cut y a GNNSAT (Yolcu y P´oczos, 2019) para la satisfacibilidad booleana (SAT).

*3. ¿Puede la heurística aprendida demostrar una generalización superior debido al sesgo de selección de instancias? *Sí, demostramos que ECO-DQN muestra una generalización deficiente en instancias más difíciles y queda atrapado fácilmente en el espacio de búsqueda.