Lambda the Ultimate

remember that a node may have 0 to many incoming arcs (in my approach). so one solution is to have a node contain both an "initial value" and a "binary function", and then fold the function over the input values. if the values and operation form a closed group then everything if guaranteed to work.

i can't remember the exact details, but i think only my points-on-a-sphere code worked like that.

oh, and you can also rewrite the graph dynamically. for example, i associated nodes and arcs with points on a sphere. the arc is then "connected" to the nearest node. since the data values are also points on a sphere you can "jump to" a value.

(this gives you non-linearity, even if your operations at nodes are linear).

one final comment - the "rhythm" code, which generated a sequence of binary values - is "general" in that it can be used to find a solution to "any problem", providing you find the appropriate mapping from the binary output to the space of interesting representations (eg for text, interpreting it as a sequence of 7 bit ascii values).

saves you worrying so much about the programming - the problem is just one of encoding.

also, of course, the output is cyclic, with a maximum period depending on the size of the graph (number of arcs, since they store state). which is only to be expected.

ok, here's my take:

you can divide the inner loop of genetic algorithms into two steps: generating a child; evaluating the child. in the simplest cases, evaluating a child of length n takes O(n). but when the child is a program with "complexity" n, then evaluation is likely much more expensive.

so typically gp is orders of magnitude more expensive than the most brain-dead trivial ga problems because the inner evaluation loop takes longer. but it's a continuous spectrum.

also the ga/gp distinction depends, to some extent, on an artificial division between "evaluating a program" and "measuring the fitness of the program's output". you can take even the simplest ga output as not a result that needs to be measured, but as a program whose execution gives you the fitness. so everything is gp.

so, to take my rhythm generating example, you could imagine three different approaches. at the simplest (ga) extreme, the state is a binary sequence that represents therhythm directly (bang drum on "1") and is treated as "dna". at the most complex extreme (gp) it's a program that generates a sequence of values. but in between you might choose a more complex representation like the fourier transform of the final rhythm. that can be seen as ga or as gp.

the choice depends on the complexity you are looking for - in a sense, the degree of long-range correlation you want in your output. a ga is going to have a very hard time generating a regular rhythm. a fourier transform might tend to be too regular. with luck a program that models a digital circuit with components that tend to build "oscillators" might get you something that sounds good....

hmm. i guess that's obvious! (this is your slider?)

I do not think that GP is a special case of GA. GA requires a fixed genotype -> phenotype encoding where the phenotypes are objects in the solution space e.g. function calls with certain argument tuples. Once you have fixed this mapping the algorithm acts on a discrete and finite solution space. Within the GP setting you manipulate the phenotypes directly and mostly on a functional expression level. GP is a stochastic method to create terms in a formal language consisting of some alphabet e.g. {1,x,y,sin,exp,log} and compositional operators e.g. {add,mul,compose}. The set of terms that can be created by GP is unbounded. That's the main reason why GP requires more runtime resources: the terms can grow arbitrary large and they usually do so. There is no intrisic criterion to cut the solution space down or partition it into regions.

Kay

My understanding is that GP is a special case of GA, so both statements of the quote (computational complexity and intractability) come as a surprise.

I believe your understanding is correct, and the distinction made between the two is due to historical reasons. My colleague has written a paper addressing this issue.

From the paper:

Usually a maximum depth or size of tree is imposed in
GP to avoid memory overflow (caused by bloat).

That's a funny argument. It's like asserting that FOR and WHILE are equivalent because with limited computer resources you can simulate each WHILE with a FOR, a sufficient enough loop parameter bound and a BREAK. Or one obtains that integrals are just finite sums because one cannot calculate infintitely many terms practically. Usually mathematicians look for somewhat more profound reasons before they equate things but boys who know typing on a computer keyboard may have a different attitude.

Kay

Usually mathematicians look for somewhat more profound reasons before they equate things but boys who know typing on a computer keyboard may have a different attitude.

To bring this more or less to PLT topic: it looks like Evolutionary Computation (EC) community might benefit from cooperation with PLT community - denotational semantics alone could bring at least a unification of vocabulary. Acquiring a taste for category theory may be a useful side effect as well. Applications of metaprogramming ideas look promising.

On the other hand I believe EC people have a lot of great ideas just waiting to be generalized in context of PLT.

my (amateur, non-biologist) understanding is that the solutions that evolution "arrives at" are often rather ad-hoc and, from a mathematical point of view, quite inelegant. so while arbitrary limits on depths of recursion (or the need for a stack at all) might disturb a mathematician of delicate sensibilities, that doesn't mean that it won't work.