Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

As part of an assignment I'll have to write a genetic programming algorithm that does prediction of atmospheric pollutant levels. Since I have no experience, can anyone point me pointers to propositions of programming languages in which evolved programs will be written.

Clarification: I'm not asking what will be the language I'll write the genetic algorithm itself (as I will be able to make the decision myself), I'm asking in what programming language the evolved programs should be created.

My instructor suggested Lisp, but I don't like this idea --- first I would have to work on some kind of Abstract Syntax Tree, secondly reliably doing crossovers on tree structure can be hell of a mess.

I'd rather use something that is dedicated for genetic programming like slash/A. SlashA does not require working on ASTs --- programs in bytecode are a just an array of ints that can be changed in any fasion necessary since every int array represents some slash/A program.

Additional remarks:

  • I'd like to avoid manipulating ASTs!
  • This problem is hard (maybe not as hard as predicting stock values). This is due to the fact that (most probably) we don't have enough input information (there are some hidden parameters). Creating a model that has better performance that model that returns mean is somewhat of a challenge (mean models have 35% MAPE), most models have MAPE of about 25%, best have 20%.
  • I'd like to have a language that manages datasets with many features with assumption that I'm not sure which are important. (Slash/A has a disadvantage here --- in this language input features are read sequentially --- so some features will be used with bigger probability).
  • I'd like to be able to program this in Python, so python libs would be great --- but I can do bindings for C/C++ (no Java, no Matlab, etc).

I'm conscious this is a survey question, so if it is to early for such question please close it, but I feel it is specific enough.

share|improve this question

2 Answers 2

up vote 10 down vote accepted

Your pollutant problem probably doesn't need much of a language at all. It looks like a symbolic regression rather than a control problem, in which case you could just use standard tree GP, with features and a few useful constants as the terminal set and relevant operators in the function set. The GP system will weed out irrelevant features and there are techniques to handle very large datasets. Generally, specify the smallest function set that you estimate could solve the problem, and expand it with care if necessary.

You'll need to choose between tree and linear GP early on. Lisp is tree, Slash/A is linear. Read up on both to understand the pros & cons, but from what you wrote I'd suggest a simple tree GP system. It's not too hard to write your own, but there are existing Python implementations. These ones below are for evolutionary algorithms in Python in general but not all do GP and some are inactive:

  1. PyGressionGP (GP for symbolic regression in Python) -- http://code.google.com/p/pygressiongp/
  2. PyGene -- https://github.com/blaa/PyGene
  3. A Simple Genetic Programming in Python -- http://zhanggw.wordpress.com/2009/11/08/a-simple-genetic-programming-in-python-4/
  4. Pyevolve -- https://github.com/perone/Pyevolve -- also see blog -- http://pyevolve.sourceforge.net/wordpress/ -- and this post -- http://pyevolve.sourceforge.net/wordpress/?p=549
  5. esec (Evolutionary Computation in Python) -- http://code.google.com/p/esec/
  6. Peach -- http://code.google.com/p/peach/
  7. PyBrain (does a lot, not just NN) -- http://pybrain.org/
  8. dione -- http://dione.sourceforge.net/
  9. PyGEP (Genetic Expression Programming) -- http://code.google.com/p/pygep/
  10. deap (Distributed Evolutionary Algorithms) -- http://code.google.com/p/deap/

Also, see the (free) introductory book on GP by well-known GP authors Poli, Langdon and McPhee:

A Field Guide to Genetic Programming -- http://www.gp-field-guide.org.uk/

share|improve this answer
    
Do you have any references to pros and cons of linar and tree GP? –  jb. Feb 13 '12 at 12:48
    
I've seen a few comparisons but haven't got any concrete references. You could look at what Banzhaf and Brameier published in the 2000s - they did quite a bit of work on linear GP and published a book on LGP in 2007 I think. –  Graham Jones Feb 14 '12 at 13:42
    
Hm... why don't these people unite? –  vonPetrushev Feb 19 '12 at 2:52
    
I'm not sure what you mean - why don't tree and linear GP people unite? There's no religious divide, they're just different flavours of the same idea (and there are others as well, like Gene Expression Progamming (GEP) - gene-expression-programming.com). –  Graham Jones Feb 20 '12 at 7:14
    
I;m not saying that tree GP is evil or sth. I just wanted to roll my own implementatiom, and linear is so much easier. I had working Python prototype in like 4 hours from scratch. –  jb. Feb 23 '12 at 19:03

If you are going to evolve a program, you are likely to manipulate a syntax tree anyway; that way whatever program you evolve will automatically be syntactically correct.

There are two things you will want to keep in mind when selecting a language.

  1. Avoid low-level constructs that may cause the evolved program to crash on some data. For example, pointer arithmetic. If you are going to use C or C++ as the language for your evolved programs, you may want to restrict it to a version without pointer arithmetic.
    I would vote against assembly language for similar reasons, although virtual machines like the JVM and the CLR should provide you with something of a safety net.
  2. Suitable for large data sets; if I understand your assignment correctly, the output programs will themselves have to manipulate large data sets.

You will probably want to use a target language that you are already familiar with. I am not familiar with Python myself, but AFAIK it satisfies the criteria above, so it should be a good choice for your target language.

share|improve this answer
    
See github.com/arturadib/slash-a --- in this language you have no AST manipulation! Program is represetned as an array of bytecode and since every array is a correct program you can use whatever genetic operations you want. –  jb. Feb 11 '12 at 22:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.