It would be cool to make something like that, but more general. A wider scope of problems, more construction elements, more universal attachments, etc.
The standard method of genetic programming is to represent your algorithm/whatever as a tree. The leaves are data and the nodes are operations that the "universe" supports. Then two parents producing a child via "sex" is just trading subbranches. Mutation is random changes.
That works for a linear sequence of steps because there's a standard way to traverse a tree. The question is, how do you represent a machine in a tree? It's (usually) not a linear thing.
Take a wheel and a stick. They are two leaves, I guess. The node is the operator "attach"? But where? I need to know where on the stick AND where on the wheel. And if the connection is rigid, floppy, powered or what. Where is all that knowledge stored? How can I "break out" each of those things to allow them to mutate separately? Also, you can't have a whole-organism coordinate system, for instance, because a single mutation messes it all up.
Another idea is to use an algorithm to build the machine and represent the algorithm as a tree. But what's the advantage of that? I didn't realize until this morning: This is exactly what embryology is. A machine isn't a linear object, but constructing a machine is a linear process.
So to attach a wheel and a stick, I'd have an embryology something like this:
1) Place stick
2) Locate end of stick
3) Locate center of wheel
4) Attach
Or maybe:
1) Place stick
2) Advertises marker at X
3) Locate marker
4) Locate center of wheel
5) Attach
The marker system would be key. If there's more than one stick in the structure, "locate end of stick" is ambiguous. Whereas if the stick knows that it is, say, the left shin, it can hang out cards saying "I'M THE LEFT SHIN" and "HERE IS MY LOWER EXTREMITY" and the wheel can look for that.
Could one of my graduate students get on this and give me credit so I become rich and famous but don't have to stop the N projects I'm working on to get it done? Kthx!
Why would you want to represent it as a tree? You only have to represent the machine as a string of numbers, the "genome". In the case of the stick-and-wheel, wou could reduce it to three reals: length of stick, attachment point, size of wheel. Or to n reals, where n is the number of parameters you want to include...
ReplyDeleteI am a strict amateur when it comes to genetic algorithms, I only wrote some very basic ones as an exercise in Mathematica and Matlab. But I found that 90% of the problem is how to express your problems as a genome, the rest is pretty easy...
Oops, forgot to check the "email follow-ups" thing.
ReplyDeleteWell, maybe I don't need a tree represenation, although your "string of numbers" doesn't necessarily mean it isn't a tree too. For instance "5 + (3 - 2)" is a tree represented as a string.
ReplyDeleteA tree representation is nice because of the dependencies. Say I have two wheels and a stick. For each wheel, I'd like to say "attach to the stick". That's a tree like the above math problem: "wheel attachTo (wheel attachTo stick)" or something.
However, you could just give absolute XY coordinates. "wheel attachTo (6,7)" and then whatever is at (6,7) is what the wheel gets attached to. That seems both ugly and contrived to me, though. In real life, a developing embryo doesn't just place things, it finds the right attachment point and latches on.
How about using a netlist similar to pspice? The genome would consist of a number of nodes (i.e. junctions of sticks and wheels) and components (sticks and wheels).
ReplyDeleteThe parser would have to ignore nonsensical input (junk dna!) or else nonsensical mutations just die at birth.
I think that the spice-netlist may be a tree-structure in itself, but there my knowledge of algorithms gets spotty fast!
I don't know anything about pspice, but "nodes (i.e. junctions of sticks and wheels) and components (sticks and wheels)" sounds similar to my first idea. I rejected that idea for some reason I can't now remember, but knowing it is in use elsewhere could be enough to get me over any difficulties in using it.
ReplyDeletePerhaps one problem is that electrical connections aren't too fussy with where you do it. But with a machine, you'd have to be able to specify a location on each piece where the junction takes place. Local coordinate system of some kind I guess? Or maybe each kind of piece only has a few set attachment points and you just specify which one? In either case, where does that information live? In the component node or in the junction node? Or as a separate child?