A common genetic encoding for both direct and indirect encodings of networks

ABSTRACT

In this paper we present a Common Genetic Encoding (CGE) for networks that can be applied to both direct and indirect encoding methods. As a direct encoding method, CGE allows the implicit evaluation of an encoded phenotype without the need to decode the phenotype from the genotype. On the other hand, one can easily decode the structure of a phenotype network, since its topology is implicitly encoded in the genotype's gene-order. Furthermore, we illustrate how CGE can be used for the indirect encoding of networks. CGE has useful properties that makes it suitable for evolving neural networks. A formal definition of the encoding is given, and some of the important properties of the encoding are proven such as its closure under mutation operators, its completeness in representing any phenotype network, and the existence of an algorithm that can evaluate any given phenotype without running into an infinite loop.

REFERENCES

• 1: P. J. Angeline, G. M. Saunders, and J. B. Pollack. An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 5:54--65, 1994.
• 2: F. Gomez, J. Schmidhuber, and R. Miikkulainen. Efficient non-linear control through neuroevolution. In Proceedings of the European Conference on Machine Learning (ECML 2006), 2006.
• 3: F. Gruau. Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm. PhD thesis, Ecole Normale Superieure de Lyon, Laboratoire de l'Informatique du Parallelisme, France, January 1994.
• 4: Y. Kassahun. Towards a Unified Approach to Learning and Adaptation. PhD thesis, Technical Report 0602, Institute of Computer Science and Applied Mathematics, Christian-Albrechts University, Kiel, Germany, February 2006.
• 5: S. Luke and L. Spector. Evolving graphs and networks with edge encoding: Preliminary report. In Late-breaking papers of Genetic Programming 1996. Stanford, CA, 1996.
• 6: Stefano Nolfi , Dario Floreano, Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines, Bradford Book, 2004
• 7: J. Reisinger, K. O. Stanley, and R. Miikkulainen. Evolving reusable neural modules. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pages 69--81, 2004.
• 8: Kenneth Owen Stanley , Risto P. Miikkulainen, Efficient evolution of neural networks through complexification, The University of Texas at Austin, 2004
• 9: Matthew E. Taylor , Shimon Whiteson , Peter Stone, Comparing evolutionary and temporal difference methods in a reinforcement learning domain, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144202]
• 10: X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Theory

Keywords:
genetic encoding, genotype phenotype mapping