Genetic programming: How machine learning is evolving to solve math problems

In 1859, Charles Darwin published his groundbreaking theory of evolution in “On the Origin of Species,” where he introduced the world to the concept of natural selection. In the struggle for existence and reproduction, the strongest would survive, passing on their advantageous genes to their offspring. Never could Darwin have envisioned that centuries later, such a phenomenon would manifest in artificial intelligence.

A team of researchers at Google’s DeepMind lab has pioneered a model that combines large language models (LLMs) with the process of natural selection to create computer programs. In the model, the LLM create new offspring programs with mutations, while an “evaluator” algorithm acts as the mechanism of natural selection, eliminating invalid or weaker programs and allowing stronger ones to propagate to the next generation. When presented with a problem, their model — FunSearch — is tasked with developing multiple programs to solve it, where each program represents a distinct “genetic line.” Each program receives a score from the evaluator, and those with higher scores are passed into FunSearch’s LLM as prompts, giving birth to new programs. 

“The LLMs create new offspring programs with mutations, while an evaluator algorithm acts as the mechanism of natural selection.”

Rather than training a model that considers a number of factors and variables for a given problem and outputs a computer program, FunSearch uses a “Darwinian” approach by evolving the code in the solution programs themselves. Preliminary results from this approach show FunSearch was able to outperform traditional machine learning methods in solving difficult math problems.

The team applied a few more key techniques to improve the evolution of FunSearch programs. First, programs are divided into clusters, based on their “genetic signature,” which is calculated from their evaluator scores and code characteristics. Much like the Galapagos islands, each cluster exhibits unique traits, fostering diversity within the ecosystem. Underperforming clusters then die off, while promising ones continue to flourish and diversify. Researchers also provide boilerplate code to FunSearch, giving them greater control over the path of evolution — FunSearch only evolves code governing the critical program logic, while the researchers determine the code structure.

FunSearch has shown surprising results, exceeding state-of-the-art solutions to the mathematical problem known as the “cap-set problem.” The problem consists of finding the largest set of points (called a cap set) in a multidimensional grid where no three points lie on a line — it’s like playing a Connect Four ripoff called Connect Three and intentionally trying to lose. Solutions to the cap set problem are useful for designing error-correcting codes used in transmitting data between computers, as well as developing complex cryptography for online security.

FunSearch generated solutions (in the form of programs) that computed the largest cap sets ever found, and it was the single biggest step forward in solution size in the last 20 years. Moreover, by outperforming state-of-the-art computational solvers, FunSearch has cemented its status as a revolutionary tool in mathematical problem-solving.

“By outperforming state-of-the-art computational solvers, FunSearch has cemented its status as a revolutionary tool in mathematical problem-solving.”

FunSearch represents the newest breed of LLM applications. Complex logical optimization problems in math have been some of the largest hurdles for AI in the last decade, yet this model surpasses even human performance on these problems. These developments are exciting yet terrifying — what other capabilities might AI possess that remain undiscovered? For now, humanity remains in control, but as a species, we must adapt in tandem with technological progress. In “On the Origin of Species,” Darwin famously wrote, “It is not the strongest of the species that survives, not the most intelligent that survives. It is the one that is the most adaptable to change.”