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 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).
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
<kenneth.hoste@ugent.be>
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.