Evolving Turing's Artificial Neural Networks
Degree GrantorUniversity of Canterbury
Degree NameDoctor of Philosophy
Our project uses ideas first presented by Alan Turing. Turing's immense contribution to mathematics and computer science is widely known, but his pioneering work in artificial intelligence is relatively unknown. In the late 1940s Turing introduced discrete Boolean artificial neural networks and, it has been argued that, he suggested that these networks be trained via evolutionary algorithms. Both artificial neural networks and evolutionary algorithms are active fields of research. Turing's networks are very basic yet capable of complex tasks such as processing sequential input; consequently, they are an excellent model for investigating the application of evolutionary algorithms to artificial neural networks. We define an example of these networks using sequential input and output, and we devise evolutionary algorithms that train these networks. Our networks are discrete Boolean networks where every 'neuron' either performs NAND or identity, and they can represent any function that maps one sequence of bit strings to another. Our algorithms use supervised learning to discover networks that represent such functions. That is, when searching for a network that represents a particular function our algorithms use input-output pairs of that function as examples to aid the discovery of solution networks. To test our ideas we encode our networks and implement the algorithms in a computer program. Using this program we investigate the performance of our networks and algorithms on simple problems such as searching for networks that realize the parity function and the multiplexer function. This investigation includes the construction and testing of an intricate crossover operator. Because our networks are composed of simple 'neurons' they are a suitable test-bed for novel training schemes. To improve our evolutionary algorithms for some problems we employ the symmetry of the problem to reduce its search space. We devise and test a means of using subgroups of the group of permutation of inputs of a function to aid evolutionary searches search for networks that represent that function. In particular, we employ the action of the permutation group S₂ to 'cut down' the search space when we search for networks that represent functions such as parity.