The goal of this project is to see if artificial organisms living in an artificial environment controlled by recurrent neural networks (RNNs) selected using a darwinian genetic algorithm (GA) could mimic the behavior of real organisms in a real environment. The idea behind this project is to use a genetic algorithm to evolve the structure of an RNN which can learn and act as an artificial intelligence to an orginism living in a simplified virtual environment. The hope is that these artificial organisms will mimic some of the behaviors which we see in real organims.
Unlike the feed forward networks discussed in class, Recurrent Neural Networks or RNNs can have cycles in a graph of their nodes. This allows them to retain information about their previous inputs. In a similar way to Hopfield networks. Unlike Hopfield networks, RNNs need not have symmetric connections. That is to say if an RNN was written as a directed graph, the adjacency matrix for such a graph is not necessarily symmetrical as with a Hopfield network.
Due to the presence of recurrent connections, an RNN can "remember" previous inputs, or the calculated results from previous inputs. This allows it to perform more complicated functions than regular feed forward neural networks. Given a sufficient number of neurons, an RNN is capable of computing any function computable with a Turing machine.
The hebbian learning rule most simply stated is that neurons that influence each other's firing have more chance of triggering each other in the future. It is an unsupervised learning rule in that there is no concept of positive or negative reward. This rule would seem unsuited to this project since the survival of an organism is a particular behavior which we seek to reward, while we seek to discourage behavior which does not ensure survivial. Part of this goal will be taken care of by the genetic algorithm; however, it cannot teach the network to survive during it's life, since we are only evolving the structure.
By taking the output nodes of an RNN and forcing their output values to the values desired for a particular problem, the recurrent links in the network can be used to train the network toward producing similar values on particular sets of input. This can be used to provide the organism with an example to follow, such as the actions of their parent organism. This method of clamping was used to train recurrent binary neural networks to respond to changes in environment in the paper presented in class.
In this project the goal is to evolve the structure of a RNN, thus the RNNs which we seek to evolve must be put in a meaningful encoding which we can define genetic operators on. The main problem with this is that neural networks are more complicated and less ordered than most things which we would run a GA on. This is problematic when we attempt to define genetic operators on RNNs, since most of the standard genetic operators and encodings are less useful to RNNs than they are to most other problems. We will examine three possibilites for encoding an RNN
Direct encoding of an RNN is a binary serialization of the adjacency matrix of an RNN. Though this is an easy encoding to implement, it has problems when used in a genetic algorithm. Often times in a well performing neural network, a particular sub-part of the neural network performs a particular sub-task of the main task which the neural network must perform. This sub-part is commonly referred to as a functional block. When a direct encoding undergoes crossover to recombine its genetic material with another organism's genetic material, any such functional blocks are often split or rendered useless by the random interleaving of the genetic material. This results in the child of two fit RNNs being less fit than either of its parents. This is a problem because the genetic algorithm relies on the assumption that crossover will produce a signficant number of offspring which are at least as fit as their parents. Otherwise it is difficult to have a population which is increasing in fitness over time, since recombining genes usually makes much less fit offspring.
In this encoding, The adjacency matrix of the RNN is specified as a start symbol and list of producions which form a matrix grammar. Each non-terminal in this grammar produces a 2x2 matrix of weights or non-terminal symbols. Such a grammar also has only one production for each non-terminal, so that the start symbol deterministicially leads to a single matrix.
The hope is that in this encoding, any functional blocks which a fit RNN produces will be encoded entirely in a particular non-terminal symbol. When crossover recombines the rules in two grammars to create a new grammar, such a functional block will be included in it's entirety, or not at all. Thus, there is a better chance for the offspring of two fit RNNs to be at least as fit as its parents.
In Cellular Encoding, a number of transformations are defined on a neuron. These transformations add, remove, and copy connections into and out of the neuron. They may also define new neurons and connections with respect to the old neuron and its connections.
The genome for an RNN under cellular encoding is a parenthetical list of such transformations. The parse tree of this parenthetical list serves to show which transformations to perform on which neurons. Transformations which create a neuron have two children in the tree, and likewise for transformations which create no neurons have only one child. Transformations are applied to neurons by recursive traversal of the tree.
Under cellular encoding, by substituting entire sub-trees of the parse tree associated with the parenthetical list of transformations, it is hoped that functional blocks will be preserved across generations in a similar way to graph grammar encoding. Cellular encoding has proven to be better at this task in most applications than graph grammar encoding.
The goal of the artificial environment is to provide a system of rules which the organisms living in it must adapt to. The simple way used in this project is to provide the organisms with a finite wraparound grid world. The organims have a 360 degree visual system into this world to tell them the location of nearby organisms and nearby food or poison. Each grid location may be occupied by one organism at a time.
Each timestep every organism is given the opportunity to move one square in any direction or do a number of actions defined in the program such as eat or mate with a nearby organism. The inputs to the RNN are a one-off encoding of the closest object (food, or organism) in a particular direction as well as the amount of energy which the organism has. All actions cost energy, except for eat when the re is food in the same grid as the organism. The outputs of the RNN are used as confidence values for the particular actions.
Currently the incomplete version of gridworld is linked on this webpage. The implementation of the grid environment took longer than expected, and only direct encoding of the RNNs is currently supported. During the implementation and preparation of this report a number of concerns about the eventual results of the project came to light and are outlined in the next section
Currently the implementation calls for a single RNN which recieves all visual input and decides on all actions. It has been suggested that it might be better to have a vision/movement RNN, which would get data from the 360 degree visual system and make decisions in only one direction at a time, since this would encapsulate the relative nature of direction in a world of grids. Implementation of this is ongoing
It has also been suggested that Genetic Programming would be a better way to attack this problem than RNNs. Cellular encoding of neural networks has surprising similarities to functional programming, and as it is the best encoding for most instances of evolving RNN structure with a GA. This may be a future direction for this project