Hello everyone, I've been lurking on this list since it started and haven't yet contributed anything, mostly because I'm only a casual Common Lisp user, but I have a project idea that I think some of you will find interesting. I'm sorry that this email is so long.
I'd like to work on an implementation of various state of the art evolutionary computation algorithms, which I'll briefly explain below. This library would make Common Lisp the only language to have a usable, featureful public implementation of these techniques - for once, we could be ahead of the C/C++/Java dorks. What I'm interested in is a field called evolutionary computation. This is a family of optimization techniques which are inspired by biology, especially genetics and social insect behavior. Hopefully some of you are familiar with this area. Here I'll assume that you know what genetic algorithms and genetic programming are. For an introduction, see, e.g., http://en.wikipedia.org/wiki/Genetic_algorithm and http://en.wikipedia.org/wiki/Genetic_programming . I would try to explain them here but it would make the email even longer than it already is. Bill Clementson is interested in doing evolutionary computation in CL and has written some blog entries about this, such as http://bc.tech.coop/blog/040619.html . Genetic programming (GP) as it is commonly used is not perfect. In classic Koza-style GP, you have no control over what calls what (i.e., no control over the parameters which functions in your function set are given when constructing trees), so usually you just set things up so that all your functions take and receive the same datatype, usually float/double. There have been some variants of this, such as strongly typed GP, which attempt to allow you to restrict the search space. But you still don't really have fine-grained control over the kind of solutions you evolve, making the search space enormously large and making it somewhat difficult to incorporate problem-specific domain knowledge into your GP system. There's a relatively new evolutionary technique/algorithm which is a big leap forward in this regard. It's called grammatical evolution (GE). It was developed in 1998. See http://www.grammatical-evolution.org/pubs.html#1998 for a few different introductions. The basic idea is to separate genotype and phenotype. The "genotype" is a list of integers. This is mapped to selecting rules from a Backus-Naur form grammar you supply for the problem. The papers at grammatical-evolution.org explain precisely how this is done. But basically it allows you to custom-tailor the evolved solutions any way you want and to productively restrict the search space by altering the grammar in use. GE is becoming more popular and has been applied to things like predicting stock indices, predicting corporate bond ratings, predicting corporate bankruptcy, training artificial neural networks, and so on. Like all evolutionary methods, it can be easily parallelized. Implementations of GE are hard to come by. At the present time, all that exists publicly is a partial implementation of GE in C++ called libGE (see the link to libGE at www.grammatical-evolution.org) but its documentation is confusing as hell and you still have to use a separate genetic algorithm library to do the actual searching, requiring that the user learn and use two complicated libraries to get a single task done. To me, it is useless. I propose that an easy-to-use library implementing full-blown GE be implemented. Lisp is a great environment for prototyping things like GE; that's why GP was first developed and used in Common Lisp. I have a lot of other ideas for what could be done, such as implementing swarm intelligence algorithms. Any takers? Cheers, Warren Henning _______________________________________________ Gardeners mailing list [email protected] http://www.lispniks.com/mailman/listinfo/gardeners
