Resumen:Este trabajo aplica redes de flujo generativo (GFlowNets) a tres problemas de optimización de gráficos: el problema del vendedor ambulante, el árbol de expansión mínimo y el camino más corto. GFlowNets son modelos generativos que aprenden a muestrear soluciones proporcionalmente a una función de recompensa. Los modelos se entrenan utilizando la pérdida de equilibrio de trayectoria para construir soluciones secuencialmente, seleccionando bordes para árboles de expansión, nodos para caminos y ciudades para recorridos. Los experimentos en instancias de referencia de diferentes tamaños muestran que GFlowNets aprende a encontrar soluciones óptimas. Para cada tipo de problema, se probaron múltiples configuraciones de gráficos con diferentes números de nodos. Las soluciones generadas coinciden con las de los algoritmos clásicos (Dijkstra para el camino más corto, Kruskal para árboles de expansión y solucionadores exactos para TSP). La convergencia del entrenamiento depende de la complejidad del problema, y el número de episodios necesarios para la estabilización de pérdidas aumenta a medida que crece el tamaño del gráfico. Una vez que el entrenamiento converge, las soluciones generadas coinciden con los óptimos conocidos de los algoritmos clásicos en las instancias probadas. Este trabajo demuestra que los modelos generativos pueden resolver problemas de optimización combinatoria mediante políticas aprendidas. La principal ventaja de este enfoque basado en el aprendizaje es la escalabilidad computacional: mientras que los algoritmos clásicos tienen una complejidad fija por instancia, los GFlowNets amortizan el cálculo mediante el entrenamiento. Con suficientes recursos computacionales, el marco podría potencialmente escalar a instancias de problemas más grandes donde los métodos exactos clásicos se vuelven inviables.
Publicado originalmente en export.arxiv.org el 27 de octubre de 2025.
Ver fuente original
