If anybody out there is scratching their heads over why we need such a complicated and slow way to calculate Pi, well, here is a "hard problem" to solve.

The problem is "inverse Boggle." In the game of Boggle, the player has a grid of letters, and he must find words by connecting adjacent letters. In "inverse Boggle" you are supplied a list of words, and the challenge is to fit as many as you can into a grid of fixed size.

A Programming contest was held to see who could come up with the fastest program to solve the problem with the best result. The winner of the contest used an evolutionary algorithm to find the solution.

This is a fine example of evolutionary/genetic algorithms, although it does not address anything about why evolutionary/genetic algorithms are practical for finding mathematical functions that we do not know. Systems of finding polynomial representations is already well-known in math without GA, perhaps the author would do better if he included a problem to be solved that used something more than trivial operators -- perhaps a problem in a high number of dimensions, involving complex numbers, trig, etc. Somewhere where Taylor's series (and other variants) break down.

This is what I'm interested in seeing. We know cases where EA can be applied well and where it might be a better way of solving a problem...but the rule is, "when better ways exist", use them.

What you're considering is actually a field of research called genetic programming. A lot of information can be found at http://www.genetic-programming.org/.

In most genetic approaches, three operations are considered: selection, mutation and crossover. They are considered mandatory to fully and efficiently explore the function space. At the moment, you only seem to consider selection and mutation, but not crossover (it's mating two individuals to create offspring with characteristics of both parents).

Anyway, don't get overexcited, there's not many real world applications where GP did a good job.

Just my 2 cents, -gjb-

The program at hand pretty much does that: Mutate all formulas, find the best and reward them. With some twists and turns.

The interesting problems are when there aren't always monotone paths towards the end goal; that is, there are local maxima, and you may have to first decrease your current approximation to be able to further increase it.

Unfortunally, your description isn't clear whether your technique does such a thing.

Abigail

Admittedly, the node doesn't completely describe the program.

In the example case of evolving formulae of constants and operators only, most mutations are pretty significant. Thus, most changes except number increment/decrement should have a strong effect on the result.

Since most immediate changes to the existing structure yield worse results, you can customize the number of generations to evolve before the "fittest" cells spread to their neighbours.

An interesting varation might be to introduce some kind of mixture of two cells whenever one overwrites another.

Steffen

For some reason, I immediately thought of an old book I read called "Laws of Form". It has quite a following, check it out at LawsofForm

Basically it sets up a mathematics for setting distinctions around sets of data, and manipulating them. When I first read it, I realized that humans don't see the world in it's correct spatial depth. We look toward "outer space" for answers, where the "deeper space" is down in the miniscule. Anyways, it may be applicable to your equation's problem. It would definitely give you some clues on how to approach your modelling.

I long remember reading "The two worst ways to solve a problem are genetic algorithms and neural networks". Worst -> Slowest. This isn't a knock at GA and NN, this is the truth, as written by AI purists themselves.

Loosely: You use the former when you know what "closer to right" means, but you don't know how to make something "more right". You use the latter when you know when the right answer, but you don't know how to get there.

The day we consign math to genetic algorithms, IMHO, is the day we stop understanding math. If you are trying to fit a function to data, there are better ways. Your write-up is of course cool and is well worth of the ++, just be advised the brute-force approach to mathematics...well...it isn't mathematics anymore.

Just like an infinite number of monkeys with typewriters will eventually come up with a Shakespearean tragedy, we could try to have todays fast computers mutate a formula until it gets close to a predefined goal

I wholeheartedly agree that the example given is nothing to phone home about. Curve fitting is about what I had in mind when I first started hacking this, but since my periods of spare time are getting rare, I chose to aim lower about 1/3 through.

What inspired me in the first place was an article in the German equivalent of the Scientific American ("Spektrum der Wissenschaft") which demonstrated how somebody had written a reasonably similar program that evolved *code* in a simple assembly language (which ran on a virtual machine). The small programs were awarded for performing logic functions like a^b, etc.

The day we consign math to genetic algorithms, IMHO, is the day we stop understanding math.

I suppose that depends on two things -- first how well the programs are able to describe their new discoveries to us. This is the case for all of mathematics right now... just because you personally didn't solve some problem doesn't mean you can't understand the solution. Also when you do solve a problem it doesn't mean you can make everyone else understand.

Second, you (and everyone should do this excercise with us) need to decide whether you consider mathematics (or programming for that matter!) to be a discipline of creation or discovery. Either people are making this stuff up and it wouldn't be there otherwise, or we are just finding out what is already out there.

I personally am a discoverist!

Hmm... actually now that I think about it that second point could well be irrelevant. Who cares whether the algorithms are discovering mathematics or creating it? Oh well, its a fun thought anyway.

What does everyone think... are programs discovered or created?

Personally, I prefer thinking of programs being created - I seem to work so much more productively that way ;)

Fun aside, I think mathematics is neither completely human-created nor -discovered. It's a mixture of the two. Now, if Hilbert had been right and we could deduct everything from a created set of axioms, I'd say we created the axioms and discovered the rest.

Unfortunately, Hilbert was wrong and on the grand scale of things, to me, mathematics is a steaming pile of dung if you consider that perfectly logical things contradict themselves. Thus, mathematics must have been created by humans.

Steffen

Bananas are given to the monkeys, so there must be some mutation in the algorithm, but the best match found so far is 13 letters. It is either proof that the algorithm is grossly inefficient or that a room full of monkeys has a better chance of writing Helen Steiner Rice or "The Flintstones Meet the Jetsons" than Shakespeare.

Good meditation.

pi = 3.14159265...
22/7 = 3.14285714...
3 + 1 / 10^(1426/1726) = 3.14921493....

In what way is that more accurate?

I'm sorry, you're right. I botched up simplifying the expression. (There were lots of redundant zeros in it.) Here:s the original:

1: [0,10] (10 ^ ((11 * 1) / ((((3 - 0) - (0 ^ 1)) /
((128 - ((0 - 2) + (5 * 0))) + 3)) - (0 + 13)))) +
3 = 3.14202847846689 (Fitness: 2294.49958586465)
[download]

That's closer to pi than 22/7.