genetic programming research paper

An official website of the United States government

The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

• Publications
• Account settings

Preview improvements coming to the PMC website in October 2024. Learn More or Try it out now .

• Advanced Search
• Journal List
• Springer Nature - PMC COVID-19 Collection

A review on genetic algorithm: past, present, and future

Sourabh katoch.

Computer Science and Engineering Department, National Institute of Technology, Hamirpur, India

Sumit Singh Chauhan

Vijay kumar.

In this paper, the analysis of recent advances in genetic algorithms is discussed. The genetic algorithms of great interest in research community are selected for analysis. This review will help the new and demanding researchers to provide the wider vision of genetic algorithms. The well-known algorithms and their implementation are presented with their pros and cons. The genetic operators and their usages are discussed with the aim of facilitating new researchers. The different research domains involved in genetic algorithms are covered. The future research directions in the area of genetic operators, fitness function and hybrid algorithms are discussed. This structured review will be helpful for research and graduate teaching.

Introduction

In the recent years, metaheuristic algorithms are used to solve real-life complex problems arising from different fields such as economics, engineering, politics, management, and engineering [ 113 ]. Intensification and diversification are the key elements of metaheuristic algorithm. The proper balance between these elements are required to solve the real-life problem in an effective manner. Most of metaheuristic algorithms are inspired from biological evolution process, swarm behavior, and physics’ law [ 17 ]. These algorithms are broadly classified into two categories namely single solution and population based metaheuristic algorithm (Fig.  1 ). Single-solution based metaheuristic algorithms utilize single candidate solution and improve this solution by using local search. However, the solution obtained from single-solution based metaheuristics may stuck in local optima [ 112 ]. The well-known single-solution based metaheuristics are simulated annealing, tabu search (TS), microcanonical annealing (MA), and guided local search (GLS). Population-based metaheuristics utilizes multiple candidate solutions during the search process. These metaheuristics maintain the diversity in population and avoid the solutions are being stuck in local optima. Some of well-known population-based metaheuristic algorithms are genetic algorithm (GA) [ 135 ], particle swarm optimization (PSO) [ 101 ], ant colony optimization (ACO) [ 47 ], spotted hyena optimizer (SHO) [ 41 ], emperor penguin optimizer (EPO) [ 42 ], and seagull optimization (SOA) [ 43 ].

Classification of metaheuristic Algorithms

Among the metaheuristic algorithms, Genetic algorithm (GA) is a well-known algorithm, which is inspired from biological evolution process [ 136 ]. GA mimics the Darwinian theory of survival of fittest in nature. GA was proposed by J.H. Holland in 1992. The basic elements of GA are chromosome representation, fitness selection, and biological-inspired operators. Holland also introduced a novel element namely, Inversion that is generally used in implementations of GA [ 77 ]. Typically, the chromosomes take the binary string format. In chromosomes, each locus (specific position on chromosome) has two possible alleles (variant forms of genes) - 0 and 1. Chromosomes are considered as points in the solution space. These are processed using genetic operators by iteratively replacing its population. The fitness function is used to assign a value for all the chromosomes in the population [ 136 ]. The biological-inspired operators are selection, mutation, and crossover. In selection, the chromosomes are selected on the basis of its fitness value for further processing. In crossover operator, a random locus is chosen and it changes the subsequences between chromosomes to create off-springs. In mutation, some bits of the chromosomes will be randomly flipped on the basis of probability [ 77 , 135 , 136 ]. The further development of GA based on operators, representation, and fitness has diminished. Therefore, these elements of GA are focused in this paper.

The main contribution of this paper are as follows:

• The general framework of GA and hybrid GA are elaborated with mathematical formulation.
• The various types of genetic operators are discussed with their pros and cons.
• The variants of GA with their pros and cons are discussed.
• The applicability of GA in multimedia fields is discussed.

The main aim of this paper is two folds. First, it presents the variants of GA and their applicability in various fields. Second, it broadens the area of possible users in various fields. The various types of crossover, mutation, selection, and encoding techniques are discussed. The single-objective, multi-objective, parallel, and hybrid GAs are deliberated with their advantages and disadvantages. The multimedia applications of GAs are elaborated.

The remainder of this paper is organized as follows: Section 2 presents the methodology used to carry out the research. The classical genetic algorithm and genetic operators are discussed in Section 3 . The variants of genetic algorithm with pros and cons are presented in Section 4 . Section 5 describes the applications of genetic algorithm. Section 6 presents the challenges and future research directions. The concluding remarks are drawn in Section 7 .

Research methodology

PRISMA’s guidelines were used to conduct the review of GA [ 138 ]. A detailed search has been done on Google scholar and PubMed for identification of research papers related to GA. The important research works found during the manual search were also added in this paper. During search, some keywords such as “Genetic Algorithm” or “Application of GA” or “operators of GA” or “representation of GA” or “variants of GA” were used. The selection and rejection of explored research papers are based on the principles, which is mentioned in Table ​ Table1 1 .

Selection criterion for shortlisted research papers

Total 27,64,792 research papers were explored on Google Scholar, PubMed and manual search. The research work related to genetic algorithm for multimedia applications were also included. During the screening of research papers, all the duplicate papers and papers published before 2007 were discarded. 4340 research papers were selected based on 2007 and duplicate entries. Thereafter, 4050 research papers were eliminated based on titles. 220 research papers were eliminated after reading of abstract. 70 research papers were left after third round of screening. 40 more research papers were discarded after full paper reading and facts found in the papers. After the fourth round of screening, final 30 research papers are selected for review.

Based on the relevance and quality of research, 30 papers were selected for evaluation. The relevance of research is decided through some criteria, which is mentioned in Table ​ Table1. 1 . The selected research papers comprise of genetic algorithm for multimedia applications, advancement of their genetic operators, and hybridization of genetic algorithm with other well-established metaheuristic algorithms. The pros and cons of genetic operators are shown in preceding section.

In this section, the basic structure of GA and its genetic operators are discussed with pros and cons.

Classical GA

Genetic algorithm (GA) is an optimization algorithm that is inspired from the natural selection. It is a population based search algorithm, which utilizes the concept of survival of fittest [ 135 ]. The new populations are produced by iterative use of genetic operators on individuals present in the population. The chromosome representation, selection, crossover, mutation, and fitness function computation are the key elements of GA. The procedure of GA is as follows. A population ( Y ) of n chromosomes are initialized randomly. The fitness of each chromosome in Y is computed. Two chromosomes say C1 and C2 are selected from the population Y according to the fitness value. The single-point crossover operator with crossover probability (C p ) is applied on C1 and C2 to produce an offspring say O . Thereafter, uniform mutation operator is applied on produced offspring ( O ) with mutation probability (M p ) to generate O′ . The new offspring O′ is placed in new population. The selection, crossover, and mutation operations will be repeated on current population until the new population is complete. The mathematical analysis of GA is as follows [ 126 ]:

GA dynamically change the search process through the probabilities of crossover and mutation and reached to optimal solution. GA can modify the encoded genes. GA can evaluate multiple individuals and produce multiple optimal solutions. Hence, GA has better global search capability. The offspring produced from crossover of parent chromosomes is probable to abolish the admirable genetic schemas parent chromosomes and crossover formula is defined as [ 126 ]:

where g is the number of generations, and G is the total number of evolutionary generation set by population. It is observed from Eq.( 1 ) that R is dynamically changed and increase with increase in number of evolutionary generation. In initial stage of GA, the similarity between individuals is very low. The value of R should be low to ensure that the new population will not destroy the excellent genetic schema of individuals. At the end of evolution, the similarity between individuals is very high as well as the value of R should be high.

According to Schema theorem, the original schema has to be replaced with modified schema. To maintain the diversity in population, the new schema keep the initial population during the early stage of evolution. At the end of evolution, the appropriate schema will be produced to prevent any distortion of excellent genetic schema [ 65 , 75 ]. Algorithm 1 shows the pseudocode of classical genetic algorithm.

Algorithm 1: Classical Genetic Algorithm (GA)

Genetic operators

GAs used a variety of operators during the search process. These operators are encoding schemes, crossover, mutation, and selection. Figure ​ Figure2 2 depicts the operators used in GAs.

Operators used in GA

Encoding schemes

For most of the computational problems, the encoding scheme (i.e., to convert in particular form) plays an important role. The given information has to be encoded in a particular bit string [ 121 , 183 ]. The encoding schemes are differentiated according to the problem domain. The well-known encoding schemes are binary, octal, hexadecimal, permutation, value-based, and tree.

Binary encoding is the commonly used encoding scheme. Each gene or chromosome is represented as a string of 1 or 0 [ 187 ]. In binary encoding, each bit represents the characteristics of the solution. It provides faster implementation of crossover and mutation operators. However, it requires extra effort to convert into binary form and accuracy of algorithm depends upon the binary conversion. The bit stream is changed according the problem. Binary encoding scheme is not appropriate for some engineering design problems due to epistasis and natural representation.

In octal encoding scheme, the gene or chromosome is represented in the form of octal numbers (0–7). In hexadecimal encoding scheme, the gene or chromosome is represented in the form of hexadecimal numbers (0–9, A-F) [ 111 , 125 , 187 ]. The permutation encoding scheme is generally used in ordering problems. In this encoding scheme, the gene or chromosome is represented by the string of numbers that represents the position in a sequence. In value encoding scheme, the gene or chromosome is represented using string of some values. These values can be real, integer number, or character [ 57 ]. This encoding scheme can be helpful in solving the problems in which more complicated values are used. As binary encoding may fail in such problems. It is mainly used in neural networks for finding the optimal weights.

In tree encoding, the gene or chromosome is represented by a tree of functions or commands. These functions and commands can be related to any programming language. This is very much similar to the representation of repression in tree format [ 88 ]. This type of encoding is generally used in evolving programs or expressions. Table ​ Table2 2 shows the comparison of different encoding schemes of GA.

Comparison of different encoding schemes

Selection techniques

Selection is an important step in genetic algorithms that determines whether the particular string will participate in the reproduction process or not. The selection step is sometimes also known as the reproduction operator [ 57 , 88 ]. The convergence rate of GA depends upon the selection pressure. The well-known selection techniques are roulette wheel, rank, tournament, boltzmann, and stochastic universal sampling.

Roulette wheel selection maps all the possible strings onto a wheel with a portion of the wheel allocated to them according to their fitness value. This wheel is then rotated randomly to select specific solutions that will participate in formation of the next generation [ 88 ]. However, it suffers from many problems such as errors introduced by its stochastic nature. De Jong and Brindle modified the roulette wheel selection method to remove errors by introducing the concept of determinism in selection procedure. Rank selection is the modified form of Roulette wheel selection. It utilizes the ranks instead of fitness value. Ranks are given to them according to their fitness value so that each individual gets a chance of getting selected according to their ranks. Rank selection method reduces the chances of prematurely converging the solution to a local minima [ 88 ].

Tournament selection technique was first proposed by Brindle in 1983. The individuals are selected according to their fitness values from a stochastic roulette wheel in pairs. After selection, the individuals with higher fitness value are added to the pool of next generation [ 88 ]. In this method of selection, each individual is compared with all n-1 other individuals if it reaches the final population of solutions [ 88 ]. Stochastic universal sampling (SUS) is an extension to the existing roulette wheel selection method. It uses a random starting point in the list of individuals from a generation and selects the new individual at evenly spaced intervals [ 3 ]. It gives equal chance to all the individuals in getting selected for participating in crossover for the next generation. Although in case of Travelling Salesman Problem, SUS performs well but as the problem size increases, the traditional Roulette wheel selection performs relatively well [ 180 ].

Boltzmann selection is based on entropy and sampling methods, which are used in Monte Carlo Simulation. It helps in solving the problem of premature convergence [ 118 ]. The probability is very high for selecting the best string, while it executes in very less time. However, there is a possibility of information loss. It can be managed through elitism [ 175 ]. Elitism selection was proposed by K. D. Jong (1975) for improving the performance of Roulette wheel selection. It ensures the elitist individual in a generation is always propagated to the next generation. If the individual having the highest fitness value is not present in the next generation after normal selection procedure, then the elitist one is also included in the next generation automatically [ 88 ]. The comparison of above-mentioned selection techniques are depicted in Table ​ Table3 3 .

Comparison of different selection techniques

Crossover operators

Crossover operators are used to generate the offspring by combining the genetic information of two or more parents. The well-known crossover operators are single-point, two-point, k-point, uniform, partially matched, order, precedence preserving crossover, shuffle, reduced surrogate and cycle.

In a single point crossover, a random crossover point is selected. The genetic information of two parents which is beyond that point will be swapped with each other [ 190 ]. Figure ​ Figure3 3 shows the genetic information after swapping. It replaced the tail array bits of both the parents to get the new offspring.

Swapping genetic information after a crossover point

In a two point and k-point crossover, two or more random crossover points are selected and the genetic information of parents will be swapped as per the segments that have been created [ 190 ]. Figure ​ Figure4 4 shows the swapping of genetic information between crossover points. The middle segment of the parents is replaced to generate the new offspring.

Swapping genetic information between crossover points

In a uniform crossover, parent cannot be decomposed into segments. The parent can be treated as each gene separately. We randomly decide whether we need to swap the gene with the same location of another chromosome [ 190 ]. Figure ​ Figure5 5 depicts the swapping of individuals under uniform crossover operation.

Swapping individual genes

Partially matched crossover (PMX) is the most frequently used crossover operator. It is an operator that performs better than most of the other crossover operators. The partially matched (mapped) crossover was proposed by D. Goldberg and R. Lingle [ 66 ]. Two parents are choose for mating. One parent donates some part of genetic material and the corresponding part of other parent participates in the child. Once this process is completed, the left out alleles are copied from the second parent [ 83 ]. Figure ​ Figure6 6 depicts the example of PMX.

Partially matched crossover (PMX) [ 117 ]

Order crossover (OX) was proposed by Davis in 1985. OX copies one (or more) parts of parent to the offspring from the selected cut-points and fills the remaining space with values other than the ones included in the copied section. The variants of OX are proposed by different researchers for different type of problems. OX is useful for ordering problems [ 166 ]. However, it is found that OX is less efficient in case of Travelling Salesman Problem [ 140 ]. Precedence preserving crossover (PPX) preserves the ordering of individual solutions as present in the parent of offspring before the application of crossover. The offspring is initialized to a string of random 1’s and 0’s that decides whether the individuals from both parents are to be selected or not. In [ 169 ], authors proposed a modified version of PPX for multi-objective scheduling problems.

Shuffle crossover was proposed by Eshelman et al. [ 20 ] to reduce the bias introduced by other crossover techniques. It shuffles the values of an individual solution before the crossover and unshuffles them after crossover operation is performed so that the crossover point does not introduce any bias in crossover. However, the utilization of this crossover is very limited in the recent years. Reduced surrogate crossover (RCX) reduces the unnecessary crossovers if the parents have the same gene sequence for solution representations [ 20 , 139 ]. RCX is based on the assumption that GA produces better individuals if the parents are sufficiently diverse in their genetic composition. However, RCX cannot produce better individuals for those parents that have same composition. Cycle crossover was proposed by Oliver [ 140 ]. It attempts to generate an offspring using parents where each element occupies the position by referring to the position of their parents [ 140 ]. In the first cycle, it takes some elements from the first parent. In the second cycle, it takes the remaining elements from the second parent as shown in Fig.  7 .

Cycle Crossover (CX) [ 140 ]

Table ​ Table4 4 shows the comparison of crossover techniques. It is observed from Table ​ Table4 4 that single and k-point crossover techniques are easy to implement. Uniform crossover is suitable for large subsets. Order and cycle crossovers provide better exploration than the other crossover techniques. Partially matched crossover provides better exploration. The performance of partially matched crossover is better than the other crossover techniques. Reduced surrogate and cycle crossovers suffer from premature convergence.

Comparison of different crossover techniques

Mutation operators

Mutation is an operator that maintains the genetic diversity from one population to the next population. The well-known mutation operators are displacement, simple inversion, and scramble mutation. Displacement mutation (DM) operator displaces a substring of a given individual solution within itself. The place is randomly chosen from the given substring for displacement such that the resulting solution is valid as well as a random displacement mutation. There are variants of DM are exchange mutation and insertion mutation. In Exchange mutation and insertion mutation operators, a part of an individual solution is either exchanged with another part or inserted in another location, respectively [ 88 ].

The simple inversion mutation operator (SIM) reverses the substring between any two specified locations in an individual solution. SIM is an inversion operator that reverses the randomly selected string and places it at a random location [ 88 ]. The scramble mutation (SM) operator places the elements in a specified range of the individual solution in a random order and checks whether the fitness value of the recently generated solution is improved or not [ 88 ]. Table ​ Table5 5 shows the comparison of different mutation techniques.

Comparison of different mutation operators

Table ​ Table6 6 shows the best combination of encoding scheme, mutation, and crossover techniques. It is observed from Table ​ Table6 6 that uniform and single-point crossovers can be used with most of encoding and mutation operators. Partially matched crossover is used with inversion mutation and permutation encoding scheme provides the optimal solution.

Best combination of various operators under optimal Environment

Variants of GA

Various variants of GA’s have been proposed by researchers. The variants of GA are broadly classified into five main categories namely, real and binary coded, multiobjective, parallel, chaotic, and hybrid GAs. The pros and cons of these algorithms with their application has been discussed in the preceding subsections.

Real and binary coded GAs

Based on the representation of chromosomes, GAs are categorized in two classes, namely binary and real coded GAs.

Binary coded GAs

The binary representation was used to encode GA and known as binary GA. The genetic operators were also modified to carry out the search process. Payne and Glen [ 153 ] developed a binary GA to identify the similarity among molecules. They used binary representation for position of molecule and their conformations. However, this method has high computational complexity. Longyan et al. [ 203 ] investigated three different method for wind farm design using binary GA (BGA). Their method produced better fitness value and farm efficiency. Shukla et al. [ 185 ] utilized BGA for feature subset selection. They used mutual information maximization concept for selecting the significant features. BGAs suffer from Hamming cliffs, uneven schema, and difficulty in achieving precision [ 116 , 199 ].

