Chapter 101 17.3 Unintentionally inserting willows and willows into shadows

It was John Koza who really started to take the evolution of logic programs from theory to practice.He is a professor of computer science at Stanford University and a student of John Holland.Together with several other students of Holland, he made Holland's genetic algorithm, which was once neglected in the 1960s and 1970s, reappear, and entered the revival period of parallel algorithms in the late 1980s. Unlike "The Artist" Sims, Koza is not content to simply explore the space of possible equations, he wants to evolve the best equation that can solve a specific problem.As a far-fetched example, suppose that among all possible images there is one image that attracts the cows to gaze at it, thereby increasing milk production.Koza's method then evolves the equations that draw this particular picture.In this example, Koza rewarded equations that plotted even a slight increase in milk production until milk production could no longer be increased.Of course, the problem Koza chose was much more practical than this, such as finding an equation that can control the movement of the robot.

But in a sense, his search is similar to that of Sims and other researchers.He was also scouring the Borges library of possible computer programs—only instead of poking around aimlessly, he was looking for the best equation to solve a particular practical problem.Koza wrote in "Genetic Programming": "The solution of these problems can be reformulated as a search for the most suitable single computer program among possible computer programs." Koza's idea of ​​"finding" the equation by breeding was considered counterintuitive for the same reason computer experts scoffed at Ray's evolutionary scheme.In the past, everyone "knew" that logic programs were fragile and would not tolerate any changes.In computer science theory, a program has only two states: (1) running without failure; (2) failing to run after modification.The third state - running after random modification - is impossible.Mild program derailments are called program bugs, and this is what people spend a lot of money trying to avoid.Experts used to think that if incremental improvement (evolution) of computer equations was possible, it would surely occur only in a few rare domains or specialized types of programs.

However, the results of the study of artificial evolution unexpectedly show that the conventional wisdom is dead wrong.Sims, Ray, and Koza all have excellent evidence that logic programs can evolve through incremental improvements. Koza's approach is based on the intuition that if two mathematical equations work somewhat well in solving a problem, then some part of them is valuable.If valuable parts of the two could be reintegrated into a new program, the result could be more efficient than either parent program.Koza randomly recombined the parts of the two parent programs thousands of times, hoping that probabilistically speaking, these combinations would contain a program that made an optimal arrangement of the valuable parts of the parent program, and thus could better solve question.

Koza's approach shares many similarities with Sims'.Koza's "data broth" also contained about a dozen mathematical primitives expressed in LISP, such as addition, multiplication, and cosine.These primitives are randomly strung together to form logical "trees"—a hierarchical structure that resembles a computer flowchart.Koza's system creates 500 to 10,000 different independent logical trees like a breeding population. The "data culture" usually converges to a suitable offspring after about 50 generations of reproduction. The exchange of branches from tree to tree forces them to mutate.Sometimes a long branch is grafted, sometimes just a twig or "leaf" from the top of the branch.Each branch can be viewed as a complete logical subroutine composed of smaller branches.Through branch swapping, a small piece of equation (a branch), or a useful little program, can be preserved and even propagated.

Evolution through equations can solve all kinds of weird problems.A classic problem Koza used it to solve was how to get a broom to stand on a skateboard.The skateboard has to move back and forth, propelled by a motor, to keep the inverted broom upright in the center of the board.Motor control is computationally staggering, but the control circuitry is not much different from the circuitry that operates a robot arm.Koza discovered that he could evolve a program to achieve this control. The problems he used to test the evolution of equations are: the strategy of getting out of the maze; the solution method of the quadratic equation; the method of optimizing the shortest path connecting many cities (also known as the traveling salesman problem); Winning strategy in the game.In each case, Koza's system looked for a general formula to solve the problem each time, rather than looking for a specific answer for each test instance.The more a formula is tested with different examples, the better it will evolve.

Although equation evolution can produce effective solutions, these solutions are often as ugly as they are ugly.When Koza picked up his highly evolved treasures and started looking at the details, he was as shocked as Sims and Ray: the solution was a mess!Evolution either takes a big detour, or takes a shortcut through a logical loophole that makes a seven-mile turn.It's full of redundancies and unrefined.When something goes wrong, it is better to add a section of error correction procedures, or to divert the main flow to bypass the wrong area, than to sell the wrong part.The final formula is somewhat of a magical Rubin Goldberg linkage, relying on certain coincidences to work.Of course, it's actually a Goldberg's Magic Link.

