[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: INFO-MCL@CAMBRIDGE.APPLE.COM*Subject*: speed freak buys farm?*From*: UK0392@AppleLink.Apple.COM (EHN & DIJ Oakley,GB,IDV)*Date*: 23 Dec 92 22:12 GMT

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.

**Follow-Ups**:**Re: speed freak buys farm?***From:*pazzani@pan.ics.uci.edu (Michael Pazzani)

**Re: speed freak buys farm?***From:*hauser@netcom.com (Michael Hauser)

- Prev by Date:
**Re: Speed freak needs help** - Next by Date:
**access to fred history, etc.** - Previous by thread:
**speed data point** - Next by thread:
**Re: speed freak buys farm?** - Index(es):