home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / lisp / mcl / 1885 < prev    next >
Encoding:
Internet Message Format  |  1992-12-23  |  4.6 KB
  1. Path: sparky!uunet!olivea!apple!cambridge.apple.com!UK0392@AppleLink.Apple.COM
  2. From: UK0392@AppleLink.Apple.COM (EHN & DIJ Oakley,GB,IDV)
  3. Newsgroups: comp.lang.lisp.mcl
  4. Subject: speed freak buys farm?
  5. Message-ID: <725148821.5417973@AppleLink.Apple.COM>
  6. Date: 23 Dec 92 22:12:00 GMT
  7. Sender: info-mcl-request@cambridge.apple.com
  8. Lines: 76
  9. Approved: comp.lang.lisp.mcl@Cambridge.Apple.C0M
  10.  
  11. Friends,
  12.  
  13. Many thanks to all of you who have responded so quickly and helpfully to my
  14. plea for speed.  Rather than attempting a full summary, I will explain some
  15. more about what I am up to, and the general suggestions made.
  16.  
  17. Koza's genetic programming is derived from conventional genetic algorithms
  18. (GAs), but is a few orders of magnitude more serious in computational terms.
  19. The gist of a conventional GA is that you generate a random population of
  20. objects which have your 'factors' (could e.g. be coefficients for an equation),
  21. then breed them selectively to improve their fitness to perform according to
  22. your determined measure (sorry, I know it is a gross oversimplification!).
  23. Ultimately, you will end up with the 'fittest' (optimal) set of factors.  We
  24. run conventional GAs, and have no particular problems with speed using MCL and
  25. the Quadra 950, although of course large populations with long 'chromosomes'
  26. and complicated fitness evaluations do take time.
  27.  
  28. Koza has taken this on one step further.  Instead of making you pick a specific
  29. model (e.g. a particular form of equation), all you do is provide a set of
  30. operators, a set of variables, and various Lisp functions to evaluate the
  31. fitness, etc., and what genetic programming (GP) does is to generate a
  32. population of S-expressions which are then bred and selected according to
  33. fitness, to optimise an S-expression to solve your problem.  Thus, you could
  34. start with the four basic math operators and use genetic programming to fit an
  35. arbitrary curve to data - you could end up with almost any form of equation, of
  36. any order.  As he points out, the great majority of the time spent running GP
  37. is evaluating fitness, because you have to eval the S-expression over every
  38. object in your population (OK, Koza and collaborators have optimised this, e.g.
  39. using a fast eval, saving re-evaluating unchanged members of the population,
  40. etc.).
  41.  
  42. The particular problem that I am battling with evaluates a 1000 deep stack
  43. filter of window 7 across a test series of 600 data points - my
  44. back-of-the-envelope estimate is of the order of 15 billion evals per decent
  45. trial, and I need to do more than 10 trials.  Koza's code has been pretty
  46. carefully tuned (and is pretty involved, as well!), and my code can probably
  47. only optimise further by a factor of 4 or 5 (which I allowed for in my need for
  48. an *additional* 10-20 times acceleration!) without very time-consuming
  49. rewriting.
  50.  
  51. So, I am pretty well tied to Common Lisp (I think that the Lisp-to-C solutions
  52. would struggle to cope with the eval requirement!) without a massive amount of
  53. redevelopment effort.
  54.  
  55. The consensus about TI Explorers and Lisp Machines seems to be that neither
  56. will approach the required acceleration factor, but probably be little faster
  57. than said Quadra 950.  Going up to Unix workstations, suggestions of using
  58. RS6000, HP700, and the like with Harlequin or similar Lisp products looks as if
  59. it will offer a speed-up factor of 2 or more, maybe up to 5, but the investment
  60. required could provide at least 5 more Quadra 950s, which with careful
  61. parallelisation could prove at least as quick.
  62.  
  63. My conclusion is therefore that a Quadra farm, talking via AppleEvents
  64. (mercifully the farm would need to move little actual data around, after
  65. initialisation) to enable parallel fitness evaluation, is the only practical
  66. suggestion short of a Connection Machine and *Lisp - which I suspect might be a
  67. lot more expensive if rather more exotic!
  68.  
  69. Finally, Koza's book (published a couple of weeks ago) is:
  70. Genetic Programming: on the programming of computers by means of natural
  71. selection, Koza JR, MIT Press, 1992, ISBN 0-262-11170-5, MIT order no. KOZGII,
  72. price $55
  73. and its (excellent) accompanying video:
  74. Genetic Programming: the movie, Koza JR, MIT Press, 1992, MIT order codes
  75. KOZGVV (NTSC format, price $34.95), KOZGPV (PAL format, price $44.95), or
  76. KOZGSV (SECAM format, price $44.95)
  77. MIT Press are on 1-800-356-0343 or 617-625-8569, fax 617-625-9080.
  78. These make superb (if late) Christmas presents for yourself!
  79.  
  80. And Koza himself seems to have spent most of the last three or four years
  81. driving Explorers into the ground getting the data to quote in the book.
  82.  
  83. Thanks again to all who replied so quickly, and a happy Christmas (I must
  84. remember to ask Santa for a dozen Quadra 950s!),
  85. Howard.
  86.  
  87.