Real-coded GAs

Real-coded GAs (RGAs) have been widely used in various real-life applications. The representation of chromosomes is closely associated with real-life problems. The main advantages of RGAs are robust, efficient, and accurate. However, RGAs suffer from premature convergence. Researchers are working on RGAs to improve their performance. Most of RGAs are developed by modifying the crossover, mutation and selection operators.

The searching capability of crossover operators are not satisfactory for continuous search space. The developments in crossover operators have been done to enhance their performance in real environment. Wright [ 210 ] presented a heuristics crossover that was applied on parents to produce off-spring. Michalewicz [ 135 ] proposed arithmetical crossover operators for RGAs. Deb and Agrawal [ 34 ] developed a real-coded crossover operator, which is based on characteristics of single-point crossover in BGA. The developed crossover operator named as simulated binary crossover (SBX). SBX is able to overcome the Hamming cliff, precision, and fixed mapping problem. The performance of SBX is not satisfactory in two-variable blocked function. Eshelman et al. [ 53 ] utilized the schemata concept to design the blend crossover for RGAs. The unimodal normal distribution crossover operator (UNDX) was developed by Ono et al. [ 144 ]. They used ellipsoidal probability distribution to generate the offspring. Kita et al. [ 106 ] presented a multi-parent UNDX (MP-UNDX), which is the extension of [ 144 ]. However, the performance of RGA with MP-UNDX is much similar to UNDX. Deep and Thakur [ 39 ] presented a Laplace crossover for RGAs, which is based on Laplacian distribution. Chuang et al. [ 27 ] developed a direction based crossover to further explore the all possible search directions. However, the search directions are limited. The heuristic normal distribution crossover operator was developed by Wang et al. [ 207 ]. It generates the cross-generated offspring for better search operation. However, the better individuals are not considered in this approach. Subbaraj et al. [ 192 ] proposed Taguchi self-adaptive RCGA. They used Taguchi method and simulated binary crossover to exploit the capable offspring.

Mutation operators generate diversity in the population. The two main challenges have to tackle during the application of mutation. First, the probability of mutation operator that was applied on population. Second, the outlier produced in chromosome after mutation process. Michalewicz [ 135 ] presented uniform and non-uniform mutation operators for RGAs. Michalewicz and Schoenauer [ 136 ] developed a special case of uniform mutation. They developed boundary mutation. Deep and Thakur [ 38 ] presented a novel mutation operator based on power law and named as power mutation. Das and Pratihar [ 30 ] presented direction-based exponential mutation operator. They used direction information of variables. Tang and Tseng [ 196 ] presented a novel mutation operator for enhancing the performance of RCGA. Their approach was fast and reliable. However, it stuck in local optima for some applications. Deb et al. [ 35 ] developed polynomial mutation that was used in RCGA. It provides better exploration. However, the convergence speed is slow and stuck in local optima. Lucasius et al. [ 129 ] proposed a real-coded genetic algorithm (RCGA). It is simple and easy to implement. However, it suffers from local optima problem. Wang et al. [ 205 ] developed multi-offspring GA and investigated their performance over single point crossover. Wang et al. [ 206 ] stated the theoretical basis of multi-offspring GA. The performance of this method is better than non-multi-offspring GA. Pattanaik et al. [ 152 ] presented an improvement in the RCGA. Their method has better convergence speed and quality of solution. Wang et al. [ 208 ] proposed multi-offspring RCGA with direction based crossover for solving constrained problems.

Table ​ Table7 7 shows the mathematical formulation of genetic operators in RGAs.

Mathematical formulation of genetic operators in RGAs

Multiobjective GAs

Multiobjective GA (MOGA) is the modified version of simple GA. MOGA differ from GA in terms of fitness function assignment. The remaining steps are similar to GA. The main motive of multiobjective GA is to generate the optimal Pareto Front in the objective space in such a way that no further enhancement in any fitness function without disturbing the other fitness functions [ 123 ]. Convergence, diversity, and coverage are main goal of multiobjective GAs. The multiobjective GAs are broadly categorized into two categories namely, Pareto-based, and decomposition-based multiobjective GAs [ 52 ]. These techniques are discussed in the preceding subsections.

Pareto-based multi-objective GA

The concept of Pareto dominance was introduced in multiobjective GAs. Fonseca and Fleming [ 56 ] developed first multiobjective GA (MOGA). The niche and decision maker concepts were proposed to tackle the multimodal problems. However, MOGA suffers from parameter tuning problem and degree of selection pressure. Horn et al. [ 80 ] proposed a niched Pareto genetic algorithm (NPGA) that utilized the concept of tournament selection and Pareto dominance. Srinivas and Deb [ 191 ] developed a non-dominated sorting genetic algorithm (NSGA). However, it suffers from lack of elitism, need of sharing parameter, and high computation complexity. To alleviate these problems, Deb et al. [ 36 ] developed a fast elitist non-dominated sorting genetic algorithm (NSGA-II). The performance of NSGA-II may be deteriorated for many objective problems. NSGA-II was unable to maintain the diversity in Pareto-front. To alleviate this problem, Luo et al. [ 130 ] introduced a dynamic crowding distance in NSGA-II. Coello and Pulido [ 28 ] developed a multiobjective micro GA. They used an archive for storing the non-dominated solutions. The performance of Pareto-based approaches may be deteriorated in many objective problems [ 52 ].

Decomposition-based multiobjective GA

Decomposition-based MOGAs decompose the given problem into multiple subproblems. These subproblems are solved simultaneously and exchange the solutions among neighboring subproblems [ 52 ]. Ishibuchi and Murata [ 84 ] developed a multiobjective genetic local search (MOGLS). In MOGLS, the random weights were used to select the parents and local search for their offspring. They used generation replacement and roulette wheel selection method. Jaszkiewicz [ 86 ] modified the MOGLS by utilizing different selection mechanisms for parents. Murata and Gen [ 141 ] proposed a cellular genetic algorithm for multiobjective optimization (C-MOGA) that was an extension of MOGA. They added cellular structure in MOGA. In C-MOGA, the selection operator was performed on the neighboring of each cell. C-MOGA was further extended by introducing an immigration procedure and known as CI-MOGA. Alves and Almeida [ 11 ] developed a multiobjective Tchebycheffs-based genetic algorithm (MOTGA) that ensures convergence and diversity. Tchebycheff scalar function was used to generate non-dominated solution set. Patel et al. [ 151 ] proposed a decomposition based MOGA (D-MOGA). They integrated opposition based learning in D-MOGA for weight vector generation. D-MOGA is able to maintain the balance between diversity of solutions and exploration of search space.

Parallel GAs

The motivation behind the parallel GAs is to improve the computational time and quality of solutions through distributed individuals. Parallel GAs are categorized into three broad categories such as master-slave parallel GAs, fine grained parallel GAs, and multi-population coarse grained parallel Gas [ 70 ]. In master-slave parallel GA, the computation of fitness functions is distributed over the several processors. In fine grained GA, parallel computers are used to solve the real-life problems. The genetic operators are bounded to their neighborhood. However, the interaction is allowed among the individuals. In coarse grained GA, the exchange of individuals among sub-populations is performed. The control parameters are also transferred during migration. The main challenges in parallel GAs are to maximize memory bandwidth and arrange threads for utilizing the power of GPUs [ 23 ]. Table ​ Table8 8 shows the comparative analysis of parallel GAs in terms of hardware and software. The well-known parallel GAs are studied in the preceding subsections.

Analysis of parallel GAs in terms of hardware and software

Master slave parallel GA

The large number of processors are utilized in master-slave parallel GA (MS-PGA) as compared to other approaches. The computation of fitness functions may be increased by increasing the number of processors. Hong et al. [ 79 ] used MS-PGA for solving data mining problems. Fuzzy rules are used with parallel GA. The evaluation of fitness function was performed on slave machines. However, it suffers from high computational time. Sahingzo [ 174 ] implemented MS-PGA for UAV path finding problem. The genetic operators were executed on processors. They used multicore CPU with four cores. Selection and fitness evaluation was done on slave machines. MS-PGA was applied on traffic assignment problem in [ 127 ]. They used thirty processors to solve this problem at National University of Singapore. Yang et al. [ 213 ] developed a web-based parallel GA. They implemented the master slave version of NSGA-II in distributed environment. However, the system is complex in nature.

Fine grained parallel GA

In last few decades, researchers are working on migration policies of fine grained parallel GA (FG-PGA). Porta et al. [ 161 ] utilized clock-time for migration frequency, which is independent of generations. They used non-uniform structure and static configuration. The best solution was selected for migration and worst solution was replaced with migrant solution. Kurdi [ 115 ] used adaptive migration frequency. The migration procedure starts until there is no change in the obtained solutions after ten successive generations. The non-uniform and dynamic structure was used. In [ 209 ], local best solutions were synchronized and formed a global best solutions. The global best solutions were transferred to all processors for father execution. The migration frequency depends upon the number of generation. They used uniform structure with fixed configuration. Zhang et al. [ 220 ] used parallel GA to solve the set cover problem of wireless networks. They used divide-and-conquer strategy to decompose the population into sub-populations. Thereafter, the genetic operators were applied on local solutions and Kuhn-Munkres was used to merge the local solutions.

Coarse grained parallel GA

Pinel et al. [ 158 ] proposed a GraphCell. The population was initialized with random values and one solution was initialized with Min-min heuristic technique. 448 processors were used to implement the proposed approach. However, coarse grained parallel GAs are less used due to complex in nature. The hybrid parallel GAs are widely used in various applications. Shayeghi et al. [ 182 ] proposed a pool-based Birmingham cluster GA. Master node was responsible for managing global population. Slave node selected the solutions from global population and executed it. 240 processors are used for computation. Roberge et al. [ 170 ] used hybrid approach to optimize switching angle of inverters. They used four different strategies for fitness function computation. Nowadays, GPU, cloud, and grid are most popular hardware for parallel GAs [ 198 ].

Chaotic GAs

The main drawback of GAs is premature convergence. The chaotic systems are incorporated into GAs to alleviate this problem. The diversity of chaos genetic algorithm removes premature convergence. Crossover and mutation operators can be replaced with chaotic maps. Tiong et al. [ 197 ] integrated the chaotic maps into GA for further improvement in accuracy. They used six different chaotic maps. The performance of Logistic, Henon and Ikeda chaotic GA performed better than the classical GA. However, these techniques suffer from high computational complexity. Ebrahimzadeh and Jampour [ 48 ] used Lorenz chaotic for genetic operators of GA to eliminate the local optima problem. However, the proposed approach was unable to find relationship between entropy and chaotic map. Javidi and Hosseinpourfard [ 87 ] utilized two chaotic maps namely logistic map and tent map for generating chaotic values instead of random selection of initial population. The proposed chaotic GA performs better than the GA. However, this method suffers from high computational complexity. Fuertes et al. [ 60 ] integrated the entropy into chaotic GA. The control parameters are modified through chaotic maps. They investigated the relationship between entropy and performance optimization.

Chaotic systems have also used in multiobjective and hybrid GAs. Abo-Elnaga and Nasr [ 5 ] integrated chaotic system into modified GA for solving Bi-level programming problems. Chaotic helps the proposed algorithm to alleviate local optima and enhance the convergence. Tahir et al. [ 193 ] presented a binary chaotic GA for feature selection in healthcare. The chaotic maps were used to initialize the population and modified reproduction operators were applied on population. Xu et al. [ 115 ] proposed a chaotic hybrid immune GA for spectrum allocation. The proposed approach utilizes the advantages of both chaotic and immune operator. However, this method suffers from parameter initialization problem.

Genetic Algorithms can be easily hybridized with other optimization methods for improving their performance such as image denoising methods, chemical reaction optimization, and many more. The main advantages of hybridized GA with other methods are better solution quality, better efficiency, guarantee of feasible solutions, and optimized control parameters [ 51 ]. It is observed from literature that the sampling capability of GAs is greatly affected from population size. To resolve this problem, local search algorithms such as memetic algorithm, Baldwinian, Lamarckian, and local search have been integrated with GAs. This integration provides proper balance between intensification and diversification. Another problem in GA is parameter setting. Finding appropriate control parameters is a tedious task. The other metaheuristic techniques can be used with GA to resolve this problem. Hybrid GAs have been used to solve the issues mentioned in the preceding subsections [ 29 , 137 , 186 ].

Enhance search capability

GAs have been integrated with local search algorithms to reduce the genetic drift. The explicit refinement operator was introduced in local search for producing better solutions. El-Mihoub et al. [ 54 ] established the effect of probability of local search on the population size of GA. Espinoza et al. [ 50 ] investigated the effect of local search for reducing the population size of GA. Different search algorithms have been integrated with GAs for solving real-life applications.

Generate feasible solutions

In complex and high-dimensional problems, the genetic operators of GA generate infeasible solutions. PMX crossover generates the infeasible solutions for order-based problems. The distance preserving crossover operator was developed to generate feasible solutions for travelling salesman problem [ 58 ]. The gene pooling operator instead of crossover was used to generate feasible solution for data clustering [ 19 ]. Konak and Smith [ 108 ] integrated a cut-saturation algorithm with GA for designing the communication networks. They used uniform crossover to produce feasible solutions.

Replacement of genetic operators

There is a possibility to replace the genetic operators which are mentioned in Section 3.2 with other search techniques. Leng [ 122 ] developed a guided GA that utilizes the penalties from guided local search. These penalties were used in fitness function to improve the performance of GA. Headar and Fukushima [ 74 ] used simplex crossover instead of standard crossover. The standard mutation operator was replaced with simulated annealing in [ 195 ]. The basic concepts of quantum computing are used to improve the performance of GAs. The heuristic crossover and hill-climbing operators can be integrated into GA for solving three-matching problem.

Optimize control parameters

The control parameters of GA play a crucial role in maintaining the balance between intensification and diversification. Fuzzy logic has an ability to estimate the appropriate control parameters of GA [ 167 ]. Beside this, GA can be used to optimize the control parameters of other techniques. GAs have been used to optimize the learning rate, weights, and topology of neutral networks [ 21 ]. GAs can be used to estimate the optimal value of fuzzy membership in controller. It was also used to optimize the control parameters of ACO, PSO, and other metaheuristic techniques [ 156 ]. The comparative analysis of well-known GAs are mentioned in Table ​ Table9 9 .

Comparative study of GA’s variants in terms of pros and cons

Applications

Genetic Algorithms have been applied in various NP-hard problems with high accuracy rates. There are a few application areas in which GAs have been successfully applied.

Operation management

GA is an efficient metaheuristic for solving operation management (OM) problems such as facility layout problem (FLP), supply network design, scheduling, forecasting, and inventory control.

Facility layout

Datta et al. [ 32 ] utilized GA for solving single row facility layout problem (SRFLP). For SRFLP, the modified crossover and mutation operators of GA produce valid solutions. They applied GA to large sized problems that consists of 60–80 instances. However, it suffers from parameter dependency problem. Sadrzadeh [ 173 ] proposed GA for multi-line FLP have multi products. The facilities were clustered using mutation and heuristic operators. The total cost obtained from the proposed GA was decreased by 7.2% as compared to the other algorithms. Wu et al. [ 211 ] implemented hierarchical GA to find out the layout of cellular manufacturing system. However, the performance of GA is greatly affected from the genetic operators. Aiello et al. [ 7 ] proposed MOGA for FLP. They used MOGA on the layout of twenty different departments. Palomo-Romero et al. [ 148 ] proposed an island model GA to solve the FLP. The proposed technique maintains the population diversity and generates better solutions than the existing techniques. However, this technique suffers from improper migration strategy that can be utilized for improving the population. GA and its variants has been successfully applied on FLP [ 103 , 119 , 133 , 201 ].

GA shows the superior performance for solving the scheduling problems such as job-shop scheduling (JSS), integrated process planning and scheduling (IPPS), etc. [ 119 ]. To improve the performance in the above-mentioned areas of scheduling, researchers developed various genetic representation [ 12 , 159 , 215 ], genetic operators, and hybridized GA with other methods [ 2 , 67 , 147 , 219 ].

Inventory control

Besides the scheduling, inventory control plays an important role in OM. Backordering and lost sales are two main approaches for inventory control [ 119 ]. Hiassat et al. [ 76 ] utilized the location-inventory model to find out the number and location of warehouses. Various design constraints have been added in the objective functions of GA and its variants for solving inventory control problem [].

Forecasting and network design

Forecasting is an important component for OM. Researchers are working on forecasting of financial trading, logistics demand, and tourist arrivals. GA has been hybridized with support vector regression, fuzzy set, and neural network (NN) to improve their forecasting capability [ 22 , 78 , 89 , 178 , 214 ]. Supply network design greatly affect the operations planning and scheduling. Most of the research articles are focused on capacity constraints of facilities [ 45 , 184 ]. Multi-product multi-period problems increases the complexity of supply networks. To resolve the above-mentioned problem, GA has been hybridized with other techniques [ 6 , 45 , 55 , 188 , 189 ]. Multi-objective GAs are also used to optimize the cost, profit, carbon emissions, etc. [ 184 , 189 ].

GAs have been applied in various fields of multimedia. Some of well-known multimedia fields are encryption, image processing, video processing, medical imaging, and gaming.

Information security

Due to development in multimedia applications, images, videos and audios are transferred from one place to another over Internet. It has been found in literature that the images are more error prone during the transmission. Therefore, image protection techniques such as encryption, watermarking and cryptography are required. The classical image encryption techniques require the input parameters for encryption. The wrong selection of input parameters will generate inadequate encryption results. GA and its variants have been used to select the appropriate control parameters. Kaur and Kumar [ 96 ] developed a multi-objective genetic algorithm to optimize the control parameters of chaotic map. The secret key was generated using beta chaotic map. The generated key was use to encrypt the image. Parallel GAs were also used to encrypt the image [ 97 ].

Image processing

