Automatic programming, an example

The three problems with the code are that the variable names are all lies, there's a bunch of redundant rescaling which isn't consolidated because it's done in integer math when it should be floating point, and there are a couple bits of overfitting (bitwise operators) that don't belong. If you convert to SSA and wipe out the misleading names, you get:

a1 = perihelion+aphelion  Real
a2 = a1+a1                  Rescaling
a3 = a2+a2                  Rescaling
g1 = 12                     Rescaling
a4 = a3>>g1                 Rescaling
t1 = a4/g1                  Rescaling
a5 = a4-t1                  Rescaling
d1 = sqrt(a5)             Real
a6 = g1|a5                  Overfit
a7 = a6*d1                Real
a8 = g1^a7                  Overfit
guess = a8/g1               Rescaling

If you replace the overfitting with pass-throughs (a6=a5, a8=a7), then pretend it's floating point so that you can consolidate all the rescaling into a single multiplicative constant, you get

guess = k * (perihelion+aphelion)*sqrt(perihelion+aphelion)

Which is Kepler's third law.

This reminds me of the discussion from last week of the code that a self-modifying AI might produce; I said then that I thought people were not thinking Weirdly enough. This is indeed an example of Weirdness. Obviously no human would come up with such a thing. Yet it works, more or less; although the hardcoded numbers make me suspect that its range of applicability may not be great. Testing it on some numbers typical of, say, solar orbits around the galactic core, might produce some surprising results.

It would also be interesting to compare this for speed, as well as accuracy, with a Kepler's-law implementation.

divide by 1024

Actually by 4096. And it is a rescaling as jimrandomh points out.

aphelion=aphelion+aphelion;
aphelion=aphelion+aphelion;
guess=12;
aphelion=aphelion>>guess;

aphelion=perihelion+aphelion;
aphelion>>=10;
guess=12;
temp=aphelion/guess;
aphelion=aphelion-temp;
perihelion=sqrt(aphelion);
perihelion=perihelion*aphelion;
guess=perihelion/guess;

The XOR with 12 won't do much after dividing by 12. For small radii, OR with 12 (in units of about 10^6km) will have an effect. These two constants are probably just overfitting. Indeed, it nails Mercury, the smallest and thus most vulnerable to these effects.* Rounding** the square root is also probably overfitting or just noise. It will have a larger effect, but smooth across planets, so it is probably canceled out by the choice of other numbers. Ignoring those three effects, it is a constant times the 3/2 power of average of the axes. The deviation from Kepler's law is that it should ignore perihelion.*** But for un-eccentric orbits, there's no difference. Since the training data isn't eccentric, this failure is unsurprising. That is, the code is unsurprising; that the code is so accurate is surprising. That it correctly calculates the orbital period of Halley's comet, rather than underestimating by a factor of 2^(3/2) is implausible.***

* The control group is too homogeneous. If it contained something close in, overfitting for Mercury would have been penalized in the final evaluation.

** Are you sure it's rounding? [Edit: Yes: bitwise operations are strongly suggestive.]

*** These statements are wrong because I confused apehelion with the semi-major axis. So removing the bitwise operations yields exactly Kepler's law. If you switch from ints to doubles it becomes more accurate. But wmorgan has a constant error: it is divide by 4096, not 1024. This should make the rounding errors pretty bad for Mercury. Maybe the bitwise operations are to fix this, if they aren't noise. My C compiler does not reproduce the claimed error percentages, so I'm not going to pursue this.

"Evolution is dumb, but it works" -- I believe that showing that was the (implicit) goal, and it was amply demonstrated.

Also related: mirror.fem-net.de/CCC/28C3/mp4-h264-HQ/28c3-4764-en-automatic_algorithm_invention_with_a_gpu_h264.mp4.torrent - another outsider perspective explanation of genetic programming.

That sounds like a terrible waste.

Technically speaking this is a very swift part, since every syntax error is detected before the code is rewritten and the mutations are just abandoned.

Most random mutations are fatal, so it fits perfectly.

That is the more common approach. Grammatical evolution is one method.

Kepler's law isn't O=constant*A. This is very wrong, silly even.

This is as good an opportunity as any to link this presentation and these cool papers about evolving patches for real-world C programs in minutes. In light of an actual working example of a computer program that fixes other programs' bugs, broad brush claims about how programs can't have algorithmic insight, won't lead to correct programs, and lack "the redundancy or flexibility of genetics" won't really wash.

Program code does not have the redundancy or flexibility of genetics, as you know with syntax errors it shatters if a single character is wrong

And a single mutation in DNA in the wrong place can be disastrous, too.

Program code does not have the redundancy or flexibility of genetics

A well-written program does not have it, but many real-life programs do. In my programming environments I have usually warnings turned very sensitive, for example they complain about declared but never used variables/functions, and when I read other people's code, I see this often.

with syntax errors it shatters if a single character is wrong

Could we see a program with syntax error as a fatal mutation? Fortunately, these fatal mutations are easy to detect. (Alternatively, we could mutate the parse trees.)

Another mistake is extrapolating from a finite data source: you can't expect to get a correct program this way, the code cannot contain any algorithmic insight into the data for any reason other than pure chance.

Still I have seen humans do this and take their paychecks. Yes, I would expect such evolved program be full of bugs; but real-life applications also contain bugs and it does not prevent them from being useful. I admit I would hate to read the machine-generated code, or even worse fix the bugs or add new functionality. But this is like saying that reading DNA is, ahem, not very user-friendly. Sure, it is not; but it works.

Two more things to consider. First, unit tests -- the better unit tests you make, the higher chance is that a random program that passes them is correct. If test-driven development can reduce random human errors, it can also reduce computer-generated error, though of course the computer will make much more errors. Second, we are OK with randomized algorithms having some chance of error, as long at the chance is very very small.

So the prior probability of computer generating a correct algorithm is small, but non-zero. By making unit tests we increase the probability that the result will be correct. If we can increase this probability from epsilon to 1 - epsilon, we win.