Searching for Programs Instead of Parameters
Most optimization algorithms search for numbers. A genetic algorithm evolves a string of bits or a vector of real values, and a neural network adjusts millions of weights inside an architecture someone else designed. In both cases the shape of the solution is fixed ahead of time. The algorithm only fills in the blanks.
Genetic programming asks for something more ambitious. The thing being evolved is a program: a formula, a decision procedure, a circuit, a set of instructions. The size and structure of the solution are not decided in advance. They emerge from the search.
The idea has an early version in Nichael Cramer’s 1985 paper at the first International Conference on Genetic Algorithms, which represented simple sequential programs in a form that could be mutated and recombined. The field took its name and its standard form from John Koza, whose 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press) set out the tree-based approach that most people still mean when they say GP.
Programs as Trees
In Koza’s formulation, a program is a tree. Internal nodes are functions such as addition, multiplication, sine or an if-then-else. Leaves are terminals: input variables and constants. The expression (x + 3) * sin(y) becomes a tree with a multiplication at the root, an addition on one side and a sine on the other.
The designer chooses two sets before the run starts. The function set lists the operations the program may use, and the terminal set lists the inputs it may read. This choice matters a great deal. Give the search only arithmetic and it can never discover a periodic signal; give it fifty operators and the space becomes so large that progress slows to a crawl.
Every function must also accept any value another node might produce. Koza called this closure. Division is the usual example: a random tree will sooner or later divide by zero, so GP systems use a «protected» division that returns a fixed value in that case (Koza used 1) instead of crashing.
The first generation is random. A common recipe from Koza’s book is ramped half-and-half, which builds some trees to full depth and others with irregular shapes, across a range of depths, so the starting population contains small, large, bushy and thin programs.
Crossover and Mutation on Trees
Each program is run on a set of test cases and scored. Better programs are more likely to be selected as parents, usually through tournament selection, where a few individuals are drawn at random and the best of them wins.
Subtree crossover is the signature operator. Pick a random node in each parent, cut there, and swap the two branches. The children are valid programs by construction, because any subtree can replace any other once closure holds. Mutation does the same thing with a single parent, replacing a random branch with a freshly generated one.
Later research changed the representation without changing the principle. Cartesian GP, introduced by Julian Miller and Peter Thomson in 2000, encodes programs as graphs on a grid, which lets one node feed several others. Lee Spector’s PushGP uses a stack-based language where programs can manipulate their own code. Selection also got sharper: lexicase selection, studied by Thomas Helmuth, Lee Spector and James Matheson in a 2015 IEEE Transactions on Evolutionary Computation paper, picks parents by filtering on test cases one at a time in random order instead of averaging the errors, which keeps specialists alive that an averaged score would throw away.
Bloat
Run GP long enough and the programs grow. Trees get deeper and wider while fitness barely improves. This is called bloat, and it was noticed in the earliest runs.
Much of the extra material is code that does nothing, such as adding x and then subtracting it, or a branch that can never execute. Early explanations blamed these «introns,» arguing that they protect useful code from destructive crossover. Sean Luke later showed that the causation probably runs the other way: inactive code accumulates because trees grow, not the reverse. William Langdon and Riccardo Poli proposed an explanation that does not depend on introns at all. For any program, there are far more large programs with the same behavior than small ones, so a search that drifts among equally fit solutions will tend to drift toward larger ones.
Bloat is not a cosmetic problem. Large programs are slow to evaluate, hard to read, and more likely to overfit. Practitioners control it with depth limits, size penalties added to fitness, or multi-objective selection that treats size as a second objective. Luke and Liviu Panait compared several of these methods in a 2006 paper in Evolutionary Computation, and the simple depth limit Koza used in 1992 was competitive with the more elaborate alternatives.
Symbolic Regression
The most common use of GP today is symbolic regression: given data, find a formula that fits it. Unlike linear regression, the form of the formula is not given. Unlike a neural network, the answer is an equation a person can read.
The best-known demonstration is a 2009 Science paper by Michael Schmidt and Hod Lipson at Cornell, «Distilling Free-Form Natural Laws from Experimental Data.» They recorded the motion of physical systems, from simple harmonic oscillators to a chaotic double pendulum, and used symbolic regression to search for quantities that stayed constant over time. The system recovered Hamiltonians, Lagrangians and conservation laws without being told what physics to look for. The method became a commercial tool called Eureqa.
GP has also held up under systematic comparison. In 2021, William La Cava and colleagues published SRBench at NeurIPS, a benchmark of 14 symbolic regression methods on 252 datasets, including real-world regression tasks and physics equations with known answers. On the real-world data, Operon, a GP system that tunes constants with the Levenberg-Marquardt algorithm, produced the most accurate models, and four of the top five methods were GP-based. On the noiseless physics problems, AI Feynman, which is not a GP method, recovered the most exact equations, though its advantage shrank as noise was added. No single method won everywhere.
Case: Patents, Antennas and Lenses
Koza spent years trying to show that GP could produce results a human expert would respect. He set criteria for «human-competitive» results, one being that the result duplicates or improves on an invention that had been patented. A 2010 survey in Genetic Programming and Evolvable Machines counted at least 36 such results, including 15 that duplicated the function of a patented 20th-century invention, 6 that did the same for 21st-century patents, and 2 that were patentable new inventions. His group rediscovered six patented optical lens systems (GECCO 2005), and a patent for improved general-purpose controllers, filed with GP-generated designs, was issued in 2005 as U.S. Patent 6,847,851.
A different group built a result that flew. For NASA’s Space Technology 5 mission, Jason Lohn, Gregory Hornby and Derek Linden evolved X-band antennas under tight requirements on beam width and bandwidth. They ran two algorithms, one of which used a GP-style tree representation that allowed the antenna’s arms to branch. The evolved designs outperformed the one produced by the mission’s antenna contractor, and an evolved antenna went to space on the ST5 spacecraft in 2006. It looks like a bent paperclip, and it is not a shape anyone would have sketched by hand.
Case: Repairing Bugs With GenProg
In 2012, Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest and Westley Weimer presented a study at ICSE with a memorable title: «A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each.» Their system, GenProg, takes a buggy C program and a test suite with at least one failing test. It evolves patches by copying, deleting and moving statements that already exist elsewhere in the program, and keeps a patch if all the tests pass.
The paper helped start the field of automated program repair. It also led to one of the most useful critiques in the GP literature. In 2015, Zichao Qi, Fan Long, Sara Achour and Martin Rinard reanalyzed the patches at ISSTA. Because of errors in the test scripts, most reported patches did not pass the full test suite. Only 18 were plausible, and only 2 were correct. Many of the rest simply deleted the functionality that was failing. The authors built a system called Kali that only deletes code, and it found plausible patches for 27 defects, more than GenProg.
Language Models as Mutation Operators
Random subtree swaps are a crude way to edit code. A recent line of work replaces them with a large language model. In FunSearch, published in Nature in 2023 by Bernardino Romera-Paredes and colleagues at Google DeepMind, a population of Python programs is kept and scored by an automatic evaluator, and a pretrained language model writes new candidates by modifying the best ones.
The structure is recognizably evolutionary: a population, variation, selection, an islands model to keep diversity. Applied to the cap set problem in combinatorics, FunSearch found a cap set of size 512 in eight dimensions, where the largest known had been 496, and it improved the asymptotic lower bound. It also found heuristics for online bin packing that beat the standard first-fit and best-fit rules. As in classic GP, the output is a program, short enough for a mathematician to read and analyze.
Closing Thought
Every genetic programming system depends on a fitness function, and in GP the fitness function is the specification. The search has no idea what the programmer wanted. It only knows which tests passed. GenProg’s deleted features, the bloated trees full of dead code, and the protected division that quietly returns 1 are all the same lesson: evolution finds whatever satisfies the test, including answers nobody intended. That is why FunSearch paired its language model with a strict evaluator, and why the hardest part of using GP is still writing a test that says exactly what you mean.
By: Max Johnson B.
Deja una respuesta