The main image processing tasks are preprocessing, segmentation, object detection, denoising, and recognition. Image segmentation is an important step to solve the image processing problems. Decomposing/partitioning an image requires high computational time. To resolve this problem, GA is used due to their better search capability [ 26 , 102 ]. Enhancement is a technique to improve the quality and contrast of an image. The better image quality is required to analyze the given image. GAs have been used to enhance natural contrast and magnify image [ 40 , 64 , 99 ]. Some researchers are working on hybridization of rough set with adaptive genetic algorithm to merge the noise and color attributes. GAs have been used to remove the noise from the given image. GA can be hybridized with fuzzy logic to denoise the noisy image. GA based restoration technique can be used to remove haze, fog and smog from the given image [ 8 , 110 , 146 , 200 ]. Object detection and recognition is a challenging issue in real-world problem. Gaussian mixture model provides better performance during detection and recognition process. The control parameters are optimized through GA [ 93 ].

Video processing

Video segmentation has been widely used in pattern recognition, and computer vision. There are some critical issues that are associated with video segmentation. These are distinguishing object from the background and determine accurate boundaries. GA can be used to resolve these issues [ 9 , 105 ]. GAs have been implemented for gesture recognition successfully by Chao el al. [ 81 ] used GA for gesture recognition. They applied GAs and found an accuracy of 95% in robot vision. Kaluri and Reddy [ 91 ] proposed an adaptive genetic algorithm based method along with fuzzy classifiers for sign gesture recognition. They reported an improved recognition rate of 85% as compared to the existing method that provides 79% accuracy. Beside the gesture recognition, face recognition play an important role in criminal identification, unmanned vehicles, surveillance, and robots. GA is able to tackle the occlusion, orientations, expressions, pose, and lighting condition [ 69 , 95 , 109 ].

Medical imaging

Genetic algorithms have been applied in medical imaging such as edge detection in MRI and pulmonary nodules detection in CT scan images [ 100 , 179 ]. In [ 120 ], authors used a template matching technique with GA for detecting nodules in CT images. Kavitha and Chellamuthu [ 179 ] used GA based region growing method for detecting the brain tumor. GAs have been applied on medical prediction problems captured from pathological subjects. Sari and Tuna [ 176 ] used GA used to solve issues arises in biomechanics. It is used to predict pathologies during examination. Ghosh and Bhattachrya [ 62 ] implemented sequential GA with cellular automata for modelling the coronavirus disease 19 (COVID-19) data. GAs can be applied in parallel mode to find rules in biological datasets [ 31 ]. The authors proposed a parallel GA that runs by dividing the process into small sub-generations and evaluating the fitness of each individual solution in parallel. Genetic algorithms are used in medicine and other related fields. Koh et al. [ 61 ] proposed a genetic algorithm based method for evaluation of adverse effects of a given drug.

Precision agriculture

GAs have been applied on various problems that are related to precision agriculture. The main issues are crop yield, weed detection, and improvement in farming equipment. Pachepsky and Acock [ 145 ] implemented GA to analyze the water capacity in soil using remote sensing images. The crop yield can be predicted through the capacity of water present in soil. The weed identification was done through GA in [ 142 ]. They used aerial image for classification of plants. In [ 124 ], color image segmentation was used to discriminate the weed and plant. Peerlink et al. [ 154 ] determined the appropriate rate of fertilizer for various portions of agriculture field. They GA for determining the nitrogen in wheat field. The energy requirements in water irrigation systems can be optimized by viewing it as a multi-objective optimization problem. The amount of irrigation required and thus power requirements change continuously in a SMART farm. Therefore, GA can be applied in irrigation systems to reduce the power requirements [ 33 ].

GAs have been successfully used in games such as gomoku. In [ 202 ], the authors shown that the GA based approach finds the solution having the highest fitness than the normal tree based methods. However, in real-time strategy based games, GA based solutions become less practical to implement [ 82 ]. GAs have been implemented for path planning problems considering the environment constraints as well as avoiding the obstacles to reach the given destination. Burchardt and Salomon [ 18 ] described an implementation for path planning for soccer games. GA can encode the path planning problems via the coordinate points of a two-dimensional playing field, hence resulting in a variable length solution. The fitness function in path planning considers length of path as well as the collision avoiding terms for soccer players.

Wireless networking

Due to adaptive, scalable, and easy implementation of GA, it has been used to solve the various issues of wireless networking. The main issues of wireless networking are routing, quality of service, load balancing, localization, bandwidth allocation and channel assignment [ 128 , 134 ]. GA has been hybridized with other metaheuristics for solving the routing problems. Hybrid GA not only producing the efficient routes among pair of nodes, but also used for load balancing [ 24 , 212 ].

Load balancing

Nowadays, multimedia applications require Quality-of-Service (QoS) demand for delay and bandwidth. Various researchers are working on GAs for QoS based solutions.GA produces optimal solutions for complex networks [ 49 ]. Roy et al. [ 172 ] proposed a multi-objective GA for multicast QoS routing problem. GA was used with ACO and other search algorithms for finding optimal routes with desired QoS metrics. Load balancing is another issue in wireless networks. Scully and Brown [ 177 ] used MicroGAs and MacroGAs to distribute the load among various components of networks. He et al. [ 73 ] implemented GA to determine the balance load in wireless sensor networks. Cheng et al. [ 25 ] utilized distributed GA with multi-population scheme for load balancing. They used load balancing metric as a fitness function in GA.

Localization

The process of determining the location of wireless nodes is called as localization. It plays an important role in disaster management and military services. Yun et al. [ 216 ] used GA with fuzzy logic to find out the weights, which are assigned according to the signal strength. Zhang et al. [ 218 ] hybridized GA with simulated annealing (SA) to determine the position of wireless nodes. SA is used as local search to eliminate the premature convergence.

Bandwidth and channel allocation

The appropriate bandwidth allocation is a complex task. GAs and its variants have been developed to solve the bandwidth allocation problem [ 92 , 94 , 107 ]. GAs were used to investigate the allocation of bandwidth with QoS constraints. The fitness function of GAs may consists of resource utilization, bandwidth distribution, and computation time [ 168 ]. The channel allocation is an important issue in wireless networks. The main objective of channel allocation is to simultaneously optimize the number of channels and reuse of allocated frequency. Friend et al. [ 59 ] used distributed island GA to resolve the channel allocation problem in cognitive radio networks. Zhenhua et al. [ 221 ] implemented a modified immune GA for channel assignment. They used different encoding scheme and immune operators. Pinagapany and Kulkarni [ 157 ] developed a parallel GA to solve both static and dynamic channel allocation problem. They used decimal encoding scheme. Table ​ Table10 10 summarizes the applications of GA and its variants.

Applications of GA

Challenges and future possibilities

In this section, the main challenges faced during the implementation of GAs are discussed followed by the possible research directions.

Despite the several advantages, there are some challenges that need to be resolved for future advancements and further evolution of genetic algorithms. Some major challenges are given below:

Selection of initial population

Initial population is always considered as an important factor for the performance of genetic algorithms. The size of population also affects the quality of solution [ 160 ]. The researchers argue that if a large population is considered, then the algorithm takes more computation time. However, the small population may lead to poor solution [ 155 ]. Therefore, finding the appropriate population size is always a challenging issue. Harik and Lobo [ 71 ] investigated the population using self-adaption method. They used two approaches such as (1) use of self-adaption prior to execution of algorithm, in which the size of population remains the same and (2) in which the self-adaption used during the algorithm execution where the population size is affected by fitness function.

Premature convergence

Premature convergence is a common issue for GA. It can lead to the loss of alleles that makes it difficult to identify a gene [ 15 ]. Premature convergence states that the result will be suboptimal if the optimization problem coincides too early. To avoid this issue, some researchers suggested that the diversity should be used. The selection pressure should be used to increase the diversity. Selection pressure is a degree which favors the better individuals in the initial population of GA’s. If selection pressure (SP1) is greater than some selection pressure (SP2), then population using SP1 should be larger than the population using SP2. The higher selection pressure can decrease the population diversity that may lead to premature convergence [ 71 ].

Convergence property has to be handled properly so that the algorithm finds global optimal solution instead of local optimal solution (see Fig. ​ Fig.8). 8 ). If the optimal solution lies in the vicinity of an infeasible solution, then the global nature of GA can be combined with local nature of other algorithms such as Tabu search and local search. The global nature of genetic algorithms and local nature of Tabu search provide the proper balance between intensification and diversification.

Local and global optima [ 149 ]

Selection of efficient fitness functions

Fitness function is the driving force, which plays an important role in selecting the fittest individual in every iteration of an algorithm. If the number of iterations are small, then a costly fitness function can be adjusted. The number of iterations increases may increase the computational cost. The selection of fitness function depends upon the computational cost as well as their suitability. In [ 46 ], the authors used Davies-Bouldin index for classification of documents.

Degree of mutation and crossover

Crossover and mutation operators are the integral part of GAs. If the mutation is not considered during evolution, then there will be no new information available for evolution. If crossover is not considered during evolution, then the algorithm can result in local optima. The degree of these operators greatly affect the performance of GAs [ 72 ]. The proper balance between these operators are required to ensure the global optima. The probabilistic nature cannot determine the exact degree for an effective and optimal solution.

Selection of encoding schemes

GAs require a particular encoding scheme for a specific problem. There is no general methodology for deciding whether the particular encoding scheme is suitable for any type of real-life problem. If there are two different problems, then two different encoding schemes are required. Ronald [ 171 ] suggested that the encoding schemes should be designed to overwhelm the redundant forms. The genetic operators should be implemented in a manner that they are not biased towards the redundant forms.

Future research directions

GAs have been applied in different fields by modifying the basic structure of GA. The optimality of a solution obtained from GA can be made better by overcoming the current challenges. Some future possibilities for GA are as follows:

• There should be some way to choose the appropriate degree of crossover and mutation operators. For example Self-Organizing GA adapt the crossover and mutation operators according to the given problem. It can save computation time that make it faster.
• Future work can also be considered for reducing premature convergence problem. Some researchers are working in this direction. However, it is suggested that new methods of crossover and mutation techniques are required to tackle the premature convergence problem.
• Genetic algorithms mimic the natural evolution process. There can be a possible scope for simulating the natural evolution process such as the responses of human immune system and the mutations in viruses.
• In real-life problems, the mapping from genotype to phenotype is complex. In this situation, the problem has no obvious building blocks or building blocks are not adjacent groups of genes. Hence, there is a possibility to develop novel encoding schemes to different problems that does not exhibit same degree of difficulty.

Conclusions

This paper presents the structured and explained view of genetic algorithms. GA and its variants have been discussed with application. Application specific genetic operators are discussed. Some genetic operators are designed for representation. However, they are not applicable to research domains. The role of genetic operators such as crossover, mutation, and selection in alleviating the premature convergence is studied extensively. The applicability of GA and its variants in various research domain has been discussed. Multimedia and wireless network applications were the main attention of this paper. The challenges and issues mentioned in this paper will help the practitioners to carry out their research. There are many advantages of using GAs in other research domains and metaheuristic algorithms.

The intention of this paper is not only provide the source of recent research in GAs, but also provide the information about each component of GA. It will encourage the researchers to understand the fundamentals of GA and use the knowledge in their research problems.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Automatic programming using genetic programming

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• My Account Login
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• Open access
• Published: 14 December 2023

Mathematical discoveries from program search with large language models

• Bernardino Romera-Paredes   ORCID: orcid.org/0000-0003-3604-3590 1   na1 ,
• Mohammadamin Barekatain   ORCID: orcid.org/0000-0002-8470-8203 1   na1 ,
• Alexander Novikov 1   na1 ,
• Matej Balog   ORCID: orcid.org/0000-0002-5552-9855 1   na1 ,
• M. Pawan Kumar 1   na1 ,
• Emilien Dupont 1   na1 ,
• Francisco J. R. Ruiz   ORCID: orcid.org/0000-0002-2200-901X 1   na1 ,
• Jordan S. Ellenberg 2 ,
• Pengming Wang   ORCID: orcid.org/0009-0009-4976-4267 1 ,
• Omar Fawzi 3 ,
• Pushmeet Kohli   ORCID: orcid.org/0000-0002-7466-7997 1 &
• Alhussein Fawzi   ORCID: orcid.org/0000-0001-7341-1917 1   na1  

Nature volume  625 ,  pages 468–475 ( 2024 ) Cite this article

178k Accesses

6 Citations

1025 Altmetric

Metrics details

• Computer science
• Pure mathematics

Large language models (LLMs) have demonstrated tremendous capabilities in solving complex tasks, from quantitative reasoning to understanding natural language. However, LLMs sometimes suffer from confabulations (or hallucinations), which can result in them making plausible but incorrect statements 1 , 2 . This hinders the use of current large models in scientific discovery. Here we introduce FunSearch (short for searching in the function space), an evolutionary procedure based on pairing a pretrained LLM with a systematic evaluator. We demonstrate the effectiveness of this approach to surpass the best-known results in important problems, pushing the boundary of existing LLM-based approaches 3 . Applying FunSearch to a central problem in extremal combinatorics—the cap set problem—we discover new constructions of large cap sets going beyond the best-known ones, both in finite dimensional and asymptotic cases. This shows that it is possible to make discoveries for established open problems using LLMs. We showcase the generality of FunSearch by applying it to an algorithmic problem, online bin packing, finding new heuristics that improve on widely used baselines. In contrast to most computer search approaches, FunSearch searches for programs that describe how to solve a problem, rather than what the solution is. Beyond being an effective and scalable strategy, discovered programs tend to be more interpretable than raw solutions, enabling feedback loops between domain experts and FunSearch, and the deployment of such programs in real-world applications.

Similar content being viewed by others

Leveraging large language models for predictive chemistry

Kevin Maik Jablonka, Philippe Schwaller, … Berend Smit

Autonomous chemical research with large language models

Daniil A. Boiko, Robert MacKnight, … Gabe Gomes

Synthesizing theories of human language with Bayesian program induction

Kevin Ellis, Adam Albright, … Timothy J. O’Donnell

Many problems in mathematical sciences are ‘easy to evaluate’, despite being typically ‘hard to solve’. For example, in computer science, NP-complete optimization problems admit a polynomial-time evaluation procedure (measuring the quality of the solution), despite the widespread belief that no polynomial-time algorithms to solve such problems exist. We focus in this paper on problems admitting an efficient ‘evaluate’ function, which measures the quality of a candidate solution. Prominent examples include the maximum independent set problem and maximum constraint satisfaction problems (such as finding the ground state energy of a Hamiltonian). Our goal is to generate a ‘solve’ program, such that its outputs receive high scores from the ‘evaluate’ function (when executed on inputs of interest), and ultimately improve on the best-known solutions.

Whereas large language models (LLMs) have recently seen notable improvements in their coding capabilities 4 , 5 , 6 , 7 , 8 , with applications including debugging 9 , 10 , solving code competitions 11 , 12 and improving code performance 13 , synthesizing ‘solve’ programs for open problems requires finding new ideas that are verifiably correct. This is very hard for LLMs, as they tend to confabulate or ultimately fall short of going beyond existing results. To surpass the ‘nominal’ capabilities of LLMs, recent studies 3 have combined them with evolutionary algorithms 14 , 15 , leading to important improvements on diverse synthetic problems 16 , searching for neural network architectures 17 , 18 , 19 and solving puzzles 20 . Our proposed method, FunSearch, pushes the boundary of LLM-guided evolutionary procedures to a new level: the discovery of new scientific results for established open problems and the discovery of new algorithms. Surpassing state-of-the-art results on established open problems provides a clear indication that the discoveries are truly new, as opposed to being retrieved from the LLM’s training data.

FunSearch (short for searching in the function space) combines a pretrained (frozen) LLM, whose goal is to provide creative solutions, with an evaluator, which guards against confabulations and incorrect ideas. FunSearch iterates over these two components, evolving initial low-scoring programs into high-scoring ones discovering new knowledge. Key to the success of this simple procedure is a combination of several essential ingredients. First, we sample best performing programs and feed them back into prompts for the LLM to improve on; we refer to this as best-shot prompting. Second, we start with a program in the form of a skeleton (containing boilerplate code and potentially known structure about the problem), and only evolve the part governing the critical program logic. For example, by setting a greedy program skeleton, we evolve a priority function used to make decisions at every step. Third, we maintain a large pool of diverse programs by using an island-based evolutionary method that encourages exploration and avoids local optima. Finally, leveraging the highly parallel nature of FunSearch, we scale it asynchronously, considerably broadening the scope of this approach to find new results, while keeping the overall cost of experiments low.

We show the surprising effectiveness of FunSearch on several use cases. We consider a fundamental problem in extremal combinatorics, namely, the cap set problem 21 , 22 . FunSearch demonstrates the existence of hitherto unknown constructions that go beyond existing ones, including the largest improvement in 20 years to the asymptotic lower bound. This demonstrates that it is possible to make a scientific discovery—a new piece of verifiable knowledge about a notorious scientific problem—using an LLM. Using FunSearch, we also find new algorithms for the online bin packing problem that improve on traditional ones on well-studied distributions of interest 23 , 24 , with potential applications to improving job scheduling algorithms.

Whereas most computer search techniques output directly what the solution is (for example, a list of vectors forming a cap set), FunSearch produces programs generating the solution. For structured problems, such programs tend to be more interpretable—facilitating interactions with domain experts—and concise—making it possible to scale to large instances—compared to a mere enumeration of the solution. In addition, decision procedures (such as for bin packing) described by code in a standard programming language are crucially easier to deploy compared to other types of descriptions (for example, neural networks), which typically require specialized hardware and for which verifying design specifications is notoriously hard.

An overview of FunSearch is shown in Fig. 1 , and its components are described in more detail below. For more details and ablations showing the importance of each component, see Methods and Supplementary Information Appendix  A .

The input to FunSearch is a specification of the problem in the form of an ‘evaluate’ function, an initial implementation of the function to evolve, which can be trivial, and potentially a skeleton. At each iteration, FunSearch builds a prompt by combining several programs sampled from the programs database (favouring high-scoring ones). The prompt is then fed to the pretrained LLM and new programs are created. Newly created programs are then scored and stored in the programs database (if correct), thus closing the loop. The user can at any point retrieve the highest-scoring programs discovered so far.

