Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Evolving formulae

by tsee (Curate)
on Feb 25, 2004 at 14:31 UTC ( #331657=perlmeditation: print w/replies, xml ) Need Help??

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 less-than-appropriately 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 human-readable 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://steffen-mueller.net/symevol/symevol.tar.gz and a GIF animation created from the output images can be seen here: http://steffen-mueller.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://steffen-mueller.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://steffen-mueller.net/symevol/ )

Replies are listed 'Best First'.
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.

      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.

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.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-

Re: Evolving formulae
by Abigail-II (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

      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

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
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 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
    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.

      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

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.

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?

      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)

      That's closer to pi than 22/7.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://331657]
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (2)
As of 2021-10-28 05:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (95 votes). Check out past polls.

    Notices?