Read Me

Very rough genetic algo framework in python
-------------------------------------------

richardagreen@gmail.com


Basic class hierachy..
----------------------

"Everything" extends from the Node class which can "evaluate" itself given a value (which is generally an array of inputs). 

In the code, all example trees start from a "PassThroughNode" which is then asked to "create" which generates the actual function tree.

The only Nodes that are working currently are IntegerConstantNode, SubtractFunctionNode, MultiplyFunctionNode, GetParameterNode and AddFunctionNode. 

I think Store and Get may work, but I haven't tested / worked on them much yet. "If" definitely doesn't work yet ( I am in a quandry how to divide the logical operators and whether it should be a 2, 3, 4 or 5  child function - ie "if ( a logical_op_b c ) then d else e" requires 5 children [ logical_op_b is one of =, !=, <, > etc etc ] , whereas the simple "if a > 0 then b" requires only 2.

I haven't included stuff in later version of python (ie multiprocessing) yet...

Bits that I think are "my" ideas but have probably been done by other people
----------------------------------------------------------------------------

1) "Minor Mutations" - ie if we are mutating things that are quite succesful in the population - then a minor mutation may (in the case of an integer constant node) only change the value a small value up or down. I haven't extended this to other nodes yet but thought I'd throw it in there.

2) "Graduated targets for the natural progression of generations". If I can explain with a very basic simile - you don't put a baby in a space shuttle. Genetically, the child has to learn to stand up, walk / talk, go to college etc.. The ones that don't make the grade don't get through to the next generation. Therefore, if you have a very specific challenging task, then break down the target steps into levels where only the best progress onto the next challenge. Additionally, make some algorithms just functions which are then used by parent algorithms.

3) Construction of executable code. Each Node currently can represent itself as subcode in python format - therefore the whole algorithm can display itself as executable python code (as well as XML). This can then be eval()'d instead of node.evaluate()'d hopefully improving performance. 

4) Node simplification. There may be some benefit in applying some simple math simplification / optimization to algorithm trees - ie if you have an add node of (10,5, x[1]), then just make it add(15,x[1]).Additionally, anything that is +0 should just be simplified and anything multiplied by zero will obviously be zero. This does actually reduce the potential for benificial mutations however, but it can make the algorithm more human readable.

5) If the population doesn't generate a better solution, then the population size for the next generation is doubled and the elitism factor is reduced by 75% ( effectively halving the number that make it through to the next generation). This is reset to the initial values once the generation has provided a better fitting candidate.



Current Usage
-------------

I write "current" as it is currently configured to 
1) generate a random dataset using the formula in hidden_function2 ( currently : 2 * x + 5 + y )
2) evolve a solution to the above
3) repeat 1+2 10 times and display the time taken to find the solution

Once a solution has been display you can create a python function from it directly, eg the last few lines of the last run I did looked like:

Generating...
Stats for generating = [9, 15, 0, 56, 1] (took 0.063000202179 seconds ) 
Scoring...
Scoring took 0.171000003815 seconds
0.000000e+000
Pop size now 100 . Elitism is now 0.2 
=  + ( <8>, - (  - ( P[0],<0> ) , - ( P[0],P[0] )  ) , + (  + ( <4>,P[1] ) , - ( P[0],<8> ) ,<1> )  )  
lambda x: (8 + ( ( x[0]  - 0 )  - ( x[0]  - x[0]  )  )  + ((4 + x[1] ) + ( x[0]  - 8 )  + 1))
lambda x: (8 + ( ( x[0]  - 0 )  - ( x[0]  - x[0]  )  )  + ((4 + x[1] ) + ( x[0]  - 8 )  + 1))
( 1500,2500,6500,...)
[0.21900010108947754, 0.20300006866455078, 0.28099989891052246, 0.17100000381469727]
=  + ( <8>, - (  - ( P[0],<0> ) , - ( P[0],P[0] )  ) , + (  + ( <4>,P[1] ) , - ( P[0],<8> ) ,<1> )  )  
PRE
lambda x: (8 + ( ( x[0]  - 0 )  - ( x[0]  - x[0]  )  )  + ((4 + x[1] ) + ( x[0]  - 8 )  + 1))
POST
lambda x: (8 + ( ( x[0]  - 0 )  - ( x[0]  - x[0]  )  )  + ((4 + x[1] ) + ( x[0]  - 8 )  + 1))
Detail: [1.375, 4.6089999675750732, 2.3280000686645508, 3.562999963760376, 4.9839999675750732, 2.9530000686645508, 2.3289999961853027, 2.9369997978210449, 3.3280000686645508, 1.1560001373291016] Total:29.5620000362 Avg:2.95620000362 

# Let's create a function from that.. cut/paste :

>>> fn = lambda x: (8 + ( ( x[0]  - 0 )  - ( x[0]  - x[0]  )  )  + ((4 + x[1] ) + ( x[0]  - 8 )  + 1))

# Now "fn" is a function that I can call with whatever values I would like - ie 5,4 or 5,2 etc. The inbound parameter must be addressable

>>> fn
<function <lambda> at 0x001A2E30>
>>> fn([5,4])
19
>>> fn([5,2])
17