Loading ...
Sorry, an error occurred while loading the content.

54Design Tradeoffs, was Re: Beowulf Clusters

Expand Messages
  • Sean Luke
    Oct 2, 2001
    • 0 Attachment
      On Tuesday, October 2, 2001, at 01:36 PM, Martin C. Martin wrote:

      > Agreed. It turns out that, for my Ph.D. thesis, I had individuals with
      > ~1000 nodes stored as a linear array in prefix order. To speed
      > evaluation, I kept a function pointer in each node. Since you want data
      > to be word aligned, and since I needed to keep more than just the
      > function pointer in the genome, that meant I needed two words per
      > individual. On a 32 bit machine, that's 8 bytes per node. For a
      > population of 10,000, that's 8*1000*10,000 = 80 Meg. On a 64 bit
      > machine, that's 160 Meg. Even with a population of 4,000 that's 32/64
      > Meg.
      >
      > The solution was to keep the population in a compact representation (1
      > byte per node), then compute the bigger representation just before
      > evaluation. Computing the bigger representation is trivial; the single
      > byte is an index into a table, and all you do is copy certain fields
      > into the bigger array. So, I could have my cake and eat it too. :)

      Well, yes and no. When I wrote the code for the RoboCup project, I used
      lil-gp and hacked the living daylights out of it. A few of those hacks
      showed up in my STGP lil-gp kernel on the web. lil-gp is a really
      well-designed system. But one lesson I took away from that project was
      that a packed array representation (lil-gp uses 4 bytes per node) is not
      as easy to hack as I would have liked. Writing custom breeding
      operators for it is a nontrivial endeavor, especially when you add in
      special constraints like typing, and special-purpose nodes with unusual
      needs, like storing arbitrary-length statistics on a per-node basis.
      1-byte-per-node arrangements like DGP are IMHO even harder to hack weird
      stuff into. And as a researcher, that's basically what I am: a
      weird-stuff-hacker.

      So when I sat down to design a big, full-featured EC system for my
      thesis work, I decided on an ordering of needs for my system. First, I
      needed portability. Second, I needed hackability and maintainability.
      Third, I'd like reasonable evaluation speed. Things that were far down
      the list: breeding speed (dominated by evaluation times for me, it's
      almost inconsequential) and memory consumption (RAM is cheap).

      There are traditional computer science tradeoffs between (A) memory
      consumption, (B) speed, and (C)
      portability/modifiability/maintainability of code. I do think that
      these tradeoffs apply well to GP coding projects: you just can't have
      your cake and eat it too in all situations. For me, I decided that B
      and C were the critical items, with C being most important, and A was
      not important. So I designed a system that emphasized C, tried to do B,
      and to heck with A. So I abandoned a packed-array representation and
      went with a direct tree representation with lots of bells and whistles
      (like back-pointers). I also went with Java as my language (I almost
      did it in hand-optimized Common Lisp, but it wouldn't run on an
      important target platform of the time, an Alpha farm I had available).
      The result is, I'm proud to admit, the public-domain system with the
      largest per-node memory usage, at about 30 bytes per node. :-) But
      it's highly portable, IMHO very hackable, and acceptably fast. And when
      I did my extreme-bloating experiments, with many individuals >10,000
      nodes in size (!!) plus lots of weird internal statistics embedded in
      each node, and a population size of 1000, I never got much higher than
      512 megs -- that is, I was usually within the RAM constraints of my
      machines. So it was a good tradeoff I think.

      Adil Qureshi made similar design decisions when he put together GPsys,
      which uses about 24 bytes per node. But most other systems have gone
      the memory-is-important route, resulting in lil-gp (4 bytes per node, 17
      bytes for ERCs), DGP (1 byte per node), and GPquick (1 byte per node I
      think). Dunno about GPC++. Nic McPhee's Java-based Sutherland system
      takes a different approach. It's tree-based, but shares subtrees among
      individuals. Nic reports that this results in huge memory savings, and
      I must admit it's a really cool notion, though I'm worried about how
      tough it would be to add odd stuff into it. Maybe not a big deal.

      But I do think that optimizing for memory should be done only if you
      absolutely must. RAM is cheap, evaluation time is dominant, and large
      individuals result in exponentially larger search spaces (and thus
      "searching for larger individuals" is a hard justification to buy).
      Even so there are things that can be done independent of representation:
      John Koza proposed an interesting method for pre-determining breeding,
      which allows you to cut memory requirements in half doing generational
      evolution as well, though I think it's difficult to implement if you've
      got multiple threading. Adil's got Koza's mechanism in GPsys; I decided
      to go for steady-state, among others, in ECJ.

      Of course your requirements could be for *massive* hackability, even at
      the expense of speed and maintainability. That's what Lee Spector's
      doing with his GP stuff, all coded in Common Lisp, using Funky Lisp
      Goodness that other languages wish they had.

      Sean
    • Show all 19 messages in this topic