speed freak buys farm?

[UK0392@AppleLink.Apple.COM (EHN & DIJ Oakley,GB,IDV)]

Friends,
 
Many thanks to all of you who have responded so quickly and helpfully to my
plea for speed.  Rather than attempting a full summary, I will explain some
more about what I am up to, and the general suggestions made.
 
Koza's genetic programming is derived from conventional genetic algorithms
(GAs), but is a few orders of magnitude more serious in computational terms.
The gist of a conventional GA is that you generate a random population of
objects which have your 'factors' (could e.g. be coefficients for an equation),
then breed them selectively to improve their fitness to perform according to
your determined measure (sorry, I know it is a gross oversimplification!).
Ultimately, you will end up with the 'fittest' (optimal) set of factors.  We
run conventional GAs, and have no particular problems with speed using MCL and
the Quadra 950, although of course large populations with long 'chromosomes'
and complicated fitness evaluations do take time.
 
Koza has taken this on one step further.  Instead of making you pick a specific
model (e.g. a particular form of equation), all you do is provide a set of
operators, a set of variables, and various Lisp functions to evaluate the
fitness, etc., and what genetic programming (GP) does is to generate a
population of S-expressions which are then bred and selected according to
fitness, to optimise an S-expression to solve your problem.  Thus, you could
start with the four basic math operators and use genetic programming to fit an
arbitrary curve to data - you could end up with almost any form of equation, of
any order.  As he points out, the great majority of the time spent running GP
is evaluating fitness, because you have to eval the S-expression over every
object in your population (OK, Koza and collaborators have optimised this, e.g.
using a fast eval, saving re-evaluating unchanged members of the population,
etc.).
 
The particular problem that I am battling with evaluates a 1000 deep stack
filter of window 7 across a test series of 600 data points - my
back-of-the-envelope estimate is of the order of 15 billion evals per decent
trial, and I need to do more than 10 trials.  Koza's code has been pretty
carefully tuned (and is pretty involved, as well!), and my code can probably
only optimise further by a factor of 4 or 5 (which I allowed for in my need for
an *additional* 10-20 times acceleration!) without very time-consuming
rewriting.
 
So, I am pretty well tied to Common Lisp (I think that the Lisp-to-C solutions
would struggle to cope with the eval requirement!) without a massive amount of
redevelopment effort.
 
The consensus about TI Explorers and Lisp Machines seems to be that neither
will approach the required acceleration factor, but probably be little faster
than said Quadra 950.  Going up to Unix workstations, suggestions of using
RS6000, HP700, and the like with Harlequin or similar Lisp products looks as if
it will offer a speed-up factor of 2 or more, maybe up to 5, but the investment
required could provide at least 5 more Quadra 950s, which with careful
parallelisation could prove at least as quick.
 
My conclusion is therefore that a Quadra farm, talking via AppleEvents
(mercifully the farm would need to move little actual data around, after
initialisation) to enable parallel fitness evaluation, is the only practical
suggestion short of a Connection Machine and *Lisp - which I suspect might be a
lot more expensive if rather more exotic!
 
Finally, Koza's book (published a couple of weeks ago) is:
Genetic Programming: on the programming of computers by means of natural
selection, Koza JR, MIT Press, 1992, ISBN 0-262-11170-5, MIT order no. KOZGII,
price $55
and its (excellent) accompanying video:
Genetic Programming: the movie, Koza JR, MIT Press, 1992, MIT order codes
KOZGVV (NTSC format, price $34.95), KOZGPV (PAL format, price $44.95), or
KOZGSV (SECAM format, price $44.95)
MIT Press are on 1-800-356-0343 or 617-625-8569, fax 617-625-9080.
These make superb (if late) Christmas presents for yourself!
 
And Koza himself seems to have spent most of the last three or four years
driving Explorers into the ground getting the data to quote in the book.
 
Thanks again to all who replied so quickly, and a happy Christmas (I must
remember to ask Santa for a dozen Quadra 950s!),
Howard.