Specification

The input to FunSearch is a specification of the problem in the form of an ‘evaluate’ function, which scores candidate solutions. In addition, we provide an initial program (which can be trivial) to evolve. Although in principle these are the minimum requirements, we found that performance tends to improve significantly if we write the initial ‘solve’ program in the form of a skeleton (containing boilerplate code and previous knowledge of the problem in the form of a program structure), and only use FunSearch to evolve the critical part that governs its logic. Fig. 2a shows an example in which the skeleton takes the form of a simple greedy algorithm, and the crucial part to evolve by FunSearch is the priority function that is used to make the greedy decision at every step. This delegates to FunSearch precisely the part that is usually the hardest to come up with. Whereas a fixed skeleton may constrain the space of programs that can be discovered, we find it improves overall results because it focuses the LLM resources on only evolving the critical part, instead of also using the LLM to recreate already known program structures (with more opportunities for mistakes that would render the entire program incorrect). If available, the user can optionally provide extra known information about the problem at hand, in the form of docstrings, relevant primitive functions or import packages, which FunSearch may use.

The ‘evaluate’ function takes as input a candidate solution to the problem, and returns a score assessing it. The ‘solve’ function contains the algorithm skeleton, which calls the function to evolve that contains the crucial logic. a , Cap set. The function to evolve is called ‘priority’. b , Online bin packing. The function to evolve is called ‘heuristic’. The ‘main’ function implements the evaluation procedure by connecting the pieces together. Specifically, it uses the ‘solve’ function to solve the problem and then scores the resulting solutions using the ‘evaluate’ function. In the simplest cases, ‘main’ just executes ‘solve’ once and uses ‘evaluate’ to score the output, for example, a . In specific settings such as online algorithms, the ‘main’ function implements some more logic, for example, b .

Pretrained LLM

The LLM is the creative core of FunSearch, in charge of coming up with improvements to the functions presented in the prompt and sending these for evaluation. We obtain our results with a pretrained model, that is, without any fine-tuning on our problems. We use Codey, an LLM built on top of the PaLM2 model family 25 , which has been fine-tuned on a large corpus of code and is publicly accessible through its API 26 . Because FunSearch relies on sampling from an LLM extensively, an important performance-defining tradeoff is between the quality of the samples and the inference speed of the LLM. In practice, we have chosen to work with a fast-inference model (rather than slower-inference, higher-quality), and the results in the paper are obtained using a total number of samples on the order of 10 6 . Beyond this tradeoff, we have empirically observed that the results obtained in this paper are not too sensitive to the exact choice of LLM, as long as it has been trained on a large enough corpus of code. See Supplementary Information Appendix  A for a comparison to StarCoder 6 , a state-of-the-art open-source LLM for code.

Programs generated by the LLM are evaluated and scored on a set of inputs. For example, in the cap set problem (‘Extremal combinatorics’ section) the inputs are the values of the dimensionality n that we are interested in, and in combinatorial optimization (‘Bin packing’ section), the inputs correspond to different bin packing instances. The scores across different inputs are then combined into an overall score of the program using an aggregation function, such as the mean. The scored programs are then sent to the programs database. Programs that were incorrect (that did not execute within the imposed time and memory limits, or produced invalid outputs) are discarded, and the remaining scored programs are then sent to the programs database.

Programs database

The programs database keeps a population of correct programs, which are then sampled to create prompts. Preserving and encouraging diversity of programs in the database is crucial to enable exploration and avoid being stuck in local optima. To encourage diversity, we adopt an islands model, also known as a multiple population and multiple-deme model 27 , 28 , which is a genetic algorithm approach. Several islands, or subpopulations, are created and evolved independently. To sample from the program database, we first sample an island and then sample a program within that island, favouring higher-scoring and shorter programs (see Methods for the exact mechanism). Crucially, we let information flow between the islands by periodically discarding the programs in the worst half of the islands (corresponding to the ones whose best individuals have the lowest scores). We replace the programs in those islands with a new population, initialized by cloning one of the best individuals from the surviving islands.

New prompts are created by ‘best-shot prompting’ from the programs database, and are then fed to the LLM to generate a new program. We first sample k programs from a single island in the programs database, according to the procedure described above. Sampled programs are then sorted according to their score, and a version is assigned to each (‘v0’ for the lowest scoring program, ‘v1’ for the second lowest scoring and so on). These programs are then combined into a single prompt—with the version appended as a suffix to the function name; for example, in the case of Fig. 2a , this would be ‘ p riority_v0’, ‘priority_v1’, ...—and the header of the function we wish to generate (for example, ‘priority_vk’) is added to the end of the prompt. In practice, we set k  = 2, as two functions lead to better results compared to just one, with diminishing returns beyond that. Constructing a prompt by combining several programs (as opposed to only one) enables the LLM to spot patterns across the different programs and generalize those. Related approaches to prompt building have been recently considered, for example ref. 16 , and were shown to perform well on different domains.

Distributed approach

We implement FunSearch as a distributed system that has three types of workers—a programs database, samplers and evaluators—which communicate asynchronously. The programs database stores and serves programs, samplers generate new functions using the pretrained LLM and evaluators assess programs, as shown in Supplementary Fig. F.26 . In the example shown in Fig. 2a , the programs database stores priority functions, samplers generate new implementations of ‘priority’ and evaluators score the proposals by executing the ‘main’ function on user-specified inputs. Our distributed system offers several advantages. First, it naturally leverages parallelism across different tasks: for example, LLM sampling and evaluation are performed concurrently. Second, it enables scaling to more than one sampler and evaluator, which would be a very limiting setup, considering that evaluation can take minutes for many problems of interest. Running evaluators in parallel considerably broadens the scope of this approach to such problems. The distributed setting enables the running of many evaluator nodes on inexpensive CPU hardware, whereas few samplers run on machines with accelerators for fast LLM inference; this keeps the overall cost and energy usage of experiments low. In our experiments, we typically use 15 samplers and 150 CPU evaluators (can be served on five CPU servers each running 32 evaluators in parallel). See Supplementary Information Appendix  A for more details. Also, because of the randomness of LLM sampling and the evolutionary procedure, for some problems we run several experiments to get the best reported results. See Methods and Supplementary Information Appendix  A.3 for a full statistical analysis.

We now describe some of the new discoveries made by FunSearch in two different fields: pure mathematics and applied computer science. Further discoveries on other problems (namely, the corners problem and Shannon capacity of cycle graphs) are presented in Supplementary Information Appendix  B . The full discovered programs are available in Supplementary Information Appendix  C .

Extremal combinatorics

We apply FunSearch to two related problems in extremal combinatorics: a branch of mathematics that studies the maximal (or minimal) possible sizes of sets satisfying certain properties.

The cap set problem 21 , once described by Terence Tao as ‘perhaps my favourite open question’ 29 , refers to the task of finding the largest possible set of vectors in \({{\mathbb{Z}}}_{3}^{n}\) (known as a cap set) such that no three vectors sum to zero. Geometrically, no three points of a cap set are in a line (see Fig. 3 for an example with n  = 2).

The circles are the elements of \({{\mathbb{Z}}}_{3}^{2}\) with the ones belonging to the cap set shown in blue. The possible lines in \({{\mathbb{Z}}}_{3}^{2}\) are also shown (with colours indicating lines that wrap around in arithmetic modulo 3). No three elements of the cap set are in a line.

The problem has drawn much interest for a variety of reasons. For one, it is an analogue of the classical number theory problem of finding large subsets of primes in which no three are in arithmetic progression. For another, it differs from many problems in combinatorics in that there is no consensus among mathematicians about what the right answer should be. Finally, the problem serves as a model for the many other problems involving ‘three-way interactions’. For instance, progress towards improved upper bounds for the cap set problem 30 , 31 immediately led to a series of other combinatorial results, for example, on the Erdös–Radio sunflower problem 32 .

The exact size of the largest possible cap set in n dimensions is known only for n  ≤ 6. A brute force approach is not practical as the search space quickly becomes enormous with growing n , for example, around 3 1,600 for n  = 8. Previous methods impose potentially suboptimal restrictions on the search space 33 , 34 . By contrast, we search the full space by means of an algorithm skeleton that uses a function ‘priority’ : \({{\mathbb{Z}}}_{3}^{n}\to {\mathbb{R}}\) . Intuitively, this function provides a priority with which each \(x\in {{\mathbb{Z}}}_{3}^{n}\) should be included in the cap set. Our algorithm starts with an empty set and iteratively adds the vector \(x\in {{\mathbb{Z}}}_{3}^{n}\) with the highest priority that does not violate the cap set constraint; Fig. 2a . Starting from a trivial constant function, we evolve the crucial ‘priority’ component of our approach to result in large cap sets.

Using this approach, we discovered cap sets of sizes shown in Fig. 4a . Notably, in dimension n  = 8, FunSearch found a larger cap set than what was previously known, thus illustrating the power of FunSearch to discover new constructions. This also shows the scalability of FunSearch to larger dimensions, in which the previously best-known construction relied on a complex combination of cap sets in lower dimensions 33 , 34 . By contrast, FunSearch discovered a larger cap set from scratch, without having to be explicitly taught any way of combining cap sets. Moreover, we do not just discover the set of 512 eight-dimensional vectors in itself, but a program that generates it: we show this program in Fig. 4b . Through inspecting the code, we obtain a degree of understanding of what this set is: specifically, manual simplification of Fig. 4b provides the construction in Fig. 4c . Some properties of this construction are similar to the construction of the Hill cap 35 , 36 , which results in the optimal 112-cap in \({{\mathbb{Z}}}_{3}^{6}\) .

a , Size of the largest cap set in \({{\mathbb{Z}}}_{3}^{n}\) for different dimensions n . b , The function ‘priority’ : \({{\mathbb{Z}}}_{3}^{n}\to {\mathbb{R}}\) discovered by FunSearch that results in a cap set of size 512 in n  = 8 dimensions. One feature to note is that the priority is affected by whether the same entry appears in positions i and − i ( − i denotes the i th position counting from the end). This motivates the notion of reflections, used in c . c , An explicit construction of this new 512-cap, which we were able to manually construct thanks to having discovered the cap set by searching in function space. See Supplementary Information  Appendix  E.2 for more details and for relation to Hill cap.

Admissible sets

Beyond finding the size of the largest cap set c n in dimension n , a fundamental problem in additive combinatorics 22 is determining the capacity \(C=\mathop{\sup }\limits_{n}\,{c}_{n}^{1/n}\) . The breakthrough result from ref. 31 established an upper bound of C  ≤ 2.756. In this work, we are interested in lower bounds on C . To this end, we use the framework of constant weight admissible sets (or admissible sets for short) 34 , 37 , which has established the current state-of-the-art.

Formally, admissible sets \({\mathcal{A}}(n,w)\) are collections of vectors in {0, 1, 2} n satisfying two properties: (1) each vector has the same number w of non-zero elements but a unique support (therefore \(| A| \le \left(\begin{array}{c}n\\ w\end{array}\right)\) ); (2) for any three distinct vectors there is a coordinate in which their three respective values are {0, 1, 2}, {0, 0, 1} or {0, 0, 2}. Informally, an admissible set describes how to combine cap sets in smaller dimensions into large cap sets in higher dimensions 34 . We denote the set of full-size admissible sets (with \(| A| =\left(\begin{array}{c}n\\ w\end{array}\right)\) ) as \({\mathcal{I}}(n,w)\) . The current state-of-the-art 38 has relied on SAT solvers to construct large admissible sets.

As before, we evolve a function ‘priority’ : \({\{0,1,2\}}^{n}\to {\mathbb{R}}\) , which is used to iteratively grow admissible sets. Starting from a trivial constant function, we discover one that provides us with an \({\mathcal{I}}(12,7)\) admissible set; the discovered program is shown in Fig. 5b . This discovery alone already improves the lower bound on the cap set capacity from 2.2180 (ref. 38 ) to 2.2184. Yet, interpreting the program found by FunSearch (Fig. 5b ) helps us significantly push the boundaries of what admissible sets we can construct. Specifically, we notice that the discovered ‘priority’ function treats the n coordinates in a highly symmetric way, and indeed it turns out that the admissible set it constructs is preserved under independent cyclic permutations of coordinates within four disjoint groups of coordinate triples. Hereinafter we call such admissible sets symmetric (see Supplementary Information Appendix  D for a formal definition).

a , Summary of lower bounds on the cap set capacity C . b , The ‘priority’ function \({\{0,1,2\}}^{n}\to {\mathbb{R}}\) discovered by FunSearch that results in an \({\mathcal{I}}(12,7)\) admissible set. The source code shows that when n  = 12, the function treats the four triples of coordinates {0, 4, 8}, {1, 5, 9}, {2, 6, 10} and {3, 7, 11} together. We then checked that the admissible set is in fact symmetric under independent cyclic permutations of coordinates within each of these four triples. See Supplementary Information Appendices D and   E.3 for more details.

We now use FunSearch to directly search for symmetric admissible sets. Note that this is a more restricted and also much smaller search space, which allows for significantly higher dimensions and weights than were previously possible. This led us to discovering a full-size \({\mathcal{I}}(15,10)\) admissible set (indicating C  ≥ 2.219486) and a partial admissible set in \({\mathcal{A}}(24,17)\) of size 237,984, which implies a new lower bound on the cap set capacity of 2.2202 (Fig. 5a ). Although this is a great improvement to the lower bound compared to research in the last 20 years, we note it is still far from the upper bound and we hope our results inspire future work on this problem.

Not only does FunSearch scale to much larger instances than traditional combinatorial solvers (Supplementary Information Appendix A.4 ), but it is also a unique feature of searching in function space that we were able to inspect the code discovered by FunSearch and infer a new insight into the problem, in the form of a new symmetry. The procedure we followed in this section is a concrete example of how LLM-based approaches can be used in mathematical sciences: FunSearch suggests a solution, which is examined by researchers, who may note features of interest. These features are used to refine the search, leading to better solutions. This process can be iterated, with both human and search consistently in the loop.

Bin packing

Combinatorial optimization is a subfield of mathematics that plays an important role across a wide range of areas, from theoretical computer science to practical problems in logistics and scheduling. Whereas many combinatorial optimization problems are provably hard to solve for large instances, it is typically possible to achieve strong performance using heuristics to guide the search algorithm. The choice of a heuristic is crucial for obtaining strong performance, but designing a good heuristic is difficult in practice. In this section, we show that FunSearch can be used to discover effective heuristics for one of the central problems in combinatorial optimization: bin packing 39 .

The goal of bin packing is to pack a set of items of various sizes into the smallest number of fixed-sized bins. Bin packing finds applications in many areas, from cutting materials to scheduling jobs on compute clusters. We focus on the online setting in which we pack an item as soon as it is received (as opposed to the offline setting in which we have access to all items in advance). Solving online bin packing problems then requires designing a heuristic for deciding which bin to assign an incoming item to.

Heuristics for online bin packing are well studied and several variants exist with strong worst case performance 40 , 41 , 42 , 43 , 44 , 45 . However, they often show poor performance in practice 39 . Instead, the most commonly used heuristics for bin packing are first fit and best fit. First fit places the incoming item in the first bin with enough available space, whereas best fit places the item in the bin with least available space where the item still fits. Here, we show that FunSearch discovers better heuristics than first fit and best fit on simulated data.

To achieve this, we define a heuristic as a program that takes as input an item and an array of bins (containing the remaining capacity of each bin) and returns a priority score for each bin. The ‘solve’ function picks the bin with the highest score according to the heuristic (Fig. 2b ). FunSearch is then used to evolve this heuristic, starting from best fit.

We first evaluate FunSearch on the well-known OR-Library bin packing benchmarks 23 , consisting of four datasets, OR1 to OR4, containing bin packing instances with an increasing number of items (see Supplementary Information Appendix  E.4 for details). We evolve our heuristic on a training set of generated bin packing instances with the same number of items as those in OR1 and, after the evolutionary process is concluded, test it on the OR1 to OR4 datasets. We measure performance as the fraction of excess bins used over the L 2 lower bound 46 of the optimal offline packing solution (which is generally not achievable in the online setting).

As can be seen in Table 1 , FunSearch outperforms both first fit and best fit across all datasets. Further, the learned heuristic generalizes: even though it has only seen instances of the same size as OR1 during training, it generalizes across problem sizes, performing even better on large instances and widening the gap to best fit. In addition to the OR benchmarks, we also use FunSearch to evolve heuristics on bin packing instances sampled from a Weibull distribution, as these closely follow many real-world scheduling problems 24 , 47 (see Supplementary Information Appendix  E.4 for details). As shown in Table 1 , the performance of FunSearch is very strong on this dataset, significantly outperforming first fit and best fit across instances, as well as scaling gracefully to large instances (being only 0.03% off the lower bound on the optimum for 100,000 items). In addition, FunSearch is robust and consistently outperforms these baselines as shown in the statistical analysis in the Supplementary Information Appendix  A.3 .

We observed that several heuristics discovered by FunSearch use the same general strategy for bin packing (see Fig. 6 for an example). Instead of packing items into bins with the least capacity (such as best fit), the FunSearch heuristics assign items to least capacity bins only if the fit is very tight after placing the item. Otherwise, the item is typically placed in another bin, which would leave more space after the item is placed. This strategy avoids leaving small gaps in bins that are unlikely to ever be filled (see Supplementary Information Appendix  E.5 for example visualizations of such packings).

This example illustrates frequently observed behaviour: instead of always packing items into the best fit bin, the heuristic encourages packing the item only if the fit is tight. Comments in the code were manually added. See Supplementary Information Appendix  C for more discovered heuristics.

As this example demonstrates, the benefits of FunSearch extend beyond theoretical and mathematical results to practical problems such as bin packing. Indeed, bin packing, and related combinatorial optimization problems, are ubiquitous and find applications across a range of industries. We are optimistic that FunSearch could be applied to several such use cases with potential for real-world impact.

