Genetic Programming

John Kozaformalized the use of LISP S-Expressions as the representation of Choice for Genetic Programming. Lisp S-expressions map directly onto a parse tree, which can be manipulated via the usual methods of tree modification. Functions that accept zero arguments or constants (quoted or otherwise are terminals) and other functions are non-terminals.

The standard GP algorithm takes five inputs.

1. a set of terminal functions, T
2. a set of non-terminal functions, NT
3. a set of control parameters P
4. a fitness funtion, f(x)
5. a termination criterion t

Contained in the set of control parameters are

• n - the initial number of S-expressions
• Di - the initial maximum depth of nesting of an S-Expression
• Pr - probability of reproduction of a fit individual
• Pc - probablility of recombination of a fit individual
• Pm - probabiliy of mutation of a fit indivudual
• Dc - maximum depth of nesting of an S-Expression during a run

The standard algorithm runs a follows

1. (setf *generation-count* 0)
2. (setf *current-population* (random-experssions :count n :nesting Di :terminals T :non-terminals TF))
3. (set *current-fitness* (loop for individial in *current-population* collect (fitness individual))
4. Filter the current population by fitness, producing a new individual by a randomly chosen method.
5. (setf *current-population* *new-population*)
6. (until t)

Fitness is usually measured by standardzed fitness where the fittest indvidiual has a fitness of zero. Reproduction is a asexual copy, mutation is asxual copying with reandom errors, and crosover is splicing together two infvidials from one half of each individial, the splice point being arbitarily chosen. It is important that the union of T and NT (called C) is sufficent to solve the target problem, and that all the functions accept and return arguments of the same type.

Intresting Lisp Factoid of the Day

You can put docstrings in Lambda expressions. Whee, just what I always wanted!

((lambda (x) "This is documented" (format t "~A" x)) 
1

More on Cooperatives

Of course, my recent ramblings on co-operatives only echo a train of thought someone , somewhere else has had and put into action: take a look at the SelectParks co-operative. At least I know I'm not going crazy, now.

More Lisp on Gentoo

The sbcl-cvs ebuild turned out to be a good example of the pitfalls awaiting the CVS ebuilder. Recently the contrib/systems directory was removed from sbcl cvs as Win32 doesn't do symlinks. Unfortunately, the plain-vanilla Gentoo asdf ebuild still wanted them, so when you loaded up Slime it complained it couldn't find SB-BSD-SOCKETS.

The solution was to create the symlinks as part of the ebuild. Slime now works with it..Here's the new ebuild. It needs to live in /usr/local/portage/dev-lisp and you need PORTDIR_OVERLAY="/usr/local/portage" in your make.conf.

Edit: perhaps I should also warn you that this ebuild uses cmucl to compile sbcl and will pull that in, too.

Lisp on Gentoo

One thing about Lisp is that releases of packages tend to be infrequent: for instance Gentoo's cl-mcclim is ancient, and doesn't compile with the *unmasked* sbcl (.94) in portage. Advice on #lisp is that many asdf packages should be pulled from CVS rather than messing about with distro packages. One nice thing about Gentoo is that you can write ebuild scripts that pull distro packages straight from CVS, so I'm going to write a few ebuilds for myself and publish them here to save a few people time. First off is the SBCL CVS ebuild.