For a deterministic problem space, I need to find a neural network with the optimal node and link structure. I want to use a genetic algorithm to simulate many neural networks to find the best network structure for the problem domain.
I've never used genetic algorithms for a task like this before. What are the practical considerations? Specifically, how should I encode the structure of a neural network into a genome?
Section 4.2 of "Essentials of Metaheuristics" has a wealth of information on alternative ways of encoding graph structures via Genetic Algorithms.
With particular regard to evolving ANNs, I would personally not be inclined to implement this sort of thing 'from scratch':
The field of neuroevolution has been around for some time, and the implementation some of the methods, such as Neuroevolution of Augmenting Topologies (NEAT) now incorporate the results of much practical experience.
According to the above link:
We also developed an extension to NEAT called HyperNEAT that can evolve neural networks with millions of connections and exploit geometric regularities in the task domain. The HyperNEAT Page includes links to publications and a general explanation of the approach.
Using evolutionary algorithms to evolve neural networks is called neuroevolution.
Some neuroevolution algorithms optimize only the weights of a neural network with fixed topology. That sounds not like what you want. Other neuroevolution algorithms optimize both the weights and topology of a neural net. These kinds of algorithms seem more appropriate for your aims, and are sometimes called TWEANNs (Topology and Weight Evolving Neural Networks).
One popular algorithm is called NEAT, and is probably a good place to start, if only because there are a multitude of implementations, one of which hopefully is written in your favorite language. That would at least give you a baseline to work with.
NEAT encodes a neural network genome directly as a graph structure. Mutations can operate on the structure of the network by adding new links (by connecting two nodes not previously connected) or new nodes (by splitting an existing connection), or can operate only on changing the weights associated with edges in the graphs (called mutating the weights). To give you an idea of the order of magnitude of the sizes of ANNs this particular algorithm works with, it would likely struggle with more than 100 or 200 nodes.
There are more scalable TWEANNs, but they're more complex and make assumptions about the kinds of structures they generate that may not always be productive in practice. For example, another way to encode the structure of a neural network, is as the product of a seed pattern that is repeatedly expanded by a grammar (e.g. an L-system). You can much more easily explore larger structures, but because they're generated by a grammar they'll have a characteristic self-repeating sort of feel. HyperNEAT is a popular extension of NEAT that makes a different sort of assumption (that patterns of weights can be easily expressed as a function of geometry), and can scale to ANNs with millions of connections when that assumption well-fits a particular domain.
There are a few survey papers linked in the top link if you want to observe a greater variety of techniques.