The effectiveness of FunSearch in discovering new knowledge for hard problems might seem intriguing. We believe that the LLM used within FunSearch does not use much context about the problem; the LLM should instead be seen as a source of diverse (syntactically correct) programs with occasionally interesting ideas. When further constrained to operate on the crucial part of the algorithm with a program skeleton, the LLM provides suggestions that marginally improve over existing ones in the population, which ultimately results in discovering new knowledge on open problems when combined with the evolutionary algorithm. Another crucial component of the effectiveness of FunSearch is that it operates in the space of programs: rather than directly searching for constructions (which is typically an enormous list of numbers), FunSearch searches for programs generating those constructions. Because most problems we care about are structured (highly non-random), we believe that solutions are described more concisely with a computer program, compared to other representations. For example, the trivial representation of the admissible set \({\mathcal{A}}(24,17)\) consists of more than 200,000 vectors, but the program generating this set consists of only a few lines of code. Because FunSearch implicitly encourages concise programs, it scales to much larger instances compared to traditional search approaches in structured problems. In a loose sense, FunSearch attempts to find solutions that have low Kolmogorov complexity 48 , 49 , 50 (which is the length of the shortest computer program that produces a given object as output), whereas traditional search procedures have a very different inductive bias. We believe that such Kolmogorov-compressed inductive bias is key to FunSearch scaling up to the large instances in our use cases. In addition to scale, we have empirically observed that FunSearch outputs programs that tend to be interpretable: that is, they are clearly easier to read and understand compared to a list of numbers. For example, by scrutinizing FunSearch’s output for the admissible set problem, we found a new symmetry, which was then subsequently used to improve the results even further. Despite the rarity of symmetric solutions, we observe that FunSearch preferred symmetric ones, as these are more parsimonious (that is, they require less information to specify), in addition to the natural bias of LLMs (trained on human-produced code) in outputting code with similar traits to human code. This is in contrast to traditional genetic programming that does not have this bias (and in addition requires hand-tuning the mutation operators 51 ).

We note that FunSearch, at present, works best for problems having the following characteristics: (1) availability of an efficient evaluator; (2) a ‘rich’ scoring feedback quantifying the improvements (as opposed to a binary signal) and (3) ability to provide a skeleton with an isolated part to be evolved. For example, the problem of generating proofs for theorems 52 , 53 , 54 falls outside this scope, because it is unclear how to provide a rich enough scoring signal. By contrast, for MAX-SAT, the number of satisfied clauses can be used as a scoring signal. In this paper, we have explicitly striven for simplicity and we are confident that FunSearch can be further extended to improve its performance and be applicable to more classes of problems. In addition, the rapid development of LLMs is likely to result in samples of far superior quality at a fraction of the cost, making FunSearch more effective at tackling a broad range of problems. As a result, we foresee that automatically tailored algorithms will soon become common practice and deployed in real-world applications.

Implementation details of FunSearch

Distributed system.

We implement FunSearch as a distributed system that has three types of workers: a programs database, samplers and evaluators. The programs database stores the initial user-provided program, as well as all programs received from the evaluators. The samplers are in charge of performing the LLM inference step; to do so they repeatedly query the programs database for prompts. To achieve higher sampling throughput, samplers generate several samples from each prompt. The samples from the LLM (that is, the generated programs) are sent to the evaluators, which score programs by executing them on inputs of interest and assessing the outputs using ‘evaluate’. Programs that are correct are sent to the programs database to be stored. Each of the three FunSearch components is provided as both Python code and pseudocode (Supplementary Information Appendix  F ).

Prompt building

When queried for a prompt, the programs database samples k programs to encourage the LLM to merge ideas from them (we typically set k  = 2; Supplementary Information  Appendix  E.1 ). Programs are sorted according to their score in increasing order, starting from version 0 (‘v0’). Using these k programs, the prompt is built as explained next.

For the sake of clarity, we use here the problem specification from Fig. 2a to precisely describe the prompting mechanism. The overall structure of the prompt mimics the structure of the program skeleton, with the following differences: (1) the ‘priority’ function is stripped out and replaced with the k  = 2 programs sampled, first ‘priority_v0’ and then ‘priority_v1’. (2) After that, a ‘priority_v2’ function with no body is appended: the LLM will be in charge of completing the body of that function. (3) All other functions that appear before ‘priority_v0’ are removed. See Extended Data Fig. 1 for an example of the structure of a prompt.

Evolutionary method and program selection

Another key feature of FunSearch is the method used for evolution of the population of programs from the programs database, as well as for program selection: that is, how the programs database samples programs when queried for a prompt. For this, we use the islands model, a parallel genetic algorithm 27 , 28 . Specifically, we split the population into m separate groups or islands. Each island is initialized with a copy of the user-provided initial program and is evolved separately. That is, whenever a prompt is required, we first uniformly sample an island and then sample k  = 2 programs from that island to build the prompt. The programs generated from the LLM on the basis of that prompt will later be stored in the same island. Every 4 h, we discard all the programs from the m /2 islands whose best instances have the lowest score. Each of these islands is then seeded with a single program, obtained by first choosing one of the surviving m /2 islands uniformly at random and then retrieving the highest-scoring program from that island (breaking ties in favour of older programs). The evolutionary process is then restarted from this state, in which the reset islands contain one high-performing program each (Extended Data Fig. 2 ).

This method has several advantages. First, drawing the analogy in which an island corresponds to an experiment, this approach effectively allows us to run several smaller experiments in parallel instead of a single large experiment. This is beneficial because single experiments can get stuck in local minima, in which most programs in the population are not easily mutated and combined into stronger programs. The multiple island approach allows us to bypass this and effectively kill off such experiments to make space for new ones starting from more promising programs. Second, promising experiments are run for longer, as the islands that survive a reset are the ones with higher scores.

Within each island, we further cluster programs according to their signature. We define the signature of a program as the tuple containing the program’s scores on each of the inputs (for example, the cap set size for each input n ). Programs with the same signature are clustered together. When sampling a program within an island, we first sample an island’s cluster and then a program within that cluster (Extended Data Fig. 3 ). This approach, which aims to preserve diversity 55 , 56 , is related to Lexicase 57 in that both approaches consider a set of test cases for scoring an individual, and it is related to fitness uniform optimization 58 , which also clusters individuals on the basis of their fitness value; however, we sample the clusters on the basis of their score instead of uniformly, as detailed next.

When sampling a cluster, we favour those with larger score values. Specifically, let s i denote the score of the i th cluster, defined as an aggregation (for example, mean) of all the scores in the signature that characterizes that cluster. The probability P i of choosing cluster i is

where T cluster is the temperature parameter, n is the current number of programs in the island, and T 0 and N are hyperparameters (given in Supplementary Information Appendix  E.1 ). This approach is sometimes referred to as the Boltzmann selection procedure 59 .

When sampling a program within a cluster, we favour shorter programs. In particular, let ℓ i denote the negative length of the i th program within the chosen cluster (measured as the number of characters), and let \({\widetilde{{\ell }}}_{i}=\frac{{{\ell }}_{i}-\mathop{\min }\limits_{{i}^{{\prime} }}{{\ell }}_{{i}^{{\prime} }}}{\mathop{\max }\limits_{{i}^{{\prime} }}{{\ell }}_{{i}^{{\prime} }}+1{0}^{-6}}\) . We set the probability of each program proportional to \(\exp ({\widetilde{{\ell }}}_{i}/{T}_{{\rm{program}}})\) , where T program is a temperature hyperparameter.

Owing to randomness in LLM sampling and in the evolutionary procedure, repeating an experiment can lead to different results. For some problems (for example, cap set through the admissible set problem and online bin packing) every single run of FunSearch surpasses the baseline, with only some variation in the magnitude of the difference. For example, all experiments on admissible sets improve on the previous best capacity lower bound, with 60% of experiments on \({\mathcal{I}}(12,7)\) finding a full-size admissible set. For other problems, many independent repetitions of an experiment may be necessary to improve on previous best results. In particular, the case of cap set by direct construction in n  = 8 dimensions is particularly challenging, with only four out of 140 experiments discovering a cap set of size 512. See Supplementary Information Appendix  A.3 for more details.

Related work

The rise of powerful LLMs such as that in ref. 60 has been followed by systems in which an LLM core has been enveloped by a ‘programmatic scaffold’ 61 , and several LLM calls were connected in some way to accomplish larger and more intricate tasks beyond what would be possible using a single prompt and the raw LLM, possibly by using external tools or external memory streams 62 , 63 , 64 , 65 , 66 . LLMs have also been paired with evaluators; for example, refs. 20 , 67 fine-tuned an LLM on data that had been previously generated by the LLM itself (respectively on puzzle problems and solutions, and on justifications and/or explanations for answers to questions), and they used an evaluator to assess the correctness of this data, ensuring that the fine-tuning dataset contained only correct solutions and/or explanations. More related to our approach is the use of LLMs as mutation operators on code, and ref. 3 was the first study to show that coupling an LLM with a programmatic way of scoring a solution can lead to a self-improvement loop. In refs. 16 , 17 , 18 , 19 , the LLM was used as a crossover operator rather than a mutation one, that is, the LLM prompts are composed of several functions, similarly to FunSearch. In refs. 3 , 16 , the task was to improve code that generated bidimensional virtual robots that could move as far as possible in a given simulated terrain (ref. 16 also considered the tasks of symbolic regression, natural language sentences and image generation). In refs. 17 , 18 , 19 the task was to find neural network architectures (described with Python code), and in ref. 68 the task was continuous exploration in the game of Minecraft. By contrast, in this paper, we tackle open problems in mathematics and algorithm design, and we surpass human-designed constructions. We achieve that by combining several ingredients: a distributed system with many samplers and evaluators that communicate asynchronously, a user-provided program specification and skeleton, as well as an evolutionary mechanism based on islands that preserves the diversity of programs. FunSearch achieves that using an off-the-shelf LLM without fine-tuning.

More broadly, LLMs have been used for program synthesis as one of its main applications 4 , 5 , 6 , 7 , 8 . There are many use cases being explored, such as automatically editing code to improve performance 13 , automatically debugging code 9 , 10 , generating code from natural language descriptions 69 , 70 , 71 and doing so to solve problems in code competitions 11 , 12 . Unlike the above approaches that provide tools to increase the productivity of software engineers, we combine in this paper the creativity of LLMs with the power of evolutionary procedures to push the boundaries of human knowledge through solving open hard problems. Another line of research uses LLMs to guide the search for formal proofs for automatic theorem proving 52 , 53 , 54 . Although this approach has the potential to eventually find new knowledge, the achievements of these methods still lag behind the frontier of human knowledge.

Genetic programming

Genetic programming is a subfield of computer science concerned with automatically generating or discovering computer programs using evolutionary methods 15 , 72 , 73 and is used for symbolic regression applications 74 , 75 and discovery of optimization algorithms 76 among others. In this broad sense, combining LLMs with evolution can be seen as an instance of genetic programming with the LLM acting as a mutation and crossover operator. However, using an LLM mitigates several issues in traditional genetic programming 51 , as shown in Supplementary Information Appendix  A and discussed in ref. 3 . Indeed, genetic programming methods require defining several parameters, chief among them the set of allowed mutation operations (or primitives) 15 . Designing such a set of operations is non-trivial and problem specific, requiring domain knowledge about the problem at hand or its plausible solution 51 . Although research has been done to mitigate this limitation, through, for example, the reuse of subprograms 77 or modelling the distribution of high-performing programs 78 , designing effective and general code mutation operators remains difficult. By contrast, LLMs have been trained on vast amounts of code and as such have learned about common patterns and routines from human-designed code. The LLM can leverage this, as well as the context given in the prompt, to generate more effective suggestions than the random ones typically used in genetic programming.

Related to genetic programming, the field of hyper-heuristics 79 , 80 seeks to design learning methods for generating heuristics applied to combinatorial optimization problems. In practice, these heuristics are often programs discovered through genetic programming, typically by evolving a heuristic on a set of instances of a given combinatorial optimization problem, such as bin packing 81 . Indeed, like FunSearch, hyper-heuristics have also been applied to online bin packing, with the learned heuristics able to match the performance of first fit 82 and best fit 83 on a set of generated bin packing instances. Augmenting the heuristics with memory of previously seen items can even lead to heuristics outperforming best fit 84 . In addition, these evolved heuristics can sometimes generalize to larger instances than the ones they were trained on 85 , similar to the learned FunSearch heuristics. However, as is the case with genetic programming, one of the fundamental limitations of hyper-heuristics is that the components of the evolved heuristic must be manually defined by the user and often need to be tailored to a specific problem to be effective. The LLM in FunSearch allows us to bypass this limitation and learn heuristics for bin packing and job scheduling as well as discovering new mathematical constructions, all within a single pipeline without problem-specific tuning.

Program superoptimization and software engineering

Searching for the best way of modifying source code is a task that appears in several branches of computer science and software development. These occurrences can be broadly classified into two groups: first, in which the goal is to find semantic-preserving modifications (this arises in program optimization and superoptimization, in which the aim is to modify the program so that it executes faster while maintaining its input–output behaviour), and second, in which the goal is to find programs with different semantics (this arises, for example, in automatic program repair and mutation testing). With some exceptions discussed below, most of these areas use relatively simple and hard-coded mutation operators on either the source code directly (such as deleting or swapping lines) or on the abstract syntax tree.

Machine learning approaches have been used for program superoptimization. For example, ref. 86 used reinforcement learning to learn the sampling probabilities used within a hierarchical probabilistic model of simple program edits introduced by STOKE 87 . Neural networks have also been proposed as a mutation operator for program optimization in ref. 88 . These studies operated on code written in Assembly (perhaps because designing meaningful and rich edit distributions on programs in higher-level languages is challenging). More recently, ref. 13 used LLMs to find performance-improving edits to code written in C++ or Python. We also note that reinforcement learning has recently been applied to discover new faster algorithms for fundamental operations such as matrix multiplication 89 and sorting 90 .

In this paper, we have not explicitly explored semantic-preserving applications such as discovering performance-improving code edits, but we believe that FunSearch could be an effective method for that setting too. In both use cases presented in the main text, the goal is to evolve programs with new semantics, but the application is different from program repair or mutation testing: in the ‘Extremal combinatorics’ section, we used FunSearch to discover a program that constructs a previously unknown mathematical object, and in the ‘Bin packing’ section, we used FunSearch to discover a program that corresponds to a more efficient heuristic for online bin packing.

Data availability

The experiments carried out in this paper do not require any data corpus other than the publicly available OR-Library bin packing benchmarks 23 . The output functions of interest produced by FunSearch are shown across the main paper and in text files in the Supplementary Information .

Code availability

The discovered functions as well as the evolutionary algorithm, code manipulation routines and a single-threaded implementation of the FunSearch pipeline are available as Python code in the Supplementary Information and at https://github.com/google-deepmind/funsearch . Furthermore, the software library launchpad 91 and a sandbox for safely executing generated code on our internal distributed system were used. No training or fine-tuning of a LLM is required; API access for inference is sufficient. We used Codey 26 , which is available through its API, and StarCoder 6 , which is open source.

Bang, Y. et al. A multitask, multilingual, multimodal evaluation of ChatGPT on reasoning, hallucination, and interactivity. Preprint at https://arxiv.org/abs/2302.04023 (2023).

Borji, A. A. categorical archive of ChatGPT failures. Preprint at https://arxiv.org/abs/2302.03494 (2023).

Lehman, J. et al. in Handbook of Evolutionary Machine Learning (eds Banzhaf, W. et al.) 331–366 (Springer, 2023).

Chen, M. et al. Evaluating large language models trained on code. Preprint at https://arxiv.org/abs/2107.03374 (2021).

Austin, J. et al. Program synthesis with large language models. Preprint at https://arxiv.org/abs/2108.07732 (2021).

Li, R. et al. StarCoder: may the source be with you! Preprint at https://arxiv.org/abs/2305.06161 (2023).

Fried, D. et al. Incoder: a generative model for code infilling and synthesis. In Proc. International Conference on Learning Representations (2022).

Nijkamp, E. et al. CodeGen: an open large language model for code with multi-turn program synthesis. In Proc. International Conference on Learning Representations (2022).

Chen, X., Lin, M., Schärli, N. & Zhou, D. Teaching large language models to self-debug. Preprint at https://arxiv.org/abs/2304.05128 (2023).

Liventsev, V., Grishina, A., Härmä, A. & Moonen, L. Fully autonomous programming with large language models. Preprint at https://arxiv.org/abs/2304.10423 (2023).

Li, Y. et al. Competition-level code generation with alphacode. Science 378 , 1092–1097 (2022).

Article   ADS   CAS   PubMed   Google Scholar  

Zelikman, E., Huang, Q., Poesia, G., Goodman, N. D. & Haber, N. Parsel: a (de-) compositional framework for algorithmic reasoning with language models. Preprint at https://arxiv.org/abs/2212.10561 (2023).

Madaan, A. et al. Learning performance-improving code edits. Preprint at https://arxiv.org/abs/2302.07867 (2023).

Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning (Addison-Wesley, 1989).

Koza, J. R. Genetic programming as a means for programming computers by natural selection. Stat. Comput. 4 , 87–112 (1994).

Article   Google Scholar  

Meyerson, E. et al. Language model crossover: variation through few-shot prompting. Preprint at https://arxiv.org/abs/2302.12170 (2023).

Chen, A., Dohan, D. M. & So, D. R. EvoPrompting: language models for code-level neural architecture search. Preprint at https://arxiv.org/abs/2302.14838 (2023).

Zheng, M. et al. Can GPT-4 perform neural architecture search? Preprint at https://arxiv.org/abs/2304.10970 (2023).

Nasir, M. U., Earle, S., Togelius, J., James, S. & Cleghorn, C. LLMatic: neural architecture search via large language models and quality-diversity optimization. Preprint at https://arxiv.org/abs/2306.01102 (2023).

Haluptzok, P., Bowers, M. & Kalai, A. T. Language models can teach themselves to program better. In International Conference on Learning Representations (2023).

Grochow, J. New applications of the polynomial method: the cap set conjecture and beyond. Bull. Am. Math. Soc. 56 , 29–64 (2019).

Article   ADS   MathSciNet   Google Scholar  

