Los grandes modelos de lenguaje descubren heurísticas complementarias para la optimización combinatoria

La optimización combinatoria (OC) es esencial en la ciencia, la ingeniería y la industria, pero diseñar heurísticas eficaces para cada nueva variante de problema exige un profundo conocimiento del dominio y meses de iteración por parte de expertos. Este artículo presenta LACE (LLM-driven Algorithm Construction via Complementary Evolution), un marco que descompone el diseño de algoritmos en un esquema de entrada, un esquema de salida, una biblioteca de herramientas y una cartera de heurísticas —la interfaz I-O-T-H— y refina la cartera mediante evolución complementaria con restricciones de tiempo. La interfaz define un contrato de problema verificado que orienta la capacidad del gran modelo de lenguaje hacia el razonamiento algorítmico de alto nivel en lugar de la implementación específica del problema, mientras que la evolución complementaria genera y selecciona iterativamente heurísticas especializadas capaces de resolver instancias heterogéneas dentro de estrictos presupuestos de tiempo de ejecución. En 36 problemas clásicos de CO-Bench, LACE alcanza una puntuación media de 0,945, frente a 0,870 del método basado en LLM más potente existente y 0,571 del prompting directo de LLM sin ningún marco, lo que sitúa la ganancia en el marco y no en el modelo. En cuatro problemas estructuralmente nuevos, LACE alcanza 0,97–0,99, mientras que cinco líneas base existentes basadas en LLM no logran producir ningún algoritmo factible. Estos resultados demuestran que el descubrimiento eficaz de algoritmos para tales problemas puede automatizarse en gran medida.

(Fuente：Nature)