Búsqueda divertida

FunSearch (abreviatura de búsqueda en el espacio de funciones ) es un método de inteligencia artificial desarrollado por Google DeepMind para descubrir programas informáticos que resuelven problemas matemáticos y algorítmicos . Combina un modelo de lenguaje extenso con un evaluador automatizado y un procedimiento de búsqueda evolutiva , generando programas candidatos, puntuándolos y utilizando los de mejor rendimiento para producir nuevos candidatos. ^{[ 1 ]}

Google DeepMind anunció FunSearch en 2023, y el artículo asociado se publicó en Nature . ^{[ 2 ]} El sistema se aplicó al problema del conjunto de tapas en combinatoria extremal y al problema de empaquetamiento de contenedores en línea , donde encontró nuevas construcciones matemáticas y nuevas heurísticas de empaquetamiento . ^{[ 3 ] [ 4 ]}

FunSearch plantea un problema como una búsqueda en programas informáticos en lugar de una búsqueda directa en soluciones individuales. El usuario proporciona una especificación del problema, una función de evaluación y un programa inicial o un esqueleto de programa . En cada iteración, FunSearch selecciona programas existentes de una base de datos , prioriza los programas con mayor puntuación, crea una solicitud para un modelo de lenguaje grande preentrenado y le pide al modelo que genere programas modificados. Los programas generados son ejecutados y puntuados por el evaluador. ^{[ 1 ]}

El proceso de búsqueda utiliza un método evolutivo basado en islas, diseñado para mantener un conjunto diverso de programas candidatos y reducir el riesgo de quedar atrapado en óptimos locales . Según el artículo original, una ventaja de este enfoque es que FunSearch genera programas que, en ocasiones, pueden ser inspeccionados, simplificados e interpretados por los investigadores, en lugar de producir únicamente una respuesta numérica final o una larga lista de objetos. ^{[ 1 ]}

FunSearch puede describirse como una búsqueda en un espacio de fragmentos de programa, generalmente funciones incrustadas en un esqueleto de programa fijo.${\displaystyle {\mathcal {F}}}$ser un espacio de funciones candidatas y dejar${\displaystyle S:{\mathcal {F}}\to \mathbb {R} }$ser una puntuación de evaluador obtenida al ejecutar un solucionador fijo que llama a la función candidata. Dada una función inicial${\displaystyle f_{0}}$FunSearch mantiene una base de datos${\displaystyle D}$de funciones evaluadas y válidas. Muestre repetidamente funciones de alta puntuación de${\displaystyle D}$, los utiliza para construir indicaciones para un modelo de lenguaje grande y le pide al modelo que genere una nueva función candidata.${\displaystyle f'}$La nueva función se ejecuta dentro del esqueleto del programa específico del problema y es evaluada por el evaluador. Si la función generada es válida, se vuelve a agregar a${\displaystyle D}$, permitiendo que las indicaciones posteriores se basen en candidatos anteriores más sólidos. ^{[ 1 ]}

En forma simplificada, el bucle de búsqueda se puede escribir como:

$${\displaystyle D\leftarrow \{(f_{0},S(f_{0}))\}}$$

$${\displaystyle f'\sim \operatorname {LLM} (\operatorname {prompt} (f_{1},\ldots ,f_{k})),\quad (f_{i},S(f_{i}))\in D}$$

$${\displaystyle {\text{si }}f'{\text{ es válido, entonces }}D\leftarrow D\cup \{(f',S(f'))\}.}$$

El objetivo idealizado es encontrar una función candidata con una puntuación alta del evaluador,

$${\displaystyle f^{*}\in \operatorname {*} {arg\,max}_{f\in {\mathcal {F}}}S(f),}$$

Aunque en la práctica FunSearch devuelve la mejor función válida descubierta durante la búsqueda. La implementación original utiliza un proceso evolutivo basado en islas para preservar la diversidad entre las funciones candidatas, favoreciendo al mismo tiempo los programas con mayor puntuación. ^{[ 1 ] [ 4 ]}

Google DeepMind publicó el software FunSearch en un repositorio público de GitHub junto con el artículo de FunSearch. El repositorio incluye ejemplos y datos para conjuntos de tapas , conjuntos admisibles, empaquetamiento de contenedores en línea , conjuntos independientes en productos fuertes de grafos de ciclos , conjuntos sin esquinas y experimentos relacionados. También incluye una implementación de un solo hilo del pipeline de FunSearch , aunque el repositorio señala que no incluye los modelos de lenguaje , el entorno de ejecución ni la infraestructura distribuida utilizados en los experimentos originales. El repositorio indica que su software está licenciado bajo la Licencia Apache 2.0 , mientras que otros materiales están licenciados bajo la Licencia Creative Commons Atribución 4.0 Internacional . ^{[ 6 ]}

En un artículo de Nature News & Views, Jean-Baptiste Mouret describió FunSearch como un sistema que conecta la programación genética con grandes modelos de lenguaje, y escribió que el trabajo demostraba cómo los modelos de lenguaje podían ayudar a evolucionar los programas informáticos. El artículo caracterizó el sistema como una prueba de concepto para el descubrimiento matemático asistido por IA. ^{[ 3 ]}

• AlphaDev
• AlphaEvolve
• Geometría Alfa
• AlphaTensor
• Demostración automatizada de teoremas
• Algoritmo evolutivo
• Lista de algoritmos de inteligencia artificial
• Lista de problemas sin resolver en matemáticas
• Síntesis de programas

• Sitio web oficial
• funsearch en GitHub