Tao, T. & Vu, V. H. Additive Combinatorics Vol. 105 (Cambridge Univ. Press, 2006).

Beasley, J. E. OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 , 1069–1072 (1990).

Castiñeiras, I., De Cauwer, M. & O’Sullivan, B. Weibull-based benchmarks for bin packing. In Proc. International Conference on Principles and Practice of Constraint Programming 207–222 (Springer, 2012).

Anil, R. et al. Palm 2 technical report. Preprint at https://arxiv.org/abs/2305.10403 (2023).

Code models overview. Vertex AI, Google Cloud https://cloud.google.com/vertex-ai/docs/generative-ai/code/code-models-overview (2023).

Tanese, R. Distributed Genetic Algorithms for Function Optimization. PhD thesis, Univ. Michigan (1989).

Cantú-Paz, E. A survey of parallel genetic algorithms. Calculateurs Paralleles, Reseaux et Systemes Repartis 10 , 141–171 (1998).

Google Scholar  

Tao, T. Open question: best bounds for cap sets. WordPress Blog https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/ (2009).

Croot, E., Lev, V. F. & Pach, P. P. Progression-free sets in are exponentially small. Ann. Math. 185 , 331–337 (2017).

Ellenberg, J. S., Gijswijt, D. On large subsets of \({F}_{q}^{n}\) with no three-term arithmetic progression. Ann. Math. 185 , 339–343 (2017).

Naslund, E. & Sawin, W. Upper bounds for sunflower-free sets. Forum Math. Sigma 5 , e15 (2017).

Edel, Y. & Bierbrauer, J. Large caps in small spaces. Des. Codes Cryptogr. 23 , 197–212 (2001).

Article   MathSciNet   Google Scholar  

Edel, Y. Extensions of generalized product caps. Des. Codes Cryptogr. 31 , 5–14 (2004).

Hill, R. On the largest size of cap in S 5,3 . Rend Lincei. Sci. Fis. Mat. Nat. 54 , 378–384 (1973).

MathSciNet   Google Scholar  

Cameron, P. J. & Van Lint, J. H. Designs, Graphs, Codes and Their Links Vol. 3 (Cambridge Univ. Press, 1991).

Calderbank, A. R. & Fishburn, P. C. Maximal three-independent subsets of {0, 1, 2} n . Des. Codes Cryptogr. 4 , 203–211 (1994).

Tyrrell, F. New lower bounds for cap sets. Discrete Analysis https://doi.org/10.19086/da.91076 (2023).

Coffman, E. G., Garey, M. R. & Johnson, D. S. in Algorithm Design for Computer System Design (eds Ausiello, G. et al.) 49–106 (Springer, 1984).

Lee, C. C. & Lee, D. T. A simple on-line bin-packing algorithm. J. ACM 32 , 562–572 (1985).

Ramanan, P., Brown, D. J., Lee, C.-C. & Lee, D.-T. On-line bin packing in linear time. J. Algorithm. 10 , 305–326 (1989).

Seiden, S. S. On the online bin packing problem. J. ACM 49 , 640–671 (2002).

Balogh, J., Békési, J., Dósa, G., Sgall, J. & Stee, R. V. The optimal absolute ratio for online bin packing. In Proc. Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , SIAM (ed. Chekuri, C.) 1425–1438 (SIAM, 2014).

Balogh, J., Békési, J., Dósa, G., Epstein, L. & Levin, A. A new and improved algorithm for online bin packing. In Proc. 26th Annual European Symposium on Algorithms (ESA 2018) 5:1–5:14 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018).

Coffman, E. G., Csirik, J., Galambos, G., Martello, S. & Vigo, D. in Handbook of Combinatorial Optimization (eds Pardalos, P. M. et al.) 455–531 (Springer, 2013).

Martello, S. & Toth, P. Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28 , 59–70 (1990).

Angelopoulos, S., Kamali, S. & Shadkami, K. Online bin packing with predictions. J. Artif. Intell. Res. 36 , 4574–4580 (2022).

Chaitin, G. J. On the length of programs for computing finite binary sequences. J. ACM 13 , 547–569 (1966).

Li, M. et al. An Introduction to Kolmogorov Complexity and its Applications Vol. 3 (Springer, 2008).

Solomonoff, R. J. A formal theory of inductive inference. Part I. Inf. Control 7 , 1–22 (1964).

O’Neill, M., Vanneschi, L., Gustafson, S. & Banzhaf, W. Open issues in genetic programming. Genet. Program. Evolvable Mach. 11 , 339–363 (2010).

Polu, S. & Sutskever, I. Generative language modeling for automated theorem proving. Preprint at https://arxiv.org/abs/2009.03393 (2020).

Polu, S. et al. Formal mathematics statement curriculum learning. In International Conference on Learning Representations (2023).

Jiang, A. Q. et al. THOR: wielding hammers to integrate language models and automated theorem provers. Adv. Neural Info. Process. Syst. 35 , 8360–8373 (2022).

Mouret, J.-B. & Doncieux, S. Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity. In Proc. 2009 IEEE Congress on Evolutionary Computation 1161–1168 (IEEE, 2009).

Pugh, J. K., Soros, L. B. & Stanley, K. O. Quality diversity: a new frontier for evolutionary computation. Front. Robotics AI 3 , 40 (2016).

Helmuth, T., Spector, L. & Matheson, J. Solving uncompromising problems with lexicase selection. IEEE Trans. Evol. Comput. 19 , 630–643 (2015).

Hutter, M. & Legg, S. Fitness uniform optimization. IEEE Trans. Evol. Comput. 10 , 568–589 (2006).

de la Maza, M. An analysis of selection procedures with particular attention paid to proportional and Boltzmann selection. In Proc. Fifth International Conference on Genetic Algorithms (Morgan Kaufmann, 1993).

OpenAI, GPT-4 technical report. Preprint at https://arxiv.org/abs/2303.08774 (2023).

Millidge, B. Scaffolded LLMs as natural language computers. Beren’s Blog https://www.beren.io/2023-04-11-Scaffolded-LLMs-natural-language-computers (2023).

Schick, T. et al. Toolformer: language models can teach themselves to use tools. Preprint at https://arxiv.org/abs/2302.04761 (2023).

Park, J. S. et al. Generative agents: interactive simulacra of human behavior. In Proc. 36th Annual ACM Symposium on User Interface Software and Technology 1–22 (ACM, 2023).

Wu, J. et al. Recursively summarizing books with human feedback. Preprint at https://arxiv.org/abs/2109.10862 (2021).

Nye, M. et al. Show your work: scratchpads for intermediate computation with language models. In Deep Learning for Code Workshop, International Conference on Learning Representations (2022).

Yao, S. et al. ReAct: dynergizing reasoning and acting in language models. In Proc. International Conference on Learning Representations (2023).

Zelikman, E., Wu, Y., Mu, J. & Goodman, N. Star: bootstrapping reasoning with reasoning. Adv. Neural Info. Process. Syst. 35 , 15476–15488 (2022).

Wang, G. et al. Voyager: an open-ended embodied agent with large language models. Preprint at https://arxiv.org/abs/2305.16291 (2023).

Yin, P. et al. Natural language to code generation in interactive data science notebooks. Preprint at https://arxiv.org/abs/2212.09248 (2022).

Ni, A. et al. Lever: learning to verify language-to-code generation with execution. In Proc. International Conference on Machine Learning 26106–26128 (PMLR, 2023).

Zhou, S., Alon, U., Xu, F. F., Jiang, Z. & Neubig, G. Docprompting: generating code by retrieving the docs. In Proc. International Conference on Learning Representations (2022).

Banzhaf, W., Nordin, P., Keller, R. E. & Francone, F. D. Genetic Programming: An Introduction: On The Automatic Evolution of Computer Programs and its Applications (Morgan Kaufmann, 1998).

Langdon, W. B. & Poli, R. Foundations of Genetic Programming (Springer Science & Business Media, 2013).

Ma, H., Narayanaswamy, A., Riley, P. & Li, L. Evolving symbolic density functionals. Sci. Adv. 8 , eabq0279 (2022).

Article   ADS   PubMed   PubMed Central   Google Scholar  

Schmidt, M. & Lipson, H. Distilling free-form natural laws from experimental data. Science 324 , 81–85 (2009).

Chen, X. et al. Symbolic discovery of optimization algorithms. Preprint at https://arxiv.org/abs/2302.06675 (2023).

Koza, J. R. Genetic Programming II: Automatic Discovery of Reusable Programs (MIT, 1994).

Salustowicz, R. & Schmidhuber, J. Probabilistic incremental program evolution. Evol. Comput. 5 , 123–141 (1997).

Article   CAS   PubMed   Google Scholar  

Burke, E. et al. in Handbook of Metaheuristics (eds Glover, F. & Kochenberger, G. A.) 457–474 (Springer, 2003).

Ross, P. in Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (eds Burke, E. K. & Kendall, G.) 529–556 (Springer, 2005).

Burke, E. K. et al. Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64 , 1695–1724 (2013).

Burke, E. K., Hyde, M. R. & Kendall, G. Evolving bin packing heuristics with genetic programming. In Proc. International Conference on Parallel Problem Solving from Nature 860–869 (Springer, 2006).

Burke, E. K., Hyde, M. R., Kendall, G. & Woodward, J. Automatic heuristic generation with genetic programming: evolving a jack-of-all-trades or a master of one. In Proc. 9th Annual Conference on Genetic and Evolutionary Computation 1559–1565 (ACM, 2007).

Burke, E. K., Hyde, M. R. & Kendall, G. Providing a memory mechanism to enhance the evolutionary design of heuristics. In Proc. IEEE Congress on Evolutionary Computation 1–8 (IEEE, 2010).

Burke, E. K., Hyde, M., Kendall, G. & Woodward, J. R. The scalability of evolved on line bin packing heuristics. In Proc. 2007 IEEE Congress on Evolutionary Computation 2530–2537 (IEEE, 2007).

Bunel, R., Desmaison, A., Kohli, P., Torr, P. H. & Kumar, M. P. Learning to superoptimize programs. In Proc. International Conference on Learning Representations (2017).

Schkufza, E., Sharma, R. & Aiken, A. Stochastic superoptimization. ACM SIGARCH Comp. Archit. News 41 , 305–316 (2013).

Shypula, A. et al. Learning to superoptimize real-world programs. In Proc. Deep Learning for Code Workshop (ICLR 2022 Workshop) (2022).

Fawzi, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610 , 47–53 (2022).

Article   ADS   CAS   PubMed   PubMed Central   Google Scholar  

Mankowitz, D. J. et al. Faster sorting algorithms discovered using deep reinforcement learning. Nature 618 , 257–263 (2023).

Yang, F. et al. Launchpad: a programming model for distributed machine learning research. Preprint at https://arxiv.org/abs/2106.04516 (2021).

Download references

Acknowledgements

We thank R. Anil, V. Feinberg, E. Taropa, T. Hubert, J. Schrittwieser and S. Nowozin for their LLM support; T. Schaul, C. Fernando, A. Barreto and P. Gupta for discussions on evolutionary algorithms; M. Figurnov and T. Cemgil for reviewing the paper; F. Piccinini and S. Kenjeyev for their support on job scheduling; S. Blackwell for technical support; O. Ronneberger, F. Gimeno, B. Huergo, A. Mehrabian and A. Anand for useful advice and G. Holland for program management support.

Author information

These authors contributed equally: Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Alhussein Fawzi

Authors and Affiliations

Google DeepMind, London, UK

Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Pengming Wang, Pushmeet Kohli & Alhussein Fawzi

Department of Mathematics, University of Wisconsin-Madison, Madison, WI, USA

Jordan S. Ellenberg

Laboratoire de l’Informatique du Parallélisme, University of Lyon (Inria, ENS Lyon, UCBL, LIP), Lyon, France

You can also search for this author in PubMed   Google Scholar

Contributions

B.R.-P. conceived the project with help from A.F. and P.K. A.F. scoped problems and developed project vision. B.R.-P. and A.N. developed the initial FunSearch codebase. A.N., B.R.-P., M. Balog, F.J.R.R., M. Barekatain, E.D. and A.F. implemented and refined the different components of the system. M. Barekatain and A.N. imported and experimented with LLMs. M. Barekatain, A.N. and M. Balog worked on evaluating, debugging and improving the efficiency of experiments. M. Balog, M. Barekatain, B.R.-P., A.N., A.F., O.F. and J.S.E. contributed to the cap set problem. M.P.K., M. Balog and J.S.E. researched and analysed results from the admissible sets problem. E.D., M. Barekatain and P.W. contributed to the online bin packing problem. F.J.R.R. and O.F. researched and did experiments on other problems (Shannon capacity and corners problems), P.K. contributed technical advice and ideas. A.F., B.R.-P., E.D., F.J.R.R., M.P.K., M. Balog, A.N., J.S.E. and M. Barekatain wrote the paper.

Corresponding authors

Correspondence to Bernardino Romera-Paredes , Pushmeet Kohli or Alhussein Fawzi .

Ethics declarations

Competing interests.

The authors of the paper are planning to file a patent application relating to subject matter contained in this paper in the name of Google DeepMind.

Peer review

Peer review information.

Nature thanks Josh Grochow, Andrea Lodi, Jean-Baptiste Mouret, Talia Ringer and Tao Yu for their contribution to the peer review of this work.

Additional information

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Extended data figures and tables

Extended data fig. 1 example of best-shot prompting, based on the skeleton from fig. 2a ..

The prompt includes k  = 2 implementations sampled from the programs database, with higher-scoring implementations being more likely to be included.

Extended Data Fig. 2 Evolutionary method.

The initial programs are separated into islands and each of them is evolved separately. After a number of iterations, the islands with the worst score are wiped and the best program from the islands with the best score are placed in the empty islands. Evolution then proceeds separately again until the next reset. This process is repeated until termination.

Extended Data Fig. 3 Program clusters within islands.

Within each island, programs are grouped into clusters based on their signature (i.e., their scores on several inputs). We first sample clusters, favoring the ones with higher score. Within the chosen clusters, we sample a program, favoring shorter programs. The sampled programs are used to prompt the LLM which generates a new program. If the new program is correct, it is added to the island, either in an existing cluster or a new one if its signature was not yet present.

Supplementary information

Supplementary information.

Further details about the method and extra results.

Supplementary Data 1

This zipped code file contains: (a) the evolutionary algorithm, code manipulation routines and a single-threaded implementation of the FunSearch pipeline; and (b) output functions of interest produced by FunSearch.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Cite this article.

Romera-Paredes, B., Barekatain, M., Novikov, A. et al. Mathematical discoveries from program search with large language models. Nature 625 , 468–475 (2024). https://doi.org/10.1038/s41586-023-06924-6

Download citation

Received : 12 August 2023

Accepted : 30 November 2023

Published : 14 December 2023

Issue Date : 18 January 2024

DOI : https://doi.org/10.1038/s41586-023-06924-6

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

This article is cited by

Large language models help computer programs to evolve.

• Jean-Baptiste Mouret

Nature (2024)

Automated discovery of algorithms from data

• Paul J. Blazek
• Kesavan Venkatesh
• Milo M. Lin

Nature Computational Science (2024)

By submitting a comment you agree to abide by our Terms and Community Guidelines . If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Subscribe to the PwC Newsletter

Join the community, search results, ai programmer: autonomously creating software programs using genetic algorithms.

1 code implementation • 17 Sep 2017

In this paper, we present the first-of-its-kind machine learning (ML) system, called AI Programmer, that can automatically generate full software programs requiring only minimal human guidance.

EC-KitY: Evolutionary Computation Tool Kit in Python with Seamless Machine Learning Integration

2 code implementations • 21 Jul 2022

EC-KitY is a comprehensive Python library for doing evolutionary computation (EC), licensed under the BSD 3-Clause License, and compatible with scikit-learn.

Evaluating Search-Based Software Microbenchmark Prioritization

1 code implementation • 24 Nov 2022

However, a simple greedy technique utilizing solely the performance change history (without coverage information) is equally or more effective than the best coverage-based techniques while being considerably more efficient, with a runtime overhead of less than 1%.

Software Engineering

Improving the Detection of Burnt Areas in Remote Sensing using Hyper-features Evolved by M3GP

1 code implementation • 31 Jan 2020

One problem found when working with satellite images is the radiometric variations across the image and different images.

A Java Implementation of Parameter-less Evolutionary Algorithms

1 code implementation • 26 Jun 2015

The Parameter-less Genetic Algorithm was first presented by Harik and Lobo in 1999 as an alternative to the usual trial-and-error method of finding, for each given problem, an acceptable set-up of the parameter values of the genetic algorithm.

Genetic Programming is Naturally Suited to Evolve Bagging Ensembles

3 code implementations • 13 Sep 2020

Experimental comparisons on classification and regression tasks taken and reproduced from prior studies show that our algorithm fares very well against state-of-the-art ensemble and non-ensemble GP algorithms.

Multiobjective Programming for Type-2 Hierarchical Fuzzy Inference Trees

1 code implementation • 16 May 2017

Hence, the proposed HFIT is an efficient and competitive alternative to the other FISs for function approximation and feature selection.

Ensemble of heterogeneous flexible neural trees using multiobjective genetic programming

Machine learning algorithms are inherently multiobjective in nature, where approximation error minimization and model's complexity simplification are two conflicting objectives.

Layered TPOT: Speeding up Tree-based Pipeline Optimization

1 code implementation • 18 Jan 2018

With the demand for machine learning increasing, so does the demand for tools which make it easier to use.

Efficient Modelling of Ion Structure and Dynamics in Inorganic Metal Halide Perovskites

1 code implementation • 20 Mar 2020

Our molecular dynamics simulations make it possible to predict the compositional dependence of the ionic diffusion coefficient on bromide/iodide ratio and vacancy concentration.

Materials Science

Immediate opening ( uupdated August July 8, 2007) for scientific research programmer at Genetic Programming Inc.

www.genetic-programming.com

( the home page of genetic programming inc., a privately funded research group that does research in applying genetic programming).

Last updated July 8, 2007

What is Genetic Programming (GP)?

