Off topic I was deeply involved in genetic programming in the past (in fact I discovered Haskell on looking for a functional language for genetic programing with better syntax than LISP). But I soon realized that GP was not the holy grial after all. The problem with evolving arbitrary programming code is the fitness landscapehttp://www.google.com/search?hl=en&q=fitness+landscape. Any evolutionary process needs a way to produce small changes that produces small increases or decreases of fitness (parsimony). This is why it is relatively easy to evolve a continuous function towards a desired value. A smal change in a parameter has a small effect in the resulting fitness, so the algoritm can step up trough the smooth fitness landscape upto a local maximum. But programs are non lineal. If I change the expression in a conditional, the flow of the program becomes radically different, so the fitness landscape, instead of a smoth continuous surface is a fractal where there are no way to climb up the mount improbable (Dawkins dixit). http://www.google.com/search?hl=en&q=mount+improbable+dawkins The only way to overcome this is to indentify the smooth parts of the fitness landscape and restrict the exploration to them trough some techniques such is the use of rules, division of the problem in subproblems and ...well any trick programmers use in their ordinary work to restrict and direct the program mutations. It is theoretically possilble to define metalevels of genetic algoritms where rules and strategies are selected by extracting sucessful patterns after evolving a big number of sucessful programs, These metaleves can discover from simple rules such are "if a push is inserted, a pop must be inserted somewhere else (push-pop gene mutation rule), upto the re-discovery of complex rules above mentioned. These rules later would be used to restrict the mutations of the lower levels. Finally the rules could become so accurate that no mutation at the lower level is necessary because the evolved higuer level rules give the solution at the first try. So the genetic algoritms have the potential to design arbitrary complex programs right from scratch, but it may require a few billion years of computing. Anyway this stuff is really interesting and I suspect that the combination of rules and metalevels has some future, at least for helping programmers with intelligent IDEs. 2010/12/8 Kenneth Hoste

Hi Jan,

Hi Jan,

On 11/29/2010 12:55 PM, Jan Snajder wrote:

...

Dear Haskellers,

I am pleased to announce the release of genprog-0.1, a genetic programming library.

(snip)

Very interesting, and nice job on the code (elegant, well-structured, well-documented, ...)!

Genetic programming recently got my attention because one of the bots in the Google AI contest was built using this technique (see http://ai-contest.com/forums/viewtopic.php?f=17&t=1136), and it performed really well (way better than my hand-crafted bot).

I have a bit of experience with genetic algorithms, on a practical and pragmatic level. The field of genetic programming is something I hope to look at and play with in the upcoming months (just for fun).

I was kind of planning to implement my own genetic programming library in Haskell as I became familiar with the field, but after diving into your code it quickly became clear to me you've done a way better job than I would have.

I really like the example you provided for evolving an expression that computes a specified integer value. I plan to start playing with that and improve the example (faster convergence to a perfect solution, and also tweaking the current GP config to obtain smaller solutions).

A couple of questions (some fairly unrelated to Haskell):

How hard would it be to extend the current version to support the evolution of actual Haskell programs? As far as I can tell, the current version has support for (simple?) self-defined expressions, but this seems like a long way from supporting Haskell programs with multi-argument functions that operate on lists, etc., even if you just limit it to non-monadic Haskell98 code.

Have you considered playing with dynamic values for the various parameters that steer the evolution, i.e. population size, crossover/mutation probabilities, etc.? One thing I've always wanted to try (but never really got to it) is e.g. increasing the mutation probability as the evolution seems to be getting stuck in a (local?) optimum. Also, shrinking the population size if enough progress is being made could be interesting, to speed up the evolutionary process. Are you aware of studies that do such a thing?

Are you planning to actively maintain and extend this library? Are you using it for research purposes, or did you hack this together just for fun (if so, nice job!). What do you plan to use it for?

Anyway, great job, I hope I'll find the time to play around with this.

_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell