Who can do genetic programming with Python
eric at enthought.com
Sat Nov 24 06:14:55 CET 2001
> Python is not a very good choice for genetic programming. Its syntax is
> too complicated, especially if we take into account that it is
> indentation sensitive.
I think using the abstract syntax tree (AST) for the genome might be a
fruitful alternative to working with standard (human readable) Python code.
Jermey Hylton discussed a new-ish module called 'parser' at the last Python
conference that allows you to convert code strings to ASTs, manipulate the
boogers, and run them. I thought this was so cool, I ran home and found a
problem that could use it. The result, scipy.compiler, uses the AST to help
translate Numeric expressions from Python to faster C++ expressions that are
compiled and run on the fly. As far as GP is concerned, I haven't tried it
yet, but I think the AST makes a nice chromosome. You can create AST's from
lists, futz around with them till your hearts content (crossover, mutation),
and evaluate them. That pretty much covers the needs of GAs (or GPs or
whatever). Bytecode might work too, but I've never messed with it (and it
doesn't include the grammatical info like the AST).
As for GA/GP in Python, scipy.ga is a genetic algorithm library that
supports both string and tree chromosomes. The tree chromosomes were
designed specifically for language based (grammatically based, or whatever
you want to call it) genetic optimization. It was used for designing
electronic circuits and antennas using simple languages (CFGs defined in
Python) that described how components of the systems could be connected.
Everything but the computational engine for antenna analysis (and maybe
parts of the circuit analysis) was written in Python. Let me know if your
interested in papers on the stuff. By the way, I think you could define a
sub-set of Python to be used in the chromosomes by defining a simpler
grammar in the tools available in scipy.ga, but again I haven't explored
this avenue at all. If it worked, that would mitigate issues with Python's
The genetic programming aspects of scipy.ga haven't been talked about much,
and the entire library is short on documentation. It does, however, have
most of the needed tools and has served me very well. I'd like to add
pareto optimization and a string genome suitable for traveling salesman type
problems, but other than that, its main deficiencies are documentation, unit
testing, and a few architectural warts.
Take a look, maybe it'll be of some help. I'd love to see someone have at
optimizing python code with ASTs.
> This is why languages such as LISP are used for genetic programming;
> their syntax is simple and it's easy to verify if a program is legal or
> not and to keep it legal while performing genetic operations (mutation,
> crossover, etc.).
> I myself in the past have used stack-based languages which are promising
> since even the constraint on program legality is dropped, provided you
> make certain concessions such as allowing a bottomless operand stack,
> having the key variables of the simulation available by means of special
> operators, etc. With a suitable choice for environment, every sequence
> of legal operators is itself a legal program.
> Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
> __ San Jose, CA, US / 37 20 N 121 53 W / ICQ16063900 / &tSftDotIotE
> / \ Laws are silent in time of war.
> \__/ Cicero
> Esperanto reference / http://www.alcyone.com/max/lang/esperanto/
> An Esperanto reference for English speakers.
More information about the Python-list