How genetic programming works, sources of information about the field of genetic programming (gp), genetic algorithms (ga), and the field of genetic and evolutionary computation (gec), conferences about genetic programming (gp) and genetic and evolutionary computation (gec), application areas for genetic programming, news about genetic programming, parallelization of genetic programming, john koza’s publications on genetic programming.

Other Links

Genetic programming (GP) is an automated method for creating a working computer program from a high-level problem statement of a problem. Genetic programming starts from a high-level statement of “what needs to be done” and automatically creates a computer program to solve the problem.

There are now 36 instances where genetic programming has automatically produced a result that is competitive with human performance , including   15 instances where genetic programming has created an entity that either infringes or duplicates the functionality of a previously patented 20 th -century invention, 6 instances where genetic programming has done the same with respect to a 21 st -centry invention, and 2 instances where genetic programming has created a patentable new invention.

Given these results, we say that “Genetic programming now routinely delivers high-return human-competitive machine intelligence.” Click here for our definitions of “human-competitive,”   the “AI ratio” (“artificial-to-intelligence” ratio) and “high-return,”   “routine,” and “machine intelligence.” This statement is the most important point of the 2003 book Genetic Programming IV : Routine Human-Competitive Machine Intelligence . Click here to read chapter 1 of Genetic Programming IV in PDF format.   Click here for 2004 awards for human-competitive results (based on presentations at the GECCO-2004 conference in Seattle on June 27, 2004).

The fact that genetic programming can evolve entities that are competitive with human-produced results suggests that genetic programming can be used as an automated invention machine to create new and useful patentable inventions. In acting as an invention machine, evolutionary methods, such as genetic programming, have the advantage of not being encumbered by preconceptions that limit human problem-solving to well- troden paths. Genetic programming has delivered a progression of qualitatively more substantial results in synchrony with five approximately order-of-magnitude increases in the expenditure of computer time (over the 15-year period from 1987 to 2002).

Genetic programming has 16 important attributes that one would reasonably expect of a system for automatic programming (sometimes also called program synthesis or program induction ). Genetic programming has seven important differences from conventional approaches to artificial intelligence (AI) and machine learning (ML). For additional information, click here for PowerPoint (PPT) presentation on genetic programming (about 5 Megabytes) similar to that presented at the 2003 Accelerating Change Conference on September 13, 2003 and similar to the overview lecture given on September 24, 2003 in John Koza’s course at Stanford University on genetic algorithms (GA) and genetic programming (GP).

Genetic programming starts with a primordial ooze of thousands of randomly created computer programs. This population of programs is progre ss ively evolved over a series of generations. The evolutionary search uses the Darwinian principle of natural selection (survival of the fittest) and analogs of various naturally occurring operations, including cro ss over (sexual recombination), mutation, gene duplication, gene deletion. Genetic programming sometimes also employs developmental proce ss es by which an embryo grows into fully developed organism. Old Chinese saying says “animated gif is worth one mega-word,” so click here for short tutorial of “What is GP?” including about two dozen animated gifs . This short tutorial contains a discu ss ion of the preparatory steps of a run of genetic programming, the executional steps (that is, the flowchart of genetic programming ), an illustrative simple run of genetic programming for a problem of symbolic regre ss ion of a quadratic polynomial, a discu ss ion of developmental genetic programming for the automatic synthesis of both the topology and sizing of analog electrical circuits (potentially also including placement and routing), and the use of a turtle to draw complex structures (such as antenna). In addition, genetic programming can automatically create, in a single run, a general (parameterized) solution to a problem in the form of a graphical structure whose nodes or edges represent components and where the parameter values of the components are specified by mathematical expre ss ions containing free variables. That is, genetic programming can automatically create a general solution to a problem in the form of a parameterized topology .

The technique of genetic programming (GP) is one of the techniques of the field of genetic and evolutionary computation (GEC) which, in turn, includes techniques such as genetic algorithms (GA), evolution strategies (ES), evolutionary programming (EP), grammatical evolution (GE), and machine code (linear genome) genetic programming.

• 16 authored books, 4 videos, and 4 edited books on genetic programming (GP) , including 6 books in the Genetic Programming Book series from Kluwer Academic Publishers (as part of the bigger list of 73 authored books, 32 edited books, and 4 videos on genetic and evolutionary computation ).
• 17 conference proceedings books on genetic programming (GP) , including the 3 annual GP conferences, 5 annual GECCO conferences (that now include the annual GP conference), 6 annual Euro-GP conferences, the 2003 Genetic Programming Theory and Practice workshop (GPTA), the 1995 AAAI Symposium on Genetic Programming, and the 1995 Workshop on Genetic Programming (as part of a bigger list of 99 conference proceedings books on evolutionary computation) .
• 3,440 published papers on genetic programming (as of November 28, 2003) in a searchable bibliography (with many on-line versions of papers) by over 880 authors maintained by William Langdon’s and Steven M. Gustafson
• Over 4,000 published papers on evolutionary computation in a searchable bibliography maintained by Karsten Weicker and Nicole Weicker containing entries on genetic and evolutionary computation and related areas (e.g. artificial life).
• About two dozen conferences with Published Proceedings that are held regularly in the field of genetic programming and genetic and evolutionary computation (GEC)
• 2004 awards for human-competitive results (based on presentations at the GECCO-2004 conference in Seattle on June 27, 2004).
• E-Mail Mailing List on Genetic Programming , the EC-Digest (formerly the GA-Digest), and other mailing lists.
• Genetic Programming and Evolvable Machines journal (published by Kluwer Academic Publishers and edited by Wolfgang Banzhaf) (started January 2000). This journal is available as part of membership in the International Society for Genetic and Evolutionary Computation (ISGEC)
• Evolutionary Computation journal (published by The MIT Press and edited by Marc Schoenauer). This journal is available as part of membership in International Society for Genetic and Evolutionary Computation (ISGEC)
• IEEE Transactions on Evolutionary Computation journal (published by IEEE Neural Network Society and edited by Xin Yao)
• Software for genetic programming, genetic algorithms, and other evolutionary computation techniques, including the "Little LISP" Computer Code for Genetic Programming as Contained in 1992 book Genetic Programming (Koza 1992)
• 37 completed Ph.D. theses on genetic programming
• 58 students working on thesis involving genetic programming
• A partial list of people compiled by Bill Langdon who are active in genetic programming
• International Society for Genetic and Evolutionary Computation (ISGEC) . ISGEC is the only membership organization in the field of genetic and evolutionary computation. It operates of the annual GECCO conference (largest conference in the field of genetic and evolutionary computation) and the biannual FOGA conference.
• Evo-Net —The Network of Excellence in Evolutionary Computation (an extensive clearinghouse of information about the field of genetic and evolutionary computation and operator of the annual Euro-GP conferences and the Evo-Net workshops)
• The GA Archives , including back i ss ues of the GA-Digest and EC-Digest, genetic algorithm code in various programming languages, an extensive list of conference announcements in the field of genetic and evolutionary computation, etc.
• Book series of genetic programming for Kluwer Academic Publishers book series on genetic programming, edited by John R. Koza
• Book series on genetic algorithms and evolutionary computation from Kluwer Academic Publishers, edited by David E. Goldberg.
• Courses (and short courses) at various universities on genetic algorithms, genetic programming, and evolutionary computation
• For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University
• 11 Books of Student Papers from John Koza's Courses at Stanford University on genetic algorithms and genetic programming and artificial life
• 6 Course Readers from John Koza's courses at Stanford University on genetic algorithms and genetic programming and artificial life
• John Koza's home page at Stanford University
• For information about the 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection , the 1994 book Genetic Programming II: Automatic Discovery of Reusable Programs , the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving , and the 2003 book Genetic Programming IV : Routine Human-Competitive Machine Intelligence . Click here to read chapter 1 of Genetic Programming IV book (2003) in PDF format.
• 36 human-competitive results produced by genetic programming , including 21 previously patented inventions replicated by genetic programming and 2 patentable new inventions generated by genetic programming.
• Link to http://www.genetic-programming.COM (“genetic-programming.COM” WITH the hyphen) (Genetic Programming Inc.) including information about 1,000-Pentium parallel computer for doing genetic programming research.
• Jobs for scientific research programmer at Genetic Programming Inc.
• Link to Jaime Fernandez’s genetic programming notebook site (“geneticprogramming.com” WITHOUT the hyphen)
• David Beasley’s Frequently Asked Questions about genetic and evolutionary computation . This comes in 6 parts. Part 2 has a summary of the different types of genetic and evolutionary computation.
• Annual 2005 Genetic and Evolutionary Computation (GECCO) conference to be held on June 25–29, 2005 (Saturday – Wednesday) in Washington DC . GECCO is the largest conference in the field of genetic and evolutionary computation. The GECCO-2005 conference is a combination of the 10 th annual Genetic Programming Conference (GP-2005) and the 14 th International Conference on Genetic Algorithms (ICGA-2005). GECCO is operated by the International Society for Genetic and Evolutionary Computation ( ISGEC ).
• Annual 2005 Euro-Genetic-Programming Conference (and the co-located Evolutionary Combinatorial Optimization conference and other Evo-Net workshops) to be held on March 30 – April 1, 2005 (Wednesday-Friday) in Lausanne , Switzerland .
• Annual NASA/DoD Conference on Evolvable Hardware (EH) to be held on June 24 – 26 (Thursday – Saturday), 2004 in Seattle.
• Genetic Programming Theory and Practice (GPTP) workshops at the University of Michigan in Ann Arbor in 2003 and 2004 and 2005 Genetic Programming Theory and Practice (GPTP) workshop to be held at the University of Michigan in Ann Arbor
• 2004 Asia-Pacific Workshop on Genetic Programming (ASPGP) held in Cairns , Australia on December 6-7 (Monday-Tuesday), 2004
• Past GP conferences f or 1996, 1997, and 1998 (including the SGA-98, the Symposium on Genetic Algorithms)
• Past Euro-GP conferences for 1998, 1999, 2000, 2001, 2002, and 2003
• Past GECCO conferences (Genetic and Evolutionary Computation Conferences) for 1999, 2000, 2001, 2002, 2003, and 2004. Starting in 1999, the annual GECCO conference includes the annual Genetic Programming Conference.

There are numerous applications of genetic programming. We are particularly interested in applying genetic programming to

• “Black Art Problems,” such as the automated synthesis of analog electrical circuits, controllers, antennas, networks of chemical reactions, optical systems, and other areas of design,
• “Programming The Unprogrammable ” (PTU) involving the automatic creation of computer programs for unconventional computing devices such as cellular automata, multi-agent systems, parallel programming systems, field-programmable gate arrays, field-programmable analog arrays, ant colonies, swarm intelligence, distributed systems, and the like, and
• Commercially Useful New Inventions (CUNI) involving the use of genetic programming as an automated "invention machine" for creating commercially usable new inventions.

We are constantly looking for new domain areas in which to apply the techniques of genetic programming to achieve human-competitive machine intelligence.

· For May 2003 IEEE Intelligent Systems article “What’s AI done for me lately? Genetic programming’s human-competitive results”, visit IEEE Intelligent Systems . Click here for PDF file .

· For February 2003 Scientific American article “Evolving inventions” on genetic programming by John Koza, Martin A. Keane, and Matthew J. Streeter, visit Scientific American.

· For Salon article on "Software that Writes Software" b y Alexis Willihnganz (August 10, 1999)

· For E. E. Times article on automatic synthesis of analog electrical circuits using genetic programming .

· For article in Computerbits on genetic programming .

· For Scientific American article by W. Wayt Gibbs on genetic programming.

· For Busine ss Week article (June 23, 1997) entitled "Stanford Eggheads and Entrepreneurs"

· For Busine ss Week article (August 25, 1997) entitled "What Matters is How Smart You Are"

· For U. S. News and World Report article on evolutionary computation and genetic programming.

· For Slashdot.org posting (August 10, 1999).

· For the451.com article entitled "Re-inventing the 'invention machine" (April 14, 2000).

In July 1999, Genetic Programming Inc. started operating a new 1,000-node Beowulf-style parallel cluster computer consisting of 1,000 Pentium II 350 MHz proce ss ors and a host computer. Click here for technical discu ss ion of parallel genetic programming and building the 1,000-Pentium Beowulf-style parallel cluster computer . About half of the 36 human-competitive results produced by genetic programming were obtained using computing systems that were substantially smaller than the 1,000-Pentium computer mentioned above. Fifteen of these human-competitive results were obtained on a 1995-vintage parallel computer system composed of 64 PowerPC 80 MHz proce ss ors with a spec95fp rating. This 1995-vintage computer has total computational power equal to only about 1/60 of that of the 1000-Pentium machine mentioned above. Five of these results were obtained on a 70-Alpha machine (whose spec95fp rating is 1/9 of that of the 1,000-Pentium machine mentioned above). One of these human competitive results were obtained with a 1994-vintage machine (whose spec95fp rating is 1/1,320 of that of the 1,000-Pentium machine mentioned above). The individual proce ss ors in the1 ,000 -Pentium machine have (as of July 2003) about 1/8 the speed of proce ss ors contained in commercially available $999 laptops, so that the 1,000-Pentium machine is approximately equivalent to a 125-proce ss or machine with 2003-vintage proce ss ors.

1000-Pentium Beowulf-Style Cluster Computer

( left and right sides) (july 29, 1999).

For picture of uninterruptable power supply (UPS) for new 1000-Pentium computer. Design and contracting of site for 1000-Pentium computer by Gordon Prill Inc . of Mountain View , California . The 1,000-Pentium machine was a ss embled by Stan Fox of the COMPAQ Sunnyvale Staging Center . For picture of earlier 70-node parallel computer with Senator Barbara Boxer (California), John Koza (back row), Oscar Stiffelman (front row), Forrest H Bennett III, and William Mydlowec. For picture of earlier 70-node parallel computer with Ellen Goldberg (President of Santa Fe Institute) , John Koza, Forrest H Bennett III, and Oscar Stiffelman.

• 1992 book on genetic programming entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection from The MIT Pre ss . The MIT Pre ss also publishes a videotape entitled Genetic Programming: The Movie a ss ociated with the first book. Click here for more information about this 1992 videotape .
• 1994 book on genetic programming entitled   Genetic Programming II: Automatic Discovery of Reusable Programs from The MIT Pre ss . The MIT Pre ss also publishes a videotape entitled Genetic Programming II Videotape: The Next Generation. associated with this second book. Click here for additional information about this 1994 videotape .
• 1999 book Genetic Programming III: Darwinian Invention and Problem Solving from Morgan Kaufmann (by John R. Koza, Forrest H Bennett III, David Andre, and Martin A. Keane). Morgan Kaufmann also publishes Genetic Programming III Videotape: Human-Competitive Machine Intelligence (by John R. Koza, Forrest H Bennett III, David Andre, Martin A. Keane, and Scott Brave). Click here for information about this 1999 videotape .
• 2003 book Genetic Programming IV : Routine Human-Competitive Machine Intelligence from Kluwer Academic Publishers (by John R. Koza, Martin A. Keane, Matthew J. Streeter, William Mydlowec, Je ss en Yu, and Guido Lanza ) (ISBN 1-4020-7446-8) Kluwer Academic Publisher also publishes a DVD disk Genetic Programming IV: Video: Routine Human-Competitive Machine Intelligence (by John R. Koza, Martin A. Keane, Matthew J. Streeter, William Mydlowec, Je ss en Yu, Guido Lanza, and David Fletcher) that is bound into this 2003 book.
• Stanford University technical reports from the Computer Science Department and Stanford BioMedical Informatics of which I am author or co-author can be obtained on the web, including
• STAN-TR-CS 1314 (1990) entitled Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems
• STAN-TR-CS 1528 (1994) entitled Architecture-Altering Operations for Evolving the Architecture of a Multi-Part Program in Genetic Programming
• STAN-TR-CS 1542 (1995) entitled Parallel Genetic Programming on a Network of Transputers
• SMI-95-0586 (1995) entitled A Programming Course in Bioinformatics for Computer and Information Science Students
• SMI-2000-0851 (2000) entitled Reverse Engineering and Automatic Synthesis of Metabolic Pathways from Observed Data Using Genetic Programming
• Abstracts, citations, and copies of research papers (almost all available in Post Script or PDF) by John Koza:

Click here for list of patents

Contact Information

Please send corrections or additions to this page to:

John R. Koza

Genetic Programming Inc. (Third Millennium On-Line Products Inc.)

Post Office Box K

Los Altos , California 94023 USA

FAX: 650-941-9430

E-mail: [email protected]

E-mail: [email protected]

· For information about t he annual Genetic and Evolutionary Computation Conference (GECCO) operated by the Association for Computing Special Interest Group on Genetic and Evolutionary Computation (SIGEVO)

· For information about the annual Human-Competitive Awards (the “ humies ”) in genetic and evolutionary computation offered at the annual Genetic and Evolutionary Computation Conference (GECCO)

· The home page of Genetic Programming Inc. at www.genetic-programming.com .

· The home page of John R. Koza (including online versions of most published papers)

· For information about John Koza’s course on genetic algorithms and genetic programming at Stanford University

· For information about National Popular Vote

· Information about the 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection , the 1994 book Genetic Programming II: Automatic Discovery of Reusable Programs , the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving , and the 2003 book Genetic Programming IV : Routine Human-Competitive Machine Intelligence . Click here to read chapter 1 of Genetic Programming IV book in PDF format.

· 4,000+ published papers on genetic programming (as of November 28, 2003) in a searchable bibliography (with many on-line versions of papers) by over 880 authors maintained by William Langdon’s and Steven M. Gustafson.

· For information on the Genetic Programming and Evolvable Machines journal

· For information on the Genetic Programming book series, see the Call For Book Proposals

Exploring the use of multi-gene genetic programming in regional models for the simulation of monthly river runoff series

• ORIGINAL PAPER
• Published: 04 January 2023
• Volume 37 , pages 1917–1941, ( 2023 )

Cite this article

• Dario Pumo 1 &
• Leonardo V. Noto 1  

244 Accesses

5 Citations

Explore all metrics

