How to evolve a RETE...

So... Combining NEAT and a RETE... How is that done?

Prep

First off, some links to read:

• EVOLVING NEURAL NETWORKS THROUGH AUGMENTING TOPOLOGIES by Kenneth O. Stanley and Risto Miikkulainen. This is an essential NEAT primer.


• The Wikipedia page on the RETE algorithm has a good overall description of the network.

Encoding

NEAT evolves the structure and weights of a neural network simultaneuosly. It does this by 1) encoding both the network connections and weight information in a single genome, and 2) tagging new network structures with unique identifiers as they are created in each generation.
So, the first challenge in adapting NEAT to RETEs is in defining the genome representation. In a NEAT evolved neural network there is only one node structure: a node takes multiple weighted inputs, (real valued activation levels) and propagates the processed value to multiple other nodes of the same type. A RETE uses different type nodes, basically one and two input nodes. The values propagated are tokens which represent knowledge of the current state of objects in working memory. A genome representation of a RETE must have the following properties:

• Encode only valid RETEs. Encoding must specify the following:
  
  
  
  • Alpha node expressions
  
  
  • Alpha node connections. (Alpha nodes can only connect downstream to Alpha Nodes, Rule Nodes, or Beta/Gamma nodes. The Alpha node network is a tree.)
  
  
  • Beta/Gamma node expressions
  
  
  • Beta/Gamma node connections. (Beta/Gamma nodes must have two inputs, and connect downstream to Rule nodes or Beta/Gamma nodes)
  
  
  
  • Rule nodes (RHS code, probably a single operation per node, with multiple nodes to describe more complex RHS functionality)
  
  
  
  


• Node graph must be acyclic


• Be variable length, to enable continual complexification


• Two parallel encodings should be used: alpha nodes (encoded top down) and beta/gamma nodes. (encoded bottom up)

Working memory object structure can be specified by analyzing the LHS conditions in Alpha/Beta/Gamma nodes. Thus their structure does not need to be separately encoded.
The main difficulty I forsee is not in encoding the network structure, but encoding the node expressions. In NEAT the analog is encoding the node connection weights. The logical expressions in RETE nodes are far more complex. Also, the structure is resident in the nodes. (As opposed to the network edges.) One possible solution is to encode expressions in a way similar to Grammatical Evolution. In NEAT the weight of a node connection produced in crossover is calculated from the average of the matching genes in crossover parents. This would be possible with a GE type encoding for node expressions, as the distance between two arbitrary numerical strings can be easily calculated. However, averaging two GE genomes would introduce far more nonlinearity than averaging two neural network connection weights.

Evolution

I plan on incorporating the major innovations of neat: historical marking, continual complexification, speciation.