Retropropagación caótica de grafos inspirada en el cerebro para la optimización combinatoria

Área de la Ciencia:

• Inteligencia Artificial
• Aprendizaje Automático
• Ciencia Computacional

Sus antecedentes:

• Las redes neuronales de grafos (GNN) ofrecen soluciones aproximadas eficientes para problemas de optimización combinatoria (COP).
• Los métodos actuales de retropropagación en GNN a menudo caen en mínimos locales, lo que limita el rendimiento de la optimización.
• Los métodos existentes luchan por igualar el estado del arte (SOTA) en la resolución de COPs a gran escala.

Objetivo del estudio:

• Desarrollar un nuevo algoritmo de entrenamiento para GNN que supere las limitaciones de la retropropagación tradicional.
• Mejorar el rendimiento de optimización de las GNN para resolver problemas complejos de optimización combinatoria.
• Introducir un método de entrenamiento inspirado en la dinámica caótica para mejorar el aprendizaje de GNN.

Principales métodos:

• Se introdujo la Retropropagación Caótica de Grafos (CGBP), un nuevo algoritmo de entrenamiento para GNN.
• Se incorporó una función de pérdida local en el proceso de entrenamiento de GNN para inducir dinámica caótica.
• Se aprovechó la ergodicidad global y la pseudorandomidad de la dinámica caótica para un aprendizaje efectivo de GNN.

Principales resultados:

• CGBP demuestra un aprendizaje eficiente y global de GNN para resolver COPs.
• Se aplicó CGBP a los problemas de Conjunto Independiente Máximo (MIS), Corte Máximo (MC) y Coloreo de Grafos (GC).
• Se logró un rendimiento competitivo o superior en comparación con los métodos SOTA en conjuntos de datos de referencia a gran escala.

Conclusiones:

• CGBP aborda eficazmente el problema de los mínimos locales en el entrenamiento de GNN para COPs.
• La dinámica caótica en CGBP permite una optimización eficiente y global.
• CGBP sirve como un módulo universal enchufable para mejorar los métodos de aprendizaje existentes para una mejor búsqueda y rendimiento.