The use of new data-driven approaches based on the so-called expert systems to simulate runoff generation processes is a promising frontier that may allow for overcoming some modeling difficulties related to more complex traditional approaches. The present study highlights the potential of expert systems in creating regional hydrological models, for which they can benefit from the availability of large database. Different soft computing models for the reconstruction of the monthly natural runoff in river basins are explored, focusing on a new class of heuristic models, which is the Multi-Gene Genetic Programming (MGGP). The region under study is Sicily (Italy), where a regression based rainfall-runoff model, here used as benchmark model, was previously built starting from the analysis of a regional database relative to several gauged watersheds across the region. In the present study, different models are created using the same dataset, including: six MGGPs generated considering different modeling set-up; a Multi-Layer Perceptron Artificial Neural Network (ANN); two new hybrid models (ANN-MGGP), combining a Classifier ANN and two MGGPs that simulate separately low and high runoff. Results show how all the soft computing models perform similarly and outperform the benchmark model, demonstrating that MGGP can be considered as a valid alternative to the much more consolidated ANN technique. The new introduced hybrid ANN-MGGP is the only model showing at least satisfactory performance (i.e. Nash–Sutcliffe Efficiency above 0.5) over the full range of 38 watersheds explored, representing a useful regional tool for reconstructing monthly runoff series also at ungauged sites.

Graphical abstract

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Season algorithm-multigene genetic programming: a new approach for rainfall-runoff modelling.

Ali Danandeh Mehr & Vahid Nourani

Runoff Simulation Under Future Climate Change Conditions: Performance Comparison of Data-Mining Algorithms and Conceptual Models

Icen Yoosefdoost, Abbas Khashei-Siuki, … Omolbani Mohammadrezapour

A Genetic Programming Approach to System Identification of Rainfall-Runoff Models

Jayashree Chadalawada, Vojtech Havlicek & Vladan Babovic

Abbreviations

Basin authority of Sicilian Region (Autorità di Bacino della Regione Sicilia)

• Artificial neural network

Curve number

Digital elevation model

Genetic algorithm

Gene expression programming

Geographic information system

• Genetic programming

Hidden layer

Linear genetic programming

Percent difference in RMSE for soft computing models with respect to the benchmark model

Nash–Sutcliffe efficiency

Multi-gene genetic programming

Output layer

Quantum GIS

Soil conservation service

Supplementary material

Simple moving average

Sub-expression trees

Root mean squared error

Root mean squared error for the benchmark model

Root mean squared error for soft computing model

Trinacria model for monthly time series

Abda Z, Zerouali B, Chettih M, Santos CAG, de Farias CAS, Elbeltagi A (2022) Assessing machine learning models for streamflow estimation: a case study in Oued Sebaou watershed (Northern Algeria). Hydrol Sci J 67(9):1328–1341. https://doi.org/10.1080/02626667.2022.2083511

Article   Google Scholar  

Achite M, Banadkooki FB, Ehteram M et al (2022) Exploring Bayesian model averaging with multiple ANNs for meteorological drought forecasts. Stoch Environ Res Risk Assess 36:1835–1860. https://doi.org/10.1007/s00477-021-02150-6

Adnan RM, Petroselli A, Heddam S et al (2021) Short term rainfall-runoff modelling using several machine learning methods and a conceptual event-based model. Stoch Environ Res Risk Assess 35:597–616. https://doi.org/10.1007/s00477-020-01910-0

Babovic V (2009) Introducing knowledge into learning based on genetic programming. J Hydroinf 11(3–4):181–193

Berry MJA, Linoff G (1997) Data mining techniques. Wiley, New York

Google Scholar  

Bhadra A, Bandyopadhyay A, Singh R, Raghuwanshi NS (2010) Rainfall-runoff modeling: comparison of two approaches with different data requirements. Water Resour Manag 24:37–62

Boughton W, Chiew F (2007) Estimating runoff in ungauged catchments from rainfall, PET and the AWBM model. Environ Model Softw 22(4):476–487. https://doi.org/10.1016/j.envsoft.2006.01.009

Bourdin DR, Fleming SW, Stull RB (2012) Streamflow modelling: a primer on applications, approaches and challenges. Atmos Ocean 50(4):507–536

Bhusal A, Parajuli U, Regmi S, Kalra A (2022) Application of machine learning and process-based models for rainfall-runoff simulation in DuPage River Basin. Illinois Hydrol 2022(9):117. https://doi.org/10.3390/hydrology9070117

Cigizoglu HK (2005) Application of generalized regression neural networks to intermittent flow forecasting and estimation. J Hydrol Eng ASCE 10(4):336–341

Črepinšek M, Liu S-H, Mernik M (2013) Exploration and exploitation in evolutionary algorithms: a survey. ACM Comput Surv 45(3):33. https://doi.org/10.1145/2480741.2480752

Cutore P, Cristaudo G, Campisano A, Modica C, Cancelliere A, Rossi G (2007) Regional models for the estimation of streamflow series in ungauged Basins. Water Resour Manag 21:789–800. https://doi.org/10.1007/s11269-006-9110-7

Danandeh Mehr A, Kahya E, Olyaie E (2013) Streamflow prediction using linear genetic programming in comparison with a neuro-wavelet technique. J Hydrol 505:240–249

Demirel MC, Booij MJ, Hoekstra AY (2015) The skill of seasonal ensemble low-flow forecasts in the Moselle River for three different hydrological models. Hydrol Earth Syst Sci 19:275–291. https://doi.org/10.5194/hess-19-275-2015

Di Piazza A, Lo Conti F, Noto LV, Viola F, La Loggia G (2011) Comparative analysis of different techniques for spatial interpolation of rainfall data to create a serially complete monthly time series of precipitation for Sicily, Italy. Int J Appl Earth Obs Geoinf 13:396–408

Di Piazza A, Lo Conti F, Viola F, Eccel E, Noto LV (2015) Comparative analysis of spatial interpolation methods in the mediterranean area: application to temperature in sicily. Water 7(5):1866–1888. https://doi.org/10.3390/w7051866

Escalante-Sandoval C, Amores-Rovelo L (2017) Regional monthly runoff forecast in southern Canada using ANN K-Means, and L-Moments Techniques, Canadian water resources. Journal Revue Canadienne Des Ressources Hydriques 42(3):205–222. https://doi.org/10.1080/07011784.2017.1290552

Gandomi AH, Alavi AH (2012a) A new multi-gene genetic programming approach to nonlinear system modeling. Part I: materials and structural engineering problems. Neural Comput Appl 21:171–187. https://doi.org/10.1007/s00521-011-0734-z

Gandomi AH, Alavi AH (2012b) A new multi-gene genetic programming approach to nonlinear system modeling. Part II: geotechnical and earthquake engineering problems. Neural Comput Appl 21:189–201

Gauch M, Mai J, Lin J (2021) The proper care and feeding of CAMELS: How limited training data affects streamflow prediction. Environ Model Softw 135:104926. https://doi.org/10.1016/j.envsoft.2020.104926

Ghorbani MA, Khatibi R, Danandeh Mehr A, Asadi H (2018) Chaos-based multigene genetic programming: a new hybrid strategy for river flow forecasting. J Hydrol 562:455–467

He Y, Bárdossy A, Zehe E (2011) A review of regionalisation for continuous streamflow simulation. Hydrol Earth Syst Sci 15(11):3539–3553

Hrnjica B, Danandeh Mehr A (2018) Optimized genetic programming applications: emerging research and opportunities. IGI Global, New York

Kajbaf AA, Bensi M, Brubaker KL (2022) Temporal downscaling of precipitation from climate model projections using machine learning. Stoch Environ Res Risk Assess. https://doi.org/10.1007/s00477-022-02259-2

Khan MT, Shoaib M, Hammad M, Salahudin H, Ahmad F, Ahmad S (2021) Application of machine learning techniques in rainfall-runoff modelling of the Soan River Basin. Pakistan Water 2021(13):3528. https://doi.org/10.3390/w13243528

Kratzert F, Klotz D, Herrnegger M, Sampson AK, Hochreiter S, Nearing G (2019) Toward improved predictions in ungauged basins: exploiting the power of machine learning. Water Resour Res 55:11344–11354. https://doi.org/10.1029/2019WR026065

Kisi O (2004) River flow modeling using artificial neural networks. J Hydrol Eng ASCE 9(1):60–63

Kisi O, Cigizoglu HK (2007) Comparison of different ANN techniques in river flow prediction. Civ Eng Environ Syst 24(3):211–231

Kisi O, Nia AM, Gosheh MG, Tajabadi MRJ, Ahmadi A (2012) Intermittent streamflow forecasting by using several data driven techniques. Water Resourc Manag 26(2):457–474

Kizza M, Guerrero JL, Rodhe A, Chong-yu X, Ntale HK (2013) Modelling catchment inflows into Lake Victoria: regionalisation of the parameters of a conceptual water balance model. Hydrol Res 44(5):789–808

Koza J (1992) Genetic programming, on the programming of computers by means of natural selection. MIT Press, Cambridge

Lee S, Ryu JH, Min K, Won JS (2003) Landslide susceptibility analysis using GIS and artificial neural network. Earth Surf Proc Land 28:1361–1376

Livneh B, Kumar R, Samaniego L (2015) Influence of soil textural properties on hydrologic fluxes in the Mississippi river basin. Hydrol Process 29:4638–4655. https://doi.org/10.1002/hyp.10601

MacKay DJC (1992) Bayesian interpolation. Neural Comput 4(3):415–447

Mehr AD (2018a) An improved gene expression programming model for streamflow forecasting in intermittent streams. J Hydrol 563:669–678. https://doi.org/10.1016/j.jhydrol.2018.06.049

Mehr AD (2018b) Month ahead rainfall forecasting using gene expression programming. Am J Earth Environ Sci 1(2):63–70

Mehr AD, Demirel MC (2016) On the calibration of multigene genetic programming to simulate low flows in the Moselle River. Uludağ Univ J Faculty Eng 21(2):365–376. https://doi.org/10.17482/uumfd.278107

Mehr AD, Nourani V (2018) Season algorithm-multigene genetic programming: a new approach for rainfall-runoff modelling. Water Resour Manag 32:2665–2679. https://doi.org/10.1007/s11269-018-1951-3

Meshgi A, Schmitter P, Chui TM, Babovic V (2015) Development of a modular streamflow model to quantify runoff contributions from different land use types in tropical urban environments using genetic programming. J Hydrol 525:711–723

Mohammad-Azari S, Bozorg-Haddad O, Loáiciga HA (2020) State-of-art of genetic programming applications in water-resources systems analysis. Environ Monitor Assessm 192(2):73. https://doi.org/10.1007/s10661-019-8040-9

Moriasi DN, Arnold JG, Van Liew MW, Bingner RL, Harmel RD, Veith TL (2007) Model evaluation guidelines for systematic quantification of accuracy in watershed simulations. Trans ASABE 50(3):885–900

Mosavi A, Ozturk P, Chau K (2018) Flood prediction using machine learning models literature review. Water 10(11):1536. https://doi.org/10.3390/w10111536

Nash JE, Sutcliffe JV (1970) River flow forecasting through conceptual models, 1. Discuss Princip J Hydrol 10:282–290

Nearing GS, Kratzert F, Sampson AK, Pelissier CS, Klotz D, Frame JM et al (2021) What role does hydrological science play in the age of machine learning? Water Resour Res 57:e2020WR028091. https://doi.org/10.1029/2020WR028091

Noh H, Kwon S, Seo IW, Baek D, Jung SH (2021) Multi-gene genetic programming regression model for prediction of transient storage model parameters in natural rivers. Water 13(1):76. https://doi.org/10.3390/w13010076

Noto LV (2014) Exploiting the topographic information in a PDM-based conceptual hydrological model. J Hydrol Eng 19(16):1173–1185. https://doi.org/10.1061/(ASCE)HE.1943-5584.0000908

Noto LV, Cipolla G, Francipane A, Pumo D (2022) Climate change in the mediterranean basin (part I): induced alterations on climate forcings and hydrological processes. Water Resour Manag. https://doi.org/10.1007/s11269-022-03400-0

Pumo D, Viola F, Noto LV (2016a) Generation of natural runoff monthly series at ungauged sites using a regional regressive model. Water 8(5):209. https://doi.org/10.3390/w8050209

Pumo D, Caracciolo D, Viola F, Noto LV (2016b) Climate change effects on the hydrological regime of small non-perennial river basins. Sci Total Environ 2016(542):76–92. https://doi.org/10.1016/j.scitoten.2015.10.109

Pumo D, Lo Conti F, Viola F, Noto LV (2017) An automatic tool for reconstructing monthly time-series of hydro-climatic variables at ungauged basins. Environ Model Softw 95:381–400. https://doi.org/10.1016/j.envsoft.2017.06.045

Rahimzad M, Moghaddam Nia A, Zolfonoon H, Soltani J, Mehr AD, Kwon H (2020) Performance comparison of an LSTM-based deep learning model versus conventional machine learning algorithms for streamflow forecasting. Water Resour Manag 35:4167–4187. https://doi.org/10.1007/s11269-021-02937-w

Ravansalar M, Rajaee T, Kisi O (2017) Wavelet-linear genetic programming: a new approach for modeling monthly streamflow. J Hydrol 549:461–475

Razavi T, Coulibaly P (2013) Streamflow prediction in ungauged basins: review of regionalization methods. J Hydrol Eng 18(8):958–975

Riahi-Madvar H, Dehghani M, Seifi A, Singh VP (2019) Pareto optimal multigene genetic programming for prediction of longitudinal dispersion coefficient. Water Resour Manag 33:905–921

Roushangar K, Alizadeh F (2019) Scenario-based prediction of short-term river stage–discharge process using wavelet-EEMD-based relevance vector machine. J Hydroinf 21(1):56–76. https://doi.org/10.2166/hydro.2018.023

Roushangar K, Alizadeh F, Nourani V (2018) Improving capability of conceptual modeling of watershed rainfall–runoff using hybrid wavelet-extreme learning machine approach. J Hydroinf 20(1):69–87. https://doi.org/10.2166/hydro.2017.011

Samaniego L, Kumar R, Attinger S (2010) Multiscale parameter regionalization of a grid-based hydrologic model at the mesoscale. Water Resour Res 46:W05523. https://doi.org/10.1029/2008WR007327

Sachindra DA, Kanae S (2019) Machine learning for downscaling: the use of parallel multiple populations in genetic programming. Stoch Env Res Risk Assess 33:1497–1533. https://doi.org/10.1007/s00477-019-01721-y

Sattar AMA, Gharabaghi B (2015) Gene expression models for prediction of longitudinal dispersion coefficient in streams. J Hydrol 524:587–596. https://doi.org/10.1016/j.jhydrol.2015.03.016

Searson D (2015) GPTIPS 2: an open-source software platform for symbolic data mining. In: Al., AHG et (ed) Chapter 22 in handbook of genetic programming applications. Springer, New York

Shoaib M, Shamseldin AY, Melville BW, Khan MM (2015) Runoff forecasting using hybrid wavelet gene expression programming (WGEP) approach. J Hydrol 527:326–344

Shu XS, Ding W, Peng Y, Wang ZR, Wu J, Li M (2021) Monthly streamflow forecasting using convolutional neural network. Water Resour Manag 35(15):5089–5104

Singh KK, Pal M, Singh VP (2010) Estimation of mean annual flood in Indian catchments using backpropagation neural network and M5 model tree. Water Resour Manag 24:2007–2019

Sordo-Ward A, Granados A, Iglesias A, Garrote L, Bejarano MD (2019) Adaptation effort and performance of water management strategies to face climate change impacts in six representative basins of Southern Europe. Water 11(5):1078

Stathakis D (2009) How many hidden layers and nodes? Int J Remote Sens 30(8):2133–2147. https://doi.org/10.1080/01431160802549278

Xu W, Chen J, Zhang XJ (2022) Scale effects of the monthly streamflow prediction using a state-of-the-art deep learning model. Water Resour Manag 36:3609–3625. https://doi.org/10.1007/s11269-022-03216-y

Yesilnacar E, Topal T (2005) Landslide susceptibility mapping: a comparison of logistic regression and neural networks methods in a medium scale study, Hendek region (Turkey). Eng Geol 79:251–266

Zhang Y, Chiew FHS, Li M, Post D (2018) Predicting runoff signatures using regression and hydrological modeling approaches. Water Resour Res 54:7859–7878. https://doi.org/10.1029/2018WR023325

Download references

Acknowledgements

The authors thank anonymous reviewers for their helpful suggestions on the quality improvement of the present paper.

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

Author information

Authors and affiliations.

Dipartimento di Ingegneria, Università degli Studi di Palermo, Viale delle Scienze, Ed. 8, 90128, Palermo, Italy

Dario Pumo & Leonardo V. Noto

You can also search for this author in PubMed   Google Scholar

Contributions

DP is the first and corresponding author. Both authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by DP. The first draft of the manuscript was written by DP and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Dario Pumo .

Ethics declarations

Conflict of interest.

The authors have no relevant financial or non-financial interests to disclose.

Data availability

Data used in this article can be found, on request, at the website of the Basin Authority of Sicilian Region (Autorità di Bacino della Regione Sicilia) through the following link: https://www.regione.sicilia.it/istituzioni/regione/strutture-regionali/presidenza-regione/autorita-bacino-distretto-idrografico-sicilia . Data can also be freely visualized at the website of ISPRA (Istituto Superiore per la Protezione e la Ricerca Ambientale, https://www.isprambiente.gov.it ).

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file1 (DOCX 4053 kb)

Rights and permissions.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Pumo, D., Noto, L.V. Exploring the use of multi-gene genetic programming in regional models for the simulation of monthly river runoff series. Stoch Environ Res Risk Assess 37 , 1917–1941 (2023). https://doi.org/10.1007/s00477-022-02373-1

Download citation

Accepted : 20 December 2022

Published : 04 January 2023

Issue Date : May 2023

DOI : https://doi.org/10.1007/s00477-022-02373-1

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Evolutionary optimization
• Regional runoff model
• Soft computing
• Find a journal
• Publish with us
• Track your research