Content area
Usingthis representation, a genetic-programming system 'mutates' a program by randomly changing one node in the tree to a different value (Fig. la). Instead of replacing random parts of a syntax tree, an LLM can generate a variation of a program written in a standard programming language, such as Python. To do so, a simple, but powerful, approach is to select two programs, concatenate them, and ask the LLM to complete the program using the concatenated pair as a prompt - resulting in the generation of a third program (Fig. 1b). Romera-Paredes et al. used this fresh approach to genetic programming to find ways of solving mathematical problems in optimization and geometry that were better than the best attempts of human programmers.
Computer science
A branch of computer science known as genetic programming has been given a boost with the application of large language models that are trained on the combined intuition of the world's programmers. See p.468
Although machines outperform humans at many tasks, from manufacturing to playing games12, they are commonly considered incapableofcreating or inventing things. But this is changing: over the past three years, technology companies have been releasing artificial intelligence (AI) programs that can draw or write with impressive creativity. Scientific discovery might be the next target, as computers start to uncover knowledge that has eluded scientists. On page 468, Romera-Paredes et al.3 report an autonomous mathematical discovery for which AI was used - not to check a proof or to execute tedious computations, but to solve open problems. This proof of concept is likely to be followed by other programs like it, as software becomes a creative contributor to scientific discoveries.
Romera-Paredes and colleagues' work is the latest step in a long line of research that attempts to create programs automatically by taking inspiration from biological evolution, a field called genetic programming4. The process starts with running many random programs to find out how well each one can solve a target problem. The best programs are then selected, copied and randomly modified, in a manner that is similar to genetic variation. The process then begins again with these modified programs, which are selected and modified until one program solves the problem adequately.
The key question in genetic programming is how to represent programs so that they can be modified easily, but meaningfully, by random variation. In other words, what is the 'DNA' of a computer program? For instance, adding random letters to a program written in the Python scripting language is unlikely to result in a program that follows Python syntax, which means that the vast majority of modified programs cannot be executed by the computer, and are therefore useless.
To approach this problem, geneticprogramming researchers have taken inspiration from compilers, which are programs that transform text written in a programming language into code that a computer can interpret. Compilers represent programs in the computer's memory with an abstract 'tree' structure. Usingthis representation, a genetic-programming system 'mutates' a program by randomly changing one node in the tree to a different value (Fig. la). For example, a mutation might replace a plus sign with a minus sign, or the number 2 with a 3. Similarly, the system mixes two programs by exchanging randomly chosen sub trees from the two separate programs.
This approach has given rise to many fascinating results. For the past 20 years, a competition has been held to showcase how evolution-inspired algorithms measure up to those made by humans (see human-competitive.org/awards). One example is a program called Eureqa, which automatically finds the equations of motion for classic dynamical systems, such as a swinging pendulum, using data alone5. Another example is the GenProg system6, which provides a way of automatically repairing existingopen-source programs - and even earned its developers money doing so.
Nevertheless, genetic programming has so far been successful only for equations or short sections of programs, typically comprising a dozen lines. The reason for this is that programming is hard. It requires the right syntax and intuition about what could work. And every change requires the programmer to take the context of the rest of the program into account. In general, random variations in syntax trees are rarely meaningful and the genetic-programming process yields results only through millions of repetitions.
This situation is changing with large language models (LLMs). These large neural networks are trained to predict the next words in a line of code for a given context (known as a prompt), after having been fed millions of lines of code. This large body of examples gives the model an 'intuition' about what a typical programmer would write in the same situation. LLMs that are specialized in code generation are used daily by many programmers in the same way that people use the autocomplete function available in many apps - the model guesses the most likely text to follow each piece of code, so there is no need to type it or to memorize the function names.
LLMs are game-changing tools for programmers, but they might also be the missing piece of the genetic-programming puzzle: they embed the knowledge ofthousands of programmers to generate meaningful code for a given context. Instead of replacing random parts of a syntax tree, an LLM can generate a variation of a program written in a standard programming language, such as Python. To do so, a simple, but powerful, approach is to select two programs, concatenate them, and ask the LLM to complete the program using the concatenated pair as a prompt - resulting in the generation of a third program (Fig. 1b). The result will probably have valid syntax and be meaningful in its context. However, it might not be exact or optimal. This is why the process must be iterated, by selecting the highest-performing programs, generating variations using the LLM and then testing these variations.
Romera-Paredes et al. used this fresh approach to genetic programming to find ways of solving mathematical problems in optimization and geometry that were better than the best attempts of human programmers. The authors' system shows promise, but it still requires guidance in the form of an 'evaluate function', which nudges the model in the most productive direction. A more direct way would be to use a 'validate function', which determines when the problem has been solved. The authors' evaluate function is similar to a school test that has been designed to reward learning by striking a balance between easy and difficult questions.
Using automatic programmers, such as the one developed by Romera-Paredes and colleagues, will require the same level of careful judgement in crafting the right tests. However, the authors' innovation demonstrates the power and potential of using LLMs to write creative programs for solving problems, and this advance is part of a developing success story7,8. As the problems intended for these models become ever more relevant, it's clear that LLMs will breathe new life into genetic programming.
Jean-Baptiste Mouret is at the French National Institute for Research in Digital Science and Technology (INRIA), the University of Lorraine, and the French national research agency (CNRS), 54000 Nancy, France.
e-mail: [email protected]
1. Silver, D. et al. Nature 529,484-489 (2016).
2. Hsu, F.-H. Behind Deep Blue: Building the Computer that Defeated the World Chess Champion (Princeton Univ. Press, 2002).
3. Romera-Paredes, B. et al. Nature 625, 468-475 (2024).
4. Koza, J. R. Genetic Programming (MIT, 1992).
5. Schmidt, M. & Lipson, H. Science 324, 81-85 (2009).
6. Le Goues, C., Dewey-Vogt, M., Forrest, S. A. & Weimer, W. R. In Proc. 34th International Conference on Software Engineering 3-13 (IEEE, 2012).
7. Lehman, J. etal. in Handbook of Evolutionary Machine Learning (eds Banzhaf, W. et al.) Ch. 11 (Springer Nature Singapore, 2024).
8. Meyerson, E. et al. Preprint at https://arxiv.org/ abs/2302.12170 (2023).
Copyright Nature Publishing Group Jan 18, 2024