pySTEP

Python Strongly Typed gEnetic Programming

A light Genetic Programming API that allows the user to easily evolve populations of trees with precise grammatical and structural constraints. In other worlds you can set up building blocks and rules that define individuals during the evolution.

Why using rules and constraints ?

Let's take the example of the DNA of a human being which is 95% similar to the DNA of a chimp. This means that there is some strong similarity in the building blocks and the structure of the genetic code. A completely random genetic code would make no sense on a functional practical point of view because it would give some kind of unfit and disfunctional goo... I just think that, to be useful, artificial evolution has to be able to integrate basic rules that determine the shape of the individuals generated, so that we can get practical results. This does not mean we eliminate random search and we still admit poorly fit individuals. But at least we focus the search in the direction of the problem by only generating potentially useful solutions.

pySTEP is presently functional, running and stable. Still in the process of adding extra tutorials, extra features for reading the populations from the database, and modify some of the crossover code (so far, only 1-point crossover is used).

There has been a lot of improvement going on since the first version:

You can download the last version here.

License Agreement

copyright: (c) 2009 Mehdi Khoury under the mit license.
http://www.opensource.org/licenses/mit-license.html

Documentation and Help

This distribution comes with several pieces of documentation:

In order to be able to use this package, you need to have installed on your machine:

- Python 2.6.1

- psyco for python 2.6

- pysqlite for python 2.6 and the corresponding version of SQlite

- numpy for python 2.6

Tutorials

A detailed html documentation explains how to set the parameters in the settings module and describes each and every of the 5 different tutorials (see tutorial1 to tutorial5 in the api documentation).

How to set Grammar Rules to build trees

If you want to build a tree with very detailed and specific grammar rules, you need to know what Pystep expects you to do.

A tree always starts with a Root node at the top. The root node has no specific operator in it, but it is recognised by Pystep as the top of the tree.

You must specify for each parent node what are the possible children nodes. You must specify how many children nodes this parent node can have, and for each child node you must specify a function and a terminal set (if a parent can only have function nodes as children, specify the function set and an empty terminal set)... This looks all a bit confusing at the moment, so let's get through it with simple examples.

Example 1: A tree with simple arithmetic and one result.

# default function set applicable for nodes:
defaultFunctionSet= [(1,2,'+'),(1,2,'*'),(1,1,'^2'),(1,2,'-'),(1,1,'cos'),(1,1,'sin'),(1,1,'neg')]
# default terminal set applicable for nodes:
defaultTerminalSet= [(3,0,'x')]

treeRules = {

# The root node only has one child. This child can be either a function node or a terminal node.
'root':[(defaultFunctionSet,defaultTerminalSet)],

# The + node has two children. Each child can be either a function node or a terminal node.
'+':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The * node has two children. Each child can be either a function node or a terminal node.
'*':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The ^2 node only has one child. This child can be either a function node or a terminal node.
'^2':[(defaultFunctionSet,defaultTerminalSet)],

# The - node has two children. Each child can be either a function node or a terminal node.
'-':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The neg node only has one child. This child can be either a function of the type +, *, -, cos, and sin or a terminal node.
'neg':[([(1,2,'+'),(1,2,'*'),(1,2,'-'),(1,1,'cos'),(1,1,'sin')],defaultTerminalSet)],

# The cos node only has one child. This child can be either a function of the type +, *, -, neg, and sin or a terminal node.
'cos':[([(1,2,'+'),(1,2,'*'),(1,2,'-'),(1,1,'sin'),(1,1,'neg')],defaultTerminalSet)],

# The sin node only has one child. This child can be either a function of the type +, *, -, neg, and cos or a terminal node.
'sin':[([(1,2,'+'),(1,2,'*'),(1,2,'-'),(1,1,'cos'),(1,1,'neg')],defaultTerminalSet)]
}

 

Example 2: A tree with hybrid systems: mixing discrete and contimuous representation (logic+arithmetic).

# default function set applicable by for branches:
defaultFunctionSet= [(1,2,'+'),(1,2,'*'),(1,1,'^2'),(1,2,'-'),(1,1,'cos'),(1,1,'sin'),(1,1,'neg')]
# default terminal set applicable by for branches:
defaultTerminalSet= [(3,0,'x'),(3,0,'y')]


