Introduction
If you look at formulae, algebraic expressions, the right way, you'll realize
they're no more than pieces of data. They are 'functional' data that
describes how one may go about doing something much like a cooking recipe.
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.
A computer is probably a good approximation of a large number of
monkeys anyway.
Of course, even a computer has limits and needs some pushing in the right
direction. Enter evolutionary algorithms. The basic idea is to reward steps
in the right direction without making small steps backwards completely
contraproductive. More generally speaking, you mutate a whole matrix of
formulas, judge the quality (or fitness) of a particular formula and
reward it by copying it to adjacent matrix elements if its fitness is higher
than that of its neighbours. Every such mutation of all matrix elements
is called a generation. The program at hand pretty much does that: Mutate all
formulas, find the best and reward them. With some twists and turns.
Preparation
Data Representation
In order to work with formulas as data types, one needs some way of
representing the formula as a data type a computer can work with.
Naturally, one chooses to use trees after a moment of thinking because
that's exactly how we evaluate a formula, too: 2 + 4 * 5 becomes
+
/ \
2 *
/ \
4 5
And we calculate the result from bottom up: 2 + 4 * 5 = 2 + 20 = 22.
So well, we have a matrix of trees of operators and numbers. The operators
that may occurr in the formulas are all binary operators for now: Addition,
subtraction, multiplication, division, and exponentiation.
Mutation
So well, we have a data representation and now we need to find sensible
operations on it that change it. Some operations should modify the formula
significantly, but most should just change it a little bit. Here is a summary
of which mutations I chose for the program at hand:
 Number Increment / Decrement
When this mutation is executed, a random number is chosen from the tree and
incremented or decremented by one.
 Switching Operands
This mutation exchanges the operands of a random operator in the tree.
 Replacing Operators
This mutation replaces a random operator in the tree with any other operator.
 Modifying Operators
This lessthanappropriately named mutation also replaces an operator, but only
with one of the same precedence level. It replaces addition with subtraction,
multiplication with division and vice versa. Exponentiation currently has no
counterpart. (There are no logarithms yet.)
 Expanding a Number to an Operator
A random number in the tree is replaced by either an addition of two numbers or
a subtraction. One of the operands of the new operator is the number it that
is being replaced. The other is a zero.
 Folding an Operator to a Number
A random operator is replaced by the numeric value it represents.
 No mutation
The last possibility is that no mutation takes place in this generation.
This is useful for introducing some stability.
Implementation
Fortunately, an implementation of the data type outlined above already exists
on CPAN. Math::Symbolic does exactly that and then some. Furthermore, the
module makes it easy for us to render the tree humanreadable and to evaluate
its value. It also has facilities of replacing a tree node with any other
tree node which is required for the expanding and folding mutations.
Further UI elements could make use of the fact that Math::Symbolic can
convert formulas to LaTeX.
Using this module, the first implementation was quickly carried out in
an afternoon. Unfortunately, the initial version did not offer much feedback
about the progress and results.
In the current version, the program offers facilities to print images of the
current matrix every generation. In these images, an area of n x n pixels
corresponds to one cell or formula. The color of the area shows the cell's
fitness with high fitness being lighter and undefined or extremely low fitness
being colored with a signalling red. For example, divisions by zero would yield
such a red cell. The algorithm that maps certain fitness ranges to a color
still requires some tweaking and directly depends on the function that
calculates the fitness of a formula.
After finishing the planned number of generations, the program prints a list
of the formulas with the highest fitness.
Example
After lots of general discussion, I'll present a simple example:
We search for a formula to calculate pi as accurately as possible. Thus,
fitness is determined by a formula's distance from pi.
A sample run of 500 generations yielded the following best approximation:
3 + 1 / 10^(1426/1726) which beats the commonly memorized idiom of
22/7 in accuracy by about an order of magnitude. (22/7 approximates pi
correctly to the third decimal.)
The code can be found at http://steffenmueller.net/symevol/symevol.tar.gz
and a GIF animation created from the output images can be seen here:
http://steffenmueller.net/symevol/animation.html (ca. 700kb for 25 seconds).
Since the animation is rather fast, there's also a version running four times
slower at http://steffenmueller.net/symevol/animation_slow.html (also 700kb,
but 100 seconds).
Future
While the current version can only deal with constants and operators, it would
be a sensible  albeit challenging  extension to include a limited set of
variables in the mutations and judge the fitness of such formulas by their
approximation of a function.
Furthermore, one could easily add a notion of persistence to continue
simulations at any time.
The program could output the results as a nicely formatted LaTeX source file
instead of just printing plain text.
(A copy of this text can be found at http://steffenmueller.net/symevol/ )
Re: Evolving formulae
by bunnyman (Hermit) on Feb 25, 2004 at 15:36 UTC

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.
 [reply] 

 [reply] 
Re: Evolving formulae
by gjb (Vicar) on Feb 25, 2004 at 16:01 UTC

What you're considering is actually a field of research called genetic programming. A lot of information can be found at http://www.geneticprogramming.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
 [reply] 
Re: Evolving formulae
by AbigailII (Bishop) on Feb 25, 2004 at 15:02 UTC

The program at hand pretty much does that: Mutate all formulas, find the best and reward them. With some twists and turns.
This is all well known. It's also well known that "just finding the best" isn't always the best approach. It's an
approach that will only work if in the field of all possible
approximations, there's always a monotone path (that is, every
next approximation is better) towards the ultimate goal.
However, if that's the case, there's usual an efficient,
direct way of solving the problem.
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
 [reply] 

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
 [reply] 
Re: Evolving formulae
by zentara (Archbishop) on Feb 25, 2004 at 16:14 UTC

If you look at formulae, algebraic expressions, the right way, you'll realize they're no more than pieces of data.
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'm not really a human, but I play one on earth.
flash japh
 [reply] 
Re: Evolving formulae
by flyingmoose (Priest) on Feb 25, 2004 at 21:33 UTC

While this is of course cool, curve fitting (and things like Taylor's series) seem to be better ways to fight this problem. At least this works very well in dealing with functions.
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 writeup is of course cool and is well worth of the ++, just be advised the bruteforce 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
FYI  when the predefined goal is the input numerical value for pi, then you know the goal, and you are there. Hence the above quote about the better methods for solving a problem. Pi is probably a very bad case, curve fitting would probably serve a better example and would have a more interesting fitness function.
 [reply] 

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.
 [reply] 

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?
 [reply] 

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 humancreated 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
 [reply] 

Re: Evolving formulae
by ccarden (Monk) on Feb 26, 2004 at 19:20 UTC

Regarding monkeys and Shakespeare, check out the Monkey Shakespeare Simulator.
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.  [reply] 
Re: Evolving formulae
by Anonymous Monk on Feb 26, 2004 at 15:17 UTC

A sample run of 500 generations yielded the following best approximation: 3 + 1 / 10^(1426/1726) which beats the commonly memorized idiom of 22/7 in accuracy by about an order of magnitude. (22/7 approximates pi correctly to the third decimal.)
pi = 3.14159265...
22/7 = 3.14285714...
3 + 1 / 10^(1426/1726) = 3.14921493....
In what way is that more accurate?
 [reply] 

1: [0,10] (10 ^ ((11 * 1) / ((((3  0)  (0 ^ 1)) /
((128  ((0  2) + (5 * 0))) + 3))  (0 + 13)))) +
3 = 3.14202847846689 (Fitness: 2294.49958586465)
That's closer to pi than 22/7.  [reply] [d/l] 

