1. Re: Handling overflow when doing random math
- Posted by poplar at vicon.net
Jun 16, 2002
Replying to:
=====================================
From: Andy Serpa <renegade at earthling.net>
Subject: RE: Handling Overflow When Doing Random Math
=====================================
Interesting, to say the least, this comment of yours:
>It is not limited to math functions, although that is mainly what
I've
>been doing. I also incorporate boolean operators so it can do
>comparisons, use if statements, etc.
>The basic framework can handle any type of program, really.
Thanks for the thoughtful reply, Andy. I am quite interested in what
you are doing. I don't know what your plans are for your code, but I
hope you can post enough to get others interested in trying out the
ideas and maybe adding some ideas of their own. It sounds like you
have solved a lot of the problems in this kind of project.
The scope of your project sounds a bunch bigger than my efforts, which
were mostly on the "experimenting for fun" level. I have downloaded
the .pdf files and will attempt to absorb them in the next few weeks.
I did see something on the site you gave about the number of inputs
being important, but some inputs will be just noise and the
math-beings (or algobots or progines or whatever they should be
called) should be able to handle that.
A bit of elaboration for those interested: my little guys had a linear
genetic makeup with varying length of math instructions (pointers to
functions) and 3 register numbers (of a total of 6 registers
(variables). Some instructions used just two registers, but all had
three register numbers. Each being had a personal number that could
evolve up or down by a small amount according to a "direction gene".
It worked in a personal copy of the main register set which it
modified. I arbitrarily chose Register 6 as the answer register.
Many instructions did nothing because the (a usually intermediate)
result was put into the wrong register (as many genes seem to do not
much). I let the whole crew have several chances at a solution, took
an average, and "mother nature" slew the bottom half of the
population, if I remember correctly. The top half "split" into an old
unchanged form and a randomly modified form. The whole was sorted by
closeness to the answer and I filtered out the do-nothing instructions
when I printed out the best sequence. As I said, some of the
algorithms were amazing in their round-about, non-intuitive, but
successful, final "program". The inverse of pi mashed by some
trigonometric function might be used, for example.
At the time I had to stop the project (something to do with chaos, I
think), I was trying to focus on the math parser, increasing the
difficulty of the problems, reporting issues (was the best really the
best?), and a philosophical pondering of the difference between the
discreteness of programming instructions and the robust integrated
system of a living thing. I believe I was on the verge of a
breakthrough in just how confused a person can get.
--DB James (Quark)
The following material was in the message I am replying to:
=========================================
Date: Sun, 16 Jun 2002 09:55:21 +0000
From: Andy Serpa <renegade at earthling.net>
Subject: RE: Handling Overflow When Doing Random Math
>
> I wrote a program once in C that used "math-beings" in a genetic
> algorithm to evolve equations from inputs. Inaccurate beings were
> treated the way nature treats inadequate lifeforms, of course. It
> worked, and the answers were interesting, even amusing -- the
> algorithms were so unlike ours. I wanted to develop this to include
a
> math parser, so the user could easily enter new formulas for the
> program to try to match, but never got around to doing that. The
> distant ultimate goal was to have a "math-world" that could evolve
> genuinely new math responses from inputs, where the formula was not
> given (or even known).
>
That is basically genetic programming you are describing, and it is
almost exactly what my program does, using the procedure described at:
http://www.gene-expression-programming.com/
It is not limited to math functions, although that is mainly what I've
been doing. I also incorporate boolean operators so it can do
comparisons, use if statements, etc.
The basic framework can handle any type of program, really.
> tiny). I had to fight the overflow problem constantly and never
took
> the time to do that job cleanly. The point of all this is a
question:
> does anyone think there would be a simple way to confine specialized
> randomly called math functions to numbers between -1 and +1 with a
> scaling function? This would be a loose analogy to core wars where
> all the action is confined to a limited space. I suspect there
would
> be precision issues here, but maybe that could be handled, at least
> for the purposes of random math.
If I'm trying to "discover" a function based on a series of examples,
you just minimize the error and it automatically comes up with an
appropriate function. For example, given this as input:
1,2,3
2,3,7
3,4,13
4,5,21
where the first two numbers are inputs & the third is the output, it
will quickly discover the equivalent of the function:
(a*a) + b
(i.e. (4*4)+5 = 21)
I say equivalent because as you noted it will come up with strange
ways
to represent things, using something like (a-a)*(b+a) to simply
represent 0, for instance.
If you don't want to force a particular output or if you're trying to
output a probability where you can't explicitly provide a target value
because it all depends on context, I just let it make outputs on
whatever scale it feels like, and then normalize them or re-scale
them.
Does that make sense? I found it works somewhat better than trying to
force it into a particular range when you don't have a specific target
in that range. (The exception is when you want a binary output --
0/1.
Then you force it.)
Of course, the math functions are already within a particular range
because of the overflow problem. When my system generates a function
that causes overflows, it gets a low fitness and dies. You could of
course make the overflow threshold anything you want, really. (When I
want a boolean output, for instance, only functions that output 0's &
1's have a chance of getting a high fitness.) Sometimes I specify
positive numbers only, etc.
The key is the fitness function. As long as you can evaluate the
outputs it gives you, and rank them so that one is considered better
than some other one, then any method will work, but some will take
longer than others. Such is the power of evolution...