treeRules = {

# The root node has three children in a specific order. The first child can only be a If function node. The second child can only be a Then function node. The third child can only be a Else function node.

'root':[([(2,1,'if')],[]),([(2,1,'then')],[]),([(2,1,'else')],[])],

# The If node has only one child. This child can be only a function node (either and, or, >, <, or =).
'if':[([(1,2,'and'),(1,2,'or'),(1,2,'>'),(1,2,'<'),(1,2,'=')],[])],

# The Then node has only one child. This child can be either a default function node or a default terminal node.

'then':[(defaultFunctionSet,defaultTerminalSet)],

# The Else node has only one child. This child can be either a default function node or a default terminal node.
'else':[(defaultFunctionSet,defaultTerminalSet)],

# The And node has two children. Each child can be only a function node (either and, or, >, <, or =).
'and':[([(1,2,'and'),(1,2,'or'),(1,2,'>'),(1,2,'<'),(1,2,'=')],[]),([(1,2,'and'),(1,2,'or'),(1,2,'>'),(1,2,'<'),(1,2,'=')],[])],

# The Or node has two children. Each child can be only a function node (either and, or, >, <, or =).
'or':[([(1,2,'and'),(1,2,'or'),(1,2,'>'),(1,2,'<'),(1,2,'=')],[]),([(1,2,'and'),(1,2,'or'),(1,2,'>'),(1,2,'<'),(1,2,'=')],[])],

# The = node has two children. Each child can be either a default function node or a default terminal node.
'=':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The > node has two children. Each child can be either a default function node or a default terminal node.
'>':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The < node has two children. Each child can be either a default function node or a default terminal node.
'<':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The + node has two children. Each child can be either a default function node or a default terminal node.
'+':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The * node has two children. Each child can be either a default function node or a default terminal node.
'*':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The ^2 node has only one child. This child can be either a default function node or a default terminal node.
'^2':[(defaultFunctionSet,defaultTerminalSet)],

# The - node has two children. Each child can be either a default function node or a default terminal node.
'-':[(defaultFunctionSet,defaultTerminalSet),(defaultFunctionSet,defaultTerminalSet)],

# The neg node only has one child. This child can be either a function of the type +, *, -, cos, and sin or a default terminal node.
'neg':[([(1,2,'+'),(1,2,'*'),(1,2,'-'),(1,1,'cos'),(1,1,'sin')],defaultTerminalSet)],

# The cos node only has one child. This child can be either a function of the type +, *, -, neg, and sin or a default terminal node.
'cos':[([(1,2,'+'),(1,2,'*'),(1,2,'-'),(1,1,'sin'),(1,1,'neg')],defaultTerminalSet)],

# The sin node only has one child. This child can be either a function of the type +, *, -, neg, and cos or a default terminal node.
'sin':[([(1,2,'+'),(1,2,'*'),(1,2,'-'),(1,1,'cos'),(1,1,'neg')],defaultTerminalSet)]
}

 

Quick Run

To execute the evolution run of the first tutorial, create a main method in Python (there is one main module already made for you in the package if you want...).
Inside, you need to:
1- import the module called "evolver"
2- define a name and path for you database.
3- and then call the EvolutionRun method from the evolver module.
e.g. of a main file:

import evolver

if __name__ == "__main__":

dbname=r'C:\pop_db'
evolver.EvolutionRun(2000,(0,1,'root'),2,8,'AddHalfNode',100, 0.001 ,0.5,0.49,dbname,True)


This means that we define:

The run will create a database file containing tables of names tab0, tab1,... where every table contains the population for the corresponding generation.

For those who want details of the populations, there are methods in the module writepop that allow to:
- get stats from a database table: GetPopStatFromDB(dbname,tablename)
- print the population from a database table to a file: PrintPopFromDB(dbname,tablename,filename)

On a more personal note, I enjoyed programming this API using the Eclipse IDE (there is a pyDev module that allows to use Eclipse to program in Python).

It's great and I recommend it !

Feedback and input are highly welcomed :)

Interesting links:

ECJ : Java Genetic Programming Package

pyGP : The Python Genetic Programming Project implements a Genetic Programming System a la J Koza in Python.

Dione : Genetic Programming framework written in Python. Takes advantage of python\'s compiler to make things simple. Includes basic genetic operations (rank/roulette selection,crossover,mutation,steady state,elitistm ...)

Personal WebPage

Here

 

Get pySTEP at SourceForge.net. Fast, secure and Free Open Source software downloads