Need some guidance re: genetic algorithms/programming

[blike]

Firstly, I am not a developer by trade or training -- it's mostly a former side-hobby that I'm trying to pick up again. I've embarked on a fairly ambitious development project (which, at my pace, will likely take years). But I'm willing to spend the time reading and learning. Recently I've become very interested in genetic programming / genetic algorithms for finding general solutions to problems. I don't know that vb.net is is the best choice (in fact, in my readings it seems that LISP was the standard for GP), but it seems at least as capable as C# and I am at least familiar with BASIC.

My question is how to approach the problem of generating function trees (http://en.wikipedia.org/wiki/File:Ge...ogram_Tree.png).

Initially I had considered encoding these trees as strings and then manipulating the strings, then writing a routine to parse the strings and evaluate the results. However, to me this seems entirely convoluted and round-about, not to mention very static with respect to how many nodes and child-nodes are generated. I stumbled across CodeDOM and wondered if it can be put to use somehow in this situation.

What do you guys think would be a good general approach to generating and then applying these function trees to datasets?

[jakkjakk]

Can you provide an example of what your input would be and then what you would expect the output to be? Your picture looks like a binary tree to me which is a data structure. You can put your data into a tree it really doesn't make a difference.

It doesn't really make a difference which language you use. LISP would probably be the most efficient language but the hardest to implement because most programs in LISP are recursive and very compact. C# or VB are pretty much the same just the syntax is different. (Ok, there's subtle differences, but lets not start a war about which one is better here)

[Shaggy Hiker]

What does the link have to do with GA? Is the idea to evolve equations? If so, I have such a program in VB.NET, but written for 2003 and could be improved a bit for 2005. I, too, started encoding the equations as strings, but that is really poor from a performance standpoint. String manipulations are really slow. What I ended up doing, if I remember it right, was creating a small Gene class that had a couple integer members to hold the information about the gene. Therefore, a genome was a List(of Gene) (except that back in .NET 2003, there was no such thing as a List (of anything), so it was actually implemented as an array.

By the way, I think this is a truly awesome area to start in hobby programming. I believe there are whole realms untapped when it comes to GA development. I'm currently working on a GA based AI learning engine for a robot, but the horizon is without limit in this area.

One thing I would encourage is that you use at least two levels of GA so that you incorporate hybrid vigor into your design. By two levels, I mean that you run the GA for X number of iterations, take the winner and put it aside, then get a new starting population, run it for X iterations, put the winner aside, and so forth until you have an entire population that consists of winners of previous GA runs. You then run this population of winners through the GA. In every trial that I have performed, the winner of this group of winners is better than any of the winners themselves. My current equation evolver program goes to three levels, such that it is getting the winner of the winners of the winners. However, this takes a very long time. In fact, if T is the time it takes to get one winner of winners (the second level), then it takes T * the number of iterations. Furthermore, the winner of the winners of the winners is rarely better than any of the winners of the winners. In other words, two levels provides a substantial boost, but a third level provides no significant further boost. On the other hand, the population of winners of the winners is of value if you are evolving equations.