simplifying algebraic expressions

[DavidM]

Hi,

Are there any libraries for manipulating algebraic expression trees?
In particular, take an expression tree and simplify it down.

I'm working up the next release of PyGene, the genetic programming and
genetic algorithms library.

Part of PyGene works with trees holding algebraic expressions. For
example, the expression:
f = x**2 + sqrt(y) + 7
is represented as the tree:

+
**
x
2
+
sqrt
y
7

My GP code is successfully evolving expression trees to solve problems,
however they're often full of redundancies, eg adding y in one part then
subtracting y later on.

I've added some simplification code which takes out some of the more
obvious redundancies - eg replacing 'x - x' with '0', and replacing
'y / 1' with 'y' etc. But there'd be a pile of work to make this code
smart enough to go deep into the tree and fix everything.

So if someone can point me in the direction of an algebraic expressions
library that can simplify expression trees and weed out redundancies, that
would be awesome.

Many thanks if you can help.

Cheers
David

 

[Robin Becker]

Hi,

Are there any libraries for manipulating algebraic expression trees?
In particular, take an expression tree and simplify it down.

I'm working up the next release of PyGene, the genetic programming and
genetic algorithms library.

Part of PyGene works with trees holding algebraic expressions. For
example, the expression:
f = x**2 + sqrt(y) + 7
is represented as the tree:

+
**
x
2
+
sqrt
y
7

My GP code is successfully evolving expression trees to solve problems,
however they're often full of redundancies, eg adding y in one part then
subtracting y later on.

I have seen this sort of evolution strategy in the past and it's very wrong to
attempt to simplify outside the genetic framework. The implication is that you
know better than the overall fitness requirement. The additional expressions and
redundancies allow for extra mutation and combination possibilities which is a
good thing for the whole population. If you must, add the requirement to the
target ie give extra fitness points to organisms which perform efficiently.

 

[DavidM]

I have seen this sort of evolution strategy in the past and it's very wrong to
attempt to simplify outside the genetic framework. The implication is that you
know better than the overall fitness requirement. The additional expressions and
redundancies allow for extra mutation and combination possibilities which is a
good thing for the whole population. If you must, add the requirement to the
target ie give extra fitness points to organisms which perform efficiently.

I'm sorry, but there's something important I forgot to mention - I only
want to do the simplification *after* a winning successful organism has
evolved and satisfied the fitness function.

 

[Mark Westwood]

Hi David

It seems that all you are asking for are the capabilities of
Mathematica or Maple or some other CAS. A quick Google reveals that
there is a CAS written in Python, called SAGE. That might be a good
place to start; but I'll admit that I know nothing about it.

I'm with Robin Becker on this one, if GP is good enough for your
problem, then the answers it produces should be good enough. Set the
fitness criteria in favour of shorter rather than longer expressions
and let you system run a little longer. Not only do you avoid having
to integrate into your system a novel library, you avoid a world of
pain trying to decide whether or not x**2 is 'simpler' than x*x, (is
x**4 'simpler' than (x**2)*(x**2) ?) and making sure that you don't
define any circular simplification rules.

If you don't like the computer algebra approach, you could google for
'program transformation' and follow some of the links.

Good luck !

Mark Westwood

 

[DavidM]

I'm with Robin Becker on this one, if GP is good enough for your
problem, then the answers it produces should be good enough. Set the
fitness criteria in favour of shorter rather than longer expressions
and let you system run a little longer.

Thanks for your comments.

I tried this and came up with some very interesting results.

In the fitness function, I added a multiplier:

badness *= numnodes


Where 'badness' is the calculated fitness (always >0, lower is better),
and 'numnodes' is the number of nodes in the program tree.

Result? The population never evolved past a certain point, and problem
never got solved.

So I tried to make the multiplier more gentle:

badness *= math.log(1 + numnodes)

Same result.

Tried even more gentle:

badness *= math.pow(numnodes, 1.0/12)

That is, multiply badness by the twelfth root of the number of nodes.

Population evolved better, but still didn't breed a winning organism.

Finally, I set a threshold, and only punished organisms if they exceeded
this complexity threshold:

if numnodes > threshold:
badness *= math.pow(numnodes - threshold, 1.0/12)

That worked.

Seems that I have to allow a 'punishment free' threshold of complexity,
otherwise the population stagnates.

Cheers
David

 

[Alex Martelli]

Seems that I have to allow a 'punishment free' threshold of complexity,
otherwise the population stagnates.

Sounds like you've hit on a good simulation of life: to get innovation,
you must be very tolerant of errors!-)


Alex

 

[frithiof.jensen]

So if someone can point me in the direction of an algebraic expressions
library that can simplify expression trees and weed out redundancies, that
would be awesome.

half-joking:

Maxima http://maxima.sourceforge.net/ --- ala os.popen('maxima .... ') ... ^_^

The problem with genetic algorithm's, as I understand Stuar Kaufmann, is that
while "weeding out redundancies" the fitness space becomes more spiky and
therefore harder to search. The "optimal" solution decays into simple random
guessing in in infinite search space. So, sloppiness and waste is Good - it
helps by creating an area of the fitness space where the "creature" can "move"
i.e. adopt/evolve.