Take, for example, a problem Koza once played to his evolutionary machine.It was a figure consisting of two intertwined helixes, roughly similar to the double helix on a pinwheel.Koza asked the evolutionary equation machine to evolve an optimal equation to determine which of the 200 or so data points lies on each line of the intertwined double helix. Koza loaded 10,000 randomly generated computer formulas into his data culture.He let them evolve while his machine picked out the equations most likely to yield the correct formula.While Koza slept, the program tree swapped branches, occasionally producing a program that worked better.While he was on vacation, the machine was running as usual.When he returned from vacation, the system had evolved an answer that could perfectly divide the double helix.

This is the future of software programming!Define a problem, and the machine finds a solution while the programmer is golfing.But the solutions found by Koza's machines offer a glimpse into the handiwork of evolution.Here's the formula it came up with: (SIN (IFLTE (IFLTE (+ YY) (+ XY) (- XY) (+ YY)) (* XX) (SIN (IFLTE (% YY) (% (SIN (SIN (% Y 0.30400002))) X) (% Y 0.30400002) (IFLTE (IFLTE (% (SIN (% (% Y (+ XY)) 0.30400002)) (+ XY)) (% X 0.10399997) (- XY) (* (+ -0.12499994 -0.15999997) ( - XY))) 0.30400002 (SIN (SIN (IFLTE (% (SIN (% (% Y 0.30400002) 0.30400002)) (+ XY)) (% (SIN Y) Y) (SIN (SIN (SIN (% (SIN X ) (+ -0.12499994 -0.15999997))))) (% (+ (+ XY) (+ YY)) 0.30400002)))) (+ (+ XY) (+ YY))))) (SIN (IFLTE (IFLTE Y (+ XY) (- XY) (+ YY)) (* XX) (SIN (IFLTE (% YY) (% (SIN (SIN (% Y 0.30400002))) X) (% Y 0.30400002) (SIN (SIN (IFLTE (IFLTE (SIN (% (SIN X) (+ -0.12499994 -0.15999997))) (% X -0.10399997) (- XY) (+ XY)) (SIN (% (SIN X) (+ -0.12499994 -0.15999997 ))) (SIN (SIN (% (SIN X) (+ -0.12499994 -0.15999997)))) (+ (+ XY) (+ YY)))))) (% Y 0.30400002))))).

This formula is not only ugly, but also puzzling.Even to a mathematician or a computer programmer, the evolved formula is a mess.Evolution wrote code that only a drunk human programmer could have written, Tom Ray said.In my opinion, it might be more accurate to say that evolution generates code that only aliens could write.This is absolutely not what humans do.Going back to the origin of this equation, Koza finally found the way this program handles the problem.It is entirely by perseverance and unscrupulousness that it has opened up a difficult, tortuous and puzzling solution.But it works.

The answer that evolution came up with seemed odd, since just about any high school student could write a very succinct and elegant equation describing the two spirals on one line. In Koza's world there is no evolutionary pressure for simplicity of solution.It was impossible for his experiments to find that refined equation, because it wasn't constructed for it.Koza tried to add some parsimony to the run, but found that adding parsimony at the start of the run made the solution less efficient.Although the solution obtained is simple, it is only at the middle and lower level.He has evidence that adding parsimony late in the evolution process—that is, letting the system find a solution that works before starting to simplify it—is a better way to evolve succinct equations.

But Koza firmly believes the importance of simplicity is overrated.Simplicity, he says, is nothing more than "a human standard of beauty."Nature itself is not particularly minimalistic.Case in point: David Stocker, then a scientist at Stanford University, analyzed the neural circuits in the tail muscles of crayfish.When the crayfish tries to flee, its neural network triggers a strange backflip.To humans, that kind of circuit looks as complicated as a baroque building, and it can be simplified immediately by canceling a few redundant loop instructions.But that messy mess works.Nature doesn't simplify just for the sake of elegance.