473,389 Members | 1,348 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,389 software developers and data experts.

simplifying algebraic expressions

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
Jun 26 '07 #1
6 5665
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.
--
Robin Becker

Jun 26 '07 #2
On Tue, 26 Jun 2007 11:11:39 +0100, Robin Becker wrote:
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.
Jun 26 '07 #3
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

On 26 Jun, 12:06, DavidM <nos...@nowhere.comwrote:
On Tue, 26 Jun 2007 11:11:39 +0100, Robin Becker wrote:
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.

Jun 26 '07 #4
On Tue, 26 Jun 2007 04:22:23 -0700, Mark Westwood wrote:
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
Jun 26 '07 #5
DavidM <no****@nowhere.comwrote:
...
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
Jun 27 '07 #6

"DavidM" <no****@nowhere.comwrote in message
news:46********@news.orcon.net.nz...
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.
Jun 30 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

72
by: Raymond Hettinger | last post by:
Peter Norvig's creative thinking triggered renewed interest in PEP 289. That led to a number of contributors helping to re-work the pep details into a form that has been well received on the...
6
by: DennisNedry | last post by:
Any general ideas on techniques for creating parsers for algebraic and linear equations?
2
by: Sehboo | last post by:
Hi, I have several regular expressions that I need to run against documents. Is it possible to combine several expressions in one expression in Regex object. So that it is faster, or will I...
4
by: Egyd Csaba | last post by:
Hi All, I'd like to "compress" the following two filter expressions into one - assuming that it makes sense regarding query execution performance. .... where (adate LIKE "2004.01.10 __:30" or...
1
by: Hul Tytus | last post by:
comp.infosystems.www.authoring.html simplifying mailto In form entry code, the "POST action=mailto:xxx@xxx.xxx" command requests a Subject and a CC heading from the reader -- in lynx that is, I...
0
by: steve | last post by:
If you think you can easily translate most relational division problems to sql you should write a book. If your not even sure what relational division even is or how it can do done in a sane way...
9
by: Cristian | last post by:
algebraic expression 'a*b+c' with CIN .Is it possible? How to transfer the algebraic expression 'a*b+c' to the variable s (all double) with cout in a "Console Application" ? cout<<"Input a,b,c...
2
by: Federico Zenith | last post by:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hello everybody, I am looking into a problem that probably someone had before, so I hope I can avoid reinventing the wheel... I am looking into...
14
by: serave | last post by:
How do i evaulate a mathematical expression that is entered in a text field. Ex: Text Fields: Xo=23 X1= 250 Expression: y = Xoe^(x1+Xo)-cos(X0+X1)+